Verkon yksinkertaistettu algoritmi - Network simplex algorithm

In matemaattisen optimoinnin , verkko simplex-algoritmi on kaavio teoreettinen erikoistumista simplex-algoritmi . Algoritmi muotoillaan yleensä vähimmäiskustannusvirtaongelman muodossa . Verkko-simplex-menetelmä toimii käytännössä erittäin hyvin, tyypillisesti 200-300 kertaa nopeammin kuin yleinen lineaarinen, saman mitoisen ohjelma.

Historia

Todistettavasti tehokkaan yksinkertaisen verkko-algoritmin olemassaolo oli pitkään yksi suurimmista avoimista ongelmista monimutkaisuusteoriassa, vaikka käytännössä tehokkaita versioita oli saatavilla. Vuonna 1995 Orlin toimitti ensimmäisen polynomialgoritmin, jonka ajonaika oli missä tahansa reunojen maksimikustannukset. Myöhemmin Tarjan parantaa tätä käyttäen dynaamista puita vuonna 1997. voimakkaasti polynomi kahden verkon simplex algoritmeja sama ongelma, mutta jolla on korkeampi riippuvuutta numerot reunojen ja graafin, on tunnettu jo pidempään.

Yleiskatsaus

Verkko-yksinkertaisuusmenetelmä on rajoitetun muuttujan primaalisen yksinkertaisuuden algoritmin mukauttaminen. Perusta esitetään taustalla olevan verkon juurtuneena ulottuvana puuna, jossa muuttujia edustavat kaaret ja yksinkertaisia ​​kertojia solmupotentiaalit. Jokaisella iteraatiolla jokin hinnoittelustrategia valitsee syöttävän muuttujan kaksoiskertojien (solmupotentiaalien) perusteella ja muodostaa jakson puun kaarien kanssa. Lähtevä muuttuja on syklin kaari, jolla on vähiten kasvava virtaus. Sisäänmenon korvaamista kaaren poistumiselle ja puun jälleenrakentamista kutsutaan kääntökohdaksi. Kun mikään ei-peruskaari ei ole enää kelvollinen pääsemään, on saavutettu optimaalinen ratkaisu.

Sovellukset

Verkon simplex-algoritmia voidaan käyttää ratkaisemaan monia käytännön ongelmia, kuten

Viitteet

Ulkoiset linkit