Přepravní úkol

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 3. června 2021; ověření vyžaduje 1 úpravu .

Dopravní problém ( Monge-Kantorovich problém ) je matematický problém lineárního programování speciálního druhu. [1] [2] Lze na ni nahlížet jako na problém optimálního plánu přepravy zboží z místa odeslání do místa spotřeby s minimálními náklady na přepravu.

Podle teorie výpočetní složitosti je problém transportu zařazen do třídy složitosti P . Pokud se celkový objem nabídek (zboží dostupné na výchozích místech) nerovná celkovému objemu poptávky po zboží (zboží) požadovaných odběrnými místy, dopravní problém se nazývá nevyrovnaný ( otevřený ).

Prohlášení o problému

Dopravní problém (klasický) je problém optimálního plánu přepravy homogenního produktu z homogenních míst dostupnosti do homogenních míst spotřeby na homogenních vozidlech (předem stanovené množství) se statickými daty a lineárním přístupem (to jsou hlavní podmínky problém).

U klasické přepravní úlohy se rozlišují dva typy úloh: nákladové kritérium (dosažení minima přepravních nákladů) nebo vzdálenosti a časové kritérium (minimální čas strávený přepravou). Pod názvem transportní úloha je definována široká škála úloh s jediným matematickým modelem, tyto úlohy souvisejí s úlohami lineárního programování a lze je řešit optimální metodou. Speciální metoda pro řešení dopravního problému však může jeho řešení výrazně zjednodušit, protože dopravní problém byl vyvinut za účelem minimalizace nákladů na přepravu.

Matematická formulace problému

Homogenní náklad je koncentrován u dodavatelů v objemech . Tento náklad musí být spotřebitelům dodán v objemech . - náklady na dopravu zboží od dodavatele ke spotřebiteli . Je nutné vypracovat plán přepravy, který vám umožní kompletně exportovat produkty všech výrobců, plně uspokojí potřeby všech spotřebitelů a poskytne minimální celkové náklady na dopravu. Označte jako objem přepravy od dodavatele ke spotřebiteli . [3] $m$ ${\displaystyle a_{1},a_{2},....a_{m))$ $n$ ${\displaystyle b_{1},b_{2},....b_{n))$ $c_{ij}$ $i$ $j$ $x_{ij}$ $i$ $j$

\sum _{j=1}^{n}x_{ij}=a_{i}

i=1,2,...,m

\sum _{i=1}^{m}x_{ij}=b_{j}

j=1,2,...,n

\sum _{i=1}^{m}\sum _{j=1}^{n}c_{ij}x_{ij}\rightarrow \min

Historie hledání metod řešení

Problém poprvé formalizoval francouzský matematik Gaspard Monge v roce 1781 [4] . Pokroku v řešení problému dosáhl během Velké vlastenecké války sovětský matematik a ekonom Leonid Kantorovich [5] . Proto se tento problém někdy nazývá dopravní problém Monge-Kantorovich .

Metody řešení

Klasický transportní problém lze řešit simplexní metodou , ale vzhledem k řadě vlastností jej lze řešit jednodušeji (pro úlohy malých rozměrů).

Podmínky problému jsou umístěny v tabulce, do buněk se zadává množství nákladu přepravovaného z do nákladu a v malých buňkách odpovídající tarify . $A_{i}$ $B_j$ $X_{ij}\geqslant 0$ ${\displaystyle C_{ij))$

Iterativní vylepšení plánu dopravy

Nalezení základní linie

Je třeba stanovit základní plán a pomocí postupných operací najít optimální řešení. Referenční plán lze nalézt následujícími metodami: "severozápadní roh" , "nejmenší prvek" , dvojitá preference a Vogelova aproximace .

Metoda severozápadního rohu (diagonální nebo vylepšená)

V každé fázi je levá horní buňka zbytku tabulky vyplněna maximálním možným počtem. Plnění takovým způsobem, aby byl náklad zcela odstraněn nebo aby byla zcela uspokojena potřeba . $A_{i}$ $B_j$

Metoda nejmenších prvků

Jedním ze způsobů, jak problém vyřešit, je metoda minimálního (nejmenšího) prvku . Jeho podstata spočívá v minimalizaci bočního přerozdělování zboží mezi spotřebitele.

Algoritmus:

Z tabulky hodnot se vybere nejnižší cena a větší z čísel se zapíše do buňky, která mu odpovídá.
Řádky dodavatelů jsou kontrolovány na řádek s použitými zásobami a sloupce zákazníků na sloupec, jehož požadavky jsou plně splněny. Takové sloupce a řádky nejsou dále brány v úvahu.
Pokud nejsou všichni spotřebitelé spokojeni a ne všichni dodavatelé zboží spotřebovali, vraťte se ke kroku 1, jinak je problém vyřešen.

