Lineare Optimierung

Eine Punktmenge $M \subseteq A$ heißt konvex, wenn mit je zwei Punkten auch die Strecke $C([{a},{b}]) := { \m......ath{a}+ (1-t) * {b}, 0 <= t <= 1 }$ in liegt.

Der Durchschnitt $\bigcap_{i in I} M_i$ einer nichtleeren Familie konvexer Mengen ist wieder konvex.

Ein Punkt ( konvex) heißt extremal, wenn es keine zwei Punkte ${p}_1,{p}_2in M$ gibt, deren Mittelpunkt gleich ist.

Eine Normalform einer linearen Optimierungsaufgabe liegt vor mit

$\begin{array}{rccl}A * (x_j) & <= & (s_i) & \ldo......unktion}index{Zielfunktion} \rule{0mm}{5mm} \\\end{array}$

Durch die Einführung von Schlupfvariablen kann man das lineare -Ungleichungssystem auf ein -Gleichungssystem transformieren.

Ist $l = (l_1 *s l_{r} 0 *s 0)^T$ Lösung von , dann ist genau dann eine Ecke, wenn $rg }({a}_1, ..., {a}_{r}) = r$ oder .

Falls die lineare Optimierungsaufgabe in Normalform (mit Schlupfvariablen) eine Lösung besitzt, so ist die Menge aller Lösungen konvex. Das Maximum der Zielfunktion wird dann auch in einer Ecke des Zulässigkeitsbereiches angenommen.

Man fasst eine lineare Optimierungsaufgabe in einem Tableau zusammen:

$\begin{array}{c| cl}A & s_i & {\Big } >= 0 \\ \c......=1}^{m+n}c_j * x_j + c –> {MAX} \\end{array}$

Eine Addition einer Linearkombination der ersten

Zeilen zur Zielfunktion verändert diese zwar, doch es gilt: $\widetilde{z}| _L = z| _L$ .

Sei $\begin{array}{cc| c} E_m & \widetildeA & \widetilde{s}_i \\ \hline 0 & \widetilde{c}_j & -\widetilde{c} \end{array}$ das Tableau einer linearen Optimierungsaufgabe. Dann gilt folgendes Kriterium für eine Optimalstelle:

Falls $\widetilde{c}_j <= 0 forall j in {m+1, ..., m+n}$ , dann ist die zulässige Basislösung optimal, und $\widetilde{c}$ das Maximum der Zielfunktion.
Falls ein $\widetilde{c}_k > 0$ ( ) und keines der Elemente $\widetilde{a}_{1k}, ..., \widetilde{a}_{mk}$ positiv ist, dann existiert kein Maximum.

Der Simplexalgorithmus liefert ein Verfahren, um aus einem Tableau durch Umformungen zu einer optimalen Ecke zu gelangen. Dieser Algorithmus bricht sicher dann ab, wenn zu jedem Schritt eine nicht ausgeartete Basislösung gehört.

Eine lineare Optimierungsaufgabe, die nicht in Normalform vorliegt, löst man durch die Einführung von Scheinvariablen und durch Maximieren der sekundären Zielfunktion

$w: ( \begin{array}{c} x_1 \\ \vdots \\ x_{M+n} \\ \end{array} ) \mapsto -sum_{j=n+q-1}^{n+M} x_j$

Falls das Maximum

ist, sind die Lösungen dann genau die Lösungen der ursprünglichen Aufgabe. So kann man jede lineare Optimierungsaufgabe durch Anwendung der beiden Phasen des Simplexalgorithmus versuchen zu lösen.