Hálózati szimplex algoritmus - Network simplex algorithm

A matematikai optimalizáló , a hálózati szimplex algoritmus egy gráfelméleti specializáció a szimplex algoritmus . Az algoritmust általában egy minimális költség-áramlási probléma alapján fogalmazzák meg . A hálózati szimplex módszer a gyakorlatban nagyon jól működik, jellemzően 200-300-szor gyorsabb, mint az azonos dimenziójú általános lineáris programra alkalmazott szimplex módszer.

Történelem

Hosszú ideig a bizonyíthatóan hatékony hálózati szimplex algoritmus megléte volt az egyik legnagyobb nyitott probléma a komplexitáselméletben, annak ellenére, hogy a gyakorlatban hatékony verziók is rendelkezésre álltak. 1995-ben Orlin megadta az első polinom algoritmust futási idővel, ahol az élek maximális költsége felmerül. Később Tarján javult ez a dinamikus fák 1997 határozottan polinom kettős hálózati szimplex algoritmus ugyanaz a probléma, de nagyobb függés a számok az élek és csúcsok a grafikonon, már ismert, hosszabb ideig. ${\ displaystyle O (V ^ {2} E \ log (VC))}$${\ displaystyle C}$${\ displaystyle O (VE \ log V \ log (VC))}$

Áttekintés

A hálózati szimplex módszer a korlátozott változó primal simplex algoritmus adaptációja. Az alapot az alapul szolgáló hálózat gyökeresen átívelő fája képviseli, amelyben a változókat ívek, a szimplex szorzókat pedig csomópontpotenciálok képviselik. Minden iterációnál valamilyen árstratégia kiválaszt egy belépő változót, a kettős szorzók (csomópontpotenciálok) alapján, és ciklust alkot a fa íveivel. A kilépő változó a legkevésbé növekvő áramlással rendelkező ciklus íve. A belépés helyettesítése az elhagyó ívnek és a fa rekonstrukcióját forgónak nevezzük. Ha egyetlen nem alapív sem marad belépésre alkalmas, akkor elérte az optimális megoldást.

Alkalmazások

A hálózati szimplex algoritmus számos gyakorlati probléma megoldására használható, ideértve:

• Átrakási probléma
• Hitchcock szállítási probléma
• Hozzárendelési probléma
• Láncok és antichainek részben rendezett halmazokban
• Különálló képviselők rendszere
• Borítók és egyezés kétoldalas grafikonokban
• Vendéglátó probléma

Hivatkozások

Külső linkek

• Hálózati problémák megoldása A B-113. Szakasz, 14. szakasz végrehajtási példát mutat be