Iterace

Po nalezení základního plánu dopravy je třeba použít jeden z algoritmů pro jeho vylepšení, přibližující se optimálnímu.

Metoda padajícího kamene
Metoda potenciálů .

Řešení teorie grafů

Uvažujeme bipartitní graf , ve kterém jsou výrobní místa v horní části a místa spotřeby v dolní části. Místa výroby a spotřeby jsou ve dvojicích propojena hranami nekonečného výkonu a ceny za jednotku toku . ${\displaystyle C_{ij))$

Zdroj je uměle připojen k hornímu laloku . Kapacita hran od zdroje ke každému bodu výroby se rovná zásobě produktu v tomto bodě. Cena za jednotku toku těchto hran je 0.

Podobně se k dolnímu laloku připojuje drenáž . Propustnost žeber z každého místa spotřeby do dřezu se rovná poptávce po produktu v tomto bodě. Cena za jednotku toku pro tyto hrany je také 0.

Dále je vyřešen problém nalezení maximálního toku minimálních nákladů ( mincost maxflow ). Jeho řešení je podobné hledání maximálního průtoku ve Ford-Fulkersonově algoritmu . Pouze místo nejkratšího doplňkového toku se hledá ten nejlevnější. V souladu s tím tato dílčí úloha nepoužívá prohledávání do šířky , ale Bellman-Fordův algoritmus . Když je stream vrácen, náklady jsou považovány za záporné.

Algoritmus "mincost maxflow" lze spustit okamžitě - bez nalezení základní linie. Ale v tomto případě bude proces rozhodování poněkud delší. Provádění algoritmu „mincost maxflow“ neprobíhá více než operacemi. ( je počet hran, je počet vrcholů.) U náhodně vybraných dat je obvykle potřeba mnohem méně – pořadí operací. $O(v^{2}e^{2})$ $E$ $proti$ $O(ve)$

Při řešení nevyváženého dopravního problému se používá technika k jeho vyvážení. Chcete-li to provést, zadejte fiktivní destinace nebo odlety. Implementace bilance transportního problému je nezbytná k tomu, aby bylo možné aplikovat algoritmus řešení založený na použití transportních tabulek.

Zobecnění

Problém přenosu v nastavení sítě

V této variantě se body nedělí na výchozí a odběrná, všechny body jsou si rovny, ale výroba je dána kladným číslem a spotřeba záporným. Přeprava se provádí na dané síti, ve které mohou oblouky spojovat libovolné body, včetně výrobce-výrobce, spotřebitel-spotřebitel.

Problém je řešen mírně upravenou metodou potenciálů , prakticky stejnou jako klasické nastavení.

Dopravní problém s omezením šířky pásma

Varianta transportního problému v síťovém nastavení, ve kterém je specifikována maximální propustnost některých oblouků.

Problém je řešen mírně komplikovanou metodou potenciálů .

Problém přepravy více produktů

Varianta přepravního úkolu, ve kterém je několik produktů (body mohou vyrobit/spotřebovat několik produktů). Pro některé oblouky je nastaven limit propustnosti (bez tohoto limitu se úloha rozdělí na samostatné úlohy podle produktu).

Problém je řešen simplexovou metodou (používá se Danzig -Wulfova expanze, jako dílčí úkoly jsou použity transportní úlohy jednoho produktu).

Poznámky

↑ A. V. Kuzněcov, N. I. Kholod, L. S. Kostevich. Průvodce řešením problémů v matematickém programování . - Minsk: Higher School , 1978. - S. 110.
↑ Slovník kybernetiky / Edited by akademik V. S. Mikhalevich . - 2. - Kyjev: Hlavní vydání Ukrajinské sovětské encyklopedie pojmenované po M. P. Bazhanovi, 1989. - 751 s. - (C48). — 50 000 výtisků. - ISBN 5-88500-008-5 .
↑ Korbut, 1969 , s. 28.
↑ Monge G. Mémoire sur la théorie des deblais et de remblais. Histoire de l'Académie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année, strany 666-704, 1781.
↑ Kantorovich L. O translokaci hmot // ČR (Doklady) Akad. sci. URSS (NS), 37:199-201,1942.

Odkazy

Přepravní úkol
Algoritmy pro nalezení maximálního průtoku
http://kb.mista.ru/article.php?id=859 Řešení problému dopravy v 1C:Enterprise 8.2

Literatura

Korbut A.A. , Finkelstein Yu.Yu. Diskrétní programování. - M. : Nauka, 1969. - 368 s.