Benutzer:Stepri2005/Kurs:Optimierung/Der Simplexalgorithmus

5.1 Vorbereitungen

Wir gehen von einem linearen Optimierungsproblem in Normalform aus. Mit $A\in \mathbb {R} ^{m\times n},b\in \mathbb {R} ^{m}$ und $c\in \mathbb {R} ^{n}$ sei wieder

${\begin{array}{lll}(P):&{\text{Minimiere}}&c^{T}x\\&{\text{u. d. N.}}&Ax=b,\\&&x\geq 0\end{array}}$

und es sei wie zuvor $Z_{P}$ die zulässige Menge von $(P)$. Die Spalten von $A$ bezeichnen wir mit $a^{i}$, so dass

$A={\begin{pmatrix}a^{1}&\ldots &a^{n}\end{pmatrix}}$

ist. Wir setzen hier grundsätzlich

(5.1) $\operatorname {Rang} (A)=m$

voraus, so dass $m$ Spalten von $A$ existieren, die linear unabhängig sind.

Für eine Teilmenge $K\subseteq \{1,\ldots ,n\}$ bezeichnen wir mit $A_{K}$ die Matrix, welche die Spalten $a^{j}$ $(j\in K)$ besitzt, und mit $x_{K}$ den Vektor, der die Komponenten $x_{j}$ $(j\in K)$ hat. Sind insbesondere $J$ und $N$ Indexmengen mit

$J\subseteq \{1,\ldots ,n\},\quad |J|=m,\qquad N:=\{1,\ldots ,n\}\setminus J$

und sind die $m$ Spalten $a^{j}$ $(j\in J)$ von $A$ linear unabhängig (wegen (5.1) gibt es ja eine solche Menge $J$), so kann man eine Lösung ${\hat {x}}$ des Systems $Ax=b$ gewinnen, indem man ${\hat {x}}_{N}=0$ setzt und es gilt dann

(5.2) $b=A{\hat {x}}=A_{J}{\hat {x}}_{J}+A_{N}{\hat {x}}_{N}=A_{J}{\hat {x}}_{J}\Leftrightarrow {\hat {x}}_{J}=(A_{J})^{-1}b.$

Diese Beobachtung führt zur Einführung der folgenden Begriffe.

Definition 5.1

Es seien $J$ und $N$ Indexmengen mit

$J\subseteq \{1,\ldots ,n\},\quad |J|=m,\qquad N:=\{1,\ldots ,n\}\setminus J$

und $\{a^{j}\}_{j\in J}$ eine Teilmenge von $m$ linear unabhängigen Spalten von $A$.

(i) Dann bezeichnet man $J$ als Basisindexmenge und eine Lösung ${\hat {x}}$ von $Ax=b$ mit ${\hat {x}}_{N}=0$ als Basislösung von $Ax=b$ zur Basis $\{a^{j}\}_{j\in J}$. Wir schreiben für eine solche Basislösung auch $({\hat {x}},J)$ und definieren für $({\hat {x}},J)$ weiter:

(ii) Die Komponenten ${\hat {x}}_{j}$ $(j\in J)$ von ${\hat {x}}$ heißen Basisvariable und die Komponenten ${\hat {x}}_{j}$ $(j\in N)$ heißen Nichtbasisvariable.

(iii) Die Basislösung ${\hat {x}}$ heißt zulässig, wenn ${\hat {x}}\geq 0$ ist.

(iv) Ist ${\hat {x}}$ zulässige Basislösung, so heißt ${\hat {x}}$ nichtausgeartet bzw. nichtdegeneriert, wenn ${\hat {x}}_{J}>0$ ist und ausgeartet oder degeneriert im anderen Fall.

Ist eine nichtdegenerierte Basislösung ${\hat {x}}$ von $Ax=b$ gegeben, so kann die zugehörige Basis durch die positiven Komponenten von ${\hat {x}}$ identifiziert werden. Aus Lemma 4.6 und Bemerkung 4.7 gewinnen wir als nächstes die nachstehende Folgerung.

Korollar 5.2

Ein Vektor ${\hat {x}}$ ist genau dann Ecke des Polyeders $Z_{P}$, wenn ${\hat {x}}$ zulässige Basislösung von $Ax=b$ ist.

Zusammen mit den Sätzen 4.8 (i) und 4.14 liefert Korollar 5.2 den sog. Fundamentalsatz der linearen Optimierung:

Korollar 5.3

(i) Ist $Z_{P}\neq \emptyset$, so besitzt $(P)$ eine zulässige Basislösung.

(ii) Besitzt das Problem $(P)$ eine Lösung, so hat es auch eine zulässige Basislösung, die optimal ist.

Anstelle von $(P)$ betrachten wir nun mit $c_{0}\in \mathbb {R}$ folgendes, leicht modifizierte Problem

(5.3) ${\begin{array}{ll}{\text{Minimiere}}&f(x):=c^{T}x+c_{0}\\{\text{u. d. N.}}&Ax=b,\\&x\geq 0.\end{array}}$

Mit $e^{k}$ meinen wir im folgenden die $k$-te Spalte der $(m\times m)$-Einheitsmatrix.

Definition 5.4

Man sagt, das LOP (5.3) liegt in kanonischer Form vor, falls mit $J:=\{j_{1},\ldots ,j_{m}\}$ bei fester Reihenfolge für $j_{1},\ldots ,j_{m}$ gilt:

(a) $a^{j_{k}}=e^{k}\quad (k=1,\ldots ,m)$,

(b) $c_{j}=0\quad (j\in J)$.

Ist die zu $\{a^{j}\}_{j\in J}$ gehörige Basislösung $({\hat {x}},J)$ zulässig, d. h. ${\hat {x}}_{J}=b\geq 0$, so sagt man, dass das LOP (5.3) zulässige kanonische Form hat.

Beispiel 5.5

Seien $A\in \mathbb {R} ^{m\times n},b\in \mathbb {R} ^{m}$ und $y\in \mathbb {R} ^{n}$. Das Optimierungsproblem

${\begin{array}{ll}{\text{Minimiere}}&c^{T}y\\{\text{u. d. N.}}&Ay\leq b,\\&y\geq 0\end{array}}$

hat die Normalform

${\begin{array}{ll}{\text{Minimiere}}&(c,0)^{T}(y,z)\\{\text{u. d. N.}}&{\begin{pmatrix}A&I\end{pmatrix}}(y,z)=b,\\&(y,z)\geq 0.\end{array}}$

Letzteres Problem hat kanonische Form mit Basislösung $(z,\{n+1,\ldots ,n+m\})$, welche im Fall $b\geq 0$ zulässig ist.

---

Liegt ein LOP in zulässiger kanonischer Form mit zugehöriger Basislösung $({\hat {x}},J)$ vor, so hat seine Zielfunktion $f(x):=c^{T}x+c_{0}$ in ${\hat {x}}$ den Wert $f({\hat {x}})=c_{0}$ (man spricht auch von den aktuellen Kosten), denn

(5.4) $f({\hat {x}})=c^{T}{\hat {x}}+c_{0}=\underbrace {c_{J}^{T}} _{=0}{\hat {x}}_{J}+c_{N}^{T}\underbrace {{\hat {x}}_{N}} _{=0}+c_{0}=c_{0}.$

Der im folgenden entwickelte Simplexalgorithmus zur Lösung von $(P)$ setzt sich aus zwei Phasen zusammen:

• In Phase I wird entweder $Z_{P}=\emptyset$ festgestellt oder es wird ein zu $(P)$ äquivalentes Problem $(P^{0})$ in zulässiger kanonischer Form mit Basislösung $(x^{0},J_{0})$ 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 $(P^{0})$ in zulässiger kanonischer Form mit Basislösung $(x^{0},J_{0})$, mit $(P^{0})$ äquivalente Probleme $(P^{k})$ in zulässiger kanonischer Form mit Basislösungen $(x^{k},J_{k}),k=1,2,\ldots$ erzeugt und zwar derart, dass der Zielfunktionswert von $(P^{0})$ in $x^{k+1}$ kleiner oder gleich dem in $x^{k}$ ist. Es wird jeweils überprüft, ob $x^{k}$ Lösung von $(P^{0})$ oder die Zielfunktion von $(P^{0})$ unbeschränkt auf $Z_{P}$ ist und gegebenenfalls abgebrochen.

5.2 Phase II des Simplexalgorithmus

Im folgenden beschreiben wir die Phase II des Simplexalgorithmus, wobei wir der Einfachheit halber den Index „$k$“ für alle Größen der $k$-ten Iteration weglassen und den der $(k+1)$-ten Iteration durch ein hochgestelltes „$+$“ ersetzen.

Phase II gehe also in der $k$-ten Iteration von dem Problem

${\begin{array}{lll}(P'):&{\text{Minimiere}}&f(x):=c^{T}x+c_{0}\\&{\text{u. d. N.}}&Ax=b,\\&&x\geq 0\end{array}}$

mit zulässigem Bereich $Z_{P'}$ aus, welches zulässige kanonische Form habe. Darin haben natürlich $c,A$ und $b$ dieselben Dimensionen wie die Größen gleicher Bezeichnung im zu lösenden Problem $(P)$. (Man beachte, dass $c,c_{0},A$ und $b$ in $(P')$ die entsprechenden Größen in der $k$-ten Iteration sind.) O. B. d. A. sei dabei zunächst

$J:=\{1,\ldots ,m\},\quad N:=\{m+1,\ldots ,n\}$

und damit

$A_{J}={\begin{pmatrix}e^{1}&\ldots &e^{m}\end{pmatrix}}=I,\quad c_{J}=0,\quad c_{N}=(c_{m+1},\ldots ,c_{n})^{T},\quad {\hat {x}}_{J}=b\geq 0,$

wobei $I$ die $(m\times m)$-Einheitsmatrix ist. Dann lauten die in $(P')$ auftretenden Gleichungen zusammen mit der Zielfunktionsgleichung $w:=f(x)=c^{T}x+c_{0}$ folgendermaßen ($w$ wird hier als Variable aufgefasst):

(5.5) ${\begin{pmatrix}-w+&&&&&&c_{m+1}x_{m+1}&+\ldots +&c_{s}x_{s}&+\ldots +&c_{n}x_{n}&=&-c_{0},\\&x_{1}+&&&&&a_{1,m+1}x_{m+1}&+\ldots +&a_{1,s}x_{s}&+\ldots +&a_{1,n}x_{n}&=&b_{1},\\&&\ddots &&&&\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \\&&&x_{r}+&&&a_{r,m+1}x_{m+1}&+\ldots +&a_{r,s}x_{s}&+\ldots +&a_{r,n}x_{n}&=&b_{r},\\&&&&\ddots &&\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \\&&&&&x_{m}&a_{m,m+1}x_{m+1}&+\ldots +&a_{m,s}x_{s}&+\ldots +&a_{m,n}x_{n}&=&b_{m}.\end{pmatrix}}$

Wenn $c_{N}\geq 0$ gilt, ist die aktuelle zulässige Basislösung ${\hat {x}}$ auch optimal für $(P')$, wie wir unten zeigen werden. Da das eigentlich zu lösende Problem $(P)$ unter der Voraussetzung (5.1) mit Problem $(P^{0})$, von dem die Phase II ausgeht und dieses wiederum mit $(P')$ äquivalent ist, wie unten gezeigt wird, gilt diese Aussage auch entsprechend für $(P)$.

Wenn ${\hat {x}}$ nicht optimal ist, gibt es mindestens einen Index $s\in N$, für den $c_{s}<0$ ist. Als nächstes untersucht man die $s$-te Spalte as der aktuellen Koeffizientenmatrix. Ist $a^{s}\leq 0$, so muss, wie unten bewiesen wird, $\inf _{x\in Z_{P'}}f(x)=-\infty$ sein und bricht man das Verfahren ab. Im anderen Fall wählt man nach einer noch festzulegenden Regel ein Element $a_{r,s}>0$ in der Spalte $a^{s}$ aus. Die $s$-te Spalte und die $r$-te Zeile der aktuellen Koeffizientenmatrix bezeichnet man dann als Pivotspalte bzw. Pivotzeile und das Element $a_{r,s}$ 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

$J^{+}:=\{1,\ldots ,r-1,\overbrace {s} ^{r{\text{-te Stelle}}},r+1,\ldots ,m\}$

überführt. Dabei wird also die frühere Nichtbasisvariable ${\hat {x}}_{s}$ neue Basisvariable und die frühere Basisvariable ${\hat {x}}_{r}$ neue Nichtbasisvariable. Wie wir zeigen werden, erreicht man bei geeigneter Wahl der Pivotzeile $r$, dass der Wert der Zielfunktion von $(P')$ in ${\hat {x}}^{+}$ kleiner oder gleich dem in ${\hat {x}}$ ist, also $f({\hat {x}}^{+})\leq f({\hat {x}})$ bzw., wie (5.4) zeigt, $c_{0}^{+}\leq c_{0}$ gilt.

Die Regeln für einen solchen Austauschschritt, der er an die Stelle der $s$-ten Spalte von $A$ bringt, sind leicht anzugeben:

• man multipliziere die $r$-te Gleichung des Systems $Ax=b$ mit $1/a_{r,s}$ (es ist ja $a_{r,s}\neq 0$),
• man multipliziere anschließend die umgeformte $r$-te Gleichung mit $-c_{s}$ bzw. für $1\leq i\leq m,i\neq r$ mit $-a_{i,s}$ und addiere sie zur Zielfunktionszeile bzw. zur $i$-ten Gleichung des Systems $Ax=b$.

Man erhält dann das Gleichungssystem

${\begin{pmatrix}-w+&&&c_{r}^{+}x_{r}+&&&c_{m+1}^{+}x_{m+1}&+\ldots +&0\cdot x_{s}&+\ldots +&c_{n}^{+}x_{n}&=&-c_{0}^{+}\\&x_{1}+&&a_{1,r}^{+}x_{r}+&&&a_{1,m+1}^{+}x_{m+1}&+\ldots +&0\cdot x_{s}&+\ldots +&a_{1,n}^{+}x_{n}&=&b_{1}^{+}\\&&\ddots &\vdots &&&\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \\&&&a_{r,r}^{+}x_{r}+&&&a_{r,m+1}^{+}x_{m+1}&+\ldots +&1\cdot x_{s}&+\ldots +&a_{r,n}^{+}x_{n}&=&b_{r}^{+}\\&&&\vdots &\ddots &&\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \\&&&a_{m,r}^{+}x_{r}+&&x_{m}+&a_{m,m+1}^{+}x_{m+1}&+\ldots +&0\cdot x_{s}&+\ldots +&a_{m,n}^{+}x_{n}&=&b_{m}^{+}\end{pmatrix}}$

mit den neuen Koeffizienten für $j=1,\ldots ,n$

(5.6) $a_{r,j}^{+}:={\frac {a_{r,j}}{a_{r,s}}},\quad b_{r}^{+}:={\frac {b_{r}}{a_{r,s}}},\quad c_{j}^{+}:=c_{j}-c_{s}a_{r,j}^{+},\quad -c_{0}^{+}:=-c_{0}-c_{s}b_{r}^{+},$

$a_{i,j}^{+}:=a_{i,j}-a_{i,s}a_{r,j}^{+},\quad b_{i}^{+}:=b_{i}-a_{i,s}b_{r}^{+},\qquad i=1,\ldots ,m,\quad i\neq r.$

Die Zielfunktion von $(P')$ wird durch die angegebenen Operationen nur äquivalent umgeformt. Denn man hat für alle $x$ mit $Ax=b$

$\left(c^{+}\right)^{T}x+c_{0}^{+}=\sum _{j=1}^{n}\left(c_{j}-c_{s}a_{r,j}^{+}\right)x_{j}+\left(c_{0}+c_{s}b_{r}^{+}\right)=\left(c^{T}x+c_{0}\right)+c_{s}\left(b_{r}^{+}-\sum _{j=1}^{n}a_{r,j}^{+}x_{j}\right)$

(5.7) $=\left(c^{T}x+c_{0}\right)+{\frac {c_{s}}{a_{r,s}}}\underbrace {\left(b_{r}-\sum _{j=1}^{n}a_{r,j}x_{j}\right)} _{=0}=c^{T}x+c_{0}=f(x).$

Damit kann der zur Basislösung $({\hat {x}}^{+},J^{+})$ gehörige Zielfunktionswert des neuen Problems „$(P^{+})$“ wiederum sofort abgelesen werden und beträgt $f({\hat {x}}^{+})=c_{0}^{+}$ (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:

${\begin{array}{c|ccccccccccc}-c_{0}&0&0&\cdots &0&\cdots &0&c_{m+1}&\cdots &c_{s}&\cdots &c_{n}\\\hline b_{1}&1&0&\cdots &0&\cdots &0&a_{1,m+1}&\cdots &a_{1,s}&\cdots &a_{1,n}\\b_{2}&0&1&\cdots &0&\cdots &0&a_{2,m+1}&\cdots &a_{2,s}&\cdots &a_{2,n}\\\vdots &\vdots &\vdots &&\vdots &&\vdots &\vdots &&\vdots &&\vdots \\b_{r}&0&0&\cdots &1&\cdots &0&a_{r,m+1}&\cdots &a_{r,s}&\cdots &a_{r,n}\\\vdots &\vdots &\vdots &&\vdots &&\vdots &\vdots &&\vdots &&\vdots \\b_{m}&0&0&\cdots &0&\cdots &1&a_{m,m+1}&\cdots &a_{m,s}&\cdots &a_{m,n}\end{array}}$

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:

${\begin{array}{cc|ccccc}&&m+1&\cdots &s&\cdots &n\\&-c_{0}&c_{m+1}&\cdots &c_{s}&\cdots &c_{n}\\\hline 1&b_{1}&a_{1,m+1}&\cdots &a_{1,s}&\cdots &a_{1,n}\\2&b_{2}&a_{2,m+1}&\cdots &a_{2,s}&\cdots &a_{2,n}\\\vdots &\vdots &\vdots &&\vdots &&\vdots \\r&b_{r}&a_{r,m+1}&\cdots &a_{r,s}&\cdots &a_{r,n}\\\vdots &\vdots &\vdots &&\vdots &&\vdots \\m&b_{m}&a_{m,m+1}&\cdots &a_{m,s}&\cdots &a_{m,n}\end{array}}$

Die zur neuen Nichtbasisvariablen ${\hat {x}}_{r}^{+}$ gehörende Spalte ist dann im nächsten Tableau an die Stelle der zur alten Nichtbasisvariablen $x_{s}$ gehörenden Spalte einzutragen und „$r$“ und „$s$“ sind im Tableau zu vertauschen.

Die Austauschoperationen für $A$ und $b$ kann man auch in Matrixform schreiben.

Lemma 5.6

Es sei $a_{r,s}\neq 0$ und $J^{+}=\{j_{1},\ldots ,j_{r-1},s,j_{r+1},\ldots ,j_{m}\}$ mit $s\in N$. Dann gilt:

(i) $A_{J^{+}}=I+(a^{s}-e^{r})(e^{r})^{T}$.

(ii) $A_{J^{+}}$ ist nichtsingulär und

$A_{J^{+}}^{-1}=I-{\frac {1}{a_{r,s}}}(a^{s}-e^{r})(e^{r})^{T}.$

(iii) $A^{+}=A_{J^{+}}^{-1}A,\quad b^{+}=A_{J^{+}}^{-1}b$.

Beweis.

(i) Es gilt

$A_{J^{+}}={\begin{pmatrix}a^{j_{1}}&\ldots &a^{j_{r-1}}&a^{s}&a^{j_{r+1}}&\ldots &a^{j_{m}}\end{pmatrix}}={\begin{pmatrix}e^{1}&\ldots &e^{r-1}&a^{s}&e^{r+1}&\ldots &e^{m}\end{pmatrix}}$

$=I+{\begin{pmatrix}0&\ldots &0&a^{s}-e^{r}&0&\ldots &0\end{pmatrix}}=I+(a^{s}-e^{r})(e^{r})^{T}.$

(ii) Offenbar ist

$|\det(A_{J^{+}})|=\left|\det {\begin{pmatrix}e^{1}&\ldots &e^{r-1}&a^{s}&e^{r+1}&\ldots &e^{m}\end{pmatrix}}\right|=|a_{r,s}|\neq 0$

und somit $A_{J^{+}}invertierbar.Fernergilt::<math>{\Bigl (}I+(a^{s}-e^{r})(e^{r})^{T}{\Bigr )}\left(I-{\frac {1}{a_{r,s}}}(a^{s}-e^{r})(e^{r})^{T}\right)$

$=I+(a^{s}-e^{r})(e^{r})^{T}-{\frac {1}{a_{r,s}}}(a^{s}-e^{r})(e^{r})^{T}-{\frac {1}{a_{r,s}}}(a^{s}-e^{r})\underbrace {(e^{r})^{T}(a^{s}-e^{r})} _{=a_{r,s}-1}(e^{r})^{T}=I.$

(iii) Es bezeichne $(C)_{k}^{T}$ die $k$-te Zeile einer Matrix $C$. Dann bekommt man mit (ii)

$A_{J^{+}}^{-1}A=A-{\frac {1}{a_{r,s}}}(a^{s}-e^{r})(e^{r})^{T}A=A-{\frac {1}{a_{r,s}}}(a^{s}-e^{r})(A)_{r}^{T}$

und daher mit (5.6)

$\left(A_{J^{+}}^{-1}A\right)_{r}^{T}=(A)_{r}^{T}-{\frac {1}{a_{r,s}}}(a_{r,s}-1)(A)_{r}^{T}={\frac {1}{a_{r,s}}}(A)_{r}^{T}=\left(A^{+}\right)_{r}^{T},$

$\left(A_{J^{+}}^{-1}A\right)_{i}^{T}=(A)_{i}^{T}-{\frac {1}{a_{r,s}}}a_{i,s}(A)_{r}^{T}=\left(A^{+}\right)_{i}^{T},\quad i=1,\ldots ,m,\quad i\neq r.$

Ferner hat man

$A_{J^{+}}^{-1}b=b-{\frac {1}{a_{r,s}}}(a^{s}-e^{r})(e^{r})^{T}b=b-{\frac {b_{r}}{a_{r,s}}}(a^{s}-e^{r})=b^{*}.$

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

(0) Gegeben sei das lineare Programm $(P')$ in zulässiger kanonischer Form mit $J=\{j_{1},\ldots ,j_{m}\}$ und zulässiger Basislösung $({\hat {x}},J)$ von $Ax=b$.

(1) Falls $c_{N}\geq 0$, stop! (${\hat {x}}$ ist Lösung von $(P')$ und $c_{0}=\min _{x\in Z_{P'}}f(x)$.)

(2) Wähle $s\in N$ mit $c_{s}<0$, z. B. $c_{s}:=\min _{j\in N}c_{j}$.

(3) Falls $a^{s}\leq 0$, stop! (Es ist $\inf _{x\in Z_{P'}}f(x)=-\infty$.)

(4) Bestimme $r\in \{1,\ldots ,m\}$ mit

${\frac {b_{r}}{a_{r,s}}}:=\min \left\{{\frac {b_{i}}{a_{i,s}}}{\big |}i\in \{1,\ldots ,m\}{\text{ mit }}a_{i,s}>0\right\}.$

(5) Setze

$J^{+}=\left\{j_{1}^{+},\ldots ,j_{m}^{+}\right\}:=\{j_{1},\ldots ,j_{r-1},s,j_{r+1},\ldots ,j_{m}\},\quad N^{+}:=\{1,\ldots ,n\}\setminus J^{+}.$

Berechne

$A^{+}=\left(a_{i,j}^{+}\right):=A_{J^{+}}^{-1}A=\left(I-{\frac {1}{a_{r,s}}}(a^{s}-e^{r})(e^{r})^{T}\right)A,$

$b^{+}=\left(b_{i}^{+}\right):=A_{J^{+}}^{-1}b=\left(I-{\frac {1}{a_{r,s}}}(a^{s}-e^{r})(e^{r})^{T}\right)b$

sowie

$-c_{0}^{+}:=-c_{0}-c_{s}b_{r}^{+},\quad c_{j}^{+}:=c_{j}-c_{s}a_{r,j}^{+}\qquad (j=1,\ldots ,n)$

und die neue zulässige Basislösung $({\hat {x}}^{+},J^{+})$ mit

${\hat {x}}_{J^{+}}^{+}:=b^{+},\quad {\hat {x}}_{N^{+}}^{+}:=0.$

(6) Setze

${\hat {x}}:={\hat {x}}^{+},\quad J:=J^{+},\quad A:=A^{+},\quad b:=b^{+},\quad c:=c^{+},\quad c_{0}:=c_{0}^{+}$

und gehe nach (1).

Satz 5.7

Gegeben sei das lineare Programm $(P')$ in zulässiger kanonischer Form mit $J=\{j_{1},\ldots ,j_{m}\}$ und zulässiger Basislösung $({\hat {x}},J)$ von $Ax=b$. Für den $k$-ten Iterationsschritt von Algorithmus 12 gilt dann:

(i) Ist $c_{N}\geq 0$, so ist $f({\hat {x}})\leq f(x)$ für alle $x\in Z_{P'}$.

(ii) Ist $c_{s}<0$ und $a^{s}\leq 0$ für ein $s\in N$, so ist $\inf _{x\in Z_{P'}}f(x)=-\infty$.

(iii) Ist $c_{s}<0$ und $a_{r,s}>0$ das Pivotelement, so gilt:

$(\alpha )$ $Ax=b\Leftrightarrow A^{+}x=b^{+}$.

$(\beta )$ $f(x)=c^{T}x+c_{0}=(c^{+})^{T}x+c_{0}^{+}$ für alle $x\in \mathbb {R} ^{n}$ mit $Ax=b$.

$(\gamma )$ $({\hat {x}}^{+},J^{+})$ ist eine zulässige Basislösung von $A^{+}x=b^{+}$.

$(\delta )$ Die Aufgabe

$\left(P^{+}\right):$ Minimiere $(c^{+})^{T}x+c_{0}^{+}$ auf $\left\{x\in \mathbb {R} ^{n}{\big |}A^{+}x=b^{+},x\geq 0\right\}$

ist äquivalent zur Aufgabe $(P')$ und liegt in zulässiger kanonischer Form mit Basisindexmenge $J^{+}$ vor.

$(\varepsilon )$ Es ist $f({\hat {x}})=c_{0}$ und $f({\hat {x}}^{+})=c_{0}^{+}$. Ferner ist $f({\hat {x}}^{+})\leq f({\hat {x}})$ und im Fall $b_{r}>0$ sogar $f({\hat {x}}^{+})<f({\hat {x}})$.

Beweis.

(i) Sei $x\in Z_{P'}$ beliebig. Dann ist aufgrund der gemachten Voraussetzungen mit (5.4)

$f(x)=c^{T}x+c_{0}=\underbrace {c_{J}^{T}} _{=0}x_{J}+\underbrace {c_{N}^{T}} _{\geq 0}\underbrace {x_{N}} _{\geq 0}+c_{0}\geq c_{0}=c^{T}{\hat {x}}+c_{0}=f({\hat {x}}).$

(ii) Für jedes $\delta \geq 0$ definiere man einen Vektor $x(\delta )\in \mathbb {R} ^{n}$ durch

$x_{j}(\delta ):={\begin{cases}b_{k}-\delta a_{k,s},&{\text{falls }}j=j_{k}\in J,\\\delta ,&{\text{falls }}j=s,\\0,&{\text{falls }}j\in N\setminus \{s\}.\end{cases}}$

Insbesondere ist also nach unseren Voraussetzungen

$x_{J}(\delta )=b-\delta a^{s},\quad A_{J}=I.$

Wegen $a^{s}\leq 0$ ist $x_{J}(\delta )\geq 0$ und damit $x(\delta )\geq 0$ für alle $\delta \geq 0$. Ferner gilt nach Definition von $x(\delta )$ und $x_{J}(\delta )$:

$Ax(\delta )=A_{J}x_{J}(\delta )+A_{N}x_{N}(\delta )=A_{J}x_{J}(\delta )+a^{s}x_{s}(\delta )=b-\delta a^{s}+\delta a^{s}=b.$

Also ist $x(\delta )\in Z_{P'}$ für alle $\delta \geq 0$. Wegen $c_{J}=0$ folgert man weiter

$c^{T}x(\delta )+c_{0}=c_{s}\delta +c_{0}\to -\infty$ für $\delta \to +\infty$,

so dass (ii) bewiesen ist.

(iii) $(\alpha )$ Nach Lemma 5.6 (iii) hat man

$Ax=b\Leftrightarrow A_{J^{+}}^{-1}Ax=A_{J^{+}}^{-1}b\Leftrightarrow A^{+}x=b^{+}.$

Aussage $(\beta )$ ist bereits durch (5.7) gezeigt worden.

$(\gamma )$ Wie man aus der Transformation $A\to A^{+}$ ablesen kann, ist $A_{J^{+}}^{+}=I$. Ferner ist aufgrund der Wahl der Pivotzeile $r$ im Simplexschnitt

${\frac {b_{r}}{a_{r,s}}}\leq {\frac {b_{i}}{a_{i,s}}}\quad (i\in \{1,\ldots ,m\}$ mit $a_{i,s}>0)$

und folglich wegen $b\geq 0$ und $a_{r,s}>0$

$b_{i}-{\frac {b_{r}}{a_{r,s}}}((a^{s})_{i}-(e^{r})_{i})={\begin{cases}{\frac {b_{r}}{a_{r,s}}}\geq 0&{\mbox{für }}i=r,\\b_{i}-{\frac {b_{r}}{a_{r,s}}}a_{i,s}\geq 0&{\mbox{ für }}i\in \{1,\ldots ,m\}{\text{ mit }}a_{i,s}>0,\\b_{i}-{\frac {b_{r}}{a_{r,s}}}a_{i,s}\geq 0&{\mbox{ für }}i\in \{1,\ldots ,m\}{\text{ mit }}a_{i,s}\leq 0,\end{cases}}$

so dass gilt:

(5.8) $b^{+}=A_{J^{+}}^{-1}b=\left(I-{\frac {1}{a_{r,s}}}(a^{s}-e^{r})(e^{r})^{T}\right)b=b-{\frac {b_{r}}{a_{r,s}}}(a^{s}-e^{r})\geq 0.$

Also ist $({\hat {x}}^{+},J^{+})$ eine zulässige Basislösung von $A^{+}x=b^{+}$.

$(\delta )$ Die Äquivalenz von $(P^{+})$ und $(P')$ folgt unmittelbar aus $(\alpha )$ und $(\beta )$. Es ist

$c_{j}^{+}=c_{j}-c_{s}{\frac {a_{r,j}}{a_{r,s}}}\quad (j=1,\ldots ,n).$

Demnach ist $c_{s}^{+}=0$ und wegen $a_{r,j}=0$ und $c_{j}=0$ für $j\in J\setminus \{r\}$ ferner $c_{j}^{+}=0$ für $j\in J\setminus \{r\}$. Somit ist $c_{J^{+}}^{+}=0$. Wie bereits oben bemerkt wurde, hat man außerdem $A_{J^{+}}^{+}=I$.

$(\varepsilon )$ Mit (5.4) sowie Aussagen $(\beta )$ und $(\gamma )$ schließen wir zum einen

$f({\hat {x}})=c_{0},\quad f({\hat {x}}^{+})=\left(c^{+}\right)^{T}{\hat {x}}^{+}+c_{0}^{+}=c_{0}^{+}$

und zum anderen wegen $N^{+}=(N\setminus \{s\})\cup \{r\}$

$c_{0}^{+}=\left(c^{+}\right)^{T}{\hat {x}}^{+}+c_{0}^{+}=c^{T}{\hat {x}}^{+}+c_{0}=\sum _{j\in J}\underbrace {c_{j}} _{=0}{\hat {x}}_{j}^{+}+\sum _{j\in N\setminus \{s\}}c_{j}\underbrace {{\hat {x}}_{j}^{+}} _{=0}+c_{s}{\hat {x}}_{s}^{+}+c_{0}$

$=c_{s}b_{r}^{+}+c_{0}=c_{s}{\frac {b_{r}}{a_{r,s}}}+c_{0},$

wobei $c_{s}<0,a_{r,s}>0$ und ${\hat {x}}_{r}=b_{r}\geq 0$ ist.

q.e.d.

Satz 5.7 zeigt, dass nur die Darstellungen der Zielfunktion $f$ und des zulässigen Bereichs $Z_{P'}$ 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 „$(P')$“ in den beiden Ausgängen (1) und (3) von Algorithmus 12 auch durch das Problem „$(P^{0})$“ 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 $(P)$ in Normalform aus und hat man die unten beschriebene Phase I des Simplexverfahrens durchlaufen, so kann man statt „$(P')$“ dort auch „$(P)$“ schreiben, da $(P)$ in Phase I mit Hilfe von Phase II in ein äquivalentes Problem $(P^{0})$ in zulässiger kanonischer Form überführt wird, sofern nicht $Z_{P}=\emptyset$ ist.

Die zulässigen Bereiche der Probleme $(P')$ und $(P^{+})$ am Anfang und Ende eines Iterationsschrittes von Phase II des Simplexverfahrens sind also identisch. Ferner vergrößert sich beim Übergang von $({\hat {x}},J)$ zu der neu berechneten zulässigen Basislösung $({\hat {x}}^{+},J^{+})$ der Zielfunktionswert von $(P')$ nicht (vgl. Satz 5.7 (iii) $(\varepsilon )$). Im Fall, dass $({\hat {x}},J)$ nichtentartet, d. h. $b>0$ 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.

Satz 5.8

Phase II des Simplexverfahrens (Algorithmus 12) gehe von einem Problem $(P^{0})$ 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 $(P^{0})$ oder mit der Information ab, dass die Zielfunktion des Problems $(P^{0})$ auf dessen zulässigem Bereich unbeschränkt ist.

Ist jedoch $({\hat {x}},J)$ entartet, so ist aufgrund des Auswahlkriteriums der Pivotzeile $b_{r}=0$, damit $b=b^{+}$ (vgl. (5.6)) und folglich ${\hat {x}}={\hat {x}}^{+}$ möglich. Gleichzeitig ist wegen des Auswahlkriteriums für die Pivotspalte in einem solchen Fall $J\neq J^{+}$. 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 $J$ 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

Definition 5.9

Ein Vektor $v:=(v_{1},\ldots ,v_{n})^{T}\in \mathbb {R} ^{n}$ heißt lexikographisch positiv (kurz: $v\succ 0$), falls $v\neq 0$ und die erste nicht verschwindende Komponente von $v$ positiv ist. Ein Vektor $v$ heißt lexikographisch größer als ein Vektor $u$ (kurz: $v\succ u$), wenn $v-u\succ 0$ ist.

Die Relation „$\succ$“ hat die üblichen Eigenschaften einer Ordnungsrelation. Insbesondere gilt daher für alle Vektoren $u,v,w\in \mathbb {R} ^{n}$:

• $v\succ u,u\succ w\Rightarrow v\succ w$,
• $v\succ u\Rightarrow v+w\succ u+w$,
• $v\succ u,\alpha >0\Rightarrow \alpha v\succ \alpha u$,
• Für zwei Vektoren $u,v\in \mathbb {R} ^{n}$ gilt $u=v$ oder $u\succ v$ oder $v\succ u$.

Beispiel 5.10

$u:=(1,1,-1,5)^{T},v:=(-1,5,4,3)^{T},w:=(1,2,-3,4)^{T}$. Dann ist $u\succ v,w\succ v$ und $w\succ u$, also $w\succ u\succ v$.

---

Eine endliche Menge $S\subseteq \mathbb {R} ^{n}$ paarweise verschiedener Vektoren aus dem $\mathbb {R} ^{n}$ besitzt offenbar ein eindeutiges lexikographisches Minimum $u\in S$, geschrieben

$u:=l-\min(S),$

d. h. ein Element $u\in S$, so dass $v\succ u$ für alle $v\in \mathbb {R} ^{n}$ gilt.

O. B. d. A. sei nun für das Startproblem der Phase II des Simplexalgorithmus $J:=\{1,\ldots ,m\}$ und (gegebenenfalls nach einer Umsortierung der Spalten) das zugehörige zulässige kanonische Problem in ein Tableau der folgenden Form eingetragen:

(5.9) ${\begin{array}{cccccccc}-c_{0}&0&0&\ldots &0&c_{m+1}&\ldots &c_{n}\\\hline b_{1}&1&0&\ldots &0&a_{1,m+1}&\ldots &a_{1,n}\\b_{2}&0&1&\ldots &0&a_{2,m+1}&\ldots &a_{2,n}\\\vdots &\vdots &\vdots &\ddots &\vdots &\vdots &\ddots &\vdots \\b_{m}&0&0&\ldots &1&a_{m,m+1}&\ldots &a_{m,n}\end{array}}$

Weiter seien die $m+1$ Zeilen in diesem Tableau als Vektoren des $\mathbb {R} ^{n+1}$ aufgefasst:

$y^{0}:=(-c_{0},0,0,\ldots ,0,c_{m+1},\ldots ,c_{n})^{T},$

$y^{i}:=(b_{i},0,\ldots ,0,\underbrace {1} _{(i+1){\text{-te Stelle}}},0,\ldots ,0,a_{i,m+1},\ldots ,a_{i,n})^{T},\quad i=1,\ldots ,m.$

Da wir von einem Problem in zulässiger kanonischer Form ausgehen, ist insbesondere $b\geq 0$ und deshalb für das Startproblem

(5.10) $y^{i}\succ 0\quad (i=1,\ldots ,m).$

Es lässt sich nun der folgende Satz beweisen, in dem $y^{i}$ und $(y^{+})^{i}$ $(i=0,\ldots ,m)$ die Zeilen des aus (5.9) hervorgegangenen Tableaus in der $k$-ten bzw. $(k+1)$-ten Iteration kennzeichnen und dessen Voraussetzung offenbar für $k=0$ erfüllt ist. (Es muss $J=\{1,2,\ldots ,m\}$ nur für das Startproblem gelten.)

Satz 5.11

Zu Beginn der $k$-ten Iteration von Algorithmus 12 sei $y^{i}\succ 0$ $(i=1,\ldots ,m)$. Im Fall, dass kein Abbruch stattfindet, sei $s'$ die Nummer der Pivotspalte und sei die Nummer $r\in \{1,\ldots ,m\}$ der Pivotzeile nicht nach der in Schritt (4) angegebenen, sondern nach folgender Regel bestimmt:

(5.11) ${\frac {y^{r}}{y_{s'}^{r}}}:=l-\min \left\{{\frac {y^{i}}{y_{s'}^{i}}}{\big |}i\in \{1,\ldots ,m\}\ mit\ y_{s'}^{i}>0\right\}.$

Dann gilt:

(i) $r$ ist eindeutig bestimmt,

(ii) $(y^{+})^{i}\succ 0$ $(i=1,\ldots ,m)$,

(iii) $(y^{+})^{0}\succ y^{0}$.

Beweis.

(i) Für $l,r\in \{1,\ldots ,m\}$ mit $l\neq r$ kann

${\frac {y^{r}}{y_{s'}^{r}}}={\frac {y^{l}}{y_{s'}^{l}}},\quad y_{s'}^{r}>0,\quad y_{s'}^{l}>0$

nicht gelten. Denn es gibt einen Spaltenindex $\sigma \in \{2,3,\ldots ,n+1\}$ (für das Startproblem ist $\sigma :=r+1$), für den $y_{\sigma }^{r}=1$, aber $y_{\sigma }^{l}=0$ ist.

(ii) Nach den Umrechnungsregeln (5.6) gilt mit $y_{s'}^{r}>0$ für die Zeilen $(y^{+})^{i}$ $(i=1,\ldots ,m)$ des neuen Tableaus

(5.12) $\left(y^{+}\right)^{i}=y^{i}-{\frac {y_{s'}^{i}}{y_{s'}^{r}}}y^{r}\quad (i=1,\ldots ,m,i\neq r),$

$\left(y^{+}\right)^{r}={\frac {1}{y_{s'}^{r}}}y^{r}.$

Wegen $y^{r}\succ 0$ hat man also insbesondere $(y^{+})^{r}\succ 0$. Ferner folgt aus (5.12) für alle $i\in \{1,\ldots ,m\}\setminus \{r\}$ mit $y_{s'}^{i}\leq 0$ wegen (5.10) auch $(y^{+})^{i}\succ 0$. Schließlich liefert (5.12) für alle $i\in \{1,\ldots ,m\}\setminus \{r\}$ mit $y_{s'}^{i}>0$ unter Verwendung von (5.11), dass

${\frac {(y^{+})^{i}}{y_{s'}^{i}}}={\frac {y^{i}}{y_{s'}^{i}}}-{\frac {y^{r}}{y_{s'}^{r}}}\succ 0$

und damit $(y^{+})^{i}\succ 0$ ist.

(iii) Es ist

$\left(y^{+}\right)^{0}=y^{0}-{\frac {c_{s'}}{y_{s'}^{r}}}y^{r}$

mit $c_{s'}<0,y_{s'}^{r}>0$ und $y^{r}\succ 0$. Somit erschließt man

(5.13) $\left(y^{+}\right)^{0}-y^{0}=-{\frac {c_{s'}}{y_{s'}^{r}}}y^{r}\succ 0.$

q.e.d.

Die ursprüngliche Auswahlregel für die Pivotzeile in Schritt (4) des oben angegebenen Austauschschritts ging nur in den Nachweis von $b^{+}\geq 0$ ein (vgl. (5.8)). Da Aussage (ii) von Satz 5.11 ebenfalls $b^{+}\geq 0$ impliziert (dies folgte vorher mit Satz 5.7 (iii) $(\gamma )$), 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 $k$-ten Iteration von Phase II mit $(y^{(k)})^{i}$ $(i=0,1,\ldots ,m)$, so liefert die Beziehung (5.13) mit einem $\alpha _{k}\in \mathbb {R}$ und $r_{k}\in \{1,\ldots ,m\}$

$(y^{(k+1)})^{0}-(y^{(k)})^{0}=\alpha _{k}(y^{(k)})^{r_{k}}$

und nach Summation für die Indizes $k,\ldots ,\ell -1$ mit $\ell >k$

$(y^{(\ell )})^{0}-(y^{(k)})^{0}=\sum _{j=k}^{\ell }\alpha _{j}(y^{(j)})^{r_{j}}.$

Da in Phase II des Simplexalgorithmus nur Vielfache von Zeilen zueinander addiert werden, kann jede Zeile des Tableaus im $(k+1)$-ten Schritt und damit aller nachfolgenden Tableaus als Linearkombination der Zeilen im $k$-ten beschrieben werden, so dass man mit gewissen $\beta _{i}$ $(i=1,\ldots ,m)$ weiter erhält:

$(y^{(\ell )})^{0}-(y^{(k)})^{0}=\sum _{i=1}^{m}\beta _{i}(y^{(k)})^{i}.$

Wären nun die Basislösungen $({\hat {x}}^{k},J^{k})$ und $({\hat {x}}^{\ell },J^{\ell })$ identisch und $J^{k}=J^{\ell }=\{j_{1},\ldots ,j_{m}\}$, so stünden an den Positionen $j_{p}+1$ $(p=1,\ldots ,m)$ von $(y^{(k)})^{0}$ und $(y^{(\ell )})^{0}$ Nullen und, hintereinander genommen, an den entsprechenden Positionen der $(y^{(k)})^{i}$ unterschiedliche Spalten der Einheitsmatrix (die $(y^{(k)})^{i}$ sind ja Spaltenvektoren). Letzteres implizierte $\beta _{i}=0$ $(i=1,\ldots ,m)$ und $(y^{(\ell )})^{0}=(y^{(k)})^{0}$, was jedoch nach Aussage (iii) von Satz 5.11 nicht möglich ist.

Geht Phase II des Simplexverfahrens von einem Problem $(P^{0})$ 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 $(P^{0})$ bzw. mit dem Ausgang ab, dass die Zielfunktion des Problems $(P^{0})$ 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.

5.4 Phase I des Simplexalgorithmus

Nun kommen wir zur Phase I des Simplexalgorithmus. Sie geht von dem Optimierungsproblem $(P)$ in Normalform aus, also von

${\begin{array}{lll}(P):&{\text{Minimiere}}&c^{T}x\\&{\text{u. d. N.}}&Ax=b,\\&&x\geq 0\end{array}}$

mit $A\in \mathbb {R} ^{m\times n},b\in \mathbb {R} ^{m}$ und $c\in \mathbb {R} ^{n}$. O. B. d. A. können wir annehmen, dass $b\geq 0$ ist, da wir Gleichungen mit negativer rechter Seite mit $-1$ multiplizieren können. Ziel der Phase I ist es, entweder festzustellen, dass

$Z_{P}:=\{x\in \mathbb {R} ^{n}{\big |}Ax=b,\quad x\geq 0\}$

leer ist, oder Problem $(P)$ 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 $z_{i}$ $(i=1,\ldots ,m)$ einführt und die Aufgabe

${\begin{array}{ll}{\text{Minimiere}}&\sum \limits _{i=1}^{m}z_{i}\\{\text{u. d. N.}}&Ax+z=b,\\&(x,z)\geq 0\end{array}}$

betrachtet, welche sich mit $e:=(1,1,\ldots ,1)^{T}\in \mathbb {R} ^{m}$ und der $(m\times m)$-Einheitsmatrix $I$ in folgender Form schreiben lässt:

${\begin{array}{lll}(P'_{H}):&{\text{Minimiere}}&(0,e)^{T}(x,z)\\&{\text{u. d. N.}}&{\begin{pmatrix}A&I\end{pmatrix}}(x,z)=b,\\&&(x,z)\geq 0.\end{array}}$

Offenbar gilt, dass die Zielfunktion von $(P'_{H})$ den Wert $e^{T}z\geq 0$ hat und der Vektor $(0,b)$ wegen $b\geq 0$ zulässige Basislösung von $(P'_{H})$ ist. Nach Satz 4.13 besitzt Problem $(P'_{H})$ demnach eine Lösung $(x^{*},z^{*})\in \mathbb {R} ^{n+m}$. Ferner sieht man leicht ein, dass der optimale Zielfunktionswert $e^{T}z^{*}$ von $(P'_{H})$ genau dann identisch Null ist, wenn $Z_{P}\neq \emptyset$ ist.

Man schreibt jetzt die Zielfunktion von $(P'_{H})$ so um, dass man ein Problem in zulässiger kanonischer Form erhält. Für zulässige Punkte von $(P'_{H})$ gilt $Ax+z=b$, so dass folgt:

(5.15) $e^{T}z=e^{T}b-e^{T}Ax=-\left(A^{T}e\right)^{T}x+e^{T}b.$

Daher ist $(P'_{H})$ äquivalent zu dem Problem

${\begin{array}{lll}(P_{H}):&{\text{Minimiere}}&(-A^{T}e,0)^{T}(x,z)+e^{T}b\\&{\text{u. d. N.}}&{\begin{pmatrix}A&I\end{pmatrix}}(x,z)=b,\\&&(x,z)\geq 0.\end{array}}$

Letzteres Problem hat wegen $b\geq 0$ zulässige kanonische Form mit zugehöriger Basislösung $((0,b),J)$ für $J:=\{n+1,\ldots ,n+m\}$ 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 $(P)$ einträgt (wie unten deutlich wird, ist es zweckmäßig, die mit $0\cdot z_{1}+\ldots +0\cdot z_{m}$ erweiterte Zielfunktion von $(P)$ selbst in Phase I mit umzuformen):

${\begin{array}{c|ccc|ccc}\sum \limits _{i=1}^{m}b_{i}&\sum \limits _{i=1}^{m}a_{i,1}&\ldots &\sum \limits _{i=1}^{m}a_{i,n}&0&\ldots &0\\\hline 0&c_{1}&\ldots &c_{n}&0&\ldots &0\\\hline b_{1}&a_{1,1}&\ldots &a_{1,n}&1&\ldots &0\\\vdots &\vdots &\ddots &\vdots &\vdots &\ddots &\vdots \\b_{m}&a_{m,1}&\ldots &a_{m,n}&0&\ldots &1\end{array}}$

Phase II des Simplexalgorithmus liefere nun als Lösung von $(P_{H})$ die zulässige Basislösung $((x^{*},z^{*}),J^{*})$ mit

$J^{*}:=\{j_{1}^{*},\ldots ,j_{m}^{*}\},\quad N^{*}:=\{1,\ldots ,n+m\}\setminus J^{*}.$

Das zugehörige, mit $(P_{H})$ äquivalente Problem in zulässiger kanonischer Form laute

${\begin{array}{ll}{\text{Minimiere}}&(c^{*},{\tilde {c}}^{*})^{T}(x,z)+c_{0}^{*}\\{\text{u. d. N.}}&{\begin{pmatrix}A^{*}&{\tilde {A}}^{*}\end{pmatrix}}(x,z)=b^{*},\\&(x,z)\geq 0.\end{array}}$

Die Spalten der Matrix ${\begin{pmatrix}A^{*}&{\tilde {A}}^{*}\end{pmatrix}}=(a_{i,j}^{*})$ seien mit $(a^{*})^{j}$ $(j=1,\ldots ,n+m)$ bezeichnet. Man beachte, dass mit Satz 5.8 insbesondere $A^{*}x+{\tilde {A}}^{*}z=b^{*}$ genau dann gilt, wenn $Ax+Iz=b$ ist und für $z=0$ damit $A^{*}x=b^{*}$ genau dann, wenn $Ax=b$ richtig ist ($(x,0)$ ist dann in beiden Fällen zulässig). Ferner hat man wegen (5.8) und (5.15)

$(c^{*},{\tilde {c}}^{*})^{T}(x^{*},z^{*})+c_{0}^{*}=e^{T}z^{*}.$

Es sind jetzt drei Fälle zu betrachten:

1. $z^{*}\neq 0.$

Dann ist, wie oben bereits bemerkt wurde, $Z_{P}=\emptyset$ und das Verfahren mit einer entsprechenden Meldung abzubrechen.

1. $z^{*}=0,J^{*}\subseteq \{1,\ldots ,n\}.$

Dies ist der angenehme Fall. $(x^{*},J^{*})$ ist eine zulässige Basislösung von $A^{*}x=b^{*}$ bzw. $Ax=b$. Insbesondere gilt $a^{j_{k}^{*}}=e^{k}$ für $k=1,\ldots ,m$ und es stehen Nullen in den Spalten mit den Indizes $j^{*}\in J^{*}$ der beiden ersten Zeilen des optimalen Tableaus, da dieses zu einem mit $(P_{H})$ ä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 $m$, 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 $(P)$ äquivalenten Problem in zulässiger kanonischer Form gehört. Phase II des Simplexalgorithmus kann folglich sofort gestartet werden.

1. $z^{*}=0,J^{*}\cap \{n+1,\ldots ,n+m\}\neq \emptyset .$

Dann liefern zwar die künstlichen Variablen keinen Beitrag, aber für das Problem $(P)$ 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 $j\in \{n+1,\ldots ,n+m\}\cap N^{*}$. Weiter hat man wegen $(x^{*},z^{*})=(x^{*},0)=b^{*}$, dass $b_{r}^{*}=0$ für $j_{r}^{*}\in J^{*}\cap \{n+1,\ldots ,n+m\}$ mit $r\in \{1,\ldots ,m\}$ gilt, wobei die Spalte mit dem Index $j_{r}^{*}$ zur Variablen $z_{\tilde {r}}$ mit ${\tilde {r}}:=j_{r}^{*}-n$ gehört. Ein solches $j_{r}^{*}$ sei nun frei gewählt. Es sind dann zwei Fälle zu unterscheiden:

(a) $a_{r,j}^{*}=0$ $(j=1,\ldots ,n)$.

Dann wird durch die $r$-te Gleichung den $x_{j}$ $(j=1,\ldots ,n)$ keine Restriktion aufgezwungen. Sie kann (auch im Ausgangssystem $Ax=b$) gestrichen werden. Offenbar ist $\operatorname {Rang} (A)<m$ gewesen. (In Phase I wird also auch festgestellt, ob die Rangbedingung erfüllt ist. Für das um die $r$-te Gleichung reduzierte System ist jetzt $\operatorname {Rang} (A)=m-1$ gefordert!) Ferner streiche man auch die $j_{r}^{*}$-te Spalte im Tableau.

(b) $a_{r,s}^{*}\neq 0$ für ein $s\in \{1,\ldots ,n\}$.

Man wähle ein solches $a_{r,s}^{*}\neq 0$ und mache einen Austauschschritt mit $a_{r,s}^{*}$. Wegen $b_{r}^{*}=0$ muss hier $a_{r,s}^{*}>0$ nicht notwendig vorliegen, da $b_{r}^{*}=0$ impliziert, dass $(b^{*})^{+}=b^{*}\geq 0$ ist. (Die Wahl der Pivotzeile ging nur in den Beweis von Satz 5.8 (iii) $(\gamma )$ und $(\varepsilon )$ bzw. in Satz 5.12 zum Nachweis von $b^{+}\geq 0$ ein.) Damit ist nun $z_{\tilde {r}}$ Nichtbasisvariable und die $j_{r}^{*}$-te Spalte kann folglich aus dem Tableau gestrichen werden. Da $(x^{*},z^{*})$ optimal für $(P_{H})$ ist, muss auch die neue Basislösung $(x^{*},z^{*})^{+}$ optimal für $(P_{H}),also<math>z^{*+}=0$ 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 $A$ von $Ax=b$ mit $b\geq 0$ Einheitsvektoren $e^{i}$ 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.

Beispiel 5.13

Gegeben sei das LOP

(5.16) ${\begin{array}{ll}{\text{Minimiere}}&-y1+2y_{2}+3y_{3}\\{\text{u. d. N.}}&y_{1}+3y_{2}-2y_{3}\leq 10,\\&3y_{1}-2y_{2}-3y_{3}\leq -5,\\&4y_{1}-2y_{2}+y_{3}=4,\\&y_{1}\geq 0,\quad y_{2}\geq 0.\end{array}}$

Setzt man $x_{1}:=y_{1},x_{2}:=y_{2},y_{3}:=x_{3}-x_{4}$, führt man zwei Schlupfvariable $x_{5}\geq 0$ und $x_{6}\geq 0$ für die beiden "$\leq$"-Ungleichungen ein und multipliziert man anschließend die so erhaltene zweite Gleichung mit $-1$, damit ihre rechte Seite positiv wird, so gelangt man mit $x=(x_{1},x_{2},x_{3},x_{4},x_{5},x_{6})^{T}$ zu folgendem LOP in Normalform:

(5.17) ${\begin{array}{ll}{\text{Minimiere}}&(-1,2,3,-3,0,0)x\\{\text{u. d. N.}}&{\begin{pmatrix}1&3&-2&2&1&0\\-3&2&3&-3&0&-1\\4&-2&1&-1&0&0\end{pmatrix}}x={\begin{pmatrix}10\\5\\4\end{pmatrix}},\\&x\geq 0.\end{array}}$

Das Problem hat nicht zulässige kanonische Form, so dass man Phase I des Simplexalgorithmus anwenden muss. Der Einheitsvektor $e^{1}$ 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 "$\leq$"-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:

${\begin{array}{r|rrrrrr|rr}-9&-1&0&-4&4&0&1&0&0\\\hline 0&-1&2&3&-3&0&0&0&0\\\hline 10&1&3&-2&2&1&0&0&0\\5&-3&2&{\mbox{3}}&-3&0&-1&1&0\\4&4&-2&1&-1&0&0&0&1\end{array}}$

Auf dieses (ohne die zweite Zeile) zu einem Problem in zulässiger kanonischer Form gehörende Tableau mit

$J^{0}:=\{5,7,8\},\quad N^{0}:=\{1,2,3,4,6\}$

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 $N^{0}$ gehören. Ist diese negativ wie hier, nämlich $-4$, 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: $5/3$ und 4). Der kleinste dieser Werte (hier: $5/3$) charakterisiert die Pivotzeile und damit das Pivotelement $a_{r,s}^{0}$ (hier: $a_{r,s}^{0}=a_{2,3}^{0}=3$).

Die $r$-te Zeile im folgenden Tableau erhält man nun, indem man die alte $r$-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:

${\begin{array}{r|rrrrrr|rr}-7/3&-5&8/3&0&0&0&-1/3&4/3&0\\\hline -15/3&2&0&0&0&0&1&-1&0\\\hline 40/3&-1&13/3&0&0&1&-2/3&2/3&0\\5/3&-1&2/3&1&-1&0&-1/3&1/3&0\\7/3&{\mbox{5}}&-8/3&0&0&0&1/3&-1/3&1\end{array}}$

mit

$J^{1}:=\{5,3,8\},\quad N^{1}:=\{1,2,4,6,7\}.$

Da die Phase II noch nicht abbricht, gelangt man bei analogem Vorgehen (die Pivotelemente sind jeweils gekennzeichnet) zu folgendem nächsten Tableau

${\begin{array}{r|rrrrrr|rr}0&0&0&0&0&0&0&1&1\\\hline -89/15&0&16/15&0&0&0&13/15&-13/15&-2/5\\\hline 69/5&0&19/5&0&0&1&-3/5&3/5&1/5\\32/15&0&2/15&1&-1&0&-4/15&4/15&1/5\\7/15&1&-8/15&0&0&0&1/15&-1/15&1/5\end{array}}$

mit

$J^{2}:=\{5,3,1\},\quad N^{2}:=\{2,4,6,7,8\}.$

Weil es keine negative Zahl mehr unter den zu $N^{2}$ in der ersten Zielfunktionszeile stehenden Zahlen gibt, ist eine Lösung $x^{*}$ des (Hilfs-)Problems mit $J^{*}:=J^{2}$ und $N^{*}:=N^{2}$ gefunden. Der zugehörige optimale Zielfunktionswert, welcher mit negativem Vorzeichen in der ersten Spalte der ersten Zeile steht, ist $z^{*}=0$. Da ferner $J^{*}\subset \{1,2,3,4,5,6\}$ 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

${\begin{array}{r|rrrrrr}\hline -89/15&0&16/15&0&0&0&13/15\\\hline 69/5&0&19/5&0&0&1&-3/5\\32/15&0&2/15&1&-1&0&-4/15\\7/15&1&-8/15&0&0&0&1/15\end{array}}$

Auch unter den zu $N^{*}$ 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

$x_{J^{*}}^{*}=(x_{5}^{*},x_{3}^{*},x_{1}^{*})^{T}=\left({\frac {69}{5}},{\frac {32}{15}},{\frac {7}{15}}\right)^{T}\Rightarrow x^{*}=\left({\frac {7}{15}},0,{\frac {32}{15}},0,{\frac {69}{5}},0\right)^{T}$

mit zugehörigem optimalen Zielfunktionswert $89/15$. Folglich ist

$y^{*}=(x_{1}^{*},x_{2}^{*},x_{3}^{*}-x_{4}^{*})^{T}=\left({\frac {7}{15}},0,{\frac {32}{15}}\right)^{T}$

mit demselben Zielfunktionswert $89/15$ Lösung von Problem (5.16).

---

5.5 Phase II des Simplexalgorithmus in Matrixform

Dieser Abschnitt dient im wesentlichen dazu zu zeigen, dass man aus dem letzten Tableau der Phase II des Simplexalgorithmus eine Lösung des zu $(P)$ dualen Problems $(D')$ 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 $-1$ multiplizierten Zielfunktionszeile (anderenfalls bekommt man (5.20) nicht!) als System $By=d$ mit der Blockmatrix bzw. den Blockvektoren

$B:={\begin{pmatrix}1&-c^{T}\\0&A\end{pmatrix}},\quad y:={\begin{pmatrix}w\\x\end{pmatrix}},\quad d:={\begin{pmatrix}c_{0}\\b\end{pmatrix}}.$

Die Variable $w$ muss man hier mitführen, damit man unten z. B. eine vollständige Basis für $By=d$ erhält. $d$ und $B$ fassen wir in dem folgenden Tableau zusammen:

$T:={\begin{pmatrix}d&B\end{pmatrix}}={\begin{pmatrix}c_{0}&1&-c^{T}\\b&0&A\end{pmatrix}}.$

Ist $\{a^{j_{1}},\ldots ,a^{j_{m}}\}$ eine Basis zu $Ax=b$ mit Basisindexmenge $J:=\{j_{1},\ldots ,j_{m}\}$, so ist offenbar durch

$\left\{{\begin{pmatrix}1\\0\end{pmatrix}},{\begin{pmatrix}-c^{j_{1}}\\a^{j_{1}}\end{pmatrix}},\ldots ,{\begin{pmatrix}-c^{j_{m}}\\a^{j_{m}}\end{pmatrix}}\right\},\quad L:=\{1,j_{1}+1,\ldots ,j_{m}+1\}$

eine Basis und Basisindexmenge zu $By=d$ gegeben. Insbesondere ist

$B_{L}:={\begin{pmatrix}1&-c_{J}^{T}\\0&A_{J}\end{pmatrix}}={\begin{pmatrix}1&-c^{j_{1}}&\cdots &-c^{j_{m}}\\0&a^{j_{1}}&\cdots &a^{j_{m}}\end{pmatrix}}.$

$B_{L}$ ist invertierbar und, wie man leicht überprüft, ist

(5.18) $B_{L}^{-1}:={\begin{pmatrix}1&c_{J}^{T}A_{J}^{-1}\\0&A_{J}^{-1}\end{pmatrix}}.$

(Man beachte, dass mit $A_{J}^{-1}$ die Matrix $(A_{J})^{-1}$ gemeint ist. Da die Matrix $(A^{-1})_{J}$ nur für $m=n$ existiert und dann identisch mit $(A_{J})^{-1}$ ist, ist aber keine Verwechslung möglich.)

$(P')$ liege nun in zulässiger kanonischer Form mit Basisindexmenge $J^{0}:=\{j_{1}^{0},\ldots ,j_{m}^{0}\}$ vor, so dass Phase II gestartet werden kann. Bezeichnet $I_{\ell }$ im folgenden die $(\ell \times \ell )$-Einheitsmatrix, so ist also insbesondere $A_{J^{0}}=I_{m}$ und $c_{J^{0}}=0$.

Es sei nun

(5.19) $L^{0}:=\left\{1,j_{1}^{0}+1,\ldots ,j_{m}^{0}+1\right\},\quad B^{0}:=B,\quad d^{0}:=d,\quad T^{0}:=T$

und ein hochgestelltes „$k$“ kennzeichne im folgenden den Iterationsindex der Phase II. Insbesondere schreiben wir für $k\in \mathbb {N} _{0}$

$B^{k}:={\begin{pmatrix}1&-\left(c^{k}\right)^{T}\\0&A^{k}\end{pmatrix}},\quad d^{k}:={\begin{pmatrix}c_{0}^{k}\\b^{k}\end{pmatrix}}.$

Nutzen wir aus, dass

$A^{k+1}=\left[A_{J^{k+1}}^{k}\right]^{-1}A^{k},\quad b^{k+1}=\left[A_{J^{k+1}}^{k}\right]^{-1}b^{k}$

ist (vgl. Lemma 5.6) und verwenden wir, dass die Regeln (5.7) für die neue Zielfunktionszeile

$\left(c^{k+1}\right)^{T}=-(c^{k})^{T}+(c_{J^{k+1}}^{k})^{T}A^{k+1},\quad c_{0}^{k+1}=c_{0}^{k}+c_{J^{k+1}}^{k}b^{k+1}$

liefern (alle Komponenten von $c_{J^{k+1}}^{k}$, bis auf die mit dem Index der im $k$-ten Schritt gewählten Pivotspalte, sind Null!), so erhalten wir, wie man leicht verifiziert,

(5.20) $B^{k+1}=\left[B_{L^{k+1}}^{k}\right]^{-1}B^{k},\quad d^{k+1}=\left[B_{L^{k+1}}^{k}\right]^{-1}d^{k},$

wobei die Existenz von $\left[B_{L^{k+1}}^{k}\right]^{-1}$ offenbar gesichert ist. Insbesondere ist also

$B^{k+1}=\left[B_{L^{k+1}}^{k}\right]^{-1}\left[B_{L^{k}}^{k-1}\right]^{-1}B^{k-1}=\ldots =\left[B_{L^{k+1}}^{k}\right]^{-1}\cdots \left[B_{L^{1}}^{0}\right]^{-1}B^{0},$

$d^{k+1}=\left[B_{L^{k+1}}^{k}\right]^{-1}\left[B_{L^{k}}^{k-1}\right]^{-1}d^{k-1}=\ldots =\left[B_{L^{k+1}}^{k}\right]^{-1}\cdots \left[B_{L^{1}}^{0}\right]^{-1}d^{0},$

so dass man mit

$C^{k+1}:=\left[B_{L^{k+1}}^{k}\right]^{-1}\cdots \left[B_{L^{1}}^{0}\right]^{-1}$

und (5.19) die Gleichungen

(5.21) $B^{k+1}=C^{k+1}B,\quad d^{k+1}=C^{k+1}d$

erhält. Folglich ist

$B_{L^{k+1}}^{k+1}=C^{k+1}B_{L^{k+1}}$

Da $B_{L^{k+1}}^{k+1}=I_{m+1}$ für die von uns vorgestellte Form des Simplexalgorithmus ist, impliziert die letztere Gleichung $C^{k+1}=B_{L^{k+1}}^{-1}$, so dass wir die Gleichungen (5.21) in der Form

(5.22) $B^{k+1}=B_{L^{k+1}}^{-1}B,\quad d^{k+1}=B_{L^{k+1}}^{-1}d$

schreiben können. Man beachte, dass sich $B_{L^{k+1}}^{-1}$ aus der Kenntnis der Basisindexmenge $L^{k+1}$ bzw. $J^{k+1}$ und der Ausgangsmatrix $B$ gemäß (5.18) berechnen lässt. Folglich kann man $d^{k+1}$ und $B^{k+1}$ und damit das $k$-te Simplextableau

(5.23) $T^{k}={\begin{pmatrix}d^{k}&B^{k}\end{pmatrix}}=B_{L^{k}}^{-1}{\begin{pmatrix}d&B\end{pmatrix}}$

vollständig mit $J^{k}$ durch die Ausgangsdaten beschreiben.

Das $k$-te Simplextableau $T^{k}$ wollen wir noch vollständig ausschreiben. Dazu sortieren wir der Anschaulichkeit halber die Spalten der Anfangsdaten $A$ und $c$ in der $k$-ten Iteration so um, dass

$J^{k}=\{1,\ldots ,m\},\quad N^{k}:=\{m+1,\ldots ,m+n\}$

und damit

$A={\begin{pmatrix}A_{J^{k}}&A_{N^{k}}\end{pmatrix}},\quad c={\begin{pmatrix}c_{J^{k}}\\c_{N^{k}}\end{pmatrix}}$

ist. So können wir das $k$-te Simplextableau $T^{k}$ unter Verwendung von (5.18) und (5.23) in folgender Form darstellen:

$T^{k}={\begin{pmatrix}d^{k}&B^{k}\end{pmatrix}}={\begin{pmatrix}1&c_{J^{k}}^{T}A_{J^{k}}^{-1}\\0&A_{J^{k}}^{-1}\end{pmatrix}}{\begin{pmatrix}c_{0}&1&-c_{J^{k}}^{T}&c_{N^{k}}^{T}\\b&0&A_{J^{k}}&A_{N^{k}}\end{pmatrix}}$

= ${\begin{pmatrix}c_{J^{k}}^{T}A_{J^{k}}^{-1}b+c_{0}&1&0^{T}&-\left(c_{N^{k}}^{T}-c_{J^{k}}^{T}A_{J^{k}}^{-1}A_{N^{k}}\right)\\A_{J^{k}}^{-1}b&0&I_{m}&A_{J^{k}}^{-1}A_{N^{k}}\end{pmatrix}}.$

Der Vektor $\left(c_{N^{k}}^{k}\right)^{T}:=c_{N^{k}}^{T}-c_{J^{k}}^{T}A_{J^{k}}^{-1}A_{N^{k}}$ heißt Vektor der relativen Kosten. Seine Komponenten bestimmen die Pivotspalte. (Man beachte, dass die Zielfunktionszeile mit $-1$ multipliziert wurde.)

Die Tatsache, dass man bei Kenntnis von $J^{k}$ einen Eckenaustausch bzw. das Tableau in der $k$-ten Iteration allein aus den Anfangsdaten gewinnen kann, macht sich der revidierte Simplexalgorithmus zunutze (siehe z. B. [Wer92]). Dieser ist wegen einer im allgemeinen erheblich geringeren Anzahl von benötigten Rechenoperationen in der Praxis meist wesentlich effektiver als der hier beschriebene, für das Verständnis und das Rechnen mit der Hand aber einfachere Simplexalgorithmus mit vollständigem Tableau. Die Aufwandsersparnis des revidierten Simplexalgorithmus ist dadurch begründet, dass der Simplexalgorithmus, wie man aus Erfahrung weiß, selten mehr als $Km$ Iterationen benötigt, wobei typischerweise $K\in [1,6]$ ist. Ist also die Anzahl $m$ der Gleichungen des Systems $Ax=b$ sehr viel kleiner als die Variablenzahl $n$, so werden von den $n$ Spalten der Matrix nur wenige zu Pivotspalten und die übrigen Spalten von $A$ bei dem hier beschriebenen Simplexalgorithmus unnötigerweise in jedem Schritt mit umgerechnet. Denn von der Matrix $A_{J^{k}}^{-1}A_{N^{k}}wirdim<math>k$-ten Schritt nur eine Spalte, die neue Pivotspalte, benötigt und die Spalten von $A$, die nie zu einer Basis gehören, interessieren nicht, weil dann die zugehörigen Koe¢zienten einer Lösung Nichtbasisvariable und damit identisch Null sind. Die im revidierten Simplexalgorithmus benötigte Matrix $A_{J^{k}}^{-1}$ läßt sich leicht aus $A_{J^{k-1}}^{-1}$ durch Multiplikation mit einer gewissen Rang-1-Matrix bestimmen, da sich $A_{J^{k}}$ gegenüber $A_{J^{k-1}}$ nur um eine Spalte ändert (s. [Wer92]).

Wir schließen mit einer weiteren Beobachtung. Schreibt man die Ausgangsdaten $A$ und $c$ in der Form

$A={\begin{pmatrix}A_{J^{0}}&A_{N^{0}}\end{pmatrix}}={\begin{pmatrix}I_{m}&A_{N^{0}}\end{pmatrix}},\quad c={\begin{pmatrix}c_{J^{0}}\\c_{N^{0}}\end{pmatrix}}={\begin{pmatrix}0\\c_{N^{0}}\end{pmatrix}}$

und sortiert man $A$ im $k$-ten Schritt nicht mehr erneut um, so hat das $k$-te Simplextableau wegen (5.23) mit (5.18) die Gestalt

$T^{k}={\begin{pmatrix}1&c_{J^{k}}^{T}A_{J^{k}}^{-1}\\0&A_{J^{k}}^{-1}\end{pmatrix}}{\begin{pmatrix}c_{0}&1&0^{T}&-c_{N^{0}}^{T}\\b&0&I_{m}&A_{N^{0}}\end{pmatrix}}$

(5.24) Fehler beim Parsen (Unbekannte Funktion „\begin{pmatrix}“): {\displaystyle = \begin{pmatrix} c^T_{J^k} A^{-1}_{J^k} b + c_0 & 1 & c^T_{J^k} A^{-1}_{J^k} & - c^T_{N^0} + c^T_{J^k} A^{-1}_{J^k} A_{N^0} \right\} \\ A^{-1}_{J^k} b & 0 & A^{-1}_{J^k} & A^{-1}_{J^k} A_{N^0} \end{pmatrix}.}

D. h. an der Stelle, wo im Ausgangstableau die Einheitsmatrix stand, befindet sich im $k$-ten Tableau die Matrix $A_{J^{k}}^{-1}$ und in den zugehörigen Zeilen der Zielfunktion, wo anfangs $0^{T}$ stand, der Vektor

(5.25) $(y^{k})^{T}:=c_{J^{k}}^{T}A_{J^{k}}^{-1}.$

Gilt für den Vektor der relativen Kosten

$(c_{N^{k}}^{T}-c_{J^{k}}^{T}A_{J^{k}}^{-1}A_{N^{k}})^{T}\geq 0,$

so ist $x^{k}$ Lösung von $(P)$. In diesem Fall hat man für den Vektor $y^{k}$, wobei wir hier der Einfachheit halber $A={\begin{pmatrix}A_{J^{k}}&A_{N^{k}}\end{pmatrix}}$ schreiben dürfen:

$(y^{k})^{T}A={\begin{pmatrix}(y^{k})^{T}A_{J^{k}}&(y^{k})^{T}A_{N^{k}}\end{pmatrix}}={\begin{pmatrix}c_{J^{k}}^{T}&c_{J^{k}}^{T}A_{J^{k}}^{-1}A_{J^{k}}\end{pmatrix}}\leq {\begin{pmatrix}c_{J^{k}}^{T}&c_{N^{k}}^{T}\end{pmatrix}}=c^{T}$

und

$b^{T}y^{k}=b^{T}(A_{J^{k}}^{-1})^{T}c_{J^{k}}=\left(x_{J^{k}}^{k}\right)^{T}c_{J^{k}}=c^{T}x^{k}.$

Nach Satz 4.18 (iii) löst daher $y^{k}$ das Problem $(D')$ bzw. mit $s^{k}:=c-A^{T}y^{k}$ das duale Problem $(D)$ (s. Abschnitt 4.6.1). Demnach lässt sich die Lösung des zu $(P)$ dualen Problems $(D')$ aus dem letzten Tableau der Phase II des Simplexalgorithmus ablesen. Dies sei abschließend an einem Beispiel demonstriert.

Beispiel 5.14

Es sei das LOP

${\begin{array}{lll}({\hat {P}}_{s}):&{\text{Minimiere}}&c^{T}x\\&{\text{u. d. N.}}&Ax\leq b,\\&&x\geq 0,x\in \mathbb {R} ^{3}\end{array}}$

mit den folgenden Daten gegeben:

$c:={\begin{pmatrix}1\\-4\\-3\end{pmatrix}},\quad A:={\begin{pmatrix}2&2&1\\1&2&2\end{pmatrix}},\quad b:={\begin{pmatrix}4\\6\end{pmatrix}}.$

Gesucht sei eine Lösung von $({\hat {P}}_{s})$ sowie eine Lösung des dazu dualen Problems

${\begin{array}{lll}({\hat {D}}_{s}):&{\text{Maximiere}}&-b^{T}z\\&{\text{u. d. N.}}&-A^{T}z\leq c,\\&&z\geq 0,z\in \mathbb {R} ^{2}.\end{array}}$

Mit

${\hat {c}}:=(1,-4,-3,0,0)^{T},\quad {\hat {A}}:={\begin{pmatrix}2&2&1&1&0\\1&2&2&0&1\end{pmatrix}}$

lässt sich $({\hat {P}}_{s})$ in folgende Normalform bringen:

${\begin{array}{lll}(P_{s}):&{\text{Minimiere}}&{\hat {c}}^{T}y\\&{\text{u. d. N.}}&{\hat {A}}y=b,\\&&y\geq 0,y\in \mathbb {R} ^{5}.\end{array}}$

Das Problem $(P_{s})$ hat schon zulässige kanonische Form, so dass Phase II des Simplexalgorithmus gestartet werden kann. Sie liefert die folgenden Tableaus:

$\left({\begin{array}{c|ccccc}0&1&-4&-3&0&0\\\hline 4&2&{\mbox{2}}&1&1&0\\6&1&2&2&0&1\end{array}}\right)\rightarrow \left({\begin{array}{c|ccccc}8&5&0&-1&2&0\\\hline 2&1&1&1/2&1/2&0\\2&-1&0&{\mbox{1}}&-1&1\end{array}}\right)\rightarrow \left({\begin{array}{c|ccccc}10&4&0&0&1&1\\\hline 1&3/2&1&0&1&-1/2\\2&-1&0&{\mbox{1}}&-1&1\end{array}}\right).$

Somit ist $(0,1,2,0,0)^{T}$ mit Zielfunktionswert $-10$ Lösung von $(P_{s})$ und folglich ${\hat {x}}:=(0,1,2)^{T}$ mit $c^{T}{\hat {x}}=-10$ Lösung von $({\hat {P}}_{s})$.

Das zu $(P_{s})$ duale Problem ist

${\begin{array}{lll}(D_{s}):&{\text{Maximiere}}&b^{T}u\\&{\text{u. d. N.}}&{\hat {A}}^{T}u\leq {\hat {c}},\\&&u\in \mathbb {R} ^{2}\end{array}}$

und hat, wie man aus dem letzten Tableau oben ablesen kann, ${\hat {u}}:=(-1,-1)^{T}$ als Lösung. (Zum Erhalt der obigen allgemeinen Resultate, hatten wir ja die Zielfunktion mit $-1$ multipliziert.) Offenbar ist dann ${\hat {z}}:=-{\hat {u}}=(1,1)^{T}$ Lösung von Problem $({\hat {D}}_{s})$.

---

5.6 Sensitivität

In der Praxis ist es häufig so, dass z. B. Schranken $c_{i}$ in Restriktionen $g_{i}(x)\leq c_{i}$ nicht wohldefinierte Größen sind, sondern geändert werden können oder müssen, wenn der optimale Zielfunktionswert nicht befriedigend ist. Daher ist die Frage von Interesse, ob man, ausgehend von einer nichtdegenerierten optimalen Basislösung $({\hat {x}},J)$ und dem zugehörigen Optimalwert $c^{T}{\hat {x}}$ von $(P)$ für ein gestörtes Problem

${\begin{array}{lll}({\tilde {P}}):&{\text{Minimiere}}&c^{T}x\\&{\text{u. d. N.}}&Ax={\tilde {b}},\\&&x\geq 0\end{array}}$

mit

(5.26) ${\tilde {b}}:=b+\Delta b$

die Änderung in Bezug auf den Optimalwert vorhersagen kann. Dieser Frage wollen wir hier nachgehen. (Natürlich kann man auch zusätzlich noch Änderungen in $A$ und $c$ betrachten.) Das duale Problem zu $({\tilde {P}})$ lautet

${\begin{array}{lll}({\tilde {D}}):&{\text{Maximiere}}&{\tilde {b}}^{T}y\\&{\text{u. d. N.}}&A^{T}y+s=c,\\&&s\geq 0\end{array}}$

und unterscheidet sich von dem dualen Problem $(D)$ zu $(P)$ nur in der Zielfunktion.

Wir definieren zunächst den Vektor

${\hat {y}}:=\left(A_{J}^{-1}\right)^{T}c_{J}.$

Dieser löst nach Abschnitt 5.5 (vgl. Formel (5.25)) das duale Problem $(D')$ bzw. mit ${\hat {s}}:=c-A^{T}{\hat {y}}$ das duale Problem $(D)$. Somit ist $({\hat {y}},{\hat {s}})$ auch zulässiger Punkt für $({\tilde {D}})$. Da $({\hat {x}},J)$ nichtdegenerierte Lösung von $(P)$ ist, gilt weiter

${\hat {x}}_{J}=A_{J}^{-1}b>0.$

Ist $\|\Delta b\|$ in (5.26) so klein, dass noch

(5.27) $A_{J}^{-1}(b+\Delta b)=A_{J}^{-1}{\tilde {b}}\geq 0$

gilt, so ist also $({\tilde {x}},J)$ mit

(5.28) ${\tilde {x}}_{J}:=A_{J}^{-1}{\tilde {b}}=A_{J}^{-1}(b+\Delta b),\quad {\tilde {x}}_{N}:=0$

eine zulässige Basislösung von $({\tilde {P}})$, welche mit $({\hat {y}},{\hat {s}})$ wegen

$c^{T}{\tilde {x}}=c_{J}^{T}{\tilde {x}}_{J}=c_{J}^{T}A_{J}^{-1}(b+\Delta b)=(b+\Delta b)^{T}{\hat {y}}={\tilde {b}}^{T}{\hat {y}}$

nach dem starken Dualitätssatz auch für $({\tilde {P}})$ optimal ist. Ist $\|\Delta b\|$ also hinreichend klein, so hat $({\tilde {P}})$ also insbesondere dieselben optimalen Basis- und Nichtbasisindizes wie $(P)$. Man beachte in diesem Zusammenhang, dass man die Gültigkeit von (5.27) auch überprüfen kann, da ja das Endtableau im Simplexalgorithmus $A_{J}^{-1}$ mitliefert (vgl. (5.24)).

Wegen (5.28) hat man weiter

${\tilde {x}}_{J}={\hat {x}}_{J}+\Delta {\hat {x}}_{J}$ mit $\Delta {\hat {x}}_{J}:=A_{J}^{-1}\Delta b$

und den zugehörigen optimalen Zielfunktionswert von $({\tilde {P}})$

$c^{T}{\tilde {x}}=c_{J}^{T}{\tilde {x}}_{J}=c_{J}^{T}{\hat {x}}_{J}+c_{J}^{T}\Delta {\hat {x}}_{J}=c^{T}{\hat {x}}+c_{J}^{T}A_{J}^{-1}\Delta b.$

Der optimale Zielfunktionswert von $({\tilde {P}})$ läßt sich also für kleine Störungen $\Delta b$ der rechten Seite $b$ in $(P)$ vorhersagen und ändert sich offenbar gegenüber dem von $(P)$ um den Wert

$c_{J}^{T}A_{J}^{-1}\Delta b=(\Delta b)^{T}{\hat {y}}.$

Die Komponenten ${\hat {y}}_{j}$ der dualen Lösung bzw. des zu ${\hat {x}}$ gehörenden Multiplikatorenvektors ${\hat {y}}$ drücken demnach die Empfindlichkeit bzw. Sensitivität des Optimalwertes von $(P)$ gegenüber solchen Störungen $(\Delta b)_{j}$ von $b_{j}$ aus. Insbesondere kann man also durch Störung der $b_{j}$, die zu den größten Multiplikatoren gehören, auch die größten Änderungen in Bezug auf den Zielfunktionswert erzielen.

Bei Problemen der Wirtschaft bedeuten die Restriktionen häufig Bedingungen für Verbräuche und die Zielfunktion die Kosten oder den Gewinn. Man bezeichnet deshalb dort die dualen Variablen ${\hat {y}}_{j}$ auch als Schattenpreise.