Dopravní problém

Dopravní problém je optimalizační úloha, jejímž cílem je minimalizovat cenu přepravy zboží. Poprvé formulována F. L. Hitchcockem v roce 1941.

Úloha

V dopravním problému se jedná o optimalizaci rozvozu nějaké homogenní látky (např. zboží, osob či materiálu) ze zdrojů (od dodavatelů) do cílových míst (k odběratelům). Ve většině případů je cílem minimalizace celkových nákladů spojených s rozvozem, popřípadě minimalizace celkové vzdálenosti, přičemž by měly být uspokojeny požadavky odběratelů.

Úkolem je tedy za takovýchto podmínek stanovit, kolik měrných jednotek určité homogenní látky dodá každý dodavatel každému odběrateli.

Máme dáno:

m zdrojů s kapacitami a_i (i = 1, …,m)
n spotřebitelů s kapacitami b_j (j = 1, …,n)
c_{i j} cena přepravované jednotky zboží od i. zdroje k j. spotřebiteli

Proměnné značíme x_{i j}, udávají množství přepravovaného zboží od i. zdroje k j. spotřebiteli.

Úloha dopravního problému:

\min _{x\in M}\sum _{i=1}^{m}\sum _{j=1}^{n}c_{ij}x_{ij},

přičemž množina M je popsána omezeními

\sum _{i=1}^{m}x_{ij}=b_{j},\ \sum _{j=1}^{n}x_{ij}=a_{i},\ \sum _{i=1}^{m}a_{i}=\sum _{j=1}^{n}b_{j},\ x_{ij}\geq \ 0.

Metody řešení

Jedná se o úlohu lineárního programování, je tedy možné ji řešit metodami lineárního programování. Pro její specifický tvar byly ale odvozeny algoritmy šité na míru dopravnímu problému: Dantzigův a modifikovaný Dantzigův algoritmus (anglicky „stepping stone algorithm“), Arsham-Kahnův algoritmus, aj.

Vlastnosti dopravního problému

Přípustné řešení

Přípustným řešením dopravního problému je vektor x = (x_{1 1},x_{1 2},...,x_{m n})T, jehož složky splňují výše zmíněné podmínky.

Věta 1: Dopravní problém má přípustné řešení.

U vyrovnaného dopravního problému, kde je součet kapacit roven součtu požadavků, existuje vždy způsob, jak tyto kapacity rozdělit mezi požadavky odběratelů. Při teoretickém důkazu dosadím výraz x_{i j}=(a_i b_j)/K, kde

K=\sum _{i=1}^{m}a_{i}=\sum _{j=1}^{n}b_{j}

, i=1,2,…,m,j=1,2,…,n.

do vlastních omezení modelu:

\sum _{j=1}^{n}x_{ij}=\sum _{j=1}^{n}{\frac {a_{i}b_{j}}{K}}={\frac {a_{i}}{K}}\sum _{j=1}^{n}b_{j}=a_{i},

\sum _{i=1}^{m}x_{ij}=\sum _{i=1}^{m}{\frac {a_{i}b_{j}}{K}}={\frac {b_{j}}{K}}\sum _{i=1}^{m}a_{i}=b_{j},

takže jsou splněna řádková i sloupcová omezení modelu a vzhledem k tomu, že kapacity i požadavky jsou vyjádřeny jako nezáporná čísla, je splněna i podmínka nezápornosti. Základní přípustné řešení

Základním přípustným řešením dopravního problému je takové přípustné řešení, které obsahuje nejvýše (m+n-1) kladných složek, u kterých tvoří vektory strukturních koeficientů lineárně nezávislou soustavu.

Věta 2: Dopravní problém má základní přípustné řešení.

Pokud za libovolnou proměnnou x_{r s} dosadím min(a_r,b_s) vynuluje se buď příslušná kapacita r-tého dodavatele, nebo požadavek s-tého odběratele. V modelu ubude jedno vlastní omezení. Stejným způsobem budu pokračovat do té doby, než v modelu zůstanou dvě omezení taková, že zůstatková kapacita bude rovna zůstatkovému požadavku. Tudíž bude možné splnit obě omezení najednou. Počet omezení v modelu je (m+n), ale kladných proměnných bude (m+n-1), tedy o jednu méně.

Optimální řešení

Optimálním řešením dopravního problému je takové přípustné řešení, které hodnotu účelové funkce minimalizuje.

Věta 3: Dopravní problém má optimální řešení.

Při důkazu tohoto tvrzení vyjdeme z grafického znázornění řešení dopravního problému, kde je množina přípustných řešení konvexní polyedr omezený podmínkami nezápornosti, kapacitami a požadavky. Z toho důvodu množina přípustných řešení nebude nikdy neomezená. Pokud se účelová funkce dotkne konvexního polyedru v jednom bodě, nabývá svého maxima, či minima, dotkne-li se ho ve více bodech, mé úloha nekonečně mnoho optimálních řešení.

Základní věta dopravního problému

Věta 4: Dopravní problém má všechny báze trojúhelníkové.

Báze B dopravního problému má rozměry [(m + n) x (m + n - 1)]. Řádky této matice tvoří omezení, z nichž je vždy jedno lineární kombinací ostatních, proto je možné vynechat jeden řádek. Takto vznikne redukovaná matice báze B₀, která je čtvercové a je tedy možné ji invertovat. Vhodnými úpravami převedeme matici B₀ na trojúhelníkovou, takže je v soustavě B₀ b=x_B, kde $b=(a_{1},...,a_{m},b_{1},...,b_{n})^{T}$ je vektor pravých stran omezení a x_B je vektor základních proměnných, alespoň jedna základní proměnná určená jednoznačně.

Duální problém k dopravnímu problému

Duální úloha k dopravnímu problému se konstruuje na základě stejných principů, jako duální úloha ke standardní úloze lineárního programování. V problematice dopravního problému je duální úloha jednou z nejdůležitějších částí, jelikož se duální úlohy využívá při řešení dopravního problému.

Vlastní omezení matematického modelu dopravního problému jsou rovnice, proto bude duální problém nesymetrický.

Počet duálních proměnných je určen počtem vlastních omezení v primárním problému a bude jich tedy (m+n). Označíme m duálních proměnných, které budou přiřazeny řádkovým omezením, jako u_i a n duálních proměnných, které budou naopak přiřazeny sloupcovým omezením, jako v_j. Vzhledem k tomu, že duální problém je nesymetrický, nebudou mít duální proměnné podmínky nezápornosti.

Duální problém bude mít (m.n) omezení, kde každé z nich odpovídá jedné proměnné v primárním problému.

Jestliže účelovou funkci v primárním problému minimalizujeme, což je splněno vždy, pokud ji z nějakého formálního důvodu nepotřebujeme maximalizovat, pak budeme účelovou funkci duálního problému maximalizovat.

Matematický model duálního problému pak vypadá následovně:

maximalizovat

f=\sum _{i=1}^{m}a_{i}u_{i}+\sum _{j=1}^{n}b_{j}v_{j}

za podmínek

u_{i}+v_{j}\leq c_{ij},

i=1,2,…,m, j=1,2,…,n.

Literatura

Ján Plesník, Jitka Dupačová, Milan Vlach: Lineárne programovanie, ALFA, Bratislava 1990, 1. vydání.
Libuše Grygarová: Úvod do lineárního programování, skripta, Státní pedagogické nakladatelství, Praha 1975, 1. vydání.
Milada Lagová, Josef Jablonský: Lineární modely, VŠE, Praha 1999, 1. vydání.

Externí odkazy

Obrázky, zvuky či videa k tématu dopravní problém na Wikimedia Commons