|
Die lineare Optimierung behandelt nur Probleme, bei denen die Variablen beliebige reelle Zahlen annehmen dürfen. Ein ''(gemischt-)ganzzahliges lineares Programm'', bei dem einige Variablen nur ganzzahlige Werte annehmen dürfen, ist ''kein Spezialfall'', sondern – im Gegenteil – eine Verallgemeinerung. Solche Optimierungsprobleme sind im Allgemeinen [[NP-Äquivalenz|NP-äquivalent]], d. h. [[P-NP-Problem|vermutlich]] nicht effizient lösbar. Dieser Fall wird von der [[Ganzzahlige lineare Optimierung|ganzzahligen linearen Optimierung]] behandelt.
=== Formen eines Linearen Optimierungsproblems===
Es gibt drei verschiedene Formen, in der sich Lineare Optimierungsprobleme darstellen lassen.
====Allgemeine Form====
Für die Allgemeine Form gelten keine Einschränkungen:
<math>\begin{matrix}\min \\ \max\end{matrix}\; \left\{ c^\top x : Ax \gtreqless b \right\}</math>
====Standardform====
Die Normalform beinhaltet die Standardform und benötigt eine Nichtnegativitätsbedingung für <math>x,b</math> und eine zu maximierende Zielfunktion (eine zu minimierende Zielfunktion lässt sich mit der Multiplikation von -1 in eine zu maximierende Zielfunktion überführen).
<math>\max \left\{ c^\top x : Ax \geq b,\;\; x,b \geq 0 \right\}</math>
====Kanonische Form====
Die Kanonische Form beinhaltet die Standardform und wird für den Simplex-Algorithmus benötigt. Sie erweitert die Matrix <math>A</math> um die Einheitsmatrix <math>E \in \mathbb{R}^{m\times m}</math> und die Schlupfvariablen <math>s = s_1, s_2, \dots, s_3</math> und aus den Größer-Gleich-Ungleichungen der Nebenbedingungen in der Standardform wird ein Gleichungssystem, so dass gilt
<math>
(A|E)\begin{pmatrix}x\\s\end{pmatrix} = b = \begin{pmatrix}a_{11} & \dots & a_{1n} & e_{11} & \dots & e_{1m}\\
\vdots & & \vdots & \vdots & & \vdots\\
a_{m1} & \dots & a_{mn} & e_{m1} & \dots & e_{mm}
\end{pmatrix} \cdot \begin{pmatrix}x_1\\ \vdots \\ x_n\\ s_1 \\ \vdots \\ s_{m-n}\end{pmatrix} = \begin{pmatrix}b_1\\ \vdots \\ b_m\end{pmatrix}
</math>
mit dem <math>s = \begin{pmatrix}s_1 & s_2 & \dots & s_{m-n}\end{pmatrix}^\top</math> als Schlupfvariablen.
Um in der ursprünglichen Notationsweise zu bleiben, gilt
<math>\max\; \left\{ c^\top x : (A | E) (x\quad s)^\top = b , \;\; x,b\geq 0\right\}</math>
=== Geometrische Interpretation ===
| 