2 phasen simplex größer gleich beispiel

Gr��er-gleich-Bedingungen

Gr��er-gleich-Bedingungen haben folgende Form:

ai1�x1+ ai2�x2+ �+ ain�xn ≥ bi

Dem Vorgehen bei Kleiner-gleich-Bedingungen entsprechend l�sst sich nun eine nichtnegative Variable einf�hren, die den �berschuss angibt.

ai1�x1+ ai2�x2+ �+ ain�xn � xn+i =bi

Tr�gt man diese Gleichung zusammen mit den anderen in ein Tableau ein, steht in der xn+i Spalte leider kein Einheitsvektor und somit gibt es auch noch keine Basisl�sung.

Ansatz �berschussvariable und k�nstliche Variable einf�hren

Eine Idee w�re, sich mit dem Zustand, dass anf�nglich keine Basisl�sung vorliegt, anzufreunden und sp�ter eine herzustellen. Da das Ganze aber automatisierbar sein soll, wird ein auf den ersten Blick etwas umst�ndlicher wirkender Weg beschritten.

ai1�x1+ ai2�x2+ �+ ain�xn � xn+i + x�n+i =bi

Deswegen zielt die 1. Phase des Simplexalgorithmus darauf ab, die k�nstlichen Variablen aus der Basis zu entfernen und zu streichen.

Beispiel:

4�x1 ≥120

Ansatz 2: Negative rechte Seite in Kauf nehmen

Eine andere M�glichkeit ist, die Gleichung

ai1�x1+ ai2�x2+ �+ ain�xn � xn+i =bi

mit -1 zu multiplizieren.

-ai1�x1- ai2�x2- �- ain�xn + xn+i =-bi

Auf diese Weise erh�lt man im Tableau Einheitsvektoren und es ist auch eine Basisl�sung vorhanden. Allerdings nimmt die Variable xn+i =-bi einen negativen Wert an, was dazu f�hrt, dass die vorhandene Basisl�sung unzul�ssig in Bezug auf die Nichtnegativit�tsbedingung ist.

Wird dieser Ansatz gew�hlt, muss die 1. Phase des Simplexalgorithmus darauf verwendet werden, diese Unzul�ssigkeiten durch geeignete Basist�usche zu beseitigen.

Gleichungen

Gleichungen haben folgende Form:

ai1�x1+ ai2�x2+ �+ ain�xn = bi

Auch hier ist das Problem, dass beim Eintragen in das Simplextableau eine Basisl�sung fehlt. An dieser Stelle hilft nur, eine k�nstliche Variable einzuf�hren.

ai1�x1+ ai2�x2+ �+ ain�xn + x�n+i =bi

Solange diese Variable gr��er als null ist, ist die Gleichung nicht erf�llt, sondern eine Kleiner-gleich-Nebenbedingung. Von daher m�ssen auch diese k�nstlichen Variablen in der 1. Phase des Simplexalgorithmuses entfernt werden.

Freie Variablen

Die Lineare Optimierung ist darauf ausgerichtet, dass Variablen nicht negativ sein d�rfen. Es kann aber in realen Problemen Variablen geben, die auch negative Werte annehmen d�rfen. Sie werden Freie Variablen genannt.

Freie Variablen k�nnen in einen positiven und einen negativen Teil gespaltet werden.

Beispiel (kein Zusammenhang mit begleitendem Beispiel):

Der Simplexalgorithmus besteht aus zwei Phasen. Da alle bisherigen Ausf�hrungen auf einem vereinfachten Modell fu�en, bei dem immer schon nach Aufstellen des Tableaus eine zul�ssige Basisl�sung vorliegt, kann mit der 2.�Phase begonnen werden.

Um gleich zu Beginn das Geheimnis zu l�ften, die Optimierung erfolgt beim Simplexalgorithmus �ber eine Folge von Basist�uschen. Da der maximale Zielwert gesucht wird, ist es zielf�hrend, wenn sich der Zielwert bei jedem Basistausch vergr��ert. Weiterhin muss sichergestellt werden, dass die Nichtnegativit�tsbedingungen eingehalten werden.

Bei einem Basistausch ist zu entscheiden, welche Variable die Basis verlassen soll und welche aufgenommen werden soll. Die aufzunehmende Variable wird �ber die Auswahl der Pivotspalte festgelegt, die verlassende �ber die Pivotzeile. Anders ausgedr�ckt, es wird festgelegt, welche Variable einen h�heren Wert annehmen soll und welche auf null gesetzt wird.

Auswahl der Pivotspalte (=Aufzunehmenden Basisvariablen)

W�hle als Pivotspalte eine Spalte s, f�r die gilt:

Falls cs≥0 Abbruch, das Optimum ist erreicht.

In Worten: Suche den kleinsten Koeffizienten in der Zielzeile, die Spalte in der er steht ist die Pivotspalte. Ist der kleinste Koeffizient gr��er als 0, ist bereits das Optimum erreicht und es braucht nicht weiter gerechnet zu werden.

Erh�ht man den Wert einer Variablen xj um eine Einheit, so �ndert sich der Zielwert um cj. Aufgrund der Umformungen beim Aufstellen des Tableaus steigt der Zielwert, wenn man den Wert einer Variable mit negativen Zielzeilenkoeffizienten erh�ht und sinkt bei einer mit positiven.

Deswegen wird der kleinste Zielzeilenkoeffizient gesucht, er verspricht die gr��te Erh�hung des Zielwertes. Existiert kein negativer Zielzeilenkoeffizient, gibt es keine M�glichkeit den Zielfunktionswert zu erh�hen. Es ist von daher nicht sinnvoll, einen Basistausch vorzunehmen, das Optimum ist erreicht.

Im Tableau wird gem�� vorstehender Regel die x2 Spalte als Pivotspalte gew�hlt.

Auswahl der Pivotzeile (=die Basis verlassende Variable)

Die Auswahl der Pivotzeile r erfolgt nach dem Quotientenkriterium.

W�hle eine Zeile r f�r die gilt:

Um die Pivotzeile zu bestimmen, wird f�r jede Zeile, in der sich ein positiver Koeffizient in der Pivotspalte befindet, der Qutient aus dem Wert auf der rechten Seite und dem Koeffizienten der Pivotspalte gebildet.

Es wird die Zeile gew�hlt, in der der Quotient am kleinsten ist. In diesem Beispiel ist es die Zeile der zweiten Nebenbedingung, die Variable x4 verl�sst die Basis, d.h. sie nimmt den Wert null an.

�ber diese Auswahlregel wird die Nichtnegativit�t der Variablen sichergestellt.

Eine ausf�hrliche Betrachtung

Ausgeschrieben lautet die erste Nebenbedingung:

0,8�x1+ 0,8�x2 + x3 =80

Urspr�nglich sind x1 und x2 null, da es Nichtbasisvariablen sind. Nun soll x2 erh�ht werden, x1 bleibt in dieser Iteration null und ist f�r die Betrachtung unerheblich.

0,8�x2 + x3 =80

Wie verh�lt sich der Wert von x3 in Abh�ngigkeit von x2? Durch Aufl�sen nach x3 l�sst sich das gut erkennen:

x3 =80 - 0,8�x2

Je gr��er x2 ist, desto kleiner wird x3. Um die Nichtnegativit�tsbedingung zu erf�llen, darf x3 aber nicht kleiner als null werden. Wie gro� darf x2 werden? 0 =80 - 0,8�x2

x2=80/0,8

x2=100.

Vorstehendes ist nichts anderes als der oben gebildete Quotient. Da keine Variable negative Werte annehmen darf, wird das f�r jede Zeile gepr�ft. Die Zeile, die die kleinste Erh�hung zul�sst, ist einschr�nkend. Die Schlupfvariable in dieser Zeile wird null und verl�sst die Basis.

F�r Zeilen in denen der Koeffizient in der Pivotspalte negativ bzw. null ist, braucht der Quotient nicht gebildet werden. Wird in einer Zeile mit negativem Koeffizient die Variable erh�ht, steigt der Wert der Basisvariablen ebenfalls, ist der Koeffizient null besteht kein Einfluss.

Betrachtung am Beispiel:

Wie bei der Wahl der Pivotspalte festgelegt wurde, soll nun m�glichst viel Superfruchtm�sli hergestellt werden. Welche Zutat geht als erstes aus?

• Haferflocken: 80 kg vorhanden, ben�tigt werden 0,8 kg pro kg Superfruchtm�sli, die Haferflocken reichen f�r 100 kg M�sli aus.
• Trockenobst: 16 kg vorhanden, ben�tigt werden 0,2 kg pro kg Superfruchtm�sli, das Trockenobst reicht f�r 80 kg M�sli aus.
• N�sse: Werden keine f�r das Superfruchtm�sli ben�tigt, von daher nicht einschr�nkend.

Das Trockenobst beschr�nkt die herstellbare Menge M�sli, werden 80 kg Superfruchtm�sli hergestellt wird es restlos aufgebraucht, es verbleibt jedoch ein Rest von 16 kg Haferflocken.