Potenciální metoda

Potenciální metoda je modifikací simplexové metody pro řešení úlohy lineárního programování ve vztahu k dopravnímu problému . Umožňuje, počínaje nějakým proveditelným řešením, získat optimální řešení v konečném počtu iterací.

Formulace dopravního problému

Existují dva typy stagingu – maticové a síťové. V matricové formulaci je přeprava povolena pouze od výrobce ke spotřebiteli. V nastavení sítě lze přepravu provádět v libovolném směru (body mohou být tranzitní). Nechť jsou  body výroby/spotřeby,  jsou dopravní oblouky , jsou ceny dopravy  podél oblouků a  jsou množinou základních sloupců.

Úkol je formulován jako [1]

nalézt

za podmínek

kde  - náklady na obloukovou dopravu,  - výroba (+) / spotřeba (-)

 - řešení

Matici omezení transportního problému tvoří sloupce obsahující pouze dva nenulové prvky - +1 pro výrobce a -1 pro spotřebitele [2] .

Poznámka: Obecně řečeno, jakákoli čtvercová podmatice (tj . ) matice je zdegenerovaná, takže aby simplexová metoda fungovala, je nutné zavést umělé proměnné nebo vyloučit jeden řádek z úvahy. Při použití výpisu (viz níže) je to jemu odpovídající řádek, který je vyloučen z úvahy.

Algoritmus

Potenciální metoda je modifikací simplexové metody, ve které je základní matice reprezentována jako strom [3] .

Duální proměnné simplexové metody pro problém dopravy se nazývají potenciály .

Potenciály se počítají podle vzorce , který je ekvivalentní

Pro oblouk jsou potenciály oblouků ve vztahu podle vzorce .

Potenciál spotřebitele se tedy rovná potenciálu výrobce + náklady na dopravu. Z ekonomického hlediska to lze interpretovat jako náklady na produkt v místě spotřeby.

Kontrola optimálnosti plánu je z ekonomického hlediska snadno interpretovatelná - pokud jsou náklady na výrobek v místě spotřeby větší než náklady na místo výroby + cena dopravy, měl by být tento oblouk přepraven. Veličina se nazývá zbytkový oblouk .

Přidáním oblouku vznikne ve stromu cyklus. Zvětšení vozíku po zavedeném oblouku vede k přepočtu průtoků v cyklu, vozík po jednom z oblouků se pak sníží na nulu. Oblouk s nulovým průtokem je odstraněn ze základny, zatímco základový graf zůstává stromem (cyklus se přeruší).

Zbývá pouze přepočítat potenciály - přidat (nebo odečíst - záleží na směru oblouku) ke všem vrcholům "houpající se větve" o zbytkovou hodnotu

Proces končí, když je splněna podmínka optimality pro všechny oblouky.

Otevřené problémy

Problém je uzavřen, pokud se součet produkce rovná součtu spotřeby.

Obvykle v nastavení je množství produkce větší než množství spotřeby. Pro řešení neuzavřených problémů a také pro snadné získání výchozího základního plánu se používá metoda umělé báze [4] . K tomu se původní graf rozšíří, zavede se „skládka“ – dodatečný bod, do kterého je přivedena veškerá nadprodukce za nulovou cenu.

Pokud zavedeme oblouky ze skládky na odběrná místa s velmi vysokou cenou, je výchozí řešení postaveno triviálně - veškerou produkci vozíme na skládku, veškerou spotřebu ze skládky.

Oblouky ke skládce z výrobních míst odpovídají dalším proměnným v simplexové metodě a oblouky ze skládky k místům spotřeby odpovídají umělým proměnným .

Metoda severozápadního rohu

Pro problém maticového transportu je možný jiný algoritmus pro konstrukci počátečního plánu.

1. Vyberte nějaký vrchol i.

2. Vyberte incident oblouku do i. Nastavme průtok podél oblouku rovný minimu objemů výroby a spotřeby na koncích oblouku. Snižme tyto objemy o množství proudění podél oblouku. Vrchol s nulovým objemem vyřadíme z uvažování spolu s oblouky, které k němu dopadají. Pojďme k bodu 2.

