Simplex-algoritmen
Fra Wikipedia, den frie encyklopedi
I matematisk optimaliseringsteori er simplex-algoritmen av George Dantzig 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.
[rediger] Problemets inndata
Anta et lineærprogrammeringsproblem,
- maksimer
- gitt
Simplex-algoritmen krever at lineærprogrammeringsproblemet er på slack form. 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.
