Benutzer:Stepri2005/Kurs:Optimierung/Grundlagen der linearen Optimierung

4.1 Das lineare Optimierungsproblem in Normalform

Es seien $c,\alpha ^{j}\in \mathbb {R} ^{n}$ und $\gamma ,b_{j}\in \mathbb {R}$ gegeben. Dann hat ein lineares Optimierungsproblem (kurz: LOP) allgemein die Form

${\begin{array}{lll}(LOP):&{\text{Minimiere bzw. Maximiere}}&c^{T}x+\gamma \\&{\text{u. d. N.}}&(\alpha ^{j})^{T}x=b_{j}\quad (j=1,\ldots ,m_{0}),\\&&(\alpha ^{j})^{T}x\leq b_{j}\quad (j=m_{0}+1,\ldots ,m_{1}),\\&&(\alpha ^{j})^{T}x\geq b_{j}\quad (j=m_{1}+1,\ldots ,m_{2}).\end{array}}$

Ein Problem vom Typ $(LOP)$ mit zwei Variablen lässt sich auf geometrische Weise lösen.

Beispiel 4.1

(i) Man betrachte das Problem

${\begin{array}{ll}{\text{Minimiere}}&x_{1}+x_{2}\\{\text{u. d. N.}}&-2x_{1}-x_{2}\leq -1,\\&x_{1}-x_{2}\leq 2,\\&x_{1},x_{2}\geq 0.\end{array}}$

Wie man sich deutlich macht, wird für dieses Problem der kleinste Zielfunktionswert hinsichtlich des zulässigen Gebietes im Punkt $x^{*}:=(0.5,0)^{T}$ angenommen und beträgt dieser Wert 0.5.

(ii) Ändert man das Beispiel aus (i) so ab, dass man darin die Zielfunktion mit $-1$ multipliziert, dann gilt:

$-x_{1}-x_{2}=-0.5,\quad -x_{1}-x_{2}=-1.5,\quad -x1-x2=-2.5.$

Für dieses Beispiel existieren also zulässige Punkte mit beliebig kleinen Zielfunktionswerten.

---

Beispiel 4.1 macht deutlich, dass nur eine der folgenden Situationen eintreten kann, wobei $Z_{LOP}$ der zulässige Bereich von $(LOP)$ ist (mit Satz 4.13 wird dies auch noch bewiesen):

1. $Z_{LOP}=\emptyset$. Dann ist $\inf _{x\in Z_{LOP}}c^{T}x=+\infty$.
2. $Z_{LOP}\neq \emptyset$. Dann hat man entweder:

(a) es existiert ein $x^{*}\in Z_{LOP}$ mit $\min _{x\in Z_{LOP}}c^{T}x=c^{T}x^{*}$ (dies ist z. B. der Fall, wenn $Z_{LOP}$ beschränkt ist) oder

(b) es gibt eine Folge $\left\{x^{k}\right\}$ in $Z_{LOP}$ mit $c^{T}x^{k}\to -\infty$ $(k\to \infty )$, d. h. es ist $\inf _{x\in Z_{LOP}}c^{T}x=-\infty$.

Man sagt nun weiter, dass ein LOP in Normalform vorliegt, wenn es die Gestalt

${\begin{array}{ll}{\text{Minimiere}}&c^{T}x\\{\text{u. d. N.}}&(\alpha ^{j})^{T}x=b_{j}\quad (j=1,\ldots ,m),\\&x_{i}\geq 0\quad (i=1,...,n),\end{array}}$

bzw. mit $A\in \mathbb {R} ^{m\times n},b\in \mathbb {R} ^{m}$ und $c\in \mathbb {R} ^{n}$ die folgende Gestalt hat:

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

Den zulässigen Bereich von $(P)$ bezeichnen wir mit

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

Bemerkenswert ist nun, dass sich jedes LOP durch die folgenden Operationen in ein LOP in Normalform überführen lässt:

• Man streiche die Konstante $\gamma$ in der Zielfunktion. (Sie ist dann nach Lösung des Problems zu dem optimalen Zielfunktionswert hinzu zu addieren.)
• Ein Maximierungsproblem mit Zielfunktion $c^{T}x$ schreibe man als Minimierungsproblem mit Zielfunktion $-c^{T}x$. (Der optimale Zielfunktionswert des Minimierungsproblems ist dann mit $-1$ zu multiplizieren.)
• „$\geq$“-Restriktionen forme man durch Multiplikation mit $-1$ zu „$\leq$“-Restriktionen um.
• „$\leq$“-Restriktionen schreibe man mittels Hinzufügung von Schlupfvariablen $y_{i}\geq 0$ als „$=$“-Restriktionen.
• Jede vorzeichenfreie Variable $x_{j}$ ersetze man durch $x_{j}:=x_{j}^{+}-x_{j}^{-}$ mit $x_{j}^{+}\geq 0$ und $x_{j}^{-}\geq 0$.

Offenbar ist dann das Ausgangsproblem mit dem zugehörigen Problem in Normalform in dem Sinne äquivalent, dass die optimalen Zielfunktionswerte beider Probleme identisch sind und dass das eine der beiden Probleme genau dann eine Lösung besitzt, wenn das andere eine hat, wobei sich eine Lösung des einen Problems aus einer Lösung des anderen ableiten lässt.

Beispiel 4.2

Gegeben sei das Problem

${\begin{array}{ll}{\text{Minimiere}}&y_{1}+y_{2}\\{\text{u. d. N.}}&2y_{1}+y_{2}\geq 1,\\&y_{1}-y_{2}=2,\\&y_{1}\geq 0.\end{array}}$

Mit $x_{1}:=y_{1},y_{2}:=x_{2}-x_{3},x_{2}\geq 0,x_{3}\geq 0$ geht dieses Problem über in das Problem

${\begin{array}{ll}{\text{Minimiere}}&x_{1}+x_{2}-x_{3}\\{\text{u. d. N.}}&-2x_{1}-x_{2}+x_{3}+x_{4}=-1,\\&x_{1}-x_{2}+x_{3}=2,\\&x_{1},x_{2},x_{3},x_{4}\geq 0.\end{array}}$

Mit $x:=(x_{1},x_{2},x_{3},x_{4})^{T}$,

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

bekommt letzteres Problem die Gestalt von $(P)$ mit $m=2$ und $n=4$.

---

4.2 Die Rangbedingung

Wir betrachten nun das lineare Optimierungsproblem $(P)$ in Normalform und seinen zulässigen Bereich $Z_{P}$ (siehe (4.1)). Üblicherweise setzt man in diesem Zusammenhang

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

voraus und damit insbesondere $m\leq n$. Dies ist eine sinnvolle Arbeitsannahme. Denn hat man $\operatorname {Rang} (A):=\ell <m$, dann besitzt das lineare Gleichungssystem $Ax=b$ entweder keine Lösung oder enthält dieses $m-\ell$ überflüssige Zeilen, die gestrichen werden können. Ist andererseits $m>n$, also das System $Ax=b$ überbestimmt, so ist es ebenfalls entweder unlösbar oder können in diesem Fall mindestens $m-n$ Gleichungen aus ihm entfernt werden. Demzufolge kann man, wenn das System $Ax=b$ überhaupt eine Lösung besitzt, nach Beseitigung aller überflüssigen Gleichungen und nach Benennung der Anzahl der verbleibenden Gleichungen in $m$ zu einem Gleichungssystem gelangen, dessen Matrix die Bedingung (4.2) erfüllt.

Sei nun $\operatorname {Rang} (A):=m$. Dann existieren $m\leq n$ Spalten von $A$, die linear unabhängig sind. Weiter hat man im Hinblick auf die Lösbarkeit des Systems $Ax=b$ bekanntlich folgendes Resultat, wobei

(4.3) ${\mathcal {N}}(A):=\{p\in \mathbb {R} ^{n}{\big |}Ap=0\}$

den Nullraum von $A$ bezeichnet.

Satz 4.3

Sei $A\in \mathbb {R} ^{m\times n},b\in \mathbb {R} ^{m}$ und $\operatorname {Rang} (A)=m$. Dann gilt:

(i) Ist $m=n$, dann hat das homogene System $Ax=0$ die Lösungsmenge ${\mathcal {N}}(A)=\{0\}$. Ist $m<n$, so besitzt es $n-m$ linear unabhängige Lösungen $x^{i}\in \mathbb {R} ^{n}$ $(i=1,\ldots ,n-m)$ und ist seine Lösungsmenge ${\mathcal {N}}(A)$ gleich dem von ${\bar {x}}^{1},\ldots ,{\bar {x}}^{n-m}$ aufgespannten $(n-m)$-dimensionalen Teilraum des $\mathbb {R} ^{n}$.