Pokud se přečíslují vrcholy výroby a spotřeby a pokaždé se vybere oblouk s nejmenším číslem, nazývá se metoda metoda severozápadního rohu [5] .

Několik poznámek o účinnosti algoritmu

Definice výstupního oblouku a přepočet potenciálů jsou poměrně efektivně implementovány. Hlavním „spotřebitelem“ času je kontrola optimálnosti [6] .

Ke zkrácení doby kontroly optimálnosti se používá několik metod.

1. Použití bariéry - jakmile je hodnota nesouladu větší než určitá hodnota, zavedeme oblouk do základny, aniž bychom procházeli zbytkem oblouků. Pokud se oblouk nenajde, snížíme bariéru na maximální zjištěný nesoulad a zavedeme odpovídající oblouk do základny.

2. Cyklické zobrazení - hledání začíná od místa, kde se zastavilo v předchozím zobrazení.

3. Výběr "uchazečů" - při prohlížení není vybrán jeden oblouk, ale několik. V dalším kroku se kontrolují pouze vybrané oblouky.

Determinant základní matice je vždy 1, takže daný celočíselný údaj dává problém celočíselná řešení.

Limity šířky pásma

Pro některé oblouky lze nastavit limity šířky pásma . Mírná komplikace algoritmu může vyřešit problém s omezenou šířkou pásma [7] .

nalézt

za podmínek

Zde  — další proměnné (zavedené za účelem transformace nerovnosti na rovnost).

Základ se bude skládat ze tří sad - , a .

kde  jsou oblouky odpovídající obvyklým omezením ( )

 — oblouky, které dosáhly limitu šířky pásma (nasycené oblouky) ( )

 — oblouky, které nedosáhly limitu šířky pásma (odpovídají dalším proměnným)( )

Základní matice má tvar

Inverzní k základně se pak rovná

Duální proměnné se počítají podle vzorce

Tady

 — potenciály (jako u standardní metody potenciálů).

 — příplatek za dopravu po nasyceném oblouku.

Mírnou úpravou grafu lze přidat také omezení šířky pásma oblouku [8] .

K oblouku A->B s náklady c a maximální propustností p jsou přidány dva vrcholy: C se spotřebou -p a D s výrobou p. Vrcholy jsou spojeny podle schématu A->C<-D->B místo A->B. Oblouk A->C má cenu c, oblouky C<-D a D->B mají nulové náklady. Takové schéma nedovolí, aby mezi body A->B procházel tok větší než p.

Algoritmus

Algoritmus je velmi podobný standardní potenciální metodě. Nasycený oblouk by neměl vyhovovat kritériu optimality, jinak by se měl proud podél něj snížit. Zbývající oblouky jsou kontrolovány pro kritérium stejným způsobem jako ve standardní verzi. Stejně jako ve standardním algoritmu se v obou případech objeví obrys, ve kterém by se měl změnit průtok (snížení pro vybraný oblouk v případě odstranění oblouku od nasycených a zvýšení v případě normálního oblouku). Když se toky změní, jeden z oblouků může jít na 0 (jako ve standardním algoritmu) nebo na horní hranici šířky pásma - převedeme to na nasycené.

Podobně jako u standardního algoritmu se přepočítávají i potenciály.

Poznámky

  1. ↑ Romanovský, 1977 , s. 109-110.
  2. ↑ Romanovský, 1977 , s. 111.
  3. ↑ Romanovský, 1977 , s. 115.
  4. ↑ Romanovský, 1977 , s. 122.
  5. ↑ Romanovský, 1977 , s. 124.
  6. ↑ Ve skutečnosti se jedná o stejné přístupy jako v simplexové metodě s mírně pozměněnou terminologií. Viz část Efficiency Techniques v článku o simplexní metodě.
  7. ↑ Romanovský, 1977 , s. 137.
  8. ↑ Romanovský, 1977 , s. 139.

Odkazy