Dopravní problém
Z Wikipedie, otevřené encyklopedie
Dopravní problém je optimalizační úloha, jejíž cílem je minimalizovat cenu přepravovaného zboží. Poprvé formulována F. L. Hitchcockem v roce 1941.
[editovat] Úloha
Máme dáno:
- m zdrojů s kapacitami ai (i = 1, …,m)
- n spotřebitelů s kapacitami bj (j = 1, …,n)
- ci j cena přepravované jednotky zboží od i. zdroje k j. spotřebiteli
Proměnné značíme xi j , udávají množství přepravovaného zboží od i. zdroje k j. spotřebiteli.
Úloha dopravního problému:

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

[editovat] 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 svůj 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.
[editovat] Reference
- 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. vyádní.

