Dopravní problém a spol.

Dopravní problém – úloha, ve které se jedná o minimalizaci nákladů při distribuci zboží ze zdrojů (od dodavatelů) do cílových míst (k odběratelům).

• vyrovnaný DP– součet kapacit dodavatelů se rovná součtu požadavků odběratelů
• nevyrovnaný DP– součet kapacit dodavatelů se nerovná součtu požadavků odběratelů

Matematický model – min z = c11x11 + c12x12 +…c1_nx1_n +…+c_m1x_m1 + c_m2x_m2

+…c_mnx_mn za podmínek že x_ij >0, i=1,2..m j=1,2,..n

Typy řešení dopravního problému:

• Základní řešení vyrovnaného DP – má m+n-1 základních proměnných (max. m+n-1 nenulovych promennych)
• Degenerované zákl. řešení – je-li počet kladných základních proměnných nižší než m+n-1 (m=dodavatelé, n=odběratelé), neboli je-li počet obsazených polí nižší než m+n-1

Modifikovana distribuci metoda:

• Vypocet výchozího zakladniho reseni
• Test optimality

- Při vypoctu výchozího základního reseni vyrovnaného dopravniho problemu vybirame (m+n-1) základních proměnných a doplnime do jednotlivých bunektabulky (m+n-1) numerických hodnot tak, aby radkove a sloupcove soucty souhlasili s kapacitami a požadavky.

- Nekterou z metod zvolime zakladni promennou a přiradíme ji maximalni moznou numerickou hodnotu, která neprekroci radkovy nebo sloupcovy soucet v tabulce.

Metody řešení dopr. problému:

• Metoda severozápadního rohu –metoda pro výpočet výchozího základního řešení dopr. problému, která obsazuje pole bez ohledu na výhodnost či nevýhodnost přepravy (vybere vždy pole v tabulce vlevo nahoře).
• Indexní metoda –metoda pro výpočet výchozího základního řešení dopravního problému, která prioritně obsazuje pole s minimálním ohodnocením přepravy.
• Voglova aproximační metoda (VAM)– metoda pro výpočet výchozího základního řešení dopravního problému, kombinace indexní metody s diferencemi

Mezi další problémy patří:

Kontejnerový dopravní problém– úloha, ve které se distribuce zboží mezi dodavateli a odběrateli provádí pomocí kontejnerů dané kapacity; cílem je minimalizace celkových přepravních nákladů (náklady jsou stejné jak pro plný, tak prázdný kontejner).

Okružní dopravní problém (= úloha dopravního cestujícího) – cílem je vyjít z nějakého stanoviště a navštívit určená místa postupně a právě jednou a vrátit se zpět do výchozího místa tak, abych ušel co nejmíň neboli najít nejkratší okruh.

Obecný distribuční problém– distribuční úloha, ve které nejsou uvedeny požadavky odběratelů a kapacity dodavatelů ve stejných jednotkách.

Přiřazovací problém– úloha o určení vzájemně jednoznačného přiřazení dvojice jednotek ze dvou skupin tak, aby efekt z tohoto přiřazení byl co nejvyšší (například přiřazení úkolů pracovním týmům).

Úloha o pokrytí – úloha o volbě obvodů pro zřízení obslužných center ze zadané množiny obvodů a rozdělení sfér jejich působnosti.

Date: 2016-01-03; view: 720