Überblick

Einführend zum Softwarepraktikum beziehungsweise als kurze Wiederholung soll an dieser Stelle noch einmal ein Überblick über die Thematik "Zweite geometrische Interpretation in der linearen Optimierung" gegegeben werden.

Definition: In einem linearen Optimierungsproblem (im folgenden kurz: LOP) wird eine lineare Zielfunktion der Variablen x₁, ..., x_n unter linearen Nebenbedingungen für diese Variablen (Gleichungen oder Ungleichungen) maximiert oder minimiert.

Bei der zweiten geometrische Interpretation handelt es sich um eine lineare Optimierung mit zwei Nebenbedingungen und beliebig vielen Variablen.
Formal kann das wie folgt beschrieben werden:

Um dieses Optimierungsproblem zu lösen, wird das Problem in den ℜ³ mit den Koordinaten u₁, u₂, u₃ wie folgt transformiert:

Das LOP hat dabei folgende Eigenschaften:

1. Das Bild aller Punkte X = ( x₁ ... x_n )^T ≥ 0 ist ein konvexer (mehrkantiger) Kegel K, der durch die Strahlen ( a_1j, a_2j, c_j )^T x_j mit x_j ≥ 0 ∀ j ∈ N erzeugt wird.
2. Das Bild aller Punkte X, die die Nebenbedingungen Ax = b erfüllen, ist die Gerade G:

   u1		b1		b1		0
   u2	=	b2	=	b2	+ λ	0	, λ ∈ ℜ
   u3		z		0		1

3. Der Lösungsbereich B des LOP wird auf den Durchschnitt K ∩ G abgebildet.
4. Bei z = max! ist der "obere" Durchstoßpunkt von G durch den Kegel K zu bestimmen. Bei z = min! ist der "untere" Durchstoßpunkt von G durch den Kegel K zu bestimmen. ("oben", "unten" bzgl. u₃-Achse!)

Hier setzt auch das Softwarepraktikum an. Mit den herkömmlichen Mitteln war es gerade bei LOP's mit vielen Variablen bisher schwer bis unmöglich, den konvexen Kegel zu visualisieren und damit die Lösung(en) für das LOP zu bestimmen.
Hier unterstützt jetzt die vorliegende Software das Lokalisieren des Lösungsbereiches bzw. der optimalen Lösung(en).

Dabei können folgende Fälle für den Lösungsbereich auftreten:

1. Der Durchschnitt G ∩ K = ∅: Damit ist B leer, es existieren weder zulässige noch optimale Lösungen.
2. Der Durchschnitt G ∩ K ist eine Strecke: z_min und z_max existieren.
3. Der Durchschnitt G ∩ K ist ein Strahl:
   1. Es existiert z_max und z_min ist unbeschränkt oder:
   2. Es existiert z_min und z_max ist unbeschränkt.

Bei der Existenz von optimalen Lösungen gibt es folgende Möglichkeiten:

1. Der Durchstoßpunkt der Geraden durch den Kegel liegt auf einer Seite des Kegels, die durch genau zwei Strahlen erzeugt wird: Die optimale Lösung ist eindeutig.
2. Der Durchstoßpunkt der Geraden durch den Kegel liegt auf einer Seite des Kegels, die durch mehr als zwei Strahlen erzeugt wird: Es gibt mehrere optimale Lösungen.

Alle möglichen Fälle für die auftretenden Lösungen bzw. für den Lösungsbereich des LOP werden durch die Software dargestellt. Der Nutzer soll allerdings die Lösung selbst ermitteln und eingeben sowie die erkannten Fälle für die Lösung(en) bzw. den Lösungsbereich kennzeichnen.