Simplex-Methoden: M-Methode und Zwei-Phasen-Verfahren

Die M-Methode in der Linearen Optimierung

Bisher wurden Informationen zur Simplex-Methode unter der Annahme bereitgestellt, dass das Problem in der Standardform vorliegt (d.h. Z maximieren unter funktionalen Nebenbedingungen der Form ≤ und Nicht-Negativitätsbedingungen für alle Variablen), wobei b_i ≥ 0 für alle i = 1, 2, ..., m. In diesem Abschnitt wird dargelegt, wie die erforderlichen Anpassungen für andere legitime Formen linearer Programmierungsmodelle vorgenommen werden. Wir werden sehen, dass all diese Anpassungen im ersten Schritt erfolgen können, sodass der Rest der Simplex-Methode wie gelernt angewendet wird.

Das einzige ernsthafte Problem, das die Einführung anderer Formen funktionaler Beschränkungen (= oder ≥) mit sich bringt, ist die Identifizierung einer ersten zulässigen Basislösung. Zuvor wurde diese erste Lösung auf sehr bequeme Weise gefunden: Die Schlupfvariablen waren die ersten Basisvariablen, wobei jede gleich der nicht-negativen Konstanten auf der rechten Seite der Gleichung war. Jetzt muss etwas anderes geschehen. Die Standardvorgehensweise in diesen Fällen ist die Technik der künstlichen Variablen. Diese Technik konstruiert ein bequemeres künstliches Problem, indem eine Hilfsvariable (sog. künstliche Variable) in jede Beschränkung eingeführt wird, die dies erfordert. Diese neue Variable wird nur zu dem Zweck eingeführt, die erste Basisvariable für diese Gleichung zu sein. Die üblichen Nicht-Negativitätsbedingungen werden auch auf diese Variablen angewendet, und die Zielfunktion wird geändert, um eine exorbitante Strafe zu verhängen, falls die künstliche Variable Werte größer als Null annimmt. Die Iterationen der Simplex-Methode zwingen die künstlichen Variablen automatisch dazu, nacheinander zu verschwinden (Null zu werden), bis alle außerhalb der Lösung sind, wonach das eigentliche Problem gelöst wird.

Anwendung der künstlichen Variablen

Um die Technik der künstlichen Variablen zu illustrieren, betrachten wir zunächst den Fall, dass die einzige Nicht-Standard-Form des Problems das Vorhandensein einer oder mehrerer Gleichheitsbeschränkungen ist.

Gleichheitsbeschränkungen

Eine Beschränkung in Form einer Gleichheit:

a_i1x₁ + a_i2x₂ + ... + a_inx_n = b_i

entspricht der Kombination von zwei Ungleichungen:

a_i1x₁ + a_i2x₂ + ... + a_inx_n ≤ b_i

a_i1x₁ + a_i2x₂ + ... + a_inx_n ≥ b_i

Doch anstatt diese Substitution vorzunehmen und damit die Anzahl der Beschränkungen zu erhöhen, ist es bequemer, die Technik der künstlichen Variablen zu nutzen. Angenommen, wir ändern das im letzten Abschnitt vorgestellte und gelöste Beispielproblem. Die einzige Änderung, die das lineare Programmierungsmodell erfährt, ist, dass die dritte Bedingung, 3x₁ + 2x₂ ≤ 18, zu einer Gleichheitsbeschränkung wird:

3x₁ + 2x₂ = 18

Die Anwendung der Technik erfordert die Einführung einer nicht-negativen künstlichen Variable (bezeichnet als x₅) in der letzten Gleichung, ähnlich einer Schlupfvariable:

3x₁ + 2x₂ + x₅ = 18

Kurz gesagt: Wenn wir eine funktionale Gleichheitsbeschränkung haben und diese in ihre Gleichheitsform umwandeln wollen, fügen wir einfach eine künstliche Variable hinzu.

Funktionale Beschränkungen der Form ≥

