Wir gehen von einem linearen Optimierungsproblem in Normalform aus. Mit und sei wieder
und es sei wie zuvor die zulässige Menge von . Die Spalten von bezeichnen wir mit , so dass
ist. Wir setzen hier grundsätzlich
- (5.1)
voraus, so dass Spalten von existieren, die linear unabhängig sind.
Für eine Teilmenge bezeichnen wir mit die Matrix, welche die Spalten besitzt, und mit den Vektor, der die Komponenten hat. Sind insbesondere und Indexmengen mit
und sind die Spalten von linear unabhängig (wegen (5.1) gibt es ja eine solche Menge ), so kann man eine Lösung des Systems gewinnen, indem man setzt und es gilt dann
- (5.2)
Diese Beobachtung führt zur Einführung der folgenden Begriffe.
- Es seien und Indexmengen mit
- und eine Teilmenge von linear unabhängigen Spalten von .
- (i) Dann bezeichnet man als Basisindexmenge und eine Lösung von mit als Basislösung von zur Basis . Wir schreiben für eine solche Basislösung auch und definieren für weiter:
- (ii) Die Komponenten von heißen Basisvariable und die Komponenten heißen Nichtbasisvariable.
- (iii) Die Basislösung heißt zulässig, wenn ist.
- (iv) Ist zulässige Basislösung, so heißt nichtausgeartet bzw. nichtdegeneriert, wenn ist und ausgeartet oder degeneriert im anderen Fall.
Ist eine nichtdegenerierte Basislösung von gegeben, so kann die zugehörige Basis durch die positiven Komponenten von identifiziert werden. Aus Lemma 4.6 und Bemerkung 4.7 gewinnen wir als nächstes die nachstehende Folgerung.
- Ein Vektor ist genau dann Ecke des Polyeders , wenn zulässige Basislösung von ist.
Zusammen mit den Sätzen 4.8 (i) und 4.14 liefert Korollar 5.2 den sog. Fundamentalsatz der linearen Optimierung:
- (i) Ist , so besitzt eine zulässige Basislösung.
- (ii) Besitzt das Problem eine Lösung, so hat es auch eine zulässige Basislösung, die optimal ist.
Anstelle von betrachten wir nun mit folgendes, leicht modifizierte Problem
- (5.3)
Mit meinen wir im folgenden die -te Spalte der -Einheitsmatrix.
- Man sagt, das LOP (5.3) liegt in kanonischer Form vor, falls mit bei fester Reihenfolge für gilt:
- (a) ,
- (b) .
- Ist die zu gehörige Basislösung zulässig, d. h. , so sagt man, dass das LOP (5.3) zulässige kanonische Form hat.
Seien und . Das Optimierungsproblem
hat die Normalform
Letzteres Problem hat kanonische Form mit Basislösung , welche im Fall zulässig ist.
Liegt ein LOP in zulässiger kanonischer Form mit zugehöriger Basislösung vor, so hat seine Zielfunktion in den Wert (man spricht auch von den aktuellen Kosten), denn
- (5.4)
Der im folgenden entwickelte Simplexalgorithmus zur Lösung von setzt sich aus zwei Phasen zusammen:
- In Phase I wird entweder festgestellt oder es wird ein zu äquivalentes Problem in zulässiger kanonischer Form mit Basislösung bestimmt. Dies wird erreicht, indem ein Hilfsproblem, welches zulässige kanonische Form hat und eine Lösung besitzt, mit Phase II des Simplexalgorithmus gelöst wird.
- In Phase II werden, ausgehend von einem Problem in zulässiger kanonischer Form mit Basislösung , mit äquivalente Probleme in zulässiger kanonischer Form mit Basislösungen erzeugt und zwar derart, dass der Zielfunktionswert von in kleiner oder gleich dem in ist. Es wird jeweils überprüft, ob Lösung von oder die Zielfunktion von unbeschränkt auf ist und gegebenenfalls abgebrochen.
Im folgenden beschreiben wir die Phase II des Simplexalgorithmus, wobei wir der Einfachheit halber den Index „“ für alle Größen der -ten Iteration weglassen und den der -ten Iteration durch ein hochgestelltes „“ ersetzen.
Phase II gehe also in der -ten Iteration von dem Problem
mit zulässigem Bereich aus, welches zulässige kanonische Form habe. Darin haben natürlich und dieselben Dimensionen wie die Größen gleicher Bezeichnung im zu lösenden Problem . (Man beachte, dass und in die entsprechenden Größen in der -ten Iteration sind.) O. B. d. A. sei dabei zunächst
und damit
wobei die -Einheitsmatrix ist. Dann lauten die in auftretenden Gleichungen zusammen mit der Zielfunktionsgleichung folgendermaßen ( wird hier als Variable aufgefasst):
- (5.5)
Wenn gilt, ist die aktuelle zulässige Basislösung auch optimal für , wie wir unten zeigen werden. Da das eigentlich zu lösende Problem unter der Voraussetzung (5.1) mit Problem , von dem die Phase II ausgeht und dieses wiederum mit äquivalent ist, wie unten gezeigt wird, gilt diese Aussage auch entsprechend für .
Wenn nicht optimal ist, gibt es mindestens einen Index , für den ist. Als nächstes untersucht man die -te Spalte as der aktuellen Koeffizientenmatrix. Ist , so muss, wie unten bewiesen wird, sein und bricht man das Verfahren ab. Im anderen Fall wählt man nach einer noch festzulegenden Regel ein Element in der Spalte aus. Die -te Spalte und die -te Zeile der aktuellen Koeffizientenmatrix bezeichnet man dann als Pivotspalte bzw. Pivotzeile und das Element als Pivotelement.
Nach Wahl des Pivotelements macht man einen sog. Austausch- oder Simplexschritt, der das obige System in ein äquivalentes System in zulässiger kanonischer Form mit Basisindexmenge
überführt. Dabei wird also die frühere Nichtbasisvariable neue Basisvariable und die frühere Basisvariable neue Nichtbasisvariable. Wie wir zeigen werden, erreicht man bei geeigneter Wahl der Pivotzeile , dass der Wert der Zielfunktion von in kleiner oder gleich dem in ist, also bzw., wie (5.4) zeigt, gilt.
Die Regeln für einen solchen Austauschschritt, der er an die Stelle der -ten Spalte von bringt, sind leicht anzugeben:
- man multipliziere die -te Gleichung des Systems mit (es ist ja ),
- man multipliziere anschließend die umgeformte -te Gleichung mit bzw. für mit und addiere sie zur Zielfunktionszeile bzw. zur -ten Gleichung des Systems .
Man erhält dann das Gleichungssystem
mit den neuen Koeffizienten für
- (5.6)
Die Zielfunktion von wird durch die angegebenen Operationen nur äquivalent umgeformt. Denn man hat für alle mit
- (5.7)
Damit kann der zur Basislösung gehörige Zielfunktionswert des neuen Problems „“ wiederum sofort abgelesen werden und beträgt (vgl. (5.4)).
Praktisch arbeitet man nicht mit dem vollständigen Gleichungssystem (5.5), sondern nur mit folgendem Tableau, wobei die rechte Seite des Gleichungssystems (5.5) meist als erste Spalte aufgeführt und die ursprüngliche erste Spalte nicht mit aufgenommen wird, da sie nie verändert wird:
Speicherplatz kann man dadurch gewinnen, dass man die zu den Basisvariablen gehörenden Spalten aus diesem Tableau streicht und die Indizes der Basis- bzw. Nichtbasisvariablen in einer Extraspalte bzw. -zeile mitführt:
Die zur neuen Nichtbasisvariablen gehörende Spalte ist dann im nächsten Tableau an die Stelle der zur alten Nichtbasisvariablen gehörenden Spalte einzutragen und „“ und „“ sind im Tableau zu vertauschen.
Die Austauschoperationen für und kann man auch in Matrixform schreiben.
- Es sei und mit . Dann gilt:
- (i) .
- (ii) ist nichtsingulär und
- (iii) .
(i) Es gilt
(ii) Offenbar ist
und somit
(iii) Es bezeichne die -te Zeile einer Matrix . Dann bekommt man mit (ii)
und daher mit (5.6)
Ferner hat man
q.e.d.
Wir geben nun eine Iteration der Phase II des Simplexverfahrens („Algorithmus 12“) an und rechtfertigen in dem daran anschließenden Satz insbesondere die im Zusammenhang mit den beiden Abbruchbedingungen gemachten Aussagen.
k-ter Iterationsschritt von Algorithmus 12
[Bearbeiten]
- (0) Gegeben sei das lineare Programm in zulässiger kanonischer Form mit und zulässiger Basislösung von .
- (1) Falls , stop! ( ist Lösung von und .)
- (2) Wähle mit , z. B. .
- (3) Falls , stop! (Es ist .)
- (4) Bestimme mit
- (5) Setze
- Berechne
- sowie
- und die neue zulässige Basislösung mit
- (6) Setze
- und gehe nach (1).
- Gegeben sei das lineare Programm in zulässiger kanonischer Form mit und zulässiger Basislösung von . Für den -ten Iterationsschritt von Algorithmus 12 gilt dann:
- (i) Ist , so ist für alle .
- (ii) Ist und für ein , so ist .
- (iii) Ist und das Pivotelement, so gilt:
- .
- für alle mit .
- ist eine zulässige Basislösung von .
- Die Aufgabe
- Minimiere auf
- ist äquivalent zur Aufgabe und liegt in zulässiger kanonischer Form mit Basisindexmenge vor.
- Es ist und . Ferner ist und im Fall sogar .
(i) Sei beliebig. Dann ist aufgrund der gemachten Voraussetzungen mit (5.4)
(ii) Für jedes definiere man einen Vektor durch
Insbesondere ist also nach unseren Voraussetzungen
Wegen ist und damit für alle . Ferner gilt nach Definition von und :
Also ist für alle . Wegen folgert man weiter
- für ,
so dass (ii) bewiesen ist.
(iii) Nach Lemma 5.6 (iii) hat man
Aussage ist bereits durch (5.7) gezeigt worden.
Wie man aus der Transformation ablesen kann, ist . Ferner ist aufgrund der Wahl der Pivotzeile im Simplexschnitt
- mit
und folglich wegen und
so dass gilt:
- (5.8)
Also ist eine zulässige Basislösung von .
Die Äquivalenz von und folgt unmittelbar aus und . Es ist
Demnach ist und wegen und für ferner für . Somit ist . Wie bereits oben bemerkt wurde, hat man außerdem .
Mit (5.4) sowie Aussagen und schließen wir zum einen
und zum anderen wegen
wobei und ist.
q.e.d.
Satz 5.7 zeigt, dass nur die Darstellungen der Zielfunktion und des zulässigen Bereichs des zu Beginn einer Iteration vorliegenden Problems durch einen Austauschschritt verändert werden, nicht aber diese selbst. Als Folge von Satz 5.7 kann man also „“ in den beiden Ausgängen (1) und (3) von Algorithmus 12 auch durch das Problem „“ ersetzen, von dem aus die Phase II startet und welches möglicherweise, wie im Fall von Beispiel 5.5, das tatsächlich zu lösende Problem ist. Geht man von einem Problem in Normalform aus und hat man die unten beschriebene Phase I des Simplexverfahrens durchlaufen, so kann man statt „“ dort auch „“ schreiben, da in Phase I mit Hilfe von Phase II in ein äquivalentes Problem in zulässiger kanonischer Form überführt wird, sofern nicht ist.
Die zulässigen Bereiche der Probleme und am Anfang und Ende eines Iterationsschrittes von Phase II des Simplexverfahrens sind also identisch. Ferner vergrößert sich beim Übergang von zu der neu berechneten zulässigen Basislösung der Zielfunktionswert von nicht (vgl. Satz 5.7 (iii) ). Im Fall, dass nichtentartet, d. h. ist, wird er echt verkleinert. Da es nur endlich viele zulässige Basislösungen eines linearen Gleichungssystems gibt und bei strikt monoton fallenden Zielfunktionswerten das Simplexverfahren nicht zu einer schon berechneten Basislösung zurückkehren kann, gelangt man zu der folgenden Aussage.
- Phase II des Simplexverfahrens (Algorithmus 12) gehe von einem Problem in zulässiger kanonischer Form aus. Sind alle durch die Phase II erzeugten Basislösungen nichtentartet, so bricht diese Phase nach endlich vielen Schritten entweder mit einer Lösung von oder mit der Information ab, dass die Zielfunktion des Problems auf dessen zulässigem Bereich unbeschränkt ist.
Ist jedoch entartet, so ist aufgrund des Auswahlkriteriums der Pivotzeile , damit (vgl. (5.6)) und folglich möglich. Gleichzeitig ist wegen des Auswahlkriteriums für die Pivotspalte in einem solchen Fall . Im entarteten Fall kann man also in einer zulässigen Basislösung bzw. einer Ecke hängen bleiben und nur die Basisdarstellung verändern. Kritisch wird es dann, wenn man nach endlich vielen Schritten wieder zur Ausgangsindexmenge gelangt. Man spricht dann von einem Zyklus, der, wenn er nicht erkannt würde, unendlich oft durchlaufen würde. Ein solcher Zyklus ist theoretisch möglich (siehe das Beispiel bei WERNER, S. 109), jedoch bei Verwendung eines Computers wegen der durch die endliche Zahlendarstellung bedingten Rechenungenauigkeiten eher unwahrscheinlich. Will man Zyklen aber auf jeden Fall ausschließen, so muss man eine Zusatzregel in die Phase II des Simplexalgorithmus einbauen. Eine solche wird im nächsten Unterabschnitt angegeben.
5.3 Das lexikographische Auswahlverfahren
[Bearbeiten]
- Ein Vektor heißt lexikographisch positiv (kurz: ), falls und die erste nicht verschwindende Komponente von positiv ist. Ein Vektor heißt lexikographisch größer als ein Vektor (kurz: ), wenn ist.
Die Relation „“ hat die üblichen Eigenschaften einer Ordnungsrelation. Insbesondere gilt daher für alle Vektoren :
- ,
- ,
- ,
- Für zwei Vektoren gilt oder oder .
. Dann ist und , also .
Eine endliche Menge paarweise verschiedener Vektoren aus dem besitzt offenbar ein eindeutiges lexikographisches Minimum , geschrieben
d. h. ein Element , so dass für alle gilt.
O. B. d. A. sei nun für das Startproblem der Phase II des Simplexalgorithmus und (gegebenenfalls nach einer Umsortierung der Spalten) das zugehörige zulässige kanonische Problem in ein Tableau der folgenden Form eingetragen:
- (5.9)
Weiter seien die Zeilen in diesem Tableau als Vektoren des aufgefasst:
Da wir von einem Problem in zulässiger kanonischer Form ausgehen, ist insbesondere und deshalb für das Startproblem
- (5.10)
Es lässt sich nun der folgende Satz beweisen, in dem und die Zeilen des aus (5.9) hervorgegangenen Tableaus in der -ten bzw. -ten Iteration kennzeichnen und dessen Voraussetzung offenbar für erfüllt ist. (Es muss nur für das Startproblem gelten.)
- Zu Beginn der -ten Iteration von Algorithmus 12 sei . Im Fall, dass kein Abbruch stattfindet, sei die Nummer der Pivotspalte und sei die Nummer der Pivotzeile nicht nach der in Schritt (4) angegebenen, sondern nach folgender Regel bestimmt:
- (5.11)
- Dann gilt:
- (i) ist eindeutig bestimmt,
- (ii) ,
- (iii) .
(i) Für mit kann
nicht gelten. Denn es gibt einen Spaltenindex (für das Startproblem ist ), für den , aber ist.
(ii) Nach den Umrechnungsregeln (5.6) gilt mit für die Zeilen des neuen Tableaus
- (5.12)
Wegen hat man also insbesondere . Ferner folgt aus (5.12) für alle mit wegen (5.10) auch . Schließlich liefert (5.12) für alle mit unter Verwendung von (5.11), dass
und damit ist.
(iii) Es ist
mit und . Somit erschließt man
- (5.13)
q.e.d.
Die ursprüngliche Auswahlregel für die Pivotzeile in Schritt (4) des oben angegebenen Austauschschritts ging nur in den Nachweis von ein (vgl. (5.8)). Da Aussage (ii) von Satz 5.11 ebenfalls impliziert (dies folgte vorher mit Satz 5.7 (iii) ), kann also auch alternativ die Regel (5.11) verwendet werden. Diese verhindert, dass man zu einer früheren Basis zurückkehrt. Denn bezeichnen wir die Zeilen des Tableaus in der -ten Iteration von Phase II mit , so liefert die Beziehung (5.13) mit einem und
und nach Summation für die Indizes mit
Da in Phase II des Simplexalgorithmus nur Vielfache von Zeilen zueinander addiert werden, kann jede Zeile des Tableaus im -ten Schritt und damit aller nachfolgenden Tableaus als Linearkombination der Zeilen im -ten beschrieben werden, so dass man mit gewissen weiter erhält:
Wären nun die Basislösungen und identisch und , so stünden an den Positionen von und Nullen und, hintereinander genommen, an den entsprechenden Positionen der unterschiedliche Spalten der Einheitsmatrix (die sind ja Spaltenvektoren). Letzteres implizierte und , was jedoch nach Aussage (iii) von Satz 5.11 nicht möglich ist.
Geht Phase II des Simplexverfahrens von einem Problem in zulässiger kanonischer Form aus und wird in jedem Schritt die Pivotzeile nach der Auswahlregel (5.11) bestimmt, so bricht also Phase II nach endlich vielen Schritten mit einer Lösung von bzw. mit dem Ausgang ab, dass die Zielfunktion des Problems auf dessen zulässigem Bereich unbeschränkt ist.
Eine weitere Regel, die zur Vermeidung von Zyklen vorgeschlagen wurde, ist Bland’s Regel, die z. B. bei LUENBERGER zu finden ist.
Nun kommen wir zur Phase I des Simplexalgorithmus. Sie geht von dem Optimierungsproblem in Normalform aus, also von
mit und . O. B. d. A. können wir annehmen, dass ist, da wir Gleichungen mit negativer rechter Seite mit multiplizieren können. Ziel der Phase I ist es, entweder festzustellen, dass
leer ist, oder Problem in eine äquivalente zulässige kanonische Form mit zugehöriger Basislösung zu überführen, von der aus die Phase II gestartet werden kann.
Man beginnt damit, dass man künstliche Variable einführt und die Aufgabe
betrachtet, welche sich mit und der -Einheitsmatrix in folgender Form schreiben lässt:
Offenbar gilt, dass die Zielfunktion von den Wert hat und der Vektor wegen zulässige Basislösung von ist. Nach Satz 4.13 besitzt Problem demnach eine Lösung . Ferner sieht man leicht ein, dass der optimale Zielfunktionswert von genau dann identisch Null ist, wenn ist.
Man schreibt jetzt die Zielfunktion von so um, dass man ein Problem in zulässiger kanonischer Form erhält. Für zulässige Punkte von gilt , so dass folgt:
- (5.15)
Daher ist äquivalent zu dem Problem
Letzteres Problem hat wegen zulässige kanonische Form mit zugehöriger Basislösung für und kann demnach mit Phase II des Simplexalgorithmus gelöst werden. Das entsprechende Ausgangstableau hat die folgende Gestalt, wenn man in die zweite Zeile zusätzlich die Koeffizienten der Zielfunktion von einträgt (wie unten deutlich wird, ist es zweckmäßig, die mit erweiterte Zielfunktion von selbst in Phase I mit umzuformen):
Phase II des Simplexalgorithmus liefere nun als Lösung von die zulässige Basislösung mit
Das zugehörige, mit äquivalente Problem in zulässiger kanonischer Form laute
Die Spalten der Matrix seien mit bezeichnet. Man beachte, dass mit Satz 5.8 insbesondere genau dann gilt, wenn ist und für damit genau dann, wenn richtig ist ( ist dann in beiden Fällen zulässig). Ferner hat man wegen (5.8) und (5.15)
Es sind jetzt drei Fälle zu betrachten:
- Dann ist, wie oben bereits bemerkt wurde, und das Verfahren mit einer entsprechenden Meldung abzubrechen.
- Dies ist der angenehme Fall. ist eine zulässige Basislösung von bzw. . Insbesondere gilt für und es stehen Nullen in den Spalten mit den Indizes der beiden ersten Zeilen des optimalen Tableaus, da dieses zu einem mit äquivalenten Problem in zulässiger kanonischer Form gehört und beide Zielfunktionszeilen parallel umgeformt wurden. Nachdem man im optimalen Tableau die erste Zeile und die letzten , zu den künstlichen Variablen gehörenden Spalten gestrichen hat (sie liefern offenbar keinen Beitrag), erhält man also ein Tableau, welches zu einem mit dem Problem äquivalenten Problem in zulässiger kanonischer Form gehört. Phase II des Simplexalgorithmus kann folglich sofort gestartet werden.
- Dann liefern zwar die künstlichen Variablen keinen Beitrag, aber für das Problem ist noch keine äquivalente zulässige kanonische Form gefunden worden. In diesem Fall streiche man im optimalen Tableau zuerst alle Spalten, die zu den künstlichen Variablen gehören, welche Nichtbasisvariable sind, d. h. alle Spalten mit Index . Weiter hat man wegen , dass für mit gilt, wobei die Spalte mit dem Index zur Variablen mit gehört. Ein solches sei nun frei gewählt. Es sind dann zwei Fälle zu unterscheiden:
- (a) .
- Dann wird durch die -te Gleichung den keine Restriktion aufgezwungen. Sie kann (auch im Ausgangssystem ) gestrichen werden. Offenbar ist gewesen. (In Phase I wird also auch festgestellt, ob die Rangbedingung erfüllt ist. Für das um die -te Gleichung reduzierte System ist jetzt gefordert!) Ferner streiche man auch die -te Spalte im Tableau.
- (b) für ein .
- Man wähle ein solches und mache einen Austauschschritt mit . Wegen muss hier nicht notwendig vorliegen, da impliziert, dass ist. (Die Wahl der Pivotzeile ging nur in den Beweis von Satz 5.8 (iii) und bzw. in Satz 5.12 zum Nachweis von ein.) Damit ist nun Nichtbasisvariable und die -te Spalte kann folglich aus dem Tableau gestrichen werden. Da optimal für ist, muss auch die neue Basislösung optimal für sein.
- Man führe den 3. Schritt nun solange durch, bis alle künstlichen Variablen aus der Basis entfernt sind und der 2. Fall eintritt.
Man beachte: sind unter den Spalten der Koeffizientenmatrix von mit Einheitsvektoren und sind die zugehörigen Koeffizienten der Zielfunktion identisch 0, so kommt man mit entsprechend weniger künstlichen Variablen aus. Dies ist die Situation bei folgendem Beispiel.
Gegeben sei das LOP
- (5.16)
Setzt man , führt man zwei Schlupfvariable und für die beiden ""-Ungleichungen ein und multipliziert man anschließend die so erhaltene zweite Gleichung mit , damit ihre rechte Seite positiv wird, so gelangt man mit zu folgendem LOP in Normalform:
- (5.17)
Das Problem hat nicht zulässige kanonische Form, so dass man Phase I des Simplexalgorithmus anwenden muss. Der Einheitsvektor ist jedoch als Spalte schon in der Restriktionsmatrix des Problems enthalten und der zugehörige Koeffizient der Zielfunktion ist identisch Null. (Diese Situation hat man offenbar z. B. immer dann, wenn man eine Schlupfvariable eingeführt hat und die rechte Seite in der ""-Ungleichung des Ausgangsproblems nichtnegativ war.) Also muss man nur noch für die zweite und dritte Restriktionsgleichung künstliche Variable einführen. Man kommt so zu folgendem Ausgangstableau für die Phase I, wobei man die Koeffizienten der ersten Zeile, welche nicht zu den beiden künstlichen Variablen gehören, als negative Summe der letzten beiden Zeilen (mit den künstlichen Variablen) errechnet:
Auf dieses (ohne die zweite Zeile) zu einem Problem in zulässiger kanonischer Form gehörende Tableau mit
wendet man nun die Phase II des Simplexalgorithmus an. Der Iterationsvorschrift in Abschnitt 5.2 entsprechend ermittelt man eine (hier eindeutige) kleinste Zahl unter den Zahlen in der obersten Zeile, welche zu Variablen mit Index aus gehören. Ist diese negativ wie hier, nämlich , so bestimmt sie die Pivotspalte. Gibt es weiter in der Pivotspalte positive Elemente (hier: 3 und 1), so hat man als nächstes die Pivotzeile zu bestimmen, indem man die in derselben Zeile stehenden Zahlen der ersten Spalte durch diese dividiert (hier bekommt man: und 4). Der kleinste dieser Werte (hier: ) charakterisiert die Pivotzeile und damit das Pivotelement (hier: ).
Die -te Zeile im folgenden Tableau erhält man nun, indem man die alte -te Zeile durch das Pivotelement dividiert. Die Werte in allen anderen Zeilen errechnet man nach den Regeln (5.7), wobei die zweite, zur Zielfunktion des Ausgangsproblems gehörende Zeile analog zur ersten mit umgerechnet wird. Das nächste Tableau lautet dann:
mit
Da die Phase II noch nicht abbricht, gelangt man bei analogem Vorgehen (die Pivotelemente sind jeweils gekennzeichnet) zu folgendem nächsten Tableau
mit
Weil es keine negative Zahl mehr unter den zu in der ersten Zielfunktionszeile stehenden Zahlen gibt, ist eine Lösung des (Hilfs-)Problems mit und gefunden. Der zugehörige optimale Zielfunktionswert, welcher mit negativem Vorzeichen in der ersten Spalte der ersten Zeile steht, ist . Da ferner ist, liegt der angenehme, oben beschriebene 2. Fall vor. Als Ausgangstableau für die Phase II erhält man nach Streichung der ersten Zeile und der letzten beiden Spalten folglich
Auch unter den zu gehörenden Zahlen der obersten Zeile dieses Tableaus kommen keine negativen Zahlen vor, so dass es bereits optimal für die Phase II ist. Als Lösung des Problems (5.17) bekommt man also
mit zugehörigem optimalen Zielfunktionswert . Folglich ist
mit demselben Zielfunktionswert Lösung von Problem (5.16).
Dieser Abschnitt dient im wesentlichen dazu zu zeigen, dass man aus dem letzten Tableau der Phase II des Simplexalgorithmus eine Lösung des zu dualen Problems ablesen kann. Er spielt ansonsten keine Rolle und kann daher gegebenenfalls übergangen werden.
Wir betrachten noch einmal das Problem (P') aus Abschnitt 5.2 und schreiben dies ähnlich wie (5.6), allerdings mit einer mit multiplizierten Zielfunktionszeile (anderenfalls bekommt man (5.20) nicht!) als System mit der Blockmatrix bzw. den Blockvektoren
Die Variable muss man hier mitführen, damit man unten z. B. eine vollständige Basis für erhält. und fassen wir in dem folgenden Tableau zusammen:
Ist eine Basis zu mit Basisindexmenge , so ist offenbar durch
eine Basis und Basisindexmenge zu gegeben. Insbesondere ist
ist invertierbar und, wie man leicht überprüft, ist
- (5.18)
(Man beachte, dass mit die Matrix gemeint ist. Da die Matrix nur für existiert und dann identisch mit ist, ist aber keine Verwechslung möglich.)
liege nun in zulässiger kanonischer Form mit Basisindexmenge vor, so dass Phase II gestartet werden kann. Bezeichnet im folgenden die -Einheitsmatrix, so ist also insbesondere und .
Es sei nun
- (5.19)
und ein hochgestelltes „“ kennzeichne im folgenden den Iterationsindex der Phase II. Insbesondere schreiben wir für
Nutzen wir aus, dass
ist (vgl. Lemma 5.6) und verwenden wir, dass die Regeln (5.7) für die neue Zielfunktionszeile
liefern (alle Komponenten von , bis auf die mit dem Index der im -ten Schritt gewählten Pivotspalte, sind Null!), so erhalten wir, wie man leicht verifiziert,
- (5.20)
wobei die Existenz von offenbar gesichert ist. Insbesondere ist also
so dass man mit
und (5.19) die Gleichungen
- (5.21)
erhält. Folglich ist
Da für die von uns vorgestellte Form des Simplexalgorithmus ist, impliziert die letztere Gleichung , so dass wir die Gleichungen (5.21) in der Form
- (5.22)
schreiben können. Man beachte, dass sich aus der Kenntnis der Basisindexmenge bzw. und der Ausgangsmatrix gemäß (5.18) berechnen lässt. Folglich kann man und und damit das -te Simplextableau
- (5.23)
vollständig mit durch die Ausgangsdaten beschreiben.
Das -te Simplextableau wollen wir noch vollständig ausschreiben. Dazu sortieren wir der Anschaulichkeit halber die Spalten der Anfangsdaten und in der -ten Iteration so um, dass
und damit