Simplex-algoritmen

Fra Wikipedia, den frie encyklopedi
Gå til: navigasjon, søk

Simplex-algoritmen av George Dantzig er i matematisk optimaliseringsteori en populær teknikk for numerisk løsning av lineærprogrammeringsproblemet. 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[rediger | rediger kilde]

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, 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[rediger | rediger kilde]

Matriseversjon av simplex-algoritmen[rediger | rediger kilde]

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[rediger | rediger kilde]

  • 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:
    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.


Referanser[rediger | rediger kilde]


Eksterne lenker[rediger | rediger kilde]