Síťový simplexní algoritmus - Network simplex algorithm

V matematické optimalizace je síť simplex algoritmus je graf teoretické specializace simplex algoritmu . Algoritmus je obvykle formulován z hlediska problému toku minimálních nákladů . Síťová simplexní metoda funguje v praxi velmi dobře, obvykle 200 až 300krát rychleji než simplexová metoda aplikovaná na obecný lineární program stejných rozměrů.

Dějiny

Po dlouhou dobu byla existence prokazatelně efektivního síťového simplexního algoritmu jedním z hlavních otevřených problémů v teorii složitosti, přestože byly k dispozici efektivní verze v praxi. V roce 1995 Orlin poskytl první polynomiální algoritmus s dobou běhu, kde je maximální cena jakýchkoli hran. Později to Tarjan vylepšil pomocí dynamických stromů v roce 1997. Silně polynomiální duální síťové simplexní algoritmy pro stejný problém, ale s vyšší závislostí na počtu hran a vrcholů v grafu, jsou známy již déle.

Přehled

Síťová simplexní metoda je adaptací algoritmu ohraničené proměnné primal simplex. Základ je reprezentován jako kořenový spanningový strom podkladové sítě, ve kterém jsou proměnné reprezentovány oblouky a simplexní multiplikátory podle potenciálů uzlů. Při každé iteraci je určitá cenová strategie vybírána proměnná zadaná na základě duálních multiplikátorů (potenciály uzlů) a tvoří cyklus s oblouky stromu. Odcházející proměnná je oblouk cyklu s nejméně zesilujícím tokem. Substituce vstupu za opuštění oblouku a rekonstrukce stromu se nazývá pivot. Když žádný nezákladní oblouk nezůstane způsobilý pro vstup, bylo dosaženo optimálního řešení.

Aplikace

Síťový simplexní algoritmus lze použít k řešení mnoha praktických problémů, včetně

Reference

externí odkazy