Lineare Optimierung

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

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

Ein Punkt {p}in M (M konvex) heißt extremal, wenn es keine zwei Punkte {p}_1,{p}_2in M gibt, deren Mittelpunkt gleich {p} 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 (m,n)-Ungleichungssystem auf ein (m,m+n)-Gleichungssystem transformieren.

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

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 m 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:

  1. Falls \widetilde{c}_j <= 0 forall j in {m+1, ..., m+n} , dann ist die zulässige Basislösung (s_1 *s s_m 0 *s 0)^T optimal, und \widetilde{c} das Maximum der Zielfunktion.
  2. Falls ein \widetilde{c}_k > 0 ( k in {m+1, ..., m+n}) 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 0 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.
 Diese Seite erfüllt die HTML-4.01-Spezifikationen!
Übersicht
Zurück Home Weiter
Index