Nätverks simplex-algoritm
Inom matematisk optimering är simplexalgoritmen för nätverk en grafteoretisk specialisering av simplexalgoritmen . Algoritmen är vanligtvis formulerad i termer av ett minimikostnadsflödesproblem . Nätverkssimplexmetoden fungerar mycket bra i praktiken, vanligtvis 200 till 300 gånger snabbare än simplexmetoden som tillämpas på allmänna linjära program med samma dimensioner. [ citat behövs ]
Historia
Länge var förekomsten av en bevisligen effektiv nätverkssimplexalgoritm ett av de stora öppna problemen inom komplexitetsteorin, även om effektiva-i-praktiska versioner fanns tillgängliga. 1995 Orlin den första polynomalgoritmen med körtid för där är maximum kostnad för eventuella kanter. Senare Tarjan detta till med hjälp av dynamiska träd 1997. Starkt polynomiska dubbelnätverk simplexalgoritmer för samma problem, men med ett högre beroende av antalet kanter och hörn i grafen, har varit kända längre.
Översikt
Nätverkssimplexmetoden är en anpassning av den begränsade variabeln primal simplexalgoritmen. Basen representeras som ett rotat spännträd i det underliggande nätverket, i vilket variabler representeras av bågar och simplexmultiplikatorerna av nodpotentialer. Vid varje iteration väljs en ingående variabel av någon prissättningsstrategi, baserad på de dubbla multiplikatorerna (nodpotentialer), och bildar en cykel med trädets bågar. Den utgående variabeln är cirkelbågen med det minst ökande flödet. Ersättandet av inträde för att lämna båge, och rekonstruktionen av trädet kallas en pivot. När ingen icke-grundläggande båge fortfarande är berättigad att komma in, har den optimala lösningen uppnåtts.
Ansökningar
Nätverkssimplexalgoritmen kan användas för att lösa många praktiska problem inklusive,
- Omlastningsproblem
- Hitchcocks transportproblem
- Uppdragsproblem
- Kedjor och antikedjor i delbeställda set
- System av distinkta representanter
- Omslag och matchning i tvådelade grafer
- Catering problem
externa länkar
- Lösa nätverksproblem Avsnitt 14, s B-113 visar ett exempel på exekvering