(ii) Das inhomogene lineare Gleichungssystem $Ax=b$ besitzt eine Lösung ${\hat {x}}\in \mathbb {R} ^{n}$ und seine Lösungsmenge ist der affine Teilraum ${\hat {x}}+{\mathcal {N}}(A)$.

Ist insbesondere $m=n$, so hat also das System $Ax=b$ unter der Rangbedingung (4.2) eine eindeutige Lösung ${\hat {x}}$. Im Fall ${\hat {x}}\geq 0$ ist dann $Z_{P}=\{{\hat {x}}\}$ und folglich ${\hat {x}}$ Lösung von $(P)$. Ist dagegen ${\hat {x}}\not \geq 0$, so folgt $Z_{P}=\emptyset$. Interessant ist also vor allem der Fall $m<n$.

4.3 Der Rand des zulässigen Bereichs

In diesem Abschnitt stellen wir Untersuchungen zu dem zulässigen Bereich

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

von Problem $(P)$ an, wobei wie zuvor $A\in \mathbb {R} ^{m\times n}$ und $b\in \mathbb {R} ^{m}$ seien. Die Spalten von $A$ bezeichnen wir mit $a^{i}$, so dass $A={\begin{pmatrix}a^{1}&\ldots &a^{n}\end{pmatrix}}$ folgt. (Die Rangbedingung für $A$ wird hier nicht benötigt.)

Definition 4.4

Eine (konvexe) Menge $P\subseteq \mathbb {R} ^{n}$, die sich mit $\alpha ^{i}\in \mathbb {R} ^{n}$ und $b_{i}\in \mathbb {R}$ in der Form

$P:=\left\{x\in \mathbb {R} ^{n}{\big |}(\alpha ^{i})^{T}x-b_{i}\leq 0\quad (i=1,\ldots ,r)\right\}$

darstellen lässt, heißt Polyeder. Ein beschränktes Polyeder heißt Polytop.

Insbesondere ist also die Menge $Z_{P}$ ein Polyeder. Der Simplexalgorithmus zur Lösung linearer Optimierungsprobleme, den wir später diskutieren wollen, erzeugt Iterierte, die auf dem Rand von $Z_{P}$ liegen. Deshalb wollen wir im folgenden Eigenschaften des Randes untersuchen.

Auf folgende Weise kann man Ecken von $Z_{P}$ charakterisieren.

Definition 4.5

Ein Punkt $x\in K$ einer konvexen Menge $K\subseteq \mathbb {R} ^{n}$ heißt Ecke oder Extrempunkt von $K$, wenn es keine Punkte $x^{1},x^{2}\in K$ mit $x^{1}\neq x^{2}$ und kein $t\in (0,1)$ gibt, so dass $x=tx^{1}+(1-t)x^{2}$ ist.

Für $x\in \mathbb {R} ^{n}$ sei nun $J(x)$ die Indexmenge

(4.5) $J(x):=\{j\in \{1,\ldots ,n\}{\big |}x_{j}>0\}.$

Lemma 4.6

Sei $x\in Z_{P},x\neq 0$. Dann gilt:

(i) $x$ ist eine Ecke von $Z_{P}\Leftrightarrow a^{j}$ $(j\in J(x))$ sind linear unabhängig.

(ii) $a^{j}$ $(j\in J(x))$ sind linear abhängig $\Rightarrow$ es existiert ein ${\hat {x}}\in Z_{P}$ mit $|J({\hat {x}})|<|J(x)|$.

Beweis.

Sei $x\in Z_{P},x\neq 0$. Dann ist insbesondere $J(x)\neq \emptyset$.

Sind die $a^{j}$ $(j\in J(x))$ linear abhängig, dann existieren $\alpha _{j}\in \mathbb {R}$, welche nicht alle identisch Null sind, so dass gilt:

$\sum _{j\in J(x)}\alpha _{j}a^{j}=0.$

Seien $\delta \in \mathbb {R}$ und $j_{o}\in J(x)$ definiert durch

$\delta :=\min _{j\in \{j\in J(x){\big |}j\neq 0\}}{\frac {x_{j}}{|\alpha _{j}|}}={\frac {x_{j_{o}}}{|\alpha _{j_{o}}|}}.$

Wegen $x_{j}>0$ $(j\in J(x))$ folgt $\delta >0$ und $\delta |\alpha _{j_{o}}|>0$ sowie $x_{j}-\delta |\alpha _{j}|\geq 0$ $(j\in J(x))$. Für $x^{1}$ und $x^{2}$ mit

$x_{j}^{1}:={\begin{cases}x_{j}+\delta \alpha _{j},&{\text{falls }}j\in J(x),\\0,&{\text{falls }}j\notin J(x),\end{cases}}\quad x_{j}^{2}:={\begin{cases}x_{j}-\delta \alpha _{j},&{\text{falls }}j\in J(x),\\0,&{\text{falls }}j\notin J(x),\end{cases}}$

hat man daher, wie man leicht verifiziert, $x^{1},x^{2}\in Z_{P},x^{1}\neq x^{2}$.

(i) Sei nun $x\in Z_{P}$ eine Ecke von $Z_{P}$. Dann müssen die $a^{j}$ $(j\in J(x))$ linear unabhängig sein, da wir anderenfalls für $x^{1},x^{2}$ die Beziehung $x={\frac {1}{2}}x^{1}+{\frac {1}{2}}x^{2}$ hätten.

Seien jetzt umgekehrt die $a^{j}$ $(j\in J(x))$ linear unabhängig und sei

$x:=ty^{1}+(1-t)y^{2}$

mit $y^{1},y^{2}\in Z_{P}$ und $t\in (0,1)$ gegeben. Dann folgt zunächst wegen $x_{j}=0$ $(j\notin J(x))$ und $y^{1},y^{2}\geq 0$, dass $y_{j}^{1}=y_{j}^{2}=0$ für $j\notin J(x)$ ist. Also hat man

$0=A(y^{1}-y^{2})=\sum _{j\in J(x)}(y_{j}^{1}-y_{j}^{2})a^{j}.$

Wegen der linearen Unabhängigkeit der $a^{j}$ $(j\in J(x))$ muss $y_{j}^{1}=y_{j}^{2}$ $(j\in J(x))$ sein, so dass insgesamt $y^{1}=y^{2}$ folgt. Also ist $x$ eine Ecke von $Z_{P}$.

(ii) Es ist $x_{j_{o}}-\delta |\alpha _{j_{o}}|=0$ und wegen $j_{o}\in J(x)$, d. h. $x_{j_{o}}>0$, daher $|J(x^{1})|<|J(x)|$ oder/und $|J(x^{2})|<|J(x)|$.

q.e.d.

Bemerkung 4.7

(i) Falls $0\in Z_{P}$ gilt, ist 0 Ecke von $Z_{P}$. (Denn der Nullvektor lässt sich nicht als „echte Konvexkombination“ zweier Vektoren $x^{1},x^{2}\geq 0$ darstellen.)

(ii) Gilt $\operatorname {Rang} (A)=m$, so können gegebenenfalls dem Nullvektor und jeder anderen Ecke $x$ von $Z_{P}$ eine Anzahl von $m$ linear unabhängigen Spalten $a^{j}$ $(j\in {\tilde {J}}(x))$ zugeordnet werden, wobei ${\tilde {J}}(x)$ eine Indexmenge ist mit $|{\tilde {J}}(x)|=m$ und ${\tilde {J}}(x)\supseteq J(x)$. (Denn falls $|J(x)|<m$ ist, kann man die nach Lemma 4.6 linear unabhängigen Vektoren $a^{j}$ $(j\in J(x))$ nach einem Satz aus der linearen Algebra durch $m-|J(x)|$ weitere Spalten $a^{j}$ zu $m$ linear unabhängigen Vektoren ergänzen.)

Für die lineare Optimierung grundlegend ist der folgende Satz.

Satz 4.8

Sei $Z_{P}$ das Polyeder in (4.4). Dann gilt:

(i) Ist $Z_{P}\neq \emptyset$, so besitzt $Z_{P}$ mindestens eine Ecke.

(ii) Die Anzahl der Ecken von $Z_{P}$ ist höchstens

${\binom {n}{m}}={\frac {n!}{m!(n-m)!}}.$

Beweis.