Um zu veranschaulichen, wie die Technik der künstlichen Variablen Beschränkungen der Form ≥ handhabt, verwenden wir das folgende Beispiel:

Minimiere Z = 0.4x₁ + 0.5x₂

unter den Nebenbedingungen:

• 0.3x₁ + 0.1x₂ ≤ 2.7
• 0.5x₁ + 0.5x₂ = 6
• 0.6x₁ + 0.4x₂ ≥ 6

x₁ ≥ 0, x₂ ≥ 0

Beachten Sie, dass die dritte Bedingung vom Typ ≥ ist, sodass ihre Umwandlung in die Gleichheitsform eine Überschussvariable (oder Surplusvariable) erfordern würde, die wie folgt subtrahiert wird:

0.6x₁ + 0.4x₂ - x₅ = 6

Hier wurde die Überschussvariable x₅ subtrahiert, da sie den Überschuss von 0.6x₁ + 0.4x₂ über 6 darstellt. (In der ersten Beschränkung würden wir eine Schlupfvariable x₃ hinzufügen, und in der zweiten Beschränkung eine künstliche Variable x₄, um alle Ungleichungen in Gleichheiten umzuwandeln.) In diesem Fall muss jedoch eine weitere Variable hinzugefügt werden. Diese zusätzliche Variable, genannt künstliche Variable, wird wie folgt hinzugefügt:

0.6x₁ + 0.4x₂ - x₅ + x₆ = 6

Der Grund dafür ist, dass, wenn die künstliche Variable nicht hinzugefügt wird, die Nicht-Negativitätsbedingungen nicht erfüllt werden. Um dies zu verstehen, betrachten wir den Fall, dass die Simplex-Methode beginnt, indem alle realen (ursprünglichen) Variablen gleich Null gesetzt werden. Dann gilt:

0.6x₁ + 0.4x₂ - x₅ = 6

Setzen wir x₁ = 0 und x₂ = 0, dann:

-x₅ = 6

oder x₅ = -6 (was die Nicht-Negativitätsbedingung nicht erfüllt)

Die künstliche Variable sorgt dafür, dass alle Variablen nicht-negativ bleiben, wenn 0.6x₁ + 0.4x₂ kleiner als 6 ist. Wenn x₁ = 0 und x₂ = 0, dann ist x₅ = 0 und:

0.6x₁ + 0.4x₂ - x₅ + x₆ = 6

x₆ = 6

Kurz gesagt, eine Beschränkung der Form ≥ erfordert die Subtraktion einer Überschussvariable und das Hinzufügen einer künstlichen Variable.

Beispiel zur M-Methode (Maximierung)

Stellen Sie sich folgendes Problem vor:

Maximiere Z = 3x₁ + 5x₂

unter den Nebenbedingungen:

• x₁ ≤ 4
• 2x₂ ≤ 12
• 3x₁ + 2x₂ = 18

x₁ ≥ 0, x₂ ≥ 0

Wie oben erläutert, konstruieren wir zur Lösung dieses Problems ein künstliches Problem, das die gleiche optimale Lösung wie das eigentliche Problem hat, indem wir zwei Änderungen am realen Problem vornehmen:

1. Anwendung der Technik der Einführung künstlicher Variablen: Eine nicht-negative künstliche Variable (bezeichnet als x₅) wird in die letzte Gleichung eingeführt, ähnlich einer Schlupfvariable:
   3x₁ + 2x₂ + x₅ = 18
2. Zuweisung einer großen Strafe, wenn x₅ > 0, was die Zielfunktion ändert von Z = 3x₁ + 5x₂ zu:
   Z = 3x₁ + 5x₂ - Mx₅
   wobei M symbolisch eine sehr große positive Zahl ist. Diese Methode, die x₅ in der optimalen Lösung auf x₅ = 0 zwingt, wird als M-Methode bezeichnet.

