Redigerer Simplex-algoritmen (avsnitt)

== Problemets inndata ==
Anta et lineærprogrammeringsproblem,
: maksimer <math>\mathbf(c)^T \mathbf{x} </math>
: gitt <math>\mathbf{A}\mathbf{x} \le \mathbf{b}, \, \mathbf{x} \ge 0 </math>

Simplex-algoritmen krever at lineærprogrammeringsproblemet er på [[normalform]].  Problemet kan da skrives som følger på matriseform:
: maksimer ''Z'' i:
: <math>
  \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}
</math>

: <math> \mathbf{x}, \, \mathbf{x}_s \ge 0 </math>

der '''x''' er variablene fra ''standard formen'', '''x'''<sub>s</sub> 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.

<!-- Usynlig tekst start
{{uoversatt2|engelsk}}

This form simplifies finding the initial ''basic feasible solution'' (BF), since all variables from the ''standard form'' can be chosen to be nonbasic (zero), while all new variables introduced in the ''augmented form'' are basic (nonzero), since their value can be trivially calculated (<math>\mathbf{x}_{s\,i} = \mathbf{b}_{j}</math> for them, since the augmented problem matrix is diagonal on its right half).
Usynlig tekst slutt -->