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 $\mathbf {(} c)^{T}\mathbf {x}$

gitt $\mathbf {A} \mathbf {x} \leq \mathbf {b} ,\,\mathbf {x} \geq 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}\geq 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–804.

Eksterne lenker

• An Introduction to Linear Programming and the Simplex Algorithm Arkivert 30. juni 2006 hos Wayback Machine., 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).