Hinweis: Bei Minimierungsproblemen wird die künstliche Variable bestraft, indem sie in der Zielfunktion mit einem Koeffizienten von +M erscheint.

Nun wird die optimale Lösung für das eigentliche Problem mit der Simplex-Methode auf das künstliche Problem angewendet.

Da x₅ die Rolle einer Schlupfvariable in der dritten künstlichen Beschränkung des Problems spielt, entspricht diese Beschränkung 3x₁ + 2x₂ = 18.

Insbesondere ist das System von Gleichungen nach der Erweiterung des künstlichen Problems (d.h. in Gleichheitsform gebracht):

Maximiere Z

unter den Nebenbedingungen:

Z - 3x₁ - 5x₂ + Mx₅ = 0

x₁ + x₃ = 4

2x₂ + x₄ = 12

3x₁ + 2x₂ + x₅ = 18

x_j ≥ 0 für j = 1, 2, 5

Wir sind nun bereit, die Koeffizienten in eine Simplex-Tabelle zu übertragen:

Tabelle 1: Initialisierung der Simplex-Tabelle

Basisvariable | Z | x1 | x2 | x3 | x4 | x5 | Rechte Seite | Verhältnis 
-------------------------------------------------------------------------- 
Z            | 1 | -3 | -5 | 0  | 0  | M  | 0            | 
x3           | 0 | 1  | 0  | 1  | 0  | 0  | 4            | 
x4           | 0 | 0  | 2  | 0  | 1  | 0  | 12           | 
x5           | 0 | 3  | 2  | 0  | 0  | 1  | 18           |

Diese Tabelle ist noch nicht in der richtigen Form, da der Koeffizient von x₅ in der Z-Gleichung ungleich Null ist (M). Bevor die Simplex-Methode den Optimalitätstest anwenden und die eintretende Basisvariable finden kann, muss diese Tabelle in die richtige Form gebracht werden, um die einseitige Bedingung zu erfüllen. Diese Bedingung besagt, dass jede Basisvariable eine 1 in der Schnittmenge ihrer Zeile und Spalte und Nullen in allen anderen Zeilen (außer der Z-Zeile) haben muss, d.h., jede Basisvariable sollte nur in ihrer eigenen Zeile einen Koeffizienten ungleich Null haben. Um den Koeffizienten M auf Null zu setzen, verwenden wir die Zeile von x₅ als Pivotzeile, multiplizieren sie mit -M und addieren das Ergebnis zur Z-Zeile. Nach Durchführung des oben beschriebenen Verfahrens sieht die Simplex-Tabelle wie folgt aus:

Tabelle 2: Angepasste Simplex-Tabelle

Basisvariable | Z | x1      | x2      | x3 | x4 | x5 | Rechte Seite | Verhältnis 
-------------------------------------------------------------------------------- 
Z            | 1 | -3M-3   | -2M-5   | 0  | 0  | 0  | -18M         | 
x3           | 0 | 1       | 0       | 1  | 0  | 0  | 4            | 
x4           | 0 | 0       | 2       | 0  | 1  | 0  | 12           | 
x5           | 0 | 3       | 2       | 0  | 0  | 1  | 18           |

Wir stellen fest, dass die vorhergehende Tabelle bereits in der entsprechenden Form ist und wir die aktuelle zulässige Basislösung ablesen können, die (0, 0, 4, 12, 18) ist. Beim Optimalitätstest sehen wir, dass sie nicht optimal ist, da es noch negative Koeffizienten in der Z-Zeile gibt (entsprechend x₁ und x₂). Bei Anwendung der Simplex-Methode auf die obige Tabelle ist der negative Koeffizient mit dem größten Betrag (-3M-3) x₁ zugeordnet. Da M eine sehr große positive Zahl ist, wird x₁ die eintretende Basisvariable. Bei Durchführung des entsprechenden Verhältnistests sehen wir, dass die Basisvariable x₃ die verlassende Variable wird. Das vollständige Lösungsverfahren für dieses Beispiel ist in den folgenden Tabellen dargestellt:

