Lineární programování (simplexová metoda)

Hledáme maximum účinkové funkce $z = a_{01} x_1 + a_{02} x_2 + \dots + a_{0N} x_N$. Máme zadaných $N$ primárních podmínek $x_1 \geq 0$, $x_2 \geq 0$, $\dots$, $x_N \geq 0$ a $M$ dodatečných podmínek, z toho $m_1$ podmínek 1.druhu ($<$), $m_2$ podmínek 2.druhu ($>$) a $m_3$ podmínek 3.druhu ($=$), $M = m_1 + m_2 + m_3$.

Dodatečné podmínky jsou zadány následovně:

$$a_{i1} x_1 + a_{i2} x_2 + \dots + a_{iN} x_N \leq b_i \geq 0 \quad \quad i = 1, \dots, m_1$$

$$a_{i1} x_1 + a_{i2} x_2 + \dots + a_{iN} x_N \geq b_j \geq 0 \quad \quad j = m_1 + 1, \dots, m_1 + m_2$$

$$a_{k1} x_1 + a_{k2} x_2 + \dots + a_{kN} x_N = b_k \geq 0 \quad \quad k = m_1 + m_2 + 1, \dots, M$$

Z množiny možných vektorů (vyhovujících $\forall$ podmínkám) vybíráme
optimální možný vektor.

Úloha nemusí mít řešení

1. Nemusí však existovat žádný možné vektory.
2. Nebo $\neg \exists$ maximum $z$, účinek $z$ roste v nějakém směru, ve kterém je množina možných vektorů otevřena (do $\infty$).

Množina možných vektorů je simplex v $N - m_3$-rozměrném prostoru. Množinu vrcholů simplexu nazýváme vertex.

Věta Jestliže existuje optimální možný vektor, pak existuje vrchol simplexu, který je optimální.

Pozn. Pokud počet primárních podmínek $N$ je větší než počet dodatečných podmínek $M$, pak každý vrchol simplexu má alespoň $N - M$ souřadnic $= 0$. Počet vrcholů - prvků vertexu $V$ je

$${M+N \choose N} = {M+N \choose M}\ \ .$$

Normální forma úlohy lineárního programování nemá žádné podmínky s nerovností, tedy $m_1 = m_2 = 0$.
Omezená normální formu má dodatečné podmínky tvaru $x_i = \tilde{b}_i + \tilde{a}_{ij} x_j \geq 0$, přičemž $x_i$ je jen v jediné podmínce (levostranná proměnná).