(i) Sei $Z_{P}\neq \emptyset$ und $x^{*}\in Z_{P}$ ein Punkt mit

(4.6) $|J(x^{*})|=\min _{x\in Z_{P}}|J(x)|.$

Ist $|J(x^{*})|=0$, so ist $x^{*}=0$ und folglich $x^{*}$ Ecke von $Z_{P}$. Also sei $|J(x^{*})|\geq 1$. Auch dann muss $x^{*}$ eine Ecke von $Z_{P}$ sein. Denn anderenfalls wären nach Aussage (i) von Lemma 4.6 die $a^{j}$ $(j\in J(x^{*}))$ linear abhängig und gäbe es dann nach Lemma 4.6 (ii) im Widerspruch zu (4.6) ein ${\hat {x}}\in Z_{P}$ mit $|J({\hat {x}})|<|J(x^{*})|$.

(ii) Nach Lemma 4.6 ist $x\in Z_{P}$ genau dann Ecke von $Z_{P}$, wenn $a^{j}$ $(j\in J(x))$ linear unabhängig sind. Wegen $a^{j}\in \mathbb {R} ^{m}$ hat man $|J(x)|\leq m$. Nun ergänze man $a^{j}$ $(j\in J(x))$ durch beliebige weitere $m-|J(x)|$ zu insgesamt $m$ Spalten auf (auch gegebenenfalls für $|J(x)|=0$). Es gibt maximal ${\binom {n}{m}}$ Möglichkeiten, $m$ aus $n$ Spalten auszuwählen (die nicht notwendig zu einer Ecke gehören müssen).

q.e.d.

Man kann sich geometrisch klarmachen, dass jeder Punkt eines beschränkten Polyeders, eines Polytops, als Konvexkombination seiner endlich vielen Ecken dargestellt werden kann. Für das Polyeder $Z_{P}$ kann man zeigen:

Satz 4.9

Sei $Z_{P}\neq \emptyset$ und bezeichne $\{v^{i}{\big |}i\in L\}$ die nichtleere Menge der Ecken von $Z_{P}$. Dann lässt sich jeder Punkt $x\in Z_{P}$ mit einer Lösung $p\geq 0$ von $Ap=0$ in der Form

(4.7) $x=\sum _{i\in L}^{}t_{i}v^{i}+p,\qquad t_{i}\geq 0\quad (i\in L),\qquad \sum _{i\in L}^{}t_{i}=1$

darstellen. Ist $Z_{P}$ beschränkt, so ist insbesondere $p=0$.

Beweis.

Für $x\in Z_{P}$ sei $J(x)$ wie in (4.5) definiert. Der Beweis erfolgt per vollständiger Induktion nach der Anzahl $|J(x)|$ positiver Komponenten von $x$.

Ist $|J(x)|=0$, so ist $x=0$. Da 0 Ecke von $Z_{P}$ ist, folgt (4.7) trivialerweise. Wir nehmen nun an, dass sich jedes $x\in Z_{P}$ mit $|J(x)|=r-1\geq 1$ in der Form (4.7) darstellen lässt. Es sei weiter $x\in Z_{P}$ derart, dass $|J(x)|=r$ gilt und $x$ selbst keine Ecke ist. (Anderenfalls wären wir fertig.) Nach Lemma 4.6 sind dann $a^{j}$ $(j\in J(x))$ linear abhängig, so dass ein $w\in \mathbb {R} ^{n}\setminus \{0\}$ existiert mit $w_{j}=0$ $(j\notin J(x))$ und $Aw=0$. Wir nehmen nun zunächst an, dass $w$ positive und negative Komponenten besitzt.

Wir definieren positive Zahlen

$\delta _{1}:=\min \left\{{\frac {x_{j}}{w_{j}}}\in \mathbb {R} {\big |}j\in J(x),\quad w_{j}>0\right\},$

$\delta _{2}:=\min \left\{-{\frac {x_{j}}{w_{j}}}\in \mathbb {R} {\big |}j\in J(x),\quad w_{j}<0\right\}$

und damit

$x^{1}:=x-\delta _{1}w,\quad x^{2}:=x+\delta _{2}w.$

Nach Konstruktion hat man $x^{i}\in Z_{P}$ mit $|J(x^{i})|<r$ für $i=1,2$ und gilt

$x=(1-t)x^{1}+tx^{2}$ mit $t={\frac {\delta _{1}}{\delta _{1}+\delta _{2}}}\in (0,1)$.

Nach Induktionsvoraussetzung besitzen $x^{1}$ und $x^{2}$ also Darstellungen

$x^{1}=\sum _{i\in L}t_{1,i}v^{i}+p^{1},\quad x^{2}=\sum _{i\in L}t_{2,i}v^{i}+p^{2}$

der Form (4.7). Mit

$t_{i}:=(1-t)t_{1,i}+tt_{2,i}\quad (i\in L),\qquad p:=(1-t)p^{1}+tp^{2}$

folgt die gewünschte Darstellung (4.7) für $x$.

Nun sei $w\geq 0$. Wie oben definiere man $\delta _{1}$ und $x^{1}$ und wende man auf $x^{1}$ die Induktionsvoraussetzung an. Die Darstellung (4.7) von $x$ folgt dann aus $x=x^{1}-\delta _{1}w$. Für $w\leq 0$ verfahre man entsprechend. Schließlich ist für jedes $x\in Z_{P}$ und $p\geq 0$ mit $Ap=0$ auch $x+tp\in Z_{P}$ für alle $t\geq 0$, so dass das System $Ap=0$ im Fall, dass $Z_{P}$ beschränkt ist, keine Lösung $p\geq 0$ mit $p\neq 0$ haben kann.

q.e.d.

4.4 Das Innere des zulässigen Bereichs

Der später im Kurs vorgestellte Simplexalgorithmus erzeugt in seiner Phase II Iterierte, welche Ecken des Polyeders $Z_{P}$ darstellen. Innere-Punkte-Verfahren der linearen Optimierung bewegen sich dagegen im sog. Inneren von $Z_{P}$. Das relative Innere der zulässigen Menge bezüglich der Fläche $\{x\in \mathbb {R} ^{n}{\big |}Ax=b\}$ ist durch das straffierte Dreieck ohne den Rand gegeben.

Allgemein ist das relative Innere $\operatorname {ri} (Z_{P})$ von $Z_{P}$ bezüglich der linearen Mannigfaltigkeit $\{x\in \mathbb {R} ^{n}{\big |}Ax=b\}$ definiert durch

$\operatorname {ri} (Z_{P})=\{x\in Z_{P}{\big |}{\text{es gibt ein }}\varepsilon >0,{\mbox{ so dass für alle }}y{\text{ mit }}Ay=b{\text{ und }}|x-y|<\varepsilon {\text{ gilt: }}y\in Z_{P}\}.$

In diesem Zusammenhang betrachten wir die Menge

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

Offenbar gilt

(4.8) $Z_{P}^{o}\subseteq \operatorname {ri} (Z_{P}),$

wobei $Z_{P}^{o}$ und $\operatorname {ri} (Z_{P})$ leer sein können. Besteht die Lösungsmenge des Systems $Ax=b$ nur aus einem Punkt ${\hat {x}}$ mit ${\hat {x}}>0$, so hat man insbesondere $\operatorname {ri} (Z_{P})=\{{\hat {x}}\}$ und somit $Z_{P}^{o}=\operatorname {ri} (Z_{P})$. In einer anderen Situation ist jedoch $Z_{P}^{o}\neq \operatorname {ri} (Z_{P})$ möglich, wie folgendes Beispiel zeigt.

Beispiel 4.10

Es seien $n:=3$ und

$A:={\begin{pmatrix}1&1&-1\\0&1&-1\end{pmatrix}},\quad b:={\begin{pmatrix}0\\0\end{pmatrix}}.$

Dann folgt:

$Z_{P}=\{(0,\alpha ,\alpha )^{T}\in \mathbb {R} ^{3}{\big |}\alpha \geq 0\},\quad \operatorname {ri} (Z_{P})=\{(0,\alpha ,\alpha )^{T}\in \mathbb {R} ^{3}{\big |}\alpha >0\},\quad Z_{P}^{o}=\emptyset .$

---

In dem durch dieses Beispiel beschriebenen Problem existiert eine Variable, die für alle $x\in Z_{P}$ identisch Null ist. In Verallgemeinerung von Beispiel 4.10 hat man:

Lemma 4.11

Sei $Z_{P}\neq \emptyset$. Dann sind folgende Bedingungen äquivalent:

(i) $Z_{P}^{o}=\emptyset$.

(ii) Es gibt ein $i\in \{1,\ldots ,n\}$, so dass $x_{i}=0$ für alle $x\in Z_{P}$ gilt.

Beweis.

Die Implikation „(ii) $\Rightarrow$ (i)“ ist trivial. Gilt andererseits (ii) nicht, so existiert zu jedem Index $i\in \{1,\ldots ,n\}$ ein $x^{i}\in Z_{P}$ mit $x_{i}^{i}>0$. Wegen $x^{i}\geq 0$ $(i=1,\ldots ,n)$ und der Konvexität von $Z_{P}$ folgt $\sum _{i=1}^{n}(1/n)x^{i}\in Z_{P}^{o}$ und somit $Z_{P}^{o}\neq \emptyset$.

q.e.d.

Ist jedoch $Z_{P}^{o}\neq \emptyset$ (und damit trivialerweise auch $Z_{P}\neq \emptyset$), so hat man:

Lemma 4.12

Ist $Z_{P}^{o}\neq \emptyset$, so gilt $Z_{P}^{o}=\operatorname {ri} (Z_{P})$.

Beweis.

Sei $x\in \operatorname {ri} (Z_{P})$. Dann existiert ein $\varepsilon >0$, so dass für jedes $y$ mit $Ay=b$ und $|x-y|<\varepsilon$ auch $y\in Z_{P}$ folgt. Wäre nun $x\notin Z_{P}^{o}$, dann könnte man ein $x^{*}\in Z_{P}^{o}$ wählen und wegen $Ax=b$ und $Ax^{*}=b$ gäbe es ein ${\tilde {x}}\in {\mathcal {N}}(A)\setminus \{0\}$, so dass $x=x^{*}+{\tilde {x}}$ gelten würde. Weiter wäre $x_{i}=x_{i}^{*}+{\tilde {x}}_{i}=0$ für mindestens ein $i$ und wegen $x^{*}>0$ außerdem ${\tilde {x}}_{i}<0$. Mit $0<\delta <\varepsilon /|{\tilde {x}}|$ folgte daher $x_{i}^{*}+(1+\delta ){\tilde {x}}_{i}=\delta {\tilde {x}}_{i}<0$, d. h. $x_{\delta }:=x^{*}+(1+\delta ){\tilde {x}}\in Z_{P}$.

Andererseits hätte man aber $Ax_{\delta }=b$ und $|x-x_{\delta }|=|\delta {\tilde {x}}|<\varepsilon$, was wegen $x\in \operatorname {ri} (Z_{P})$ auch $x_{\delta }\in Z_{P}$ implizierte. Also gilt $x\in Z_{P}^{o}$ und folglich $\operatorname {ri} (Z_{P})\subseteq Z_{P}^{o}$. Mit (4.8) folgt die Behauptung.

q.e.d.

Im Zusammenhang mit Verfahren, die Iterierte im relativen Inneren $\operatorname {ri} (Z_{P})$ von $Z_{P}$ erzeugen, ist trivialerweise $Z_{P}\neq \emptyset$ anzunehmen und ist es nach obigen Ergebnissen darüber hinaus sinnvoll, $Z_{P}^{o}\neq \emptyset$ zu fordern. Denn ist $Z_{P}^{o}=\emptyset$, dann kann man alle Variablen $x_{i}$, die für alle $x\in Z_{P}$ identisch Null sind, aus dem Problem entfernen (Lemma 4.11) und erfüllt das so verkleinerte Problem nach Umbenennung der erhaltenen Variablenzahl in $n$ die Bedingung $Z_{P}^{o}\neq \emptyset$. (Wie man solche Variablen entdeckt, findet man z. B. in Abschnitt 6.7.2 von [Ree01].) Die Forderung $Z_{P}^{o}\neq \emptyset$ garantiert überdies, dass man das relative Innere $\operatorname {ri} (Z_{P})$ von $Z_{P}$ durch die einfacher definierte Menge $Z_{P}^{o}$ beschreiben kann (Lemma 4.12). Die Menge $Z_{P}^{o}$ wird in diesem Zusammenhang kurz als das Innere von $Z_{P}$ und ein Punkt $x\in Z_{P}^{o}$ als innerer Punkt von $Z_{P}$ bezeichnet.

4.5 Existenz von Lösungen

Wir beweisen den folgenden Existenzsatz.

Satz 4.13

Sei $Z_{LOP}$ der zulässige Bereich eines Minimierungsproblems der Form $(LOP)$. Ist $Z_{LOP}\neq \emptyset$ und $\inf _{x\in Z_{LOP}}c^{T}x>-\infty$, so besitzt das Problem $(LOP)$ eine Lösung.

Beweis.

Aufgrund der Äquivalenz von Problem $(LOP)$ mit einem Problem der Form $(P)$ können wir von $(P)$ ausgehen. Seien daher $\{v^{i}{\big |}i\in L\}$ die nach Satz 4.8 nichtleere Menge der Ecken von $Z_{P}$ und $x\in Z_{P}$ beliebig. Nach Satz 4.9 lässt sich dann $x$ in der Form

$x=\sum _{i\in L}t_{i}v^{i}+p{\text{ mit }}t_{i}\geq 0\quad (i\in L),\quad \sum _{i\in L}t_{i}=1,\quad p\geq 0,\quad Ap=0$

darstellen. Es muss $c^{T}p\geq 0$ sein, da $c^{T}p<0$ im Widerspruch zur Voraussetzung

$x+tp\in Z_{P}\quad (t\geq 0),\qquad c^{T}(x+tp)\to -\infty \quad (t\to +\infty )$

implizieren würde. Demnach hat man

(4.9) $c^{T}x=c^{T}\left(\sum _{i\in L}t_{i}v^{i}+p\right)=\sum _{i\in L}t_{i}c^{T}v^{i}+c^{T}p\geq \min _{i\in L}\left(c^{T}v^{i}\right).$

q.e.d.

Für jedes Problem der Form $(P)$ kann man darüber hinaus Folgendes aussagen.

Satz 4.14

Besitzt das LOP in Normalform $(P)$ eine Lösung, so existiert auch eine Ecke von $Z_{P}$, welche Lösung von $(P)$ ist.

Beweis.

Wenn $(P)$ eine Lösung besitzt, sind die Voraussetzungen von Satz 4.13 erfüllt, so dass (4.9) folgt. Demnach löst eine Ecke ${\hat {v}}$ mit $c^{T}{\hat {v}}:=\min _{i\in L}\left(c^{T}v^{i}\right)$ das Problem $(P)$.

q.e.d.

4.6 Dualitätstheorie

Wir gehen in diesem Abschnitt zunächst von einem LOP in Normalform aus und leiten für dieses und das dazu als „duales“ bezeichnete Problem Ergebnisse her. Im Unterabschnitt 4.6.4 behandeln wir dann allgemeine lineare Optimierungsprobleme.

4.6.1 Das duale Problem zu einem Problem in Normalform

Seien $c\in \mathbb {R} ^{n},A\in \mathbb {R} ^{m\times n}$ und $b\in \mathbb {R} ^{m}$. Wir betrachten das LOP in Normalform

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

mit zulässigem Bereich

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

Nach Beispiel 3.16 (1) ist $x^{*}\in \mathbb {R} ^{n}$ genau dann eine Lösung des Problems $(P)$, wenn es Vektoren $y^{*}\in \mathbb {R} ^{m}$ und $s^{*}\in \mathbb {R} ^{n}$ gibt, so dass $(x^{*},y^{*},s^{*})\in \mathbb {R} ^{n+m+n}$ das folgende System löst

${\begin{array}{lrl}(S):&Ax=b,&x\geq 0,\\&A^{T}y+s=c,&s\geq 0,\\&x^{T}s=0.&\end{array}}$

Die Lösbarkeit des Systems $(S)$ ist auch notwendig und hinreichend dafür, dass das Problem