Tabelle 3: Simplex-Iterationen

Basisvariable | Z | x1      | x2      | x3 | x4 | x5 | Rechte Seite | Verhältnis 
-------------------------------------------------------------------------------- 
Z            | 1 | -3M-3   | -2M-5   | 0  | 0  | 0  | -18M         | 
x3           | 0 | 1       | 0       | 1  | 0  | 0  | 4            | 4 / 1 = 4 
x4           | 0 | 0       | 2       | 0  | 1  | 0  | 12           | 
x5           | 0 | 3       | 2       | 0  | 0  | 1  | 18           | 18 / 3 = 6 

Z            | 1 | 0       | -2M-5   | 3M+3 | 0  | 0  | -6M+12       | 
x1           | 0 | 1       | 0       | 1    | 0  | 0  | 4            | 
x4           | 0 | 0       | 2       | 0    | 1  | 0  | 12           | 12 / 2 = 6 
x5           | 0 | 0       | 2       | -3   | 0  | 1  | 6            | 6 / 2 = 3 

Z            | 1 | 0       | 0       | -9/2 | 0  | M+5/2 | 27          | 
x1           | 0 | 1       | 0       | 1    | 0  | 0  | 4            | 4 / 1 = 4 
x4           | 0 | 0       | 0       | 3    | 1  | -1 | 6            | 6 / 3 = 2 
x2           | 0 | 0       | 1       | -3/2 | 0  | 1/2 | 3            | 

Z            | 1 | 0       | 0       | 0    | 3/2 | M+1 | 36          | 
x1           | 0 | 1       | 0       | 0    | -1/3 | 1/3 | 2            | 
x3           | 0 | 0       | 0       | 1    | 1/3 | -1/3 | 2            | 
x2           | 0 | 0       | 1       | 0    | 1/2 | 0  | 6            | Optimal

Minimierung mit der Simplex-Methode

Eine direkte Möglichkeit, Z mit der Simplex-Methode zu minimieren, besteht darin, die Rolle der positiven und negativen Koeffizienten in der Zielfunktionszeile für den Optimalitätstest und den ersten Teil einer Iteration zu ändern. Bestimmen Sie die eintretende Basisvariable, indem Sie die Variable mit dem kleinsten positiven Koeffizienten in der Z-Gleichung wählen. Die aktuelle zulässige Basislösung ist optimal, wenn und nur wenn alle Koeffizienten der Zielfunktionsgleichung (Z-Zeile) nicht-negativ (≥ 0) sind. Wenn ja, endet der Prozess; andernfalls wird eine weitere Iteration durchgeführt, um eine neue zulässige Basislösung zu finden, die den Austausch einer Nicht-Basisvariablen gegen eine Basisvariable (als Teil 1 bezeichnet) und die Aktualisierung der Variablen der neuen Lösung (als Teil 2 bezeichnet) beinhaltet. Beachten Sie, dass nichts darüber gesagt wurde, wie die verlassende Basisvariable in einer Iteration ermittelt wird, da dieser Schritt auf die gleiche Weise durchgeführt wird wie bei der Maximierung, d.h. die Basisvariable mit dem niedrigsten Verhältnis wird gewählt. Veranschaulichen wir, wie die Simplex-Methode im Minimierungsfall verwendet wird.

Betrachten Sie das folgende Beispiel:

Minimiere Z = 3x₁ + 8x₂

unter den Nebenbedingungen:

• x₁ + 4x₂ ≤ 4
• x₁ + 2x₂ ≥ 2

x₁ ≥ 0, x₂ ≥ 0

Wenn wir dieses Problem entsprechend umwandeln und die erforderlichen Variablen hinzufügen, erhalten wir die Gleichungen:

Minimiere Z

unter den Nebenbedingungen:

Z - 3x₁ - 8x₂ - Mx₅ = 0

x₁ + 4x₂ + x₃ = 4

