dopravní problém

Druh distribučního modelu při řešení úloh lineárního programování. Dopravní problém lze formulovat takto: je dáno m kapacit k₁, k₂, ... , k_m o objemu a₁, a₂, ... , a_m a n spotřebitelů S₁, S₂, ... , S_m s požadavky o objemu b₁, b₂, ... , b_m. Kapacity mohou uspokojit požadavky spotřebitelů S. Uspokojení potřeb j-tého spotřebitele i-tou kapacitou je však spojeno s určitými náklady c_ij Úkolem je sestavit takový program zabezpečení spotřebitelů, aby celkové náklady byly minimální. Při řešení se používá speciální algoritmus, který vychází ze simplexového algoritmu, ale přihlíží ke zvláštnostem dopravního problému. Postup se nazývá distribuční metodou, která předpokládá, že je dáno výchozí základní řešení dopravního problému, obsahující nejvýše m + n – 1 nenulových proměnných; toto řešení se získává tzv. metodou severozápadního rohu, Vogelovou apromixační metodou, indexní metodou ap. Například dopravní problém je úloha, v níž se má navrhnout nejúspornější rozvoz nějaké suroviny (například uhlí), známe-li, kolik se jí vytěží v dolech, kolik každá továrna z těžby požaduje a víme, kolik stojí doprava při jedjednotkové vzdálenosti a jednotkové hmotnosti.

Datum vytvoření: 14. 3. 2000
Datum aktualizace: 25. 7. 2000
Autor: -red-

Reklama: