Nettverk simpleks algoritme - Network simplex algorithm

I matematisk optimalisering er nettverkssimpleksalgoritmen en grafteoretisk spesialisering av simpleksalgoritmen . Algoritmen er vanligvis formulert i form av et minimalkostnadstrømproblem . Network simplex-metoden fungerer veldig bra i praksis, vanligvis 200 til 300 ganger raskere enn simplex-metoden som brukes på generelle lineære programmer med samme dimensjoner.

Historie

I lang tid var eksistensen av en beviselig effektiv nettverkssimpleksalgoritme et av de største åpne problemene i kompleksitetsteorien, selv om effektive versjoner i praksis var tilgjengelige. I 1995 ga Orlin den første polynomalgoritmen kjøretid på hvor er maksimumskostnad for eventuelle kanter. Senere forbedret Tarjan dette til å bruke dynamiske trær i 1997. Sterkt polynomiske dual-network simplex-algoritmer for det samme problemet, men med større avhengighet av antall kanter og hjørner i grafen, har vært kjent lenger.

Oversikt

Network simplex-metoden er en tilpasning av den avgrensede variable primal simplex-algoritmen. Grunnlaget er representert som et rotfestet spennende tre i det underliggende nettverket, der variabler er representert av buer, og simpleksmultiplikatorene av nodepotensialer. Ved hver iterasjon velges en inngående variabel av en eller annen prisstrategi, basert på de doble multiplikatorene (nodepotensialer), og danner en syklus med treets buer. Den forlatte variabelen er syklusens bue med minst forsterkende strømning. Erstatningen for å komme inn for å forlate buen, og rekonstruksjonen av treet kalles en pivot. Når ingen ikke-basisk lysbue fortsatt er kvalifisert for å komme inn, er den optimale løsningen nådd.

applikasjoner

Network simplex-algoritmen kan brukes til å løse mange praktiske problemer, inkludert,

Referanser

Eksterne linker