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* &nbsp;+&nbsp;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 \mathbf(c)^T \mathbf{x} 
: gitt \mathbf{A}\mathbf{x} \le \mathbf{b}, \, \mathbf{x} \ge 0 

Simplex-algoritmen krever at lineærprogrammeringsproblemet er på normalform.  Problemet kan da skrives som følger på matriseform:
: maksimer *Z* i:
: 
  \begin{bmatrix}
    1 & -\mathbf{c} & 0 \\
    0 & \mathbf{A} & \mathbf{I}
  \end{bmatrix}
  \begin{bmatrix}
    Z \\ \mathbf{x} \\ \mathbf{x}_s
  \end{bmatrix} = 
  \begin{bmatrix}
    0 \\ \mathbf{b}
  \end{bmatrix}


:  \mathbf{x}, \, \mathbf{x}_s \ge 0 

der **x** er variablene fra *standard formen*, **x**s 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:
: 
  \begin{bmatrix}
    1 & \mathbf{c}_B \mathbf{B}^{-1}\mathbf{A}  -\mathbf{c} & \mathbf{c}_B \mathbf{B}^{-1} \\
    0 & \mathbf{B}^{-1}\mathbf{A} & \mathbf{B}^{-1}
  \end{bmatrix}
  \begin{bmatrix}
    Z \\ \mathbf{x} \\ \mathbf{x}_s
  \end{bmatrix} = 
  \begin{bmatrix}
    \mathbf{c}_B \mathbf{B}^{-1} \mathbf{b} \\ \mathbf{B}^{-1}\mathbf{b}
  \end{bmatrix}

der \mathbf{c}_B er koeffisienten av basisvariabene i **c**-matrisen; og **B** er [\mathbf{A} \, \mathbf{I}] som korresponderer med basisvariablene.

Det er viktig å merke seg at **B** og \mathbf{c}_B 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 \mathbf{c}_B 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 \mathbf{c}_B \mathbf{B}^{-1}\mathbf{A}  -\mathbf{c} som har mest *negativ*. Denne ikke-basisvariabelen, som vi kaller *innbasis*, skal økes for å maksimalisere problemet.
** **Velg maksimal skrittlengde**
*: Bruk ligningen \begin{bmatrix} \mathbf{B}^{-1}\mathbf{A} & \mathbf{B}^{-1} \end{bmatrix} \begin{bmatrix} \mathbf{x} \\ \mathbf{x}_s \end{bmatrix} =  \mathbf{B}^{-1}\mathbf{b} 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 \mathbf{c}_B 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 \mathbf{c}_B \mathbf{B}^{-1}\mathbf{A}  -\mathbf{c} 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&ndash;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).