x₁ + 2x₂ - x₄ + x₅ = 2

x_j ≥ 0 für j = 1, 2, 5

Mit der M-Methode zur optimalen Lösung durch die Simplex-Methode erhalten wir die folgenden Tabellen:

Tabelle 4: Simplex-Iterationen für Minimierung

Basisvariable | Z | x1 | x2 | x3 | x4 | x5 | Rechte Seite | Verhältnis 
-------------------------------------------------------------------------- 
Z            | 1 | -3 | -8 | 0  | 0  | M  | 0            | 
x3           | 0 | 1  | 4  | 1  | 0  | 0  | 4            | 
x5           | 0 | 1  | 2  | 0  | -1 | 1  | 2            | 

Z            | 1 | M-3 | 2M-8 | 0  | -M | 0  | 2M           | 
x3           | 0 | 1   | 4    | 1  | 0  | 0  | 4            | 4 / 1 = 4 
x5           | 0 | 1   | 2    | 0  | -1 | 1  | 2            | 2 / 1 = 2 

Z            | 1 | 0   | -2   | 0  | -3 | M  | 6            | 
x3           | 0 | 0   | 2    | 1  | 1  | -1 | 2            | 
x1           | 0 | 1   | 2    | 0  | -1 | 1  | 2            | Optimal

Beachten Sie, dass die erste Tabelle nicht in der richtigen Form für die Simplex-Methode war, da der Koeffizient der Basisvariablen x₅ in der Z-Zeile -M war, was die Simplex-Bedingung nicht erfüllt.

Die Zwei-Phasen-Methode

Im Beispiel mit den funktionalen Beschränkungen der Form ≥ war die eigentliche Zielfunktion:

Reales Problem: Minimiere Z = 0.4x₁ + 0.5x₂

Die M-Methode verwendet jedoch während des gesamten Verfahrens die folgende Zielfunktion:

M-Methode: Minimiere Z = 0.4x₁ + 0.5x₂ + Mx₄ + Mx₆

Da die ersten beiden Koeffizienten (0.4 und 0.5) im Vergleich zu M vernachlässigbar sind, kann die Zwei-Phasen-Methode die M-Methode durch die folgenden zwei Zielfunktionen ersetzen, die Z ganz anders definieren:

Phasen der Zwei-Phasen-Methode

• Phase 1: Minimiere Z = x₄ + x₆ (bis x₄ = 0 und x₆ = 0).
• Phase 2: Minimiere Z = 0.4x₁ + 0.5x₂ (mit x₄ = 0 und x₆ = 0).

Die Zielfunktion der Phase 1 wird berechnet, indem die Zielfunktion der M-Methode von M durch die Eliminierung vernachlässigbarer Terme abgeleitet wird. Mit anderen Worten: Phase 1 umfasst die Minimierung der Summe aller in das Problem eingeführten künstlichen Variablen. Da Phase 1 eine zulässige Basislösung für das eigentliche Problem liefert (eine, bei der x₄ = 0 und x₆ = 0), dient diese Lösung als erste zulässige Basislösung, die in Phase 2 zur Anwendung der Simplex-Methode auf das eigentliche Problem (mit der ursprünglichen Zielfunktion) verwendet wird. Bevor wir das Beispiel auf diese Weise lösen, geben wir eine Zusammenfassung der allgemeinen Merkmale.

Zusammenfassung der Zwei-Phasen-Methode

1. Erster Schritt: Die Beschränkungen des ursprünglichen Problems werden durch die Einführung künstlicher Variablen so angepasst, dass eine erste offensichtlich zulässige Basislösung für das künstliche Problem erhalten wird.
2. Phase 1: Lösen Sie das lineare Programmierproblem mit der Simplex-Methode:
   Minimiere Z = Summe aller künstlichen Variablen, unter den überarbeiteten Beschränkungen.
   Die optimale Lösung für dieses Problem (mit Z = 0) liefert eine zulässige Basislösung für das eigentliche Problem.
3. Phase 2: Die künstlichen Variablen werden eliminiert (die übrigens jetzt alle Null sind). Beginnend mit der am Ende von Phase 1 erhaltenen zulässigen Basislösung wird die Simplex-Methode angewendet, um das eigentliche Problem zu lösen.

Wir fassen die Probleme zusammen, die die Simplex-Methode in den jeweiligen Phasen löst:

Problem für Phase 1

Minimiere W = x₄ + x₆

unter den Nebenbedingungen:

• 0.3x₁ + 0.1x₂ + x₃ = 2.7
• 0.5x₁ + 0.5x₂ + x₄ = 6
• 0.6x₁ + 0.4x₂ - x₅ + x₆ = 6

und x₁, x₂, x₃, x₄, x₅, x₆ ≥ 0

Problem für Phase 2

Minimiere Z = 0.4x₁ + 0.5x₂

unter den Nebenbedingungen:

• 0.3x₁ + 0.1x₂ + x₃ = 2.7
• 0.5x₁ + 0.5x₂ = 6
• 0.6x₁ + 0.4x₂ - x₅ = 6

und x₁, x₂, x₃, x₅ ≥ 0

Der einzige Unterschied zwischen diesen beiden Problemen liegt in der Zielfunktion und der Einbeziehung (Phase 1) oder dem Ausschluss (Phase 2) der künstlichen Variablen x₄ und x₆. Ohne die künstlichen Variablen hat das Problem für Phase 2 keine offensichtliche erste zulässige Basislösung. Der einzige Zweck der Lösung des Problems für Phase 1 ist es, eine zulässige Basislösung mit x₄ = 0 und x₆ = 0 zu erhalten, die als erste zulässige Basislösung für Phase 2 dienen kann.

Die folgenden Tabellen zeigen das Ergebnis der Anwendung der Simplex-Methode auf dieses Problem für Phase 1:

Tabelle 5: Simplex-Iterationen für Phase 1

Basisvariable | W | x1   | x2   | x3 | x4 | x5 | x6 | Rechte Seite | Verhältnis 
-------------------------------------------------------------------------------- 
W            | 1 | 0    | 0    | 0  | -1 | 0  | -1 | 0            | 
x3           | 0 | 0.3  | 0.1  | 1  | 0  | 0  | 0  | 2.7          | 
x4           | 0 | 0.5  | 0.5  | 0  | 1  | 0  | 0  | 6            | 
x6           | 0 | 0.6  | 0.4  | 0  | 0  | -1 | 1  | 6            | 

W            | 1 | 1.1  | 0.9  | 0  | 0  | -1 | 0  | 12           | 
x3           | 0 | 0.3  | 0.1  | 1  | 0  | 0  | 0  | 2.7          | 2.7/0.3 = 9 
x4           | 0 | 0.5  | 0.5  | 0  | 1  | 0  | 0  | 6            | 6/0.5 = 12 
x6           | 0 | 0.6  | 0.4  | 0  | 0  | -1 | 1  | 6            | 6/0.6 = 10 

W            | 1 | 0    | 0.53 | -3.66 | 0 | -1 | 0 | 2.1          | 
x1           | 0 | 1    | 0.33 | 3.33 | 0 | 0  | 0 | 9            | 9/0.33 = 27.2 
x4           | 0 | 0    | 0.33 | -1.66 | 1 | 0  | 0 | 1.5          | 1.5/0.33 = 4.5 
x6           | 0 | 0    | 0.2  | -2   | 0 | -1 | 1 | 0.6          | 0.6/0.2 = 3 

W            | 1 | 0    | 0    | 1.64 | 0 | 1.65 | -2.65 | 0.51         | 
x1           | 0 | 1    | 0    | 6.63 | 0 | 1.65 | -1.65 | 8.01         | 8.01/1.65 = 4.8 
x4           | 0 | 0    | 0    | 1.64 | 1 | 1.65 | -1.65 | 0.51         | 0.51/1.65 = 0.30 
x2           | 0 | 0    | 1    | -10  | 0 | -5   | 5   | 3            | 

W            | 1 | 0    | 0    | 0    | -1 | 0  | -1 | 0            | 
x1           | 0 | 1    | 0    | 5    | -1 | 0  | 0  | 7.5          | 
x5           | 0 | 0    | 0    | 0.99 | 0.60 | 1  | -1 | 0.3          | 
x2           | 0 | 0    | 1    | -5.05 | 3 | 0  | 0  | 4.5          | Optimal Phase 1

Beachten Sie, dass wir eine optimale Lösung für Phase 1 erhalten haben, die in der Minimierung der Summe aller künstlichen Variablen bestand. Beachten Sie auch, dass die Zielfunktion W in der letzten Tabelle einen Nullwert aufwies, was darauf hindeutet, dass die beiden Hilfsvariablen (x₄, x₆) null sind oder sich gegenseitig aufheben, um Null zu ergeben. In unserem Fall sind die beiden künstlichen Variablen Null, weil sie in der letzten Tabelle der ersten Phase nicht in der Spalte der Basisvariablen erscheinen. Die zweite Phase besteht darin, das ursprüngliche Problem zu lösen, wobei die letzte Tabelle der ersten Phase als erste Tabelle dieser Phase dient, jedoch ohne Berücksichtigung der Spalten der künstlichen Variablen, da diese in der ersten Phase den Wert Null haben. Die Anwendung der Simplex-Methode auf die zweite Phase ist in den folgenden Tabellen dargestellt:

Tabelle 6: Simplex-Iterationen für Phase 2

Basisvariable | Z | x1   | x2   | x3    | x4 | x5 | x6 | Rechte Seite | Verhältnis 
-------------------------------------------------------------------------------- 
Z            | 1 | -0.4 | -0.5 | 0     | 0  | 0  | 0  | 0            | 
x1           | 0 | 1    | 0    | 5     | -1 | 0  | 0  | 7.5          | 
x5           | 0 | 0    | 0    | 0.99  | 0.60 | 1  | -1 | 0.3          | 
x2           | 0 | 0    | 1    | -5.05 | 3  | 0  | 0  | 4.5          | 

Z            | 1 | 0    | -0.5 | 2     | 0  | 0  | 0  | 3            | 
x1           | 0 | 1    | 0    | 5     | 0  | 0  | 0  | 7.5          | 
x5           | 0 | 0    | 0    | 0.99  | 1  | 0  | 0  | 0.3          | 
x2           | 0 | 0    | 1    | -5.05 | 0  | 0  | 0  | 4.5          | 

Z            | 1 | 0    | 0    | -0.52 | 0  | 0  | 0  | 5.25         | 
x1           | 0 | 1    | 0    | 5     | 0  | 0  | 0  | 7.5          | 
x5           | 0 | 0    | 0    | 0.99  | 1  | 0  | 0  | 0.3          | 
x2           | 0 | 0    | 1    | -5.05 | 0  | 0  | 0  | 4.5          | Optimal Phase 2

Beachten Sie, dass es nicht immer notwendig ist, die Simplex-Methode auf die erste Tabelle der zweiten Phase anzuwenden, da manchmal allein die Anwendung von Matrixoperationen, um die Tabelle in die geeignete Form für die Simplex-Methode zu bringen, ausreicht, um das Problem in der zweiten Phase zu lösen. Es ist jedoch wichtig zu beachten, dass dies nicht immer der Fall ist; wenn nach der Umwandlung der Tabelle in die entsprechende Form weitere Schritte erforderlich sind, muss die Simplex-Methode wie gelernt angewendet werden.

Hinweis: Unabhängig davon, ob die ursprüngliche Aufgabe (das reale Problem) eine Maximierung oder Minimierung ist, besteht der erste Schritt immer in der Minimierung der Summe aller künstlichen Variablen.