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:

\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.

[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

  1. Ján Plesník, Jitka Dupačová, Milan Vlach: Lineárne programovanie, ALFA, Bratislava 1990, 1. vydání.
  2. Libuše Grygarová: Úvod do lineárního programování, skripta, Státní pedagogické nakladatelství, Praha 1975, 1. vyádní.
V jiných jazycích