Simplex-algoritmen

Simplex-algoritmen av George Dantzig er i matematisk optimaliseringsteori en populær teknikk for numerisk løsning av problemer fra lineær programmering.  En ubeslektet, men med likt navn er Nelder-Mead-metoden eller downhill simplex method etter Nelder & Mead (1965) og er en numerisk metode for å optimalisere mange-dimensjonale ubegrensete problemer som hører til en mer generell klasse av søkealgoritmer.

I begge tilfellene bruker metoden konseptet med en simplex, som er en polytop med N  + 1 hjørner i N dimensjoner: et linjesegment på en linje, et triangel på et plan, et tetraeder i tre-dimensjonalt rom og så videre.

Problemets inndata 
Anta et lineærprogrammeringsproblem,
 maksimer 
 gitt 

Simplex-algoritmen krever at lineærprogrammeringsproblemet er på normalform.  Problemet kan da skrives som følger på matriseform:
 maksimer Z i:
 

 

der x er variablene fra standard formen, xs er de introduserte slack-variablene fra utvidelsesprosessen, c inneholder optimaliseringskoeffisientene, A og b beskriver systemet av begrensningslikninger, og Z er variablen som skal bli maksimert.

Systemet er typisk underbestemt.  Antall ukjente variable overstiger antall ligninger.  Differansen mellom antall variable og antall ligninger er systemets frihetsgrad. Enhver løsning, optimal eller ikke, vil inneholde noen variable med vilkårlig verdi.  Simplex-algoritmen setter disse til null.

Variable som ikke er null kalles basisvariable og variable som er null kalles ikke-basisvariable.

Revidert simplex-algoritme

Matriseversjon av simplex-algoritmen 
I enhver iterasjon i simplex-algoritmen kan beskrives med formelen:
 
der  er koeffisienten av basisvariabene i c-matrisen; og B er  som korresponderer med basisvariablene.

Det er viktig å merke seg at B og  er de eneste variable i denne ligningen (unntatt Z og x). Alt annet er konstant gjennom algoritmen.

Algoritme 
 Velg en startverdi for BF som vist over
 Dette betyr at B er identitetsmatrisen, og  er en null-vektor.

 Gjenta til man har en optimal løsning:
 Finn retningen med størst gradient
 Velg den variabelen som er assosiert med koeffisienten i  som har mest negativ. Denne ikke-basisvariabelen, som vi kaller innbasis, skal økes for å maksimalisere problemet.
 Velg maksimal skrittlengde
 Bruk ligningen  for å bestemme hvilken basisvariabel som først går til null når innbasis økes. Denne variabelen som vi kaller utbasis blir ikke-basisvariabel. Denne operasjonen innebærer en divisjon for hver basisvariabel fordi de eksisterende basisvariablene er på diagonalen.
 Omskriv problemet
 Modifiser B og  for å ta hensyn til de nye basisvariablene. Dette vil sette de nye og gamle basisvariablene på diagonalen.
 Verifiser forbedring
 Gjenta prosedyren til ingen ytterligere forbedring er mulig, slik at alle koeffisientene i  er positive. Prosedyren termineres også dersom alle koeffisientene er null eller dersom algoritmen har gått i sirkel og man har kommet til en tidligere tilstand.

Litteratur
 Greenberg, Harvey J., Klee-Minty Polytope Shows Exponential Time Complexity of Simplex Method University of Colorado at Denver (1997) PDF download
 Frederick S. Hiller and Gerald J. Lieberman: Introduction to Operations Research, 8th edition. McGraw-Hill. ISBN 0-07-123828-X
 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 29.3: The simplex algorithm, pp.790–804.

Eksterne lenker
 An Introduction to Linear Programming and the Simplex Algorithm , Spyros Reveliotis, Georgia Institute of Technology.
 Java-basert interaktivt simplex verktøy, Argonne National Laboratory.
 Simplex Algorithm av Elmer G. Wiens. Demonstrerer algoritmen i detalj.
 Tutorial for The Simplex Method av Stefan Waner, Hofstra University
 A simple example – step by step fra Mazoo's Learning Blog.
 Simplex Method En god innføring i simplex-algoritmen med eksempler (også to-fase og M-metoden).

Optimeringsalgoritmer og -metoder