${\begin{array}{llll}(D'):&{\text{Maximiere}}&b^{T}y&({\text{bzw. }}-{\text{Minimiere }}(-b)^{T}y)\\&{\text{u. d. N.}}&A^{T}y\leq c,\end{array}}$

mit zulässigem Bereich

$Z_{D'}:=\left\{y\in \mathbb {R} ^{m}{\big |}A^{T}y\leq c\right\}$

eine Lösung $y^{*}\in \mathbb {R} ^{m}$ besitzt. Denn zu $(D')$ gehören mit $x:=\mu$ die KKT-Bedingungen

${\begin{array}{rr}A^{T}y\leq c,&\\-b+Ax=0,&\\x_{i}(A^{T}y-c)_{i}=0&(i=1,\ldots ,n),\\x\geq 0.&\end{array}}$

Führt man den Schlupfvariablenvektor $s:=c-A^{T}y\geq 0$ für $(D')$ ein, so sieht man, dass letzteres System genau dann eine Lösung besitzt, wenn $(S)$ lösbar ist.

Wir hätten $(P)$ auch gleich anstelle von $(D')$ das mit $(D')$ äquivalente Problem

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

mit zulässigem Bereich

$Z_{D}:=\left\{(y,s)\in \mathbb {R} ^{m+n}{\big |}A^{T}y+s=c,\quad s\geq 0\right\}$

gegenüberstellen können, für das natürlich ebenfalls die Bedingungen $(S)$ notwendige und hinreichende Optimalitätsbedingungen sind. Man bezeichnet $(P)$ in diesem Zusammenhang als das primale und $(D')$ bzw. $(D)$ als das dazu duale Problem. Wir werden uns hier der Einheitlichkeit halber fast ausschließlich auf $(D)$ beziehen, auch in Fällen, in denen der Vektor $s$ nicht explizit benötigt wird und sich daher die Verwendung von $(D')$ anbieten würde.

Die ersten beiden Zeilen von $(S)$ sind äquivalent mit der Forderung, dass $x$ primal und $(y,s)$ dual zulässig ist. Die dritte Bedingung $x^{T}s=0$ in $(S)$ ist gerade die Komplementaritätsbedingung. In diesem Zusammenhang stellen wir noch fest, dass für ein zulässiges Punktepaar $x\in Z_{P}$ und $(y,s)\in Z_{D}$ gilt:

(4.10) $0\leq x^{T}s=(c-A^{T}y)^{T}x=c^{T}x-y^{T}Ax=c^{T}x-b^{T}y.$

Abschließend beweisen wir:

Satz 4.15

Das duale Problem zu $(D)$ ist äquivalent mit $(P)$.

Beweis.

Wir schreiben $(D)$ in ein äquivalentes Problem der Form $(P)$ um, um dann daraus das dazu duale Problem ableiten zu können. Mit $y:=u-v,u\geq 0$ und $v\geq 0$ ist $(D)$ äquivalent mit

${\begin{array}{ll}-{\text{Minimiere}}&-(b,-b,0)^{T}(u,v,s)\\&{\begin{pmatrix}A^{T}&-A^{T}&I\end{pmatrix}}(u,v,s)=c,\\&(u,v,s)\geq 0.\end{array}}$

Das dazu duale Problem lautet

${\begin{array}{ll}-{\text{Maximiere}}&c^{T}z\\&{\begin{pmatrix}A\\-A\\I\end{pmatrix}}z\leq {\begin{pmatrix}b\\b\\0\end{pmatrix}}.\end{array}}$

Mit $x:=-z$ kann dies offenbar wie ein Problem vom Typ $(P)$ geschrieben werden.

q.e.d

4.6.2 Dualitätssätze

Aus den Ergebnissen des vorangehenden Unterabschnitts gehen unmittelbar die als schwacher und starker Dualitätssatz bekannten Sätze hervor. So liefert (4.10) die Aussage des schwachen Dualitätssatzes.

Satz 4.16 (Schwacher Dualitätssatz)

Für $x\in Z_{P}$ und $(y,s)\in Z_{D}$ gilt

(4.11) $0\leq x^{T}s=c^{T}x-b^{T}y.$

Weiter bekommt man:

Satz 4.17

(i) Es gilt:

$(P)$ ist lösbar $\Leftrightarrow (S)$ ist lösbar $\Leftrightarrow (D)$ ist lösbar.

(ii) $x^{*}$ und $(y^{*},s^{*})$ sind genau dann Lösungen von $(P)$ und $(D)$, wenn $(x^{*},y^{*},s^{*})$ das System $(S)$ löst.

Beweis.

Aussage (i) ergibt sich aus Abschnitt 4.6.1. Seien nun $x^{*}$ und $(y^{*},s^{*})$ Lösungen von $(P)$ bzw. $(D)$. Dann ist zu zeigen, dass dieses Punktepaar eine Lösung von $(S)$ bildet.

Gemäß (i) gibt es in diesem Fall zu $x^{*}$ eine Lösung $({\tilde {y}},{\tilde {s}})$ von $(D)$, so dass $(x^{*},{\tilde {y}},{\tilde {s}})$ das System $(S)$ läst und somit $x^{*T}{\tilde {s}}=0$ gilt. Nach (4.10) hat man also

(4.12) $\max _{(y,s)\in Z_{D}}(b,0)^{T}(y,s)=b^{T}{\tilde {y}}=c^{T}x^{*}=\min _{x\in Z_{P}}c^{T}x.$

Dies impliziert $b^{T}y^{*}=c^{T}x^{*}$ und somit nach (4.10) $x^{*T}s^{*}=0$. Also folgt, dass $(x^{*},y^{*},s^{*})$ eine Lösung von $(S)$ ist. Die Umkehrung von Aussage von (ii) kann man unmittelbar aus Abschnitt 4.6.1 schließen.

q.e.d.

Bei einem Satz, der als Aussage die Identität (4.12) beinhaltet, spricht man von einem starken Dualitätssatz. Aus historischen Gründen geben wir als nächstes einen solchen Satz an. Bis auf Aussage (i) ist dieser in Satz 4.17 enthalten.

Satz 4.18 (Starker Dualitätssatz)

(i) Gilt $Z_{P}\neq \emptyset$ und $Z_{D}\neq \emptyset$, so besitzen beide Probleme $(P)$ und $(D)$ eine Lösung.

(ii) $x^{*}$ und $(y^{*},s^{*})$ sind genau dann Lösungen von $(P)$ und $(D)$, wenn $x^{*}\in Z_{P},(y^{*},s^{*})\in Z_{D}$ und $c^{T}x^{*}=b^{T}y^{*}$ (bzw. $x^{*T}s^{*}=0$) gilt.

Beweis.

(i) Man wähle ein $(y,s)\in Z_{D}$. Dann folgt aus Satz 4.16

$-\infty <b^{T}y\leq c^{T}x,\quad x\in Z_{P}$

und damit aus Satz 4.13, dass $(P)$ eine Lösung besitzt. Für $(D)$ kann man analog schließen. Aussage (ii) ist eine Folge der Sätze 4.16 und 4.17.

q.e.d.

Aus den Dualitätssätzen leiten wir weitere Aussagen ab. Die nachfolgende wird uns später ein Abbruchkriterium für Algorithmen liefern.

Korollar 4.19

Seien ${\bar {x}}\in Z_{P}$ und $({\bar {y}},{\bar {s}})\in Z_{D}$ mit

(4.13) $0\leq {\bar {x}}^{T}{\bar {s}}=c^{T}{\bar {x}}-b^{T}{\bar {y}}\leq \varepsilon$

für ein $\varepsilon \geq 0$ gegeben. Dann besitzen $(P)$ und $(D)$ eine Lösung und gilt

$\min _{x\in Z_{P}}c^{T}x\leq c^{T}{\bar {x}}\leq \left(\min _{x\in Z_{P}}c^{T}x\right)+\varepsilon ,$

$\left(\max _{(y,s)\in Z_{D}}(b,0)^{T}(y,s)\right)-\varepsilon \leq b^{T}{\bar {y}}\leq \max _{(y,s)\in Z_{D}}(b,0)^{T}(y,s).$

Beweis.

Nach Satz 4.18 existieren Lösungen $x^{*}$ und $(y^{*},s^{*})$ von $(P)$ und $(D)$. Für solche Punkte liefern der schwache und der starke Dualitätssatz mit (4.13)

$c^{T}x^{*}\leq c^{T}{\bar {x}}\leq b^{T}{\bar {y}}+\varepsilon \leq c^{T}x^{*}+\varepsilon$

und

$b^{T}y^{*}-\varepsilon =c^{T}x^{*}-\varepsilon \leq c^{T}{\bar {x}}-\varepsilon \leq b^{T}{\bar {y}}\leq b^{T}y^{*}.$

q.e.d.

Für ein primal und dual zulässiges Punktepaar $x\in Z_{P}$ und $(y,s)\in Z_{D}$ bezeichnet man die nichtnegative Zahl $x^{T}s=b^{T}y-c^{T}x$ als Dualitätslücke. Ist diese für ein $\varepsilon >0$ kleiner oder gleich $\varepsilon$, wie in (4.13) gefordert, so sprechen wir aufgrund von Korollar 4.19 von $\varepsilon$-optimalen Lösungen von $(P)$ und $(D)$.

Eine weitere wichtige Folgerung aus dem Vorangegangenen ist die folgende.

Korollar 4.20

(i) Es sei $Z_{P}\neq \emptyset$. Dann gilt:

$\inf _{x\in Z_{P}}c^{T}x=-\infty \Leftrightarrow Z_{D}=\emptyset .$

(ii) Es sei $Z_{D}\neq \emptyset$. Dann gilt:

$\sup _{(y,s)\in Z_{D}}(b,0)^{T}(y,s)=+\infty \Leftrightarrow Z_{P}=\emptyset .$

Beweis.

(i) Sei $\inf _{x\in Z_{P}}c^{T}x=-\infty$. Gäbe es ein $(y,s)\in Z_{D}$, so folgte aus Satz 4.16 im Widerspruch zur Annahme, dass $b^{T}y\leq c^{T}x$ für alle $x\in Z_{P}$ ist. Ist andererseits $\inf _{x\in Z_{P}}c^{T}x>-\infty$, so ist nach Satz 4.13 die Lösungsmenge von $(P)$ und daher nach Satz 4.18 auch die von $(D)$ nichtleer. Also ist insbesondere $Z_{D}\neq \emptyset$.

Aussage (ii) folgt unter Verwendung von (1.2) entsprechend.

q.e.d.

4.6.3 Strikte Komplementarität

In Abschnitt 4.6.1 haben wir festgestellt, dass ein Punktepaar $x^{*}$ und $(y^{*},s^{*})$ genau dann optimal für $(P)$ und $(D)$ ist, wenn es primal bzw. dual zulässig ist und der Komplementaritätsbedingung $x^{*T}s^{*}=0$ genügt, was gleichbedeutend damit ist, dass die zugehörige Dualitätslücke den Wert Null hat. In diesem Abschnitt beweisen wir, dass es immer ein Lösungspaar $x^{*}$ und $(y^{*},s^{*})$ von $(P)$ und $(D)$ gibt, für das die strikte Komplementaritätsbedingung erfüllt ist, d. h. für das gilt:

entweder $x_{i}^{*}=0$ oder $s_{i}^{*}=0\quad (i=1,\ldots ,n)$.

Letztere Eigenschaft lässt sich wegen $x^{*}\geq 0$ und $s^{*}\geq 0$ äquivalent ausdrücken durch

(4.14) $x^{*T}s^{*}=0,\quad x^{*}+s^{*}>0.$

Satz 4.21

Besitzen die Probleme $(P)$ und $(D)$ eine Lösung, so existieren auch Lösungen $x^{*}$ und $(y^{*},s^{*})$ von $(P)$ und $(D)$, für die (4.14) gilt.

Beweis.

Wir wollen zeigen, dass zu jedem $j\in \{1,\ldots ,n\}$ ein Lösungspaar $x^{*j}$ und $(y^{*j},s^{*j})$ der Probleme $(P)$ und $(D)$ mit $(x^{*j}+s^{*j})_{j}>0$ existiert. Denn dann folgt für

$x^{*}:=\sum _{j=1}^{n}t_{j}x^{*j},\qquad (y^{*},s^{*}):=\sum _{j=1}^{n}t_{j}(y^{*j},s^{*j}),\quad t_{j}>0\quad (j=1,\ldots ,n),\quad \sum _{j=1}^{n}t_{j}=1$

wegen der Konvexität der Lösungsmengen von $(P)$ und $(D)$ (siehe Satz 2.37), dass $x^{*}$ und $(y^{*},s^{*})$ die Probleme $(P)$ und $(D)$ lösen und somit (s. Satz 4.18) $x^{*T}s^{*}=0$ ist und dass gilt:

$x^{*}+s^{*}=\sum _{j=1}^{n}t_{j}(x^{*j}+s^{*j})>0.$

Sei also $j\in \{1,\ldots ,n\}$ fest gewählt. Existiert eine Lösung $x^{*j}$ von $(P)$ mit $x_{j}^{*j}>0$, so ist für jede Lösung $(y^{*j},s^{*j})$ von $(D)$ wegen $s^{*j}\geq 0$ trivialerweise $(x^{*j}+s^{*j})_{j}>0$. Daher gelte

(4.15) $x_{j}^{*}=0$ für jede Lösung $x^{*}$ von $(P)$.

Wir betrachten nun das Problem

${\begin{array}{lll}(P_{j}):&{\text{Minimiere}}&-x_{j}\\&{\text{u. d. N.}}&{\begin{pmatrix}A&0\\c^{T}&1\end{pmatrix}}{\begin{pmatrix}x\\x_{n+1}\end{pmatrix}}={\begin{pmatrix}b\\\mu \end{pmatrix}},\\&&(x,x_{n+1})\geq 0\end{array}}$

und das zugehörige duale Problem

${\begin{array}{lll}(D_{j}):&{\text{Maximiere}}&(b,\mu )^{T}(y,y_{m+1})\\&{\text{u. d. N.}}&{\begin{pmatrix}A^{T}&c\\0&1\end{pmatrix}}{\begin{pmatrix}y\\y_{m+1}\end{pmatrix}}+{\begin{pmatrix}s\\s_{n+1}\end{pmatrix}}={\begin{pmatrix}-e^{j}\\0\end{pmatrix}},\\&&0(s,s_{n+1})\geq 0,\end{array}}$

wobei $\mu$ der optimale Zielfunktionswert von $(P)$ und $(D)$ ist. Jeder zulässige Punkt $(x,x_{n+1})$ von $(P_{j})$ genügt $x\in Z_{P}$ und wegen $x_{n+1}\geq 0$ insbesondere $c^{T}x\leq \mu$. Also ist $x$ Lösung von $(P)$ und notwendig $x_{n+1}=0$. Weiter folgt damit aus (4.15), dass der Zielfunktionswert von $(P_{j})$ für jeden zulässigen Punkt von $(P_{j})$ identisch Null ist. Nach Satz 4.18 besitzt somit $(D_{j})$ eine Lösung $(y^{j},y_{m+1}^{j},s^{j},s_{n+1}^{j})$ mit optimalem Zielfunktionswert Null. Für diese gilt

(4.16) $b^{T}y^{j}+\mu y_{m+1}^{j}=0$

und

(4.17) $A^{T}y^{j}+y_{m+1}^{j}c+s^{j}=-e^{j},\quad y_{m+1}^{j}+s_{n+1}^{j}=0.$

Wegen $s_{n+1}^{j}\geq 0$ muss insbesondere $y_{m+1}^{j}\leq 0$ sein.

Sei zunächst $y_{m+1}^{j}=0$. Für jede Lösung $(y^{*},s^{*})$ von $(D)$ gilt

(4.18) $c=A^{T}y^{*}+s^{*},$

was zu (4.17) addiert,

$A^{T}(y^{j}+y^{*})+(s^{*}+s^{j}+e^{j})=c$

liefert. Wegen $s^{*}+s^{j}+e^{j}\geq 0$ folgt

$(y^{*j},s^{*j}):=(y^{*}+y^{j},s^{*}+s^{j}+e^{j})\in Z_{D}.$

Da (4.16)

$b^{T}y^{*j}=b^{T}y^{*}+b^{T}y^{j}=b^{T}y^{*}=\mu$

impliziert, muss $(y^{*j},s^{*j})$ eine Lösung von $(D)$ sein. Ferner ist

$s_{j}^{*j}:=(s^{*}+s^{j}+e^{j})_{j}\geq 1,$

so dass man in diesem Fall $(x^{*}+s^{*j})_{j}>0$ für jede Lösung $x^{*}$ von $(P)$ schließt.

Nun sei $y_{m+1}^{j}<0$. Dann folgt aus (4.16) und (4.17) für ${\tilde {y}}^{j}:=y^{j}/(-y_{m+1}^{j})$

$b^{T}{\tilde {y}}^{j}=\mu ,\quad A^{T}{\tilde {y}}^{j}+{\frac {s^{j}+e^{j}}{-y_{m+1}^{j}}}=c,$

so dass man wegen ${\tilde {s}}^{j}:=(s^{j}+e^{j})/(-y_{m+1}^{j})\geq 0$ folgert, dass $({\tilde {y}}^{j},{\tilde {s}}^{j})$ Lösung von $(D)$ ist. Schließlich ist ${\tilde {s}}_{j}^{j}>0$ und damit wiederum $(x^{*}+{\tilde {s}}^{j})_{j}>0$ für jede Lösung $x^{*}$ von $(P)$.

q.e.d.

In Verbindung mit den Ergebnissen von Abschnitt 4.6.1 können wir also im Hinblick auf das System

${\begin{array}{lrll}(S^{*}):&Ax=b,&x\geq 0,&{\mbox{(primale Zulässigkeit)}},\\&A^{T}y+s=c,&s\geq 0,&{\mbox{(duale Zulässigkeit)}},\\&x^{T}s=0,&x+s>0,&{\mbox{(strikte Komplementarität)}}\end{array}}$

schließen:

Korollar 4.22

Es gilt:

$(P)$ ist lösbar $\Leftrightarrow (S^{*})$ ist lösbar $\Leftrightarrow (D)$ ist lösbar.

Wir schließen mit einem Beispiel ab.

Beispiel 4.23

Gegeben sei das Problem

${\begin{array}{ll}{\text{Minimiere}}&x_{1}\\{\text{u. d. N.}}&x_{1}+x_{2}+x_{3}=1,\\&x\geq 0,\end{array}}$

mit zugehörigem dualen Problem

${\begin{array}{ll}{\text{Maximiere}}&y\\{\text{u. d. N.}}&y{\begin{pmatrix}1\\1\\1\end{pmatrix}}+{\begin{pmatrix}s_{1}\\s_{2}\\s_{3}\end{pmatrix}}={\begin{pmatrix}1\\0\\0\end{pmatrix}},\\&s\geq 0.\end{array}}$

Für jedes $t\in [0,1]$ ist $(x_{t}^{*},y_{t}^{*},s_{t}^{*})$ mit

$x_{t}^{*}:=(0,t,1-t)^{T},\quad y_{t}^{*}:=0,\quad s_{t}^{*}:=(1,0,0)^{T}$

eine Lösung des Systems $(S)$, welches hier lautet:

${\begin{array}{rl}x_{1}+x_{2}+x_{3}=1,&x\geq 0,\\y{\begin{pmatrix}1\\1\\1\end{pmatrix}}+{\begin{pmatrix}s_{1}\\s_{2}\\s_{3}\end{pmatrix}}={\begin{pmatrix}1\\0\\0\end{pmatrix}},&s\geq 0,\\x^{T}s=0.\end{array}}$

Gemäß Satz 4.17 ist damit $x_{t}^{*}$ eine Lösung von $(P)$ und $(y_{t}^{*},s_{t}^{*})$ eine von $(D)$. Man sieht ferner, dass $(x_{t}^{*},y_{t}^{*},s_{t}^{*})^{T}$ genau dann die Bedingung $x_{t}^{*}+s_{t}^{*}>0$ erfüllt, d. h. genau dann eine Lösung von $(S^{*})$ ist, wenn $t\in (0,1)$ ist.

---

4.6.4 Das duale Problem zu einem Problem in beliebiger Form

In Abschnitt 4.1 haben wir festgestellt, dass sich jedes LOP äquivalent in ein LOP in Normalform umschreiben lässt. Demnach kann jedem (primalen) LOP mittels der Ergebnisse aus Abschnitt 4.6.1 ein duales LOP zugeordnet werden. Wir führen dies zunächst anhand des Problems

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

vor. Dieses ist äquivalent mit dem Problem

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

Zu letzterem Problem gehört nach Abschnitt 4.6.1 das duale Problem

${\begin{array}{ll}{\text{Maximiere}}&-b^{T}z\\{\text{u. d. N.}}&{\begin{pmatrix}-A^{T}\\I\end{pmatrix}}z\leq {\begin{pmatrix}c\\0\end{pmatrix}}.\end{array}}$

Setzt man $y:=-z$, so bekommt dieses Problem die einfachere Gestalt

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

Mit den Schlupfvariablenvektoren

$r:=Ax-b\geq 0,\quad s:=c-A^{T}y\geq 0$

für $({\hat {P}})$ und $({\hat {D}})$ erhalten wir für Punkte $x$ und $y$, welche zulässig für $({\hat {P}})$ und $({\hat {D}})$ sind, die schwache Dualitätsaussage

$0\leq s^{T}x+r^{T}y=\left(c^{T}-y^{T}A\right)x+y^{T}(Ax-b)=c^{T}x-b^{T}y$

und die Komplementaritätsbedingung

$s^{T}x+r^{T}y=0.$

Ähnlich kann man auch für ein allgemeines Minimierungsproblem $({\tilde {P}})$ mit $m_{1}$ „$\geq$“-Restriktionen, $m_{2}$ Gleichheitsrestriktionen, $n_{1}$ nichtnegativen und $n_{2}$ freien Variablen ein duales Problem $({\tilde {D}})$ aufstellen, wobei man sinnvollerweise $n_{1}+n_{2}\neq 0$ und $m_{1}+m_{2}\neq 0$ annimmt. („$\leq$“-Restriktionen seien bereits als „$\geq$“-Restriktionen beschrieben worden.) Spaltet man die in $({\tilde {P}})$ und $({\tilde {D}})$ vorkommenden Größen wie folgt auf:

$A:={\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{pmatrix}},\quad b:={\begin{pmatrix}b_{1}\\b_{2}\end{pmatrix}},\quad y:={\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}},$

$A^{T}:={\begin{pmatrix}A_{11}^{T}&A_{21}^{T}\\A_{12}^{T}&A_{22}^{T}\end{pmatrix}},\quad c:={\begin{pmatrix}c_{1}\\c_{2}\end{pmatrix}},\quad x:={\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}},$

so gelangt man zu folgendem Paar von Problemen

${\begin{array}{llllll}({\tilde {P}}):&{\text{Min.}}&c_{1}^{T}x_{1}+c_{2}^{T}x_{2}&({\tilde {D}}):&{\text{Max.}}&b_{1}^{T}y_{1}+b_{2}^{T}y_{2}\\&{\text{u. d. N.}}&A_{11}x_{1}+A_{12}x_{2}\geq b_{1},&&{\text{u. d. N.}}&y_{1}\geq 0,\\&&A_{21}x_{1}+A_{22}x_{2}=b_{2},&&&y_{2}{\text{ frei}},\\&&x_{1}\geq 0,&&&A_{11}^{T}y_{1}+A_{21}^{T}y_{2}\leq c_{1},\\&&x_{2}{\text{ frei}},&&&A_{12}^{T}y_{1}+A_{22}^{T}y_{2}=c_{2}.\end{array}}$

Offenbar gehen „$\geq$“-Restriktionen im primalen Problem in „$\geq$“-Variable im dualen Problem über, Gleichheitsrestriktionen in freie Variable, „$\geq$“-Variable in „$\leq$“-Restriktionen und freie Variable in Gleichheitsrestriktionen.

Die Paare $(P)$ und $(D)$ bzw. $({\hat {P}})$ und $({\hat {D}})$ sind Spezialfälle von $({\tilde {P}})$ und $({\tilde {D}})$. Da die Probleme $({\tilde {P}})$ und $({\tilde {D}})$ auf äquivalente Probleme des Typs $(P)$ und $(D)$ zurückgeführt werden können, sieht man leicht ein, dass die Aussagen der Sätze 4.15, 4.16 und 4.18 entsprechend auch für sie gelten. Sind $Z_{\tilde {P}}$ und $Z_{\tilde {D}}$ die zulässigen Gebiete von $({\tilde {P}})$ und $({\tilde {D}})$, so hat man daher zusammengefasst:

Korollar 4.24

(i) Das duale Problem zu $({\tilde {D}})$ ist äquivalent zu $({\tilde {P}})$.

(ii) Für $x\in Z_{\tilde {P}}$ und $y\in Z_{\tilde {D}}$ gilt $0\leq c^{T}x-b^{T}y$.

(iii) Gilt $Z_{\tilde {P}}\neq \emptyset$ und $Z_{\tilde {D}}\neq \emptyset$, so haben die Probleme $({\tilde {P}})$ und $({\tilde {D}})$ Lösungen.

(iv) $({\tilde {P}})$ besitzt genau dann eine Lösung, wenn $({\tilde {D}})$ eine Lösung hat.

(v) $x^{*}$ und $y^{*}$ lösen $({\tilde {P}})$ und $({\tilde {D}})$ genau dann, wenn $x^{*}\in Z_{\tilde {P}},y^{*}\in Z_{\tilde {D}}$ gilt und $c^{T}x^{*}=b^{T}y^{*}$ ist.

4.6.5 Ein Beispiel

In der Praxis ist es manchmal effizienter, statt des gegebenen LOPs das dazu duale Problem zu lösen (sofern man nicht ein primal-duales Verfahren verwendet). Ein Beispiel, wo man das tun sollte, ist das im folgenden beschriebene diskrete lineare Tschebyscheff-Problem.

Gegeben seien $m$ Punkte $\xi _{j}\in \mathbb {R} ^{q}$ $(j=1,\ldots ,m)$ und dazu gehörige Werte $f_{j}$ $(j=1,\ldots ,m)$, welche z. B. Messwerte oder Funktionswerte $f_{j}:=f(\xi _{j})$ einer bekannten, in den $\xi _{j}$ definierten Funktion $f$ sein können. Weiter seien $n$ in den $\xi _{j}$ definierte Ansatzfunktionen $v_{i}$ $(i=1,\ldots ,n)$ gegeben (z.B. die Monome $v_{i}(\xi ):=\xi ^{i-1})$. Ziel ist es, die $f_{j}$ durch eine Linearkombination der $v_{i}$ (im Fall der Monome also durch ein Polynom vom Grad $n-1$) in den Punkten $\xi _{j}$ bezüglich der Maximumnorm mit kleinst möglichem Fehler zu approximieren, also folgendes Problem zu lösen:

$(T):\min _{x\in \mathbb {R} ^{n}}\max _{1\leq j\leq m}\left|f_{j}-\sum _{i=1}^{n}x_{i}v_{i}(\xi _{j})\right|.$

Wir wollen $(T)$ als ein LOP schreiben. Dazu führen wir den zusätzlichen Parameter

$x_{n+1}:=\max _{1\leq j\leq m}\left|f_{j}-\sum _{i=1}^{n}x_{i}v_{i}(\xi _{j})\right|$

ein. Fassen wir $x_{n+1}$ als zusätzliche Komponente des Variablenvektors auf, so erhalten wir das zu $(T)$ äquivalente Problem

${\begin{array}{ll}{\text{Minimiere}}&x_{n+1}\\{\text{u. d. N.}}&\max _{1\leq j\leq m}\left|f_{j}-\sum \limits _{i=1}^{n}x_{i}v_{i}(\xi _{j})\right|\leq x_{n+1}\end{array}}$

mit Variablenvektor $x\in \mathbb {R} ^{n+1}$. Der optimale Zielfunktionswert $x_{n+1}^{*}$ gibt offenbar gerade den kleinst möglichen Approximationsfehler an. (Analog kann man übrigens jedes Optimierungsproblem in eines mit linearer Zielfunktion überführen.)

Die Ungleichungsrestriktion in dem letzten Problem lässt sich äquivalent durch die $m$ Restriktionen

(4.19) $\left|f_{j}-\sum _{i=1}^{n}x_{i}v_{i}(\xi _{j})\right|\leq x_{n+1}\quad (j=1,\ldots ,m)$

ausdrücken, so dass wir durch Auflösung der Beträge zu folgendem äquivalenten linearen Optimierungsproblem gelangen:

${\begin{array}{ll}{\text{Minimiere}}&x_{n+1}\\{\text{u. d. N.}}&-\left(f_{j}-\sum \limits _{i=1}^{n}x_{i}v_{i}(\xi _{j})\right)\leq x_{n+1}\quad (j=1,\ldots ,m),\\&+\left(f_{j}-\sum \limits _{i=1}^{n}x_{i}v_{i}(\xi _{j})\right)\leq x_{n+1}\quad (j=1,\ldots ,m).\end{array}}$

Letzteres Problem ist ein lineares Optimierungsproblem. Mit den Definitionen

$B:={\begin{pmatrix}v_{1}(\xi _{1})&\ldots &v_{n}(\xi _{1})\\\vdots &\ddots &\vdots \\v_{1}(\xi _{m})&\ldots &v_{n}(\xi _{m})\end{pmatrix}},\quad e:={\begin{pmatrix}1\\\vdots \\1\end{pmatrix}},\quad d:={\begin{pmatrix}f_{1}\\\vdots \\f_{m}\end{pmatrix}}$

und den Daten $c:=(0,\ldots ,0,1)^{T}\in \mathbb {R} ^{n+1}$ sowie

$A:={\begin{pmatrix}B&-e\\-B&-e\end{pmatrix}}\in \mathbb {R} ^{2m\times (n+1)},\quad b:={\begin{pmatrix}d\\-d\end{pmatrix}}\in \mathbb {R} ^{2m}$

bekommt es die Gestalt

${\begin{array}{lll}(P_{T}):&{\text{Minimiere}}&c^{T}x\\&{\text{u. d. N.}}&Ax\leq b.\end{array}}$

Wie sich aus der Herleitung ergibt, könnte man zu $(P_{T})$ noch die Bedingung

(4.20) $x_{n+1}\geq 0$

hinzufügen. Man muss dies aber nicht tun, da sie wegen (4.19) für zulässige Punkte automatisch erfüllt ist.

Wegen (4.20) ist insbesondere $c^{T}x\geq 0$ für alle für $(P_{T})$ zulässigen Punkte $x\in \mathbb {R} ^{n+1}$. Die Menge der für $(P_{T})$ zulässigen Punkte ist nichtleer, da man nach beliebiger Wahl von $x_{1},\ldots ,x_{n}$ die Komponente $x_{n+1}$ so wählen kann, dass alle Ungleichungen in $(P_{T})$ erfüllt sind. Nach Satz 4.13 besitzt daher $(P_{T})$ und damit auch das Ausgangsproblem $(T)$ eine Lösung.

Zum Erreichen der Normalform, von der viele Algorithmen der linearen Optimierung ausgehen, müsste man nach Hinzufügung der Ungleichung (4.20) $2m$ Schlupfvariable und $n$ zusätzliche Variable für die $n$ vorzeichenfreien Variablen einführen. Das zu $(P_{T})$ gehörende Problem in Normalform hätte also

$2m$ Gleichungsrestriktionen und $2n+2m+1$ Variable.

Das zu $(P_{T})$ duale Problem lautet

${\begin{array}{lll}(D_{T}):&{\text{Maximiere}}&-b^{T}u\\&{\text{u. d. N.}}&-A^{T}u=c,\\&&u\geq 0.\end{array}}$

Dieses LOP hat offenbar bereits die Normalform und

$n+1$ Gleichungsrestriktionen und $2m$ Variable.

(Hätten wir die Bedingung (4.20) in $(P_{T})$ explizit mitberücksichtigt, so hätte uns dies eine unerwünschte „$\leq$“-Restriktion im dualen Problem eingebracht.)

In der Praxis ist die Punktzahl $m$ im allgemeinen sehr viel größer als die Variablenzahl $n$. Realistisch ist eine Beziehung $m\approx C\cdot n$, wobei $C$ mindestens gleich 10 und häufig sehr viel größer als 10 ist. Nehmen wir z. B. $m=10n$ an, so stehen also

$20n$ Gleichungsrestriktionen und $22n+1$ Variable

des primalen Problems $(P_{T})$

$n+1$ Gleichungsrestriktionen und $20n$ Variablen

des dualen Problems $(D_{T})$ gegenüber.

Die Anzahl der Iterationen, die z. B. der Simplexalgorithmus benötigt, wird im Normalfall vornehmlich durch die Anzahl der Gleichungsrestriktionen bestimmt. (Dantzig, der 1947 den im nächsten Kapitel beschriebenen Simplexalgorithmus zur Lösung linearer Optimierungsprobleme entwickelt hatte, hat aufgrund von langjährigen Erfahrungen die Vermutung geäußert, dass dieser im Mittel $m\ln(n)$ Iterationen für ein LOP in Normalform mit $A\in \mathbb {R} ^{m\times n}$ benötigt.) Bei Verwendung dieses Verfahrens ist es daher üblicherweise sehr viel effizienter, anstelle von $(P_{T})$ das Problem $(D_{T})$ zu lösen. Löst man $(D_{T})$ mit dem Simplexalgorithmus, so liefert einem dieser (wie die meisten Verfahren zur Lösung linearer Optimierungsprobleme) gleichzeitig eine Lösung des dazu dualen Problems $(P_{T})$ mit, an der man ja hauptsächlich interessiert ist (s. Abschnitt 5.5).