Ulrich Faigle - zaik.uni-koeln.de · Konvexe Funktionen 35 1. Differenzierbare konvexe Funktionen...

EINFUHRUNG IN DIE MATHEMATIKDES OPERATIONS RESEARCH

Ulrich Faigle

Skriptum zur Vorlesung

Sommersemester 2006Universitat zu Koln

Universitat zu KolnMathematisches Institut

Zentrum fur Angewandte InformatikWeyertal 80

[email protected]/AFS

Inhaltsverzeichnis

Kapitel 1. Theorie linearer Ungleichungssysteme 31. Halbraume, Hyperebenen und abgeschlossene konvexe Mengen 42. Trennung 53. Dimension und affine Hulle 84. Seitenflachen und Extrempunkte 105. Der Algorithmus von Fourier-Motzkin 116. Zwei Anwendungen 19

Kapitel 2. Polyeder und Polytope 231. Darstellung und Dekomposition von Polyedern 232. Optimierung linearer Funktionen 273. Rezessionskegel und polyedrische Kegel 284. Polytope 285. Facetten und Basislosungen 326. Rationale Polyeder 33

Kapitel 3. Konvexe Funktionen 351. Differenzierbare konvexe Funktionen 352. Minimierung konvexer Funktionen 373. Newtons Methode und die Methode innerer Punkte 44

Kapitel 4. Die Simplexmethode 471. LP-Dualitat 482. Die Simplexmethode 503. Die Zweiphasenmethode 564. Die primal-duale Methode 59

Kapitel 5. Ganzzahlige lineare Programme 611. Schnittebenen 612. Unimodularitat 66

Kapitel 6. Flusse in Netzwerken 691. Das Matching-Polytop 712. Kurzeste Wege 713. Zirkulationen und das MAX-Flow-MIN-Cut-Theorem 734. Der Algorithmus von Ford-Fulkerson 76

1

2 INHALTSVERZEICHNIS

5. Der Prafluss-Markierungsalgorithmus 77

KAPITEL 1

Theorie linearer Ungleichungssysteme

Wir betrachten Ungleichungssysteme der folgenden Form

aTi x ≤ bi (i ∈ I).

Hier ist I eine (endliche oder unendliche) Indexmenge. Die Parameter

aTi = [ai1,, . . . , ain] ∈ Rn und bi ∈ R

sind als gegeben vorausgesetzte Koordinatenvektoren und reelle Zahlen.Fur die Anwendungen ist es oft wichtig, sich auf den rationalen ZahlkorperQ zu beschranken. Unser Problem ist nun:

• Bestimme ein x ∈ Rn, das alle diese Ungleichungenn∑

j=1

aijxj ≤ bi (i ∈ I)

erfullt, oder stelle fest, dass kein solches x existiert.

Mit A = [aij] bezeichnen wir die (moglicherweise unendliche) Matrix mitden n-dimensionalen Zeilenvektoren aT

i . D.h. A ist die Abbildung

A : I × {1, . . . , n} → R mit A(i, j) = aij.

Entsprechend ist b = [bi] ∈ RI der Koeffizentenvekor der rechten Seite desUngleichungssystems. Wir notieren das Ungleichungssystem dann kurz als

Ax ≤ b ←→n∑

j=1

aijxj ≤ bi (i ∈ I).

Die Losungsmenge des Ungleichungssystem ist

P (A,b) = {x ∈ Rn | Ax ≤ b}.

EX. 1.1. Ein lineares Gleichungssystem Ax = b mit A ∈ Rm×n und b ∈Rm ist aquivalent mit dem Ungleichungssystem

Ax ≤ b−Ax ≤ −b

3

4 1. THEORIE LINEARER UNGLEICHUNGSSYSTEME

Die Losungsmenge A = {x ∈ Rn | Ax = b} ist ein sog. affiner Teilraumvon Rn.

EX. 1.2. Wir betrachten eine Matrix X = [xij] ∈ Rn×n als n2-dimensionalenKoordinatenvektor. Dann ist eine Losung X = [xij] des (unendlichen) Un-gleichungssystems∑n

i=1

∑nj=1 aiajxij ≥ 0 ([a1, . . . , an] ∈ Rn)

xij − xji = 0 (i, j = 1, . . . , n)

eine positiv semidefinite Matrix.

1. Halbraume, Hyperebenen und abgeschlossene konvexe Mengen

Wir betrachten zunachst den Fall, wo A nur aus einem einzigen Zeilenvek-tor aT besteht. Ist a 6= 0, so ist die Punktmenge

P (a, b) = {x ∈ Rn | aTx ≤ b}

ein sog. (n-dimensionaler) Halbraum. Im Fall a = 0 erhalten wir Rn =P (0, 0) als ”trivialen“ Halbraum. Ebenso ist die leere Menge ∅ = P (0,−1)ein trivialer Halbraum. Per Definition ist also die Losungsmenge eines li-nearen Ungleichungssystems immer ein Durchschnitt von Halbraumen.

EX. 1.3 (Hyperebenen). Die Hyperebene H(a, b) = {x ∈ Rn | aTx = b}ist Durchschnitt ihrer zugeordneten Halbraume

H(a, b) = P (a, b) ∩ P (−a,−b)

bzw. Losungsmenge des linearen Ungleichungssystems{a1x1 + . . . + anxn ≤ b−a1x1 − . . .− anxn ≤ −b

}←→ a1x1 + . . . + anxn = b.

Ein Halbraum P (a, b) ist eine konvexe Menge, d.h. es gilt

z(λ) = x+λ(y−x) ∈ P (a, b) fur alle x,y,∈ P (a, b) und rellen 0 < λ < 1.

Ausserdem ist P (a, b) (im Sinn der Analysis) abgeschlossen. Offensichtlichwird Abgeschlossenheit und Konvexitat unter Durchschnittsbildung erhal-ten. Also erhalten wir:

• Die Losungsmenge eines linearen Ungleichungssystems ist kon-vex und abgeschlossen.

Wir wollen nun zeigen, dass die konvexen abgeschlossenen Mengen im Rn

genau die Losungsmengen von linearen Ungleichungssystemen sind.

2. TRENNUNG 5

2. Trennung

Es sei nun S ⊆ Rn eine beliebige nichtleere, abgeschlossene und konvexeMenge. Die zentrale Beobachtung ist nun:

LEMMA 1.1 (Trennungslemma). Sei S konvex und abgeschlossen. Dannexistiert fur jedes y ∈ Rn \S ein Koordinatenvektor c ∈ Rn und ein x0 ∈ Sderart, dass

cTy > cTx0 ≥ cTx fur alle x ∈ S.

M.aW.: Mit z = cTx0 hat man y /∈ P (c, z) und S ⊆ P (c, z)

TERMINOLOGIE. Man sagt, dass die Hyperebene H = {x ∈ Rn | cTx =z} den Punkt y ∈ Rn von der Menge S ⊆ Rn trennt. H heisst Stutzhyper-ebene von S im Punkt x0.

Beweis des Trennungslemmas. Der wesentliche Punkt ist die Beobachtung, dassdas Minimierungsproblem

minx∈S‖y − x‖

eine optimale Losung x0 ∈ S besitzt. Sie Funktion x 7→ ‖x − y‖ ist namlichstetig auf Rn und wir durfen offenbar oBdA S als kompakt annehmen. (Ansonstenbeschranken wir uns auf die kompakte Menge

SR = {x ∈ S | ‖y − x‖ ≤ R},

wobei R > 0 so gross gewahlt ist, dass SR 6= ∅ gilt.) Da eine stetige Funktionauf einem Kompaktum ihre Extremwerte annimmt, wissen wir, dass eine Mini-mallosung x0 ∈ S existiert. Wir haben nun x0 6= y (wegen y /∈ S). Wir setzenc = y − x0 und rechnen nach, dass c die gewunschten Eigenschaften hat.

Wir zeigen zuerst cTx0 < cTy:

cTy − cTx0 = cT (y − x0) = ‖y − x0‖2 > 0.

Wir betrachten nun einen beliebigen Punkt x ∈ S und setzen

z(λ) = x0 + λ(x− x0) (0 < λ < 1).

Dann gilt z(λ) ∈ S und deshalb

‖c‖2 = ‖y − x0‖2 ≤ ‖y − z(λ)‖2 = ‖c− λ(x− x0)‖2.

Ausmultiplizieren ergibt

−2λcT (x− x0) + λ2‖x− x0| ≥ 0 bzw. − 2cT (x− x0) + λ‖x− x0‖ ≥ 0

und liefert

cTx− cTx0 = cT (x− x0) ≤12

limλ→0

λ‖x− x0‖2 = 0.

�


EX. 1.4. Die Voraussetzung der Abgeschlossenheit von S im Trennungs-lemma ist wichtig. Die Menge

S = {(x1, x2) | x21 + x2

2 < 1} ⊆ R2

ist konvex. Das Trennungslemma gilt aber nicht.

Man bemerke, dass man bei den Vekoren c im Trennungslemma ohne Be-schrankung der Allgemeinheit eine normierte Lange ‖c‖ = 1 fordern darf.

SATZ 1.1. Eine Teilmenge S ⊆ Rn ist genau dann konvex und abgeschlos-sen, wenn S Losungsmenge eines linearen Ungleichungssystems ist.

Beweis. Der Fall S = Rn oder S = ∅ ist trivial. In allen anderen Fallen erhaltenwir nach dem Trennungslemma

S =⋂y/∈S

Py,

wobei die Py Halbraume mit S ⊆ Py und y /∈ Py sind.�

2.1. Polaren. Einer Teilmenge S ⊆ Rn, die den Koordinatenursprung0 ∈ Rn enthalt, kann man auf zweierlei Arten eine konvexe Menge zu-ordnen. Einmal betrachten wir die Menge aller Konvexkombinationen (d.h.Linearkombinationen mit nichtnegativen Koeffizienten, die sich zu 1 auf-summieren):

conv S = {k∑

i=1

λisi | si ∈ S, λi ≥ 0,k∑

i=1

λ1 = 1}.

BEMERKUNG. Der Koeffizientenvektor (λ1, . . . , λk) einer Konvexkombinationist nichts anderes als eine Wahrscheinlichkeitsverteilung auf k ”Elementarereig-nissen “ im Sinne der Wahrscheinlichkeitsrechnung.

conv S ist die konvexe Hulle von S. Dual dazu definiert man

(1) Spol = {x ∈ Rn | sTx ≤ 1 fur alle s ∈ S}.

Spol ist die Polare zu S. Spol ist Losungsmenge eines linearen Unglei-chungssystems und deshalb abgeschlossen (und konvex). Stellen wir unsS als eine Matrix mit den Zeilenvektoren sT vor, so ist ja

Spol = P (S,1),

wobei b = 1 der Vektor mit allen Komponenten bi = 1 bedeutet.

2. TRENNUNG 7

MOTIVATION: Sei cTx ≤ z eine lineare Ungleichung, die von allen s ∈ S erfulltwird. Dann gilt z ≥ 0 (wegen 0 ∈ S). Im Fall z > 0 kann man die Koeffizientenper Division durch z skalieren und enthalt die aquivalente Ungleichung

cTx ≤ 1 (c = z−1c).

Spol ist gerade die Menge aller solcher Koordinatenvektoren c.

GEOMETRISCHE INTERPRETATION: Ein Vektor c 6= 0 ist Normalenvektor derHyperebene

H(c, 1) = {x ∈ Rn | cTx = 1}

mit Abstand d = ‖c‖−2 vom Ursprung 0. c gehort zu Spol genau dann, wenn derzugeordnete Halbraum, der den Ursprung 0 enthalt, auch die gesamte Menge S

umfasst.

Man macht sich leicht klar:

• S ⊆ (Spol)pol.• S ⊆ T =⇒ T pol ⊆ Spol.• Spol = (conv S)pol.

SATZ 1.2. Sei S ⊆ Rn eine beliebige nichtleere Menge mit 0 ∈ S.

(i) S ist ein konvex ⇐⇒ S = conv S.(ii) S ist eine abgeschlossene konvexe Menge ⇐⇒ S = (Spol)pol.

Beweis. Der Beweis von Behauptung (i) ist Routine. Wir zeigen (ii). Im FallS = (Spol)pol ist S ist S Durchschnitt von Halbraumen und somit konvex undabgeschlossen.

Sei nun umgekehrt S konvex und abgeschlossen. Wir betrachten ein Ungleichungs-system Ax ≤ b mit S = P (A,b). Wegen 0 ∈ S muss bi ≥ 0 fur jede Komponentebi von b gelten. Nach etwaiger Skalierung durfen wir somit oBdA bi ∈ {0, 1} an-nehmen.

Ersetzen wir weiterhin jede Ungleichung vom Typ aTi x ≤ 0 durch unendlich viele

Ungleichungen

(kai)T ≤ 1 (k ∈ N).

so durfen wir oBdA sogar

S = {x ∈ Rn | aTi x ≤ 1 (i ∈ I)}

annehmen. Das bedeutet aber ai ∈ Spol fur alle i ∈ I und folglich

S ⊆ (Spol)pol = Apol ⊆ S d.h. S = (Spol)pol.

�


3. Dimension und affine Hulle

Unter der Dimension des Ungleichungssystems Ax ≤ b versteht man gewohn-lich die Anzahl n der Variablen xj . Wir interessieren uns jedoch auch furdie Dimension des Losungsraums P (A,b). Allgemein definieren wir fureine beliebige Teilmenge S ⊆ Rn die (affine) Dimension

dim S = max{k | es gibt k + 1 affine unabhanige Punkte x0,x1 . . . ,xk ∈ S}.

Insbesondere ergibt sich dim ∅ = −1 und dim Rn = n.

ERINNERUNG: Eine Menge {x0, . . . ,xk} von Punkten ist affin unabhanging,wenn die Menge {x1 − x0, . . . ,xk − x0} von Vektoren linear unabhangig ist.

Unter der affinen Hulle von S versteht man die Menge aff S aller Punkte,die sich als affine Linearkombinationen aus S ausdrucken lassen:

aff S = {k∑

i=0

λisi | si ∈ S,k∑

i=0

λi = 1}.

aff S ist der kleinste affine Teilraum von Rn, der S enthalt und es gilt

dim S = dim aff S.

ERINNERUNG: Die affinen Teilraume A von Rn sind genau die Losungsmengenvon linearen Gleichungssystemen:

A = {x ∈ Rn | Ax = b}.

Bei Gleichungssystemen darf man (im Gegensatz zu Ungleichungssystemen!) im-mer A als endliche Matrix annehmen. Es gilt die Dimensionsformel

(2) dimA = n− rg A (rg A = (Zeilen/Spalten-)Rang von A)

3.1. Affine Transformationen. Unter einer affinen Transformation ver-steht man eine Abbildung T : Rn → Rm der Form

T (x) = Ax + t wobei A ∈ Rm×n, t ∈ Rm.

Affine Transformationen sind insbesondere stetige Abbildungen und manrechnet leicht nach:

• Affine Transformationen fuhren affine Teilraume in affine Teilraumeuber und Urbilder affiner Teilraume sind affine Teilraume.• Affine Transformationen erhalten Konvexitat und Urbilder konve-

xer Mengen sind konvex.

Also gilt

3. DIMENSION UND AFFINE HULLE 9

LEMMA 1.2. Affine Transformationen erhalten abgeschlossene konvexe Men-gen.

�

EX. 1.5 (Translationen). Fur ein festes t ∈ Rn ist die Translationsabbil-dung

x 7→ T (x) = x + t

affin. Sei P = P (c, z) = {x ∈ Rn | xT ≤ z} ein beliebiger Halbraum.Dann gilt

y ∈ T (P ) ⇐⇒ cT (y − t) ≤ z d.h. cTy ≤ z′ = z − cT t.

Folglich ergibt sich T (P ) = P (c, z′) wieder als Halbraum. Analog ver-halten sich naturlich auch beliebige Durchschnitte von Halbraumen unterVerschiebungen.

3.2. Abzahlbarkeit. Die Losungsmenge eines linearen Ungleichungs-systems ist zwar nicht unbedingt schon durch endlich viele Ungleichungenbeschreibbar. Eine abgeschlossene konvexe Menge S ⊆ Rn lasst sich je-doch immer durch ein System von (hochstens) abzahlbar vielen linearenUngleichungen darstellen.

Im Fall dim S = n folgt dies aus der Beobachtung, dass Qn in Rn dichtliegt. Fur jeden Punkt x ∈ S und jedes ε > 0 gilt dann

[S ∩ Uε(x)] ∩Qn 6= ∅.

Es genugt also, nur solche trennenden Halbraume Py zu betrachten, fur diey ∈ Qn gilt: Wenn wir alle rationalen Punkte einer ε-Umgebung Uε(y) vonS getrennt haben, dann ist auch y von S getrennt.

Im Fall dim S = m < n ist aff S isomorph zu Rm. Wahlen wir ein ent-sprechendes Koordinatensystem fur aff S konnen wir das obige Argumentebenso bzgl. Qk anwenden.

KOROLLAR 1.1. Genau dann ist S ⊆ Rn konvex und abgeschlossen, wennes eine hochstens abzahlbare Indexmenge I und Ungleichungen aT

i x ≤ bi

gibt mit der Eigenschaft

S = {x ∈ Rn | aTi x ≤ bi, i ∈ I}.

�


4. Seitenflachen und Extrempunkte

Sei S ⊆ Rn eine abgeschlossene konvexe Menge. Eine Teilmenge F ⊆ Sheisst Seitenflache von S wenn F ”Beruhrflache“ von S mit einer Hyerebe-ne ist, d.h. wenn es einenen Koordinatenvektor a 6= 0 und eine reelle Zahlb ∈ R gibt mit den Eigenschaften

(SF1) S ⊆ {x ∈ Rn | aTx ≤ b} = P (a, b).(SF2) F = {x ∈ S | aTx = b} = S ∩H(a, b).

Danach sind S und ∅ sicher Seitenflachen. Sie sind die sog. trivialen Sei-tenflachen. Die ubrigen (sofern sie existieren) sind die nicht-trivialen Sei-tenflachen. Ist F = {v} eine einelementige Seitenflache von S, so ist v einsog. Extrempunkt (oder Eckpunkt) von S.

Aus der Definition ergibt sich sofort, dass eine Seitenflache F von S selbereine abgeschlossene konvexe Menge ist. Wir haben

dim F ≤ dim S − 1 ⇐⇒ F 6= S.

Die Extrempunkte von S entsprechen den Seitenflachen F mit dim F = 0.

EX. 1.6. Sei S = {(x1, x2, x3) ∈ R2 | x21 +x2

2 +x23 ≤ 1}. Die nichttrivialen

Seitenflachen von S sind genau die Punkte auf der Kugeloberflache, diegleichzeitig auch die Extrempunkte von S sind.

EX. 1.7 (Stutzhyperebenen). Jede Stutzhyperebene H = H(c, b) ergibt einenichtleere Seitenflache von S. Sei x0 der Stutzpunkt von H: Dann gilt (SF1)wegen

cTx ≤ b = cTx0 fur alle x ∈ S.Die Seitenflache F = S ∩H enthalt x0 und ist folglich nichtleer.

PROPOSITION 1.1. Sind F1, F2 Seitenflachen der abgeschlossenen konve-xen Menge S ⊆ Rn, dann ist auch F = F1 ∩ F2 eine Seitenflache vonF .

Beweis. Sei F1 = S∩H(a1, b1) und F2 = S∩H(a2, b2). Wir setzen a = a1 +a2

und b = b1 + b2. Dann gilt nach Voraussetzung fur alle x ∈ S:

aT1 x ≤ b1,aT

2 x ≤ b2 und deshalb aTx ≤ b.

Ausserdem haben wir

aTx = b ⇐⇒ aT1 x = b1 und(!) aT

2 x = b2

und somit F = S ∩H(a, b).�

NOTA BENE: Wie schon das Beispiel des (Voll-)Kreises zeigt, ist die Verei-nigung F1 ∪ F2 von zwei Seitenflachen im allgemeinen keine Seitenflache!

5. DER ALGORITHMUS VON FOURIER-MOTZKIN 11

5. Der Algorithmus von Fourier-Motzkin

Wir diskutieren nun einen Algorithmus zum Losen linearer Ungleichungs-systeme, der naturlich nur bei endlichen Systemen praktisch durchfuhrbarist, aber doch auch bei unendlichen Systemen ”im Prinzip“ anwendbar ist.

Wir gehen aus von einem Ungleichungssystem

aTi x =

n∑j=1

aijxj ≤ bi (i ∈ I).

Wir wollen nun (ahnlich wie beim Gauss-Verfahren) die Variablen xj derReihe nach eliminieren und beginnen mit z.B. x1. Seien

I+ = {i ∈ I | ai1 > 0}, I− = {i ∈ I | ai1 < 0}, I0 = {i ∈ I | ai1 = 0}.Dividieren wir die Ungleichungen in I1 und I2 jeweils durch |ai1|, so erhal-ten wir das aquivalente System

(3)

x1 +∑j=2

a′rjxj ≤ b′r (r ∈ I+)

−x1 +∑j=2

a′sjxj ≤ b′s (s ∈ I−)∑j=2

atjxj ≤ bt (t ∈ I0)

x = (x1, x2, . . . , xn) ist also genau dann zulassige Losung, wenn gilt

(i) (x2, . . . , xn) erfulltn∑

j=2

atjxj ≤ bt fur alle t ∈ I0.

(ii) −bs +n∑

j=2

a′sjxj ≤ x1 ≤ br−n∑

j=2

a′rjxj fur alle r ∈ I+, s ∈ I−.

Gegeben (x2, . . . , xn), das (i) erfullt, so existiert ein x1, das (ii) erfullt, ge-nau dann, wenn gilt

(iii)n∑

j=2

(a′rj + a′sj)xj ≤ br + bs fur alle r ∈ I+ und s ∈ I−.

In diesem Fall konnen wir jedes x1 mit

(4) sups∈I−

(− bs +

n∑j=2

a′sjxj

)≤ x1 ≤ inf

r∈I+

(br −

n∑j=2

a′rjxj

)wahlen. Das heisst, wir gewinnen x1 per Rucksubstitution aus den schon alsbekannt angenommenen Grossen x2, . . . , xn.


BEMERKUNG. Wenn (iii) erfullt ist, existiert in der Tat ein x1, das (4) genugt. ImFall I∗ = ∅ oder I− = ∅ ist das offensichtlich. Im Fall I+ 6= ∅ 6= I− folgt dieBehauptung aus der Definition der reellen Zahlen.

LEMMA 1.3. Das System (3) ist aquivalent mit dem System

(i)n∑

j=2

aitxj ≤ bt (t ∈ I0)

(iii)n∑

j=2

(a′rj + a′sj)xj ≤ br + bs (r ∈ I+, s ∈ I−)

�

FM-Elimination. Lemma 1.3 fuhrt auf eine rekursive Beschreibung desEliminationsverfahrens bzgl. (3):

Fourier-MotzkinBerechne eine Losung (x2, . . . , xn) fur das System (i)&(iii);STOP wenn keine Losung existiert;Berechne x1 mit Ruckwartssubstitution nach (4).

EX. 1.8.3x + y − 2z ≤ 1

− 2y − 4z ≤ −14−x + 3y − 2z ≤ −2

y + 4z ≤ 132x − 5y + z ≤ 0

5.1. Losbarkeit und Satz der Alternative. Man bemerke: Das FM-Verfahren benutzt nur die folgenden Operationen auf dem Ungleichungssy-stem:

(i) Multiplikation einer Ungleichung mit einer positiven Zahl.(ii) Addition von zwei Ungleichungen.

Daraus folgt:• Nach jeder Elimination einer Variablen ist jede der Ungleichun-

gen des resultierenden Systems eine Linearkombination der Un-gleichungen des Ausgangssystems mit positiven Koeffizienten.

Wenn alle Variablen xj elimiert sind, sind die Koeffizienten auf der linkenSeite des Systems alle = 0. Das System ist losbar genau dann, wenn danndie Koeffizienten auf der rechten Seite alle nichtnegativ sind.

SATZ 1.3 (Satz der Alternative). Genau eine der Aussagen ist richtig:


(I) Das System Ax ≤ b besitzt eine Losung.(II) Es gibt nichtnegativen einen Vektor y ∈ RI mit nur endlich vielen

positiven Komponenten derart, dass

yT A = 0T und yTb < 0 .

BEMERKUNG. Die Ausdrucke yT A und yTb im Satz sind auch bei unendlicherIndexmenge I wohldefiniert. Wir nehmen ja an, dass nur endlich viele Komponen-ten yi von y von 0 verschieden sind. Also gibt es eine endliche Teilmenge I ′ ⊆ Iderart, dass

yT A =∑i∈I′

yiaTi und yTb =

∑i∈I′

yibi.

Beweis. Die beiden Aussagen konnen nicht gleichzeitig gelten, denn sonst hattenwir den Widerspruch

0 = 0Tx = yT Ax ≤ yTb < 0.

Um einzusehen, dass mindestens eine Aussage richtig ist, nehmen wir an, dass (I)falsch ist. Also gibt es (nach der FM-Elimination aller Variablen) eine nichtnega-tive Linearkombination der Ungleichungen aix ≤ bi mit Nullkoeffizienten linksund einem negativen Koeffizienten rechts. Wahlen wir y als den Vektor der Koef-fizienten dieser Linerkombination, so erhalten wir (II).

�

BEMERKUNG (LEMMA VON FARKAS). Im Fall eines endlichen Systems Ax ≤b ist der obige Alternativsatz auch als ”Lemma von Farkas“ bekannt. Es gibt aberauch noch eine andere Form des Lemmas von Farkas (s.u.).

KOROLLAR 1.2. Das System Ax ≤ b ist losbar genau dann, wenn jedesendliche Teilsystem A′x ≤ b′ losbar ist.

Beweis. Eine Losung x∗ von Ax ≤ b ist naturlich auch eine Losung des Teilsy-stems A′x ≤ b. Ist Ax ≤ b nicht losbar, so gilt Alternative (II) im Satz 1.3). DieAlternative (II) bezieht sich auf ein endliches Teilsystem. Also ist auch dieses nichtlosbar.

�

KOROLLAR 1.3 (Gordan). Sei A ∈ Rm×n eine Matrix. Dann gilt genaueine der Aussagen:

(I) Ax = 0,x ≥ 0 hat eine Losung x∗ 6= 0.(II) yT A < 0T hat eine Losung.

Beweis. Ubung.�

NOTATION. x < y bedeutet, dass die Relation xj < yj fur alle Komponentengilt.


5.2. Implizierte und gultige Ungleichungen. Sei S ⊆ Rn eine be-liebige nicht-leere Teilmenge und cTx ≤ z eine lineare Ungleichung. Wirsagen S impliziert cTx ≤ z, wenn gilt

cTx ≤ z fur alle x ∈ S.

Ebenso sagt man, dass cTx ≤ z eine fur S gultige Ungleichung ist. DieseImplikation erlaubt zwei Interpretationen:

OPTIMIERUNG:(i) supx∈S cTx ≤ z.

(ii) F = {x ∈| cTx = z} ist die Menge aller Optimallosungendes entsprechenden Maximierungsproblems.

GEOMETRIE:(i) Der Halbraum P (c, z) = {x ∈ Rn | cTx ≤ z} enthalt S.

(ii) F = {x ∈| cTx = z} ist eine Seitenflache von S.Man sagt, dass cTx ≤ z von Ax ≤ b impliziert wird, wenn die Unglei-chung cTx ≤ z von der Losungsmenge des Systems Ax ≤ b impliziertwird:

Ax∗ ≤ b =⇒ cTx ≤ z fur alle x∗ ∈ Rn.

Die zweite Form des ”Lemmas von Farkas“ ist nun:

LEMMA 1.4 (Farkas). Sei Ax ≤ b ein endliches losbares lineares Unglei-chungssystem. Dann wird cTx ≤ z von Ax ≤ b genau dann impliziert,wenn es einen Koeffizientenvektor y ≥ 0 gibt derart, dass

cT = yT A und yTb ≤ z.

Beweis. Sei cT = yT A eine nichtnegative Linearkombination von Zeilen von A.Dann gilt fur jede Losung x:

yT (b−Ax) ≥ 0 und folglich cTx = yT Ax ≤ yTb.

Also ist cTx ≤ z impliziert wennimmer z ≥ yTb. Die Bedingung ist also hinrei-chend. Um die Notwendigkeit einzusehen, betrachten wir das System

Ax ≤ b−cTx + xn+1 ≤ −z

Nach Annahme hat dieses keine Losung mit xn+1 > 0. Wir eliminieren nun allVariablen x1, . . . , xn. Im resultierenden System konnen nicht alle Koeffizienten inder Spalte von xn−1 den Wert 0 haben, da die FM-Methode nur positive Linear-kombinationen von Zeilen benutzt. Sei der Koeffizient ai,n+1 6= 0. Nun ist derKoeffizientenvektor Zeile i von der Form

y0(−cT , 1) + yT [A,0] mit ai,n+1 = y0 > 0, y ≥ 0 und y0cT = yT A.

Dividieren wir diese Zeile durch y0, so durfen wir annehmen:

cT = yT A, y ≥ 0 und ai,n+1 = 1.


Der Koeffizient auf der rechten Seite ist entsprechend (nach Division durch y0):

bi = −z + yTb

Waren diese (wegen der Endlichkeit von Ax ≤ b nur endlich vielen) Koeffizientenbi alle positiv, so gabe es eine Losuung mit xn+1 > 0. Also existiert mindestenseiner mit der gewunschten Eigenschaft

−z + yTb ≤ 0 d.h. yTb ≤ z

�

BEMERKUNG. Das Farkaslemma kann auf analoge Art auch fur ein unendlichesSystem Ax ≤ b abgeleitet werden, wenn die Losungsmenge S = P (A,b) kom-pakt ist. Das nachfolgende Beispiel zeigt, dass des Farkaslemma bei unendlichenSystemen ohne Zusatzannahmen falsch sein kann.

EX. 1.9. Sei S = {(x, y) ∈ R2 | x > 0, y ≥ 1/x}. S ist Losungsmenge desunendlichen Ungleichungssystems

1

r2x + y ≥ 2r (r ∈ R, r > 0)

Die Ungleichung x ≥ 0 gilt offenbar fur S. Sie lasst sich aber nicht alspositive (endliche) Linearkombination aus dem System ableiten.

5.2.1. Konstruktion von Seitenflachen. Das Lemma von Farkas (in sei-ner zweiten Form) liefert eine Methode, wie man im Prinzip alle Seiten-flachen einer durch das Ungleichungssystem Ax ≤ b beschriebenen abge-schlossenen und konvexen Menge S = P (A,b) konstruieren kann. Dabeinehmen wir gleich den nichttrivialen Fall S 6= ∅ an.

Wir wahlen eine beliebige endliche Teilmatrix AF und bilden daraus denVektor cT = 1T AF als die Summe alle Zeilenvektoren von AF . Weiterhinsei z = 1TbF die entsprechende Summe der rechten Seiten.

Da AFx ≤ bF ein Teilsystem von Ax ≤ b ist, ist die Ungleichung cTx ≤ zfur S gultig:

cTx = 1T AFx ≤ 1TbF = z fur alle x ∈ P (A,b).Folglich bestimmt die Teilmatrix AF eine Seitenflache

F = {x ∈ S | cTx = z} = {x ∈ Rn | Ax ≤ b, AFx = bF}

NOTA BENE: Im Fall AFx ≤ bF gilt immer:

1T AFx = 1TbF ⇐⇒ AFx = bF .


Es ist noch zu zeigen, dass man mit der obigen Methode tatsachlich allenichttrivialen Seitenflachen von P (A,b) erfasst. Sei z.B.

F = {x ∈ Rn | Ax ≤ b, cTx = z}

eine beliebige nichtleere Seitenflache. Nach dem Lemma von Farkas exi-stiert eine endliche Teilmatix AF und ein y ≥ 0 derart, dass

cT = yT AF und yTbF ≤ z.

Wegen F 6= ∅ haben wir sogar die Gleichheit z = yTbF . Denn:

x ∈ F =⇒ z = cTx = yT AFx ≤ yTbF ≤ z.

Daraus folgt:

• F besteht genau aus den Punkten x ∈ P (A,b), welche die Glei-chungAFx = bF erfullen, d.h. F = {x ∈ Rn | Ax ≤ b, AFx = bF}.

SATZ 1.4. Ist Ax ≤ b ein endliches Ungleichungssystem, so hat die abge-schlossene konvexe Menge P (A,b) nur endlich viele verschiedene Seiten-flachen.

Beweis. Ax ≤ b gestattet nur endlich viele verschiedene Teilsysteme AFx ≤ bF .�

EX. 1.10. Die Kugel S = {(x, y, z) ∈ Rn | x2 + y2 + z2 ≤ R} lasstsich nicht als Losungsmenge eines endlichen linearen Ungleichungssystemdarstellen, denn S hat unendlich viele Extrempunkte.

EX. 1.11. Das Standardsimplex in Rn ist die Menge

∆n = {(x1, . . . , xn) | x1 + . . . + xn = 1, x1 ≥ 0, . . . , xn ≥ 0}.

Ein Eckpunkt von ∆n entspricht einer einelementigen Seitenflache und folg-lich einer Auswahl von Ungleichungen derart, dass das zugeordnete Glei-chungssystem nur eine einzige Losung in ∆n gestattet. Also ergeben sichgenau die n Einheitsvektoren als die Ecken von ∆n.


5.2.2. Konvexe Kegel. Eine nichtleere Menge K ⊆ Rn ist ein sog.(konvexer) Kegel, wenn gilt

(K1) λx ∈ K fur alle x ∈ K und Skalare λ ≥ 0.(K2) x + y ∈ K fur alle x,y ∈ K.

Ein konvexer Kegel ist also eine unter nichtnegativen Linearkombinationenabgeschlossene Menge.

BEMERKUNG. Ein nichtleerer Kegel enthalt immer zumindest den Punkt 0 ∈ Rn.

Man kann jeder nichtleeren Menge S ⊆ Rn einen Kegel auf zwei (zueinan-der ”duale“) Weisen einen Kegel zuordnen. Zum einen betrachtet man dieMenge aller nichtnegativen Linearkombinationen

(5) cone S = {k∑

i=1

λisi |, si ∈ S, λi ≥ 0}

cone S ist die konische Hulle von S oder der von S erzeugte Kegel. Dualdazu definiert man

(6) S◦ = {x ∈ Rn | sTx ≤ 0 fur alle s ∈ S}.S◦ ist der zu S duale Kegel. S◦ ist Losungsmenge eines linearen Unglei-chungssystems und deshalb abgeschlossen (und konvex). Stellen wir uns Sals eine Matrix mit den Zeilenvektoren sT vor, so ist ja

S◦ = P (S,0).

Man beachte, dass fur konvexe Kegel die Polare und der duale Kegel mit-einander identisch sind:

LEMMA 1.5. Sei K ⊆ Rn ein konvexer Kegel. Dann gilt

K◦ = Kpol.

Beweis. . Es gilt K◦ ⊆ Kpol. Denn wir beobachten

cTx ≤ 0 =⇒ cTx ≤ 1 fur alle x ∈ K.

Ist x ∈ K, dann gilt auch λx ∈ K fur alle λ > 0. Also haben wir

limλ→∞

λ(cTx) = limλ→∞

cT (λx) ≤ 1 =⇒ cTx ≤ 0.

D.h. Kpol ⊆ K◦.�

Analog der Argumentation bei der Polaren macht sich leicht klar:• S ⊆ (S◦)◦.


• S ⊆ T =⇒ T ◦ ⊆ S◦.• S◦ = (cone S)◦.

SATZ 1.5. Sei S ⊆ Rn eine beliebige nichtleere Menge. Dann gilt

(i) S ist ein konvexer Kegel ⇐⇒ S = cone S.(ii) S ist ein abgeschlossener konvexer Kegel ⇐⇒ S = (S◦)◦.

Beweis. Der Beweis von Behauptung (i) ist Routine. Die Aussage (ii) ist derSpezialfall der analogen Aussage uber die Polare konvexer Kegel.

�

5.3. Das Projektionslemma. Wir betrachten z.B. die Projektionsab-bildung π : Rn → Rn−1, die gegeben ist durch

π(x1, x2, x3 . . . , xn) = (x2, x3, . . . , xn).

π ist stetig und deshalb ist klar, dass das Bild einer abgeschlossenen konve-xen Menge unter π wieder abgeschlossen und konvex ist. Die interessanteAussage des folgenden Lemmas ist deshalb die darin gemachte Aussageuber Endlichkeit.

LEMMA 1.6 (Projektionslemma). Sei A ∈ Rm×n und b ∈ Rm gegeben.Dann existiert eine endliche Matrix B ∈ Rk×(n−1) und ein Vektor d ∈ Rk

derart, dass gilt

π[P (A,b)] = P (B,d).

(D.h. die Projektion der Losungsmenge eines endlichen linearen Unglei-chungssystems ist selber Losungsmenge eines endlichen linearen Unglei-chungssystems.)

Beweis. Sei Bx ≤ d das lineare Ungleichungssystem, das sich aus Ax ≤ b nachFM-Elimination von x1 ergibt. Aus der Rucksubstitutoinsregel (4) ergibt sich

(x∗2, . . . , x∗n) ∈ P (B,d) ⇐⇒ es gibt ein x∗1 ∈ R mit (x∗1, x

∗2, . . . , x

∗n) ∈ P (A,b).

Das ist aber genau die Behauptung P (B,d) = π[P (A,b)].�

BEMERKUNG. Der Beweis des Projektionslemmas ist konstruktiv: Man kann einegeeignete Matrix B und einen geeigneten Vektor d mit dem FM-Verfahren berech-nen.

6. ZWEI ANWENDUNGEN 19

6. Zwei Anwendungen

6.1. Das Erfullbarkeitsproblem. Wir rechnen uber dem Zahlbereich {0, 1}mit den Operationen

⊕ 0 10 0 11 1 1

� 0 10 0 01 0 1

− 0 11 0

Eine Boolesche Funktion ist eine Funktion ϕ : {0, 1}n → {0, 1}. Es ist bekannt,dass eine Boolesche Funktion ϕ(x1, . . . , xn) in einer sog. konjuktiven Normalform(KNF) dargestellt werden kann:

ϕ(x1, . . . , xn) =∏

Ci,

wobei die Klauseln Ci die Form haben

Ci = ai1y1 ⊕ . . .⊕ ainyn mit aij ∈ {0, 1} und yi ∈ {xi, xi}.

EX. 1.12. ϕ(x1, x2, x3) = (x1 ⊕ x2)� (x1 ⊕ x2 ⊕ x3)� x3.

ERFULLBARKEITSPROBLEM: Man entscheide, ob die per KNF gegebene Boole-sche Funktion ϕ den Wert 1 annehmen kann. Das heisst: Kann eine Belegung derVariablen gefunden werden derart, dass jede Klausel Ci den Wert 1 annimmt?

Das Problem kann man mit Ungleichungssystemen modellieren. In der K KlauselCi = ai1y1 + . . . ainyn ersetzen wir xj durch 1−xj und haben dann das Problem:Gibt es eine Losung mit ganzahligen xj ∈ {0, 1} derart, dass

ai1y1 + . . . ainyn ≥ 1 ?

EX. 1.13. Sei C = x2 ⊕ x5 ⊕ x7. Dann ist C erfullbar, wenn es eine ganzzahlige(0, 1)-Losung der Ungleichung

x2 + (1− x5) + x7 ≥ 1 ←→ −x2 + x5 − x7 ≤ 0

gibt.

Das Erfullbarkeitsproblem fragt also nach einer ganzahligen (0, 1)-Losung des ausallen Klauseln gebildeten Ungleichungssystems.

2-SAT: Das Erfullbarkeitsproblem fur Boolesche Funktionen in KNF, bei denenjede Klausel hochstens 2 Variablen enthalt.

2-SAT kann mit dem FM-Verfahren effizient(!) gelost werden, denn bei jeder Ad-dition von Ungleichungen bleiben die Koeffizienten im Bereich {−1, 0,+1} unddie Anzahl der Ungleichungen erhoht sich nicht.


EX. 1.14 (Resolvente).

C1 = xk ⊕ xs

C2 = xk ⊕ xl

C = xs ⊕ xl

←→−xk − xs ≤ −1xk − xl ≤ 0

− xs − xl ≤ −1

C ist die sog. Resolvente der Klauseln C1 und C2. Offensichtlich sind C1 undC2 genau dann gleichzeitig erfullt, wenn ihre Resolvente C erfullt ist. Im Unglei-chungssystem entspricht C der Summe der aus C1 und C2 gewonnenen Unglei-chungen.

BEMERKUNG. Fur das allgemeine Erfullbarkeitsproblem ist beim gegenwartigenStand der Wissenschaft kein effizienter Losungsalgorithmus bekannt.

6.2. Stochastische Matrizen. In der Anwendungssimulation betrachtet manSysteme, die sich zu jedem (diskreten) Zeitpunkt in einem von n Zustanden {Z1, . . . , Zn}befinden. Wir nehmen an, dass das System mit Wahrscheinlichkeit

mij = Pr(Zj |Zi)

in den Zustand Zj ubergeht, wenn es vorher im Zustand Zi war. Die entsprechendeUbergangsmatrix

M = [mij ] ∈ Rn×n

hat nur nichtnegative Koeffizienten mij ≥ 0 und Spaltensummen∑n

i=1 mij = 1.D.h. M ist eine sog. stochastische Matrix: Alle Spalten sind Wahrscheinlichkeits-verteilungen.

Nehmen wir an, dass sich das System zum Zeitpunkt t mit der Wahrscheinlichkeitπi im Zustand Zi befindet (i = 1, . . . , n). Dann befindet es sich zum Zeitpunktt + 1 mit den der Wahrscheinlichkeit

π′k =n∑

i=1

mkiπi

im Zustand Zk (k = 1, . . . , n). In Matrixnotation haben wir also:

π′ = πM (π = [π1, . . . , πn], π′ = [π′1, . . . , π′n]).

π heisst stationar, wenn π = π. Eine stationare Wahrscheinlichkeitsverteilung istals ein (linker) Eigenvektor von M zum Eigenwert λ = 1.

PROPOSITION 1.2. Die stochastische Matrix M = [mij ] besitzt eine stationareWahrscheinlichkeitsverteilung.

Bew Wir setzen A = MT − I . Es genugt zu zeigen, dass

Ax = 0,x ≥ 0,x 6= 0

eine Losung hat. Diese konnen wir dann auf Koeffizientensumme 1 normieren underhalten dann das gewunschte π.

6. ZWEI ANWENDUNGEN 21

Nehmen wir an, keine solche Losung existierte. Dann gabe es nach dem Gordan-schen Satz (Korollar 1.3) einen Vektor y mit der Eigenschaft

0T > yT A = yT M − yT d.h. yj >

n∑i=1

mijyi fur alle j = 1, . . . , n.

Das kann aber nicht sein. Denn fur yk = min{y1, . . . , yn} gilt sicherlichn∑

i=1

mikyi ≥n∑

i=1

mijyk = yk.

Dieser Widerspruch beweist die Existenz der stationaren Verteilung.�

KAPITEL 2

Polyeder und Polytope

Ein Polyeder (in Rn) ist eine Teilmenge P , die sich als Durchschnitt von endlichvielen Halbraumen darstellen lasst. Per definitionem existieren also eine MatrixA ∈ Rm×n und ein Koordinatenvektor b ∈ Rm derart, dass

P = P (A,b).

Die leere Menge ∅ und der gesamte Raum Rn sind somit Polyeder. Allgemeiner istz.B. jeder affine (und insbesondere lineare) Teilraum von Rn ein Polyeder.

Die Matrix A und der Vektor b sind jedoch bei der Darstellung des PolyedersP = P (A,b) nicht eindeutig. Typischerweise gibt es unendlich viele verschiede-ne (endliche) lineare Ungleichungssysteme mit demselben Losungsraum P . Es istsogar moglich, dass sich ein Polyeder als Losungmenge eines nichtlinearen Un-gleichungssystems ergibt.

EX. 2.1. Die Punktmenge im nichtnegativen Quadranten der euklidischen Ebene

P = {(x1, x2) ∈ R2+ | x2

1 + x22 + 3x1x2 − 2x1 − 3x1x2 ≤ −1}

entspricht der Losungsmenge des linearen Ungleichungssystems

x1 + x2 ≤ 1x1 + 2x2 ≥ 1x1, x2 ≥ 0

und ist somit ein Polyeder.

1. Darstellung und Dekomposition von Polyedern

Seien V = {v1, . . . ,vk} und W = {w1, . . . ,w`} zwei endliche Teilmengen vonKoordinatenvektoren in Rn, wobei wir W 6= 0 annehmen. Wir betrachten die Men-ge

(7) P = conv V + cone W = {v + w | v ∈ conv V,w ∈ cone W},

d.h. die Minkowski-Summe der endlich erzeugten konvexen Menge conv V unddes endlich erzeugten konvexen Kegels cone W . P besteht also aus der Mengealler Linearkombinationen z vom Typ

z =k∑

i=1

µivi +∑j=1

λjwj mit µi, λj ≥ 0,k∑

i=1

µi = 1.

23

24 2. POLYEDER UND POLYTOPE

BEMERKUNG (MINKOWSKI-SUMME). Allgemein definiert man die Minkowski-Summe von beliebigen Teilmengen S, T ⊆ Rn als

(8) S + T = {s + t | s ∈ S, t ∈ T} , wobei S + ∅ = S.

�Wir zeigen, dass P ein Polyeder ist, und, dass jedes Polyeder eine Darstellungvom Typ (7) gestattet. In diesem Sinn sind Polyeder endlich erzeugt. Wir fuhrenden Beweis in mehreren Schritten.

LEMMA 2.1. Die Menge P = conv V + cone W ist ein Polyeder.

Beweis. Wir betrachten V und W als Matrizen mit Spaltenvektoren vi bzw. wj .Dann bildet die Menge aller Losungen (x,y, z) des Ungleichungssystems

z − V x − Wy = 01Tx = 1x , y ≥ 0

ein Polyeder P in Rk+m+n. P ist die Projektion von P auf die z-Koordinaten,d.h. Losungsmenge der Ungleichungssystems nach FM-Elimination der x- und y-Koordinaten.

�BEMERKUNG. Der Beweis von Lemma 2.1 zeigt, dass ein UngleichungssystemAx ≤ b derart, dass P = P (A,b) im Prinzip mit dem FM-Eliminationsverfahrenberechnet werden kann.

Sei nun P ein beliebiges Polyeder mit 0 ∈ P . Dann gibt es eine endliche Index-menge I und Ungleichungen aix ≤ bi derart, dass

P = {x ∈ Rn | aTi x ≤ bi, i ∈ I}.

Wegen 0 ∈ P durfen wir bi ∈ {0, 1} annehmen. Entsprechend zerfallen die Un-gleichungen in die die Typen A(0)x ≤ 0 und A(1)x ≤ 1.

LEMMA 2.2. Seien A und B Matrizen und P = {x | Ax ≤ 1, Bx ≤ 0}. Danngilt fur die Polare des Polyeders P :

P pol = conv [AT ,0] + cone BT .

Beweis. Die Polare von P besteht aus allen Vektoren c derart, dass die Unglei-chung cTx ≤ von den Ungleichungen Ax ≤ 1 und Bx ≤ 0 impliziert ist. Nachdem Farkaslemma bedeutet dies:

P pol = {c ∈ Rn | c = ATy + BTz,y, z ≥ 0,yT1 ≤ 1}= conv [AT ,0] + cone BT .

�

1. DARSTELLUNG UND DEKOMPOSITION VON POLYEDERN 25

SATZ 2.1 (Dekompositionsatz von Weyl-Minkowski). Genau dann ist eine Teil-menge P ⊆ Rn ein Polyeder, wenn es endliche Mengen V,W ⊆ Rn gibt mit derEigenschaft

P = conv V + cone W.

Beweis. Dass die Bedingung hinreicht, ist Inhalt von Lemma 2.1. Wir beweisendie Notwendigkeit und nehmen oBdA P 6= ∅ an. Wir betrachten zuerst den Fall0 ∈ P . Dann kann P in der Form

P = {x | Ax ≤ 1, Bx ≤ 0}

ausgedruckt werden. Nach Lemma 2.2 (und Lemma 2.1) ist Q = P pol ein Polyeder.Wegen 0 ∈ P finden wir

P = (P pol)pol = Qpol.

Wiederum aus Lemma 2.2 schliessen wir nun, dass P als Minkowski-Summe einerendlich erzeugten konvexen Menge und eines endlich erzeugten konvexen Kegelsausgedruckt werden kann.

Im Fall 0 /∈ P wahlen wir irgendein t ∈ P und betrachten die Translation (Min-kowskisumme)

P = P + {−t}.Wegen 0 ∈ P gibt es endliche Mengen V und W derart, dass


Nun verifiziert man leicht fur V = V + {−t} und W = W :


�

1.1. Dualitat von Darstellungen. Der Satz von Weyl-Minkowski zeigt, dassein Polyeder P zwei einander duale Sichtweisen erlaubt:

IMPLIZIT: P ist Losungsmenge eines endlichen linearen Ungleichungs-systems Ax ≤ b;

EXPLIZIT: P ist die Menge aller Vektoren (bzw. Punkte), die von denendlichen Mengen V und W gemass (7) erzeugt werden.

Die Situation verallgemeinert damit die bei linearen oder affinen Teilraumen A ⊆Rn bekannte. Einerseits ist A Losungsmenge eines linearen GleichungssystemsAx = b. Andererseits gibt es eine endliche Menge S = s1, . . . , sk derart, dass Adie Menge aller affinen Linearkombinationen

x = λ1s1 + . . . + λksk mitk∑

i=1

λi = 1


ist. Die Umrechnung von einer Darstellung zur anderen ist im linearen/affinen Falleffizient moglich (z.B. mit dem Gauss-Verfahren). Im allgemeinen Fall ist die Um-rechnung nicht so einfach moglich. Wie man im Prinzip umrechnen kann, wird imfolgenden Abschnitt noch deutlicher werden.

NOTA BENE. Im linearen Fall sind alle minimalen Erzeugendensysteme (Basen)gleichmachtig. Bei Ungleichungssystemen ist dies nicht mehr notwendigerweiseso!

1.2. Berechung von Erzeugendensystemen. Um ein Erzeugendensystem furden P (A,0) zu berechnen, kann man von der Relation

P (A,0)◦ = cone AT

ausgehen und mit Fourier-Motzkin eine Matrix B berechnen mit der Eigenschaft

cone AT = P (B,0).

Daraus ergibt sichP (A,0) = P (B,0)◦ = cone BT .

Also bilden die Spaltenvektoren von BT (bzw. die Zeilenvektoren von B) ein Er-zeugendensystem fur den Kegel P (A,0).

PROBLEM: Diese Berechnungsmethode eines Erzeugendensystems uber das FM-Verfahren ist im allgemeinen nicht effizient.

Diese Vorgehensweise lasst sich leicht verallgemeinern, um endliche Mengen Vund W fur eine Weyl-Minkowski-Dekomposition

P (A,b) = conv V + cone W.

zu ermitteln. Wir betrachten dazu den polyedrischen Kegel

K ={[

xt

]∈ Rn+1 | Ax− bt ≤ 0, t ≥ 0

}.

Dann haben wir

x ∈ P (A,0) ⇐⇒[x1

]∈ K.

Haben wir nun Vektoren h1, . . . ,hk ∈ Rn gefunden mit der Eigenschaft

K = cone {h1, . . . ,hk},

so durfen wie annehmen, dass die Erzeugenden folgende Form haben:

hi =[h′iti

]mit ti = 1 oder ti = 0.

Im Fall ti > 0 konnen namlich wir einfach den Vektor hi durch Division mit tientsprechend normieren. Die Mengen

V = {h′i | ti = 1} und W = {h′j | tj = 0},

2. OPTIMIERUNG LINEARER FUNKTIONEN 27

leisten das Gewunschte. Denn wir haben fur alle x ∈ P (A,b)[x1

]=

∑hi∈V

µi

[h′i1

]+

∑hj∈W

λj

[h′j0

]fur geeignete µi ≥ 0 und λj ≥ 0. Ein Blick auf die letzte Komponente zeigt zudem

1 =∑h′i∈V

µi .

Also finden wir

x =∑

i

µih′i +∑

j

λjh′j ∈ conv V + cone W.

2. Optimierung linearer Funktionen

Viele wichtige Anwendungsprobleme lassen sich als mathematische Optimierungs-probleme modellieren, wo eine lineare Zielfunktion f(x) = cTx unter (endlichvielen) linearen Ungleichungsrestriktionen zu maximieren ist:

(9) maxx∈Rn

cTx s.d. Ax ≤ b (A ∈ Rm×n,b ∈ Rm).

Stellen wir den Losungsraum P = P (A,b) nach Weyl-Minkowski in der Form

P = conv V + cone W

dar, so sieht man sofort:(0) Ist P = ∅, so hat das lineare Optimierungsproblem keine Losung.(1) Gibt es ein w ∈ cone W mit cTw > 0, so sind die Zielfunktionswerte

nach oben unbeschrankt (”∞“).(2) Gilt cTw ≤ 0 fur alle w ∈ cone W und ist V 6= ∅, dann ist

maxx∈P

cTx = maxv∈V

cTv <∞.

Beweis von (2): Es gilt unter den angenommenen Umstanden

maxx∈P

cTx = maxv∈conv V

cTx.

Sei V = {v1, . . . ,vk} und v =∑k

i=1 µivi ∈ cone V ein beliebiges Element.Dann finden wir wegen µi ≥ 0 und

∑i µ = 1:

cTv =k∑

i=1

µicTvi ≤ ( maxj=1,...,k

cTvj) ·k∑

i=1

µi = maxvj∈V

cTvj .

�Diese Beobachtungen zeigen, dass das lineare Optimierungsproblem in der Theoriedarauf reduziert werden kann:

(i) Stelle fest, ob die Ungleichungsrelation cTw ≤ 0 fur alle w ∈ W gilt(d.h. ob c ∈ P (W T ,0) = W ◦ zutrifft);

(ii) Wenn ja, lose das Problem maxv∈V cTv.


Die Frage ist deshalb, in wieweit diese Theorie in praktische Rechnung umgesetztwerden kann.

3. Rezessionskegel und polyedrische Kegel

Wir nehmen P = conv V + cone W mit endlichen Mengen V und W 6= ∅ an.Dann heisst der konvexe Kegel

P0 = cone W

der Rezessionskegel des Polyeders P = conv V + cone W . P0 hangt nur von P ab.

LEMMA 2.3. Seien A ∈ Rm×n und b ∈ Rm so, dass P (A,b) = conv V +cone Wund W 6= ∅. Dann gilt

cone W = P (A,0).

Beweis. Sei p = v +w mit v ∈ conv V und w ∈ cone W ein beliebiger Punkt inP . Wegen v + λw ∈ cone W fur alle λ, finden wir

limλ→∞

λ(Aw) = limλ→∞

A(λw) ≤ b−Av

und folglich Aw ≤ 0 bzw. cone W ⊆ P (A,0), was sofort die Darstellung

P = conv V + cone W = conv V + P (A,0)

impliziert. Denn wir haben fur alle v ∈ conv V und z ∈ P (A,0):

A(v + z) = Av + Az ≤ b + 0 = b.

Ausserdem hatten wir fur beliebige Koordinatenvektoren c festgestellt:

c ∈ (cone W )◦ ⇐⇒ (9) besitzt Optimallosung⇐⇒ c ∈ P (A,0)◦.

Also folgt (cone W )◦ = P (A,0)◦ und daraus cone W = P (A,0).�

4. Polytope

Per Definition ist ein Polytop ein beschranktes Polyeder, d.h. ein Polyeder P derart,dass ein R > 0 existiert mit der Eigenschaft

‖x‖ ≤ R fur alle x ∈ P .

M.a.W.: die Polytope sind genau die kompakten Polyeder. Dabei lassen wir P = ∅als leeres Polytop zu. Nach Weyl-Minkowski ist eine Menge P ⊆ Rn genau dannein Polytop, wenn eine endliche Menge V ⊆ Rn existiert mit

P = conv V.

LEMMA 2.4. P (A,b) ist genau dann ein Polytop, wenn P (A,0) = {0}.�

4. POLYTOPE 29

4.1. Lineare Optimierung und Polytope. Wir betrachten lineare Zielfunk-tionen f(x) = cTx uber einem Polytop. Wir wissen:

P = conv V =⇒ maxx∈P

cTx = maxv∈V

cTv.

Diese Eigenschaft gilt aber auch umgekehrt.

LEMMA 2.5. Sei P ⊆ Rn ein Polytop und V ⊆ P eine endliche Teilmenge. Danngilt

P = conv V ⇐⇒ maxx∈P

cTx = maxv∈V

cTv fur alle c ∈ Rn.

Beweis. Es ist noch zu beweisen, dass die Eigenschaft hinreichend fur P =conv V ist. Angenommen, es gabe ein y ∈ P \ conv V , dann gabe es nach demTrennungslemma auch ein c mit der Eigenschaft

cTy > max{cTx | x ∈ conv V },was die Bedingung verletzen wurde.

�

LEMMA 2.6. Sei V ⊆ Rn endlich und v0 ∈ V so, dass v /∈ conv (V \ {v0}).Dann ist v0 eine Ecke (Extrempunkt) des Polytops P = conv V .

Beweis. Sei S = conv (V \ {v0}). Im Fall v0 /∈ S existieren v1 ∈ S und c ∈ Rn

so, dasscTv > cTv1 ≥ cTx fur alle x ∈ S.

Sei z = cTv1. Dann ist z Optimalwert des Problems

maxx∈S

cTx = maxv∈V \{v0}

cTv.

Andererseits gilt

z < cTv0 ≤ maxx∈P

cTx = maxv∈V

cTv =: z∗ d.h. z∗ = cTv0.

Wir betrachten schliesslich einen beliebigen Punkt

x =∑v∈V

λvv ∈ P (= conv V ) (λv ≥ 0,∑v∈V

λv = 1).

Im Fall cTx = z∗ finden wir nun

z∗ = cTx = λv0cTv0 +

∑v 6=v0

λvv ≤ λv0z∗ + (1− λv0)z.

Wegen z < z∗ folgt daraus λv0 = 1 und deshalb x = v0. Also haben wir

P ∩ {x ∈ Rn | cTx = z∗} = {v0} d.h. v0 ist Ecke von P .

�

SATZ 2.2. Jedes nichtleere Polytop P ist die konvexe Hulle seiner Ecken.


Beweis. Sei V eine minimale Erzeugendenmenge mit P = conv V . Dann giltv /∈ conv (V \ {v} fur alle v ∈ V . Denn sonst hatte man P = conv (V \ {v} – imWiderspruch zu der Minimalitat von V . Also besteht V nur aus Ecken von P .

�NOTA BENE. Der eben bewiesene Satz garantiert insbesondere, dass jedes nicht-leere Polytop auch Ecken hat. Dies ist nicht selbstverstandlich! Sehr viele Polyederhaben keine Ecken.

4.2. Diskrete Optimierung und Polytope. Ein Grundproblem der diskretenOptimierung kann so formuliert werden. Gegeben ist eine Grundmenge E und eineGewichtsfunktion w : E → R. Ausserdem sei eine Familie F ⊆ 2E von Teilmen-gen spezifiert. Man hat nun die Aufgabe

(10) maxF∈F

∑e∈F

w(e).

Der Teilmengenfamilie F ⊆ 2E ordnet man folgendermassen ein Polytop zu. Manreprasentiert jedes F ∈ F durch seinen Inzidenzvektor χF ∈ RE , wobei

χF (e) ={

1 wenn e ∈ F0 wenn e /∈ F .

und definiert nunP(F) = conv {χF | F ∈ F} ⊆ RE .

Das diskrete Optimierungsproblem (10) wird nun zu dem Problem, die lineareFunktion mit den Koeffizienten we = w(e) uber dem Polytop P(F) zu maximie-ren:

maxx∈P(F)

∑e∈E

wexe = maxF∈F

∑e∈E

weχF (e) = maxF∈F

∑e∈F

w(e).

4.2.1. Das Zuordnungs- und Heiratsproblem. Wir gehen von endlichen undgleichmachtigen Mengen S und T (d.h. |S| = |T |) aus und betrachten die Mengealler Paare

S × T = {(s, t) | s ∈ S, t ∈ T}Eine Zuordnung (bzw. ein perfektes Matching) ist eine bijektive Abbildung π :S → T . Wir stellen uns die Zuordnung als Menge von Paaren vor:

M = M(π) = {(s, π(s)) | s ∈ S} ⊆ S × T.

M sei die Menge aller Zuordnungen. Das Zuordnungsproblem bzgl. der Gewichts-funktion w : S × T → R ist nun:

maxM∈M

∑(s,t))∈M

w(s, t)

Im Spezialfall w : S × T → {0, 1} spricht man auch vom Heiratsproblem.

Das Zuordnungspolytop P(M) ist von der MengeM aller Zuordnungen erzeugt.Wir suchen eine implizite Beschreiben, d.h. ein System linearer Ungleichungendessen Losungen x gerade die Punkte in P(M) sind.

4. POLYTOPE 31

Sei x ∈ P(M). Wir bezeichnen die Komponenten von x mit xst. Welche Un-gleichungen muss x erfullen? Ist x der Inzidenzvektor eines perfekten Matchings,dann gilt sicherlich:

(M0) xs,t ≥ 0 fur alle (s, t) ∈ S × T .(M1)

∑s∈S xst = 1 fur alle s ∈ S.

(M2)∑

t∈T xst = 1 fur alle t ∈ T .

Diese Ungleichungen gelten naturlich auch fur alle Konvexkombinationen von Zu-ordnungen und deshalb fur alle x ∈ P(M). Es stellt sich heraus, dass sie P(M)schon vollstandig bestimmen!

LEMMA 2.7. P(M) = {x ∈ RS×T | x erfullt (M0)-((M2)}.

Das Lemma wird hier nicht bewiesen, da es aus sich spater als Folgerung aus einemallgemeinen Optimierungsalgorithmus fur sog. Flusse in Netzwerken ergeben wird.

BEMERKUNG. Man bemerke, dass es |S|! viele Zuordnungen gibt und diese alleEcken von P(M) sind. Zur Beschreibung von P(M) genugen aber schon 2|S|Gleichungen und |S| Ungleichungen.

4.2.2. Das Rundreiseproblem. Wir gehen von einer endlichen Menge S ausund betrachten die Menge E = S × S. Eine Rundreise (oder aus TSP-Tour) isteine Anordnung der Elemente von S:

τ = s0s1 . . . , sns0,

bei der ausser s0 kein Element zweimal auftritt. Wieder stellen wir τ als Mengevon Paaren dar:

T = T (τ) = {(s0, s1), . . . , (sn, s0)}

Gegeben eine Distanzfunktion d : S×S → R+, definiert man die Lange von T als

d(T ) =∑

(s,t)∈T

d(s, t).

Sei T die Menge aller Rundreisen. Das Rundreiseproblem (TSP-Problem) ist

minT∈T

d(T ) ←→ maxT∈T

∑(s,t)∈T

−d(s, t).

Auch hier kann man naturlich das entsprechende Rundreisepolyeder P(T ) defi-nieren, dessen Struktur allerdings zum grossen Teil noch ungeklart ist. Obwohlsehr viele Klassen von gultigen Ungleichungen fur P(T ) bekannt sind, ist einevollstandige Beschreibung eines der grossen gegenwartigen offenen Probleme derBerechenbarkeitstheorie der theoretischen Informatik.


5. Facetten und Basislosungen

5.1. Facetten. Unter einer Facette eine Polyeders P 6= ∅ versteht man eineSeitenflache F ⊆ P der Dimension

dim F = dim P − 1.

SATZ 2.3. Sei F eine echte Seitenflache des Polyeders P = P (A,b). Dann ist Fein Durchschnitt von Facetten von P .

Sei m = dim P . Dann existiert eine Teilmatrix A0 von A so, dass

m = n− rg AP und APx = bP fur alle x ∈ P .

OBdA nehmen wir an, dass die Zeilen von A0 linear unabhanging sind. Ausseremexistiert eine Teilmatrix AF so dass

F = {x ∈ P | AFx = bF } und dim F = n− rg AF .

Auch sei oBdA angenommen, dass die Zeilen von AF linear unabhangig sind.Ausserdem konnen wir annehmen, dass AP eine Teilmatrix von AF ist, da jedesx ∈ F auch die Gleichung APx = bP erfullt.

Sei nun aTi x ≤ bi eine beliebige Ungleichung, die in AFx ≤ bF auftritt, aber

nicht APx ≤ bP . Aufgrund der linearen Unabhangingkeit der Zeilen ist aTi x ≤ bi

nicht von APx = bP impliziert. Also schliessen wir:

Fi = {x ∈ P | Apx = bP ,aTi x = bi} 6= P d.h. Fi ist echte Seitenflache.

Wegen

rg[AP

aTi

]= rg Ap + 1 d.h. dim Fi = dim P − 1

erkennen wir Fi als Facette. Offenbar ist F gerade der Durchschnitt aller solcherFacetten Fi (bzw. Losungsmenge der Gesamtheit der entsprechenden Gleichun-gen).

�Anwendung auf Polytope. Polytope haben Ecken und folglich Seitenflachen allerDimensionen d mit −1 ≤ d ≤ dim P , wie der Beweis des vorigen Satzes zeigt.

Zusammen mit APx = bP implizieren die Facettenungleichungen des PolytopsP (A,b) jede andere Ungleichung aTx ≤ b in Ax ≤ b.

Um das zu sehen betrachten wir

z = maxx∈P

aTx ≤ b.

Dann ist Fa = {x ∈ P | aTx = z} eine Seitenflache und deshalb Durchschnittvon Facetten. Also implizieren die Facettenungleichungen

aTx ≤ z ≤ b.

Das bedeutet:

6. RATIONALE POLYEDER 33

• Im Prinzip reicht das System APx = bP zusammen mit den Facetten-ungleichungen vollig aus, um P (A,b) eindeutig zu beschreiben.

5.2. Basislosungen. Wir betrachten ein Polyeder, das sich als die Menge allesnichtnegativen Losungen eines linearen Gleichungssystems ergibt:

P = {x ∈ Rn | Ax = b,x ≥ 0} .

P ist also Losungsraum des linearen (Un-)Gleichungssystems:

Ax = b−Ix ≤ 0.

Sei r = rg A. Genau dann ist ein Punkt v ≥ 0 eine Ecke von P , wenn es eineMenge N von |N | = n − r Indizes j gibt derart, dass v eindeutige Losung desfolgenden Systems ist:

Ax = beT

j x = 0 (fur alle j ∈ N).

Aquivalent dazu ist:(i) vj = 0 fur alle j ∈ N ;

(ii) Die Teilmatrix B der r Spalten A·j mit Index j ∈ N bildet eine Spalten-Basis von A

(iii) BvB = b.Folglich:

Ecke von P ←→ nichtnegative Basislosung von Ax = b

LEMMA 2.8. P hat hochstens(nr

)Ecken.

�

6. Rationale Polyeder

Ein Polyeder P ⊆ Rn heisst rational, wenn P mit rationalen Parametern prasen-tiert werden kann. Das ist auf zwei Arten moglich:

Implizit : Angabe einer Matrix A ∈ Qm×n und eines Vektors b ∈ Qm so, dassP = P (A,b)

Explizit : Angabe von endlichen Mengen von Vektoren V,W ⊆ Qn so, dassP = conv V + cone W.

Wir haben gesehen, dass alle Rechnungen (insbesondere Umrechnungen von Dar-stellungen) bei Polyedern im Prinzip mit dem Fourier-Motzkinschen Verfahrenmoglich sind. Das beruht nur auf den folgeden Operationen:

• Multipikation mit einem positiven Skalar;• (Komponentenweise) Addition von Vektoren.

Diese Operationen fuhren nie aus dem Skalarbereich Q heraus. Kurz gesagt:

Samtliche Kenngrossen rationaler Polyeder sind rational

KAPITEL 3

Konvexe Funktionen

Sei F ⊆ Rn ein Definitionsbereich und f : F → R eine Funktion. Unter demEpigraphen von f versteht man die Menge

epif = {(x, z) ∈ Rn+1 | x ∈ F , z ∈ R, z ≥ f(x)}.

Man nennt f konvex, wenn der Epigraph epif eine konvexe Menge in Rn+1 dar-stellt.

LEMMA 3.1. f : F → R ist konvex genau dann, wenn gilt(i) F ist konvex;

(ii) fur alle x,y ∈ F und 0 < λ < 1:

f [x + λ(y − x)] ≤ f(x) + λ[f(y)− f(x)].

Beweis. Seien (x, z) und (y, w) Punkte im Epigraphen von f . Konvexitat istgleichbedeutend mit der Eigenschaft

(x, z) + (λ(y − x), λ(w − z)) ∈ epif (0 < λ < 1).

Nach Komponenten aufgeschlusselt bedeutet dies, dass x + λ(y − x) ∈ F undsomit (i) erfullt sein muss. Ausserdem mussen wir haben:

f [x + λ(y − x)] ≤ z + λ(w − z) = (1− λ)z + λw.

Die Wahl z = f(x) und w = f(y) ergibt die Notwendigkeit von (ii). Offensicht-lich ist (ii) zusammen mit (i) aber auch hinreichend.

�

Lemma 3.1 zeigt, dass Konvexitat von Funktionen im Grunde eine ”eindimensio-nale“ Eigenschaft ist: f ist konvex genau dann wenn die Richtungsfunktionen

t 7→ fh(t) = f(x + th) t ∈ R so, dass x + th ∈ F

in beliebige Richtungen h ∈ Rn und in beliebigen Punkten x in der Variablen tkonvex sind.

1. Differenzierbare konvexe Funktionen

Wir betrachten zuerst den eindimensionalen Fall.

LEMMA 3.2. Sei f : (a, b) → R differenzierbar. Genau dann ist f konvex, wenndie Ableitung f ′(x) auf (a, b) monoton wachst.

35

36 3. KONVEXE FUNKTIONEN

Beweis. Sei x < y. Wir betrachten z(λ) = x + λ(y − x). Dann finden wir

f ′(x) = limλ→0

f(z(λ))− f(x)λ(y − x)

≤ limλ→0

λ[f(y)− f(x)]λ(y − x)

=f(y)− f(x)

y − xd.h.

f ′(y) = limx→y

f(y)− f(x)y − x

≥ f ′(x) .

Die Bedingung ist also notwendig. Wir zeigen nun, dass sie auch hinreicht, undnehmen oBdA x < y an. Nach dem Zwischenwertsatz existiert dann ein x < ξ < ymit

f ′(x) ≤ f ′(ξ) =f(y)− f(x)

y − xd.h. f(y) ≥ f(x) + f ′(x)(y − y).

Sei nun z = x + λ(y − x). Dann ergibt sich auf die gleiche Weise

f(x) ≥ f(z) + f ′(z)(x− z)f(y) ≥ f(z) + f ′(z)(y − z)

und daraus

f(x) + λ[f(y)− f(x)] = (1− λ)f(x) + λf(y) ≥ f(z) + f ′(z) · 0 = f(z).

�Betrachten wir nun den allgemeinen Fall F ⊆ Rn und eine bei jedem x ∈ Fdifferenzierbaren Funktion f : F → R. Dann erhalten wir nach der Kettenregelfur die Richtung h und die Funktion fh(t) = f(x + th):

f ′h(0) = ∇f(x)h =n∑

j=1

∂f(x)∂xj

hj .

Ist f konvex, so zeigt der obige Beweis:

fh(t) ≥ fh(0) + f ′h(0)(t− 0) = fh(0) + f ′h(0)t.

Die Wahl h = y − x und t = 1 ergibt somit die charakteristische Eigenschaftdifferenzierbarer konvexer Funktionen f : F → R:

(11) f(y) ≥ f(x) +∇f(x)(y − x) fur alle x,y ∈ F

1.1. Quadratische Funktionen. Eine Funktion f : Rn → R der Form

f(x) =12xT Qx− cTx =

12

n∑i=1

n∑j=1

qijxixj −n∑

j=1

cjxj .

mit einer symmetrischen Matrix Q = [qij ] ∈ Rn×n und c ∈ Rn heisst quadratisch.f(x) hat den Gradienten

∇f(x) = xT Q− cT .

Nach der Kettenregel ergibt sich fur die Richtungsfunktion ph(t) = f(x + th) dieAbleitung

p′h(t) = ∇f(x + th)h = xT Qh− cTh + thT Qh.

Also ist p′h(t) monoton wachsend, wenn hT Qh ≥ 0 gilt.

2. MINIMIERUNG KONVEXER FUNKTIONEN 37

Die Matrix Q heisst positiv semidefinit, wenn fur alle h ∈ Rn gilt:

hT Qh =n∑

i=1

n∑j=1

qijhihj ≥ 0.

Also erhalten wir mit dieser Terminologie:

PROPOSITION 3.1. Die quadratische Funktion f(x) = 12x

T Qx − cT ist genaudann konvex, wenn Q positiv semidefinit ist.

�

Trivialerweise ist die Nullmatrix Q = 0 positiv semidefinit. Also finden wir:

KOROLLAR 3.1. Jede lineare Funktion ist konvex.�

BEMERKUNG. Die Konvexitat linearer Funktionen kann man naturlich viel einfa-cher auch direkt beweisen . . .

2. Minimierung konvexer Funktionen

Wir betrachten bzgl. der differenzierbaren konvexen Funktion f : F → R dasProblem

minx∈F

f(x).

BEMERKUNG. Das Maximierungsproblem ist fur allgemeine konvexe Funktionensehr viel schwerer zu losen! Wir beschranken uns deshalb auf das Minimierungs-problem.

2.1. Notwendige und hinreichende Optimalitatsbedingungen. Welche Be-dingungen muss der Punkt x ∈ F erfullen, damit er als Minimum in frage kommt?

Sei x + h ∈ F und ph(t) = f(x + th). Dann gilt notwendigerweise

(12)n∑

j=1

∂f(x)∂xj

hj = ∇f(x)h = p′h(0) = limt→0+

f(x + th)− f(x)t

≥ 0

Diese Bedingung ist aber auch hinreichend dafur, dass x ein Minimum ist. Dennfur jedes andere y ∈ F gilt dann (mit h = y − x) wegen der Konvexitat von f :

f(y) ≥ f(x) +∇f(x)h ≥ f(x).

Also finden wir:

SATZ 3.1. x ∈ F minimiert die differenzierbare konvexe Funktion f : F → Rgenau dann, wenn x die Bedingung (12) erfullt.

�


2.2. Minimierung uber Teilraumen. Sei f : F → R konvex und differen-zierbar und

F = {x ∈ Rn | Ax = b} (A ∈ Rm×n,b ∈ Rm)

ein affiner Teilraum von Rn. Dann gilt fur jedes x ∈ F und h ∈ Rn:

x + h ∈ F ⇐⇒ x− h ∈ F ⇐⇒ h ∈ ker A.

Der Punkt x ∈ F minimiert also f genau dann, wenn

(13) ∇f(x)h =n∑

j=1

∂f(x)∂xj

hj = 0 fur alle h ∈ ker A.

Die Bedingung (13) besagt, dass ∇f(x) orthogonal zu ker A bzw. dass ∇f(x) imZeilenraum von A liegt (d.h. eine Linearkombination der Zeilenvektoren aT

i von Aist). Als zu (13) aquivalent erhalten wir folglich die Optimalitatsbedingung:

(14) ∇f(x) = yT A =m∑

i=1

yiaTi

fur einen geeigneten Vektor yT = [y1, . . . , ym].

Im Fall einer uberF zu minimierenden quadratischen konvexen Funktion der Formf(x) = 1

2xT Qx−cTx hat man wegen∇f(x) = xT Q−cT somit nur das (lineare)

GleichungssystemQx − ATy = cAx = b

zu losen.

2.2.1. Projektionen auf (affine) Teilraume. Unter der Projektion eines gegebe-nen Vektors p ∈ Rn auf den Teilraum

F = {x ∈ Rn | Ax = b}versteht man einen Vektor p, der den (euklidischen) Abstand zu F minimiert:

‖p− p‖2 = minx∈F‖p− x‖2.

Wegen‖p− x‖2 = (p− x)T (p− x) = pTp− 2pTx + xTx

reduziert sich die Berechnung von p auf das konvexe Minimierungsproblem:

min f(x) =12xTx− pTx s.d. Ax = b.

Also finden wir p als Losung von

x − ATy = pAx = b

Einsetzen von x = p + ATy fuhrt auf das Gleichungssystem

Ap + AATy = b bzw. Ay = b mit A = AAT , b = b−Ap.


2.2.2. Das Regressionsproblem. Die Aufgabe besteht darin, die ”beste“ Losungdes linearen Gleichungssystems

Ax = b

zu bestimmen. Das soll heissen, wir suchen ein x ∈ Rn derart, dass der Abstand‖b−Ax‖ so klein wie moglich ist:

minx∈Rn

‖b−Ax‖2 = bTb− 2bT Ax + xT AT Ax.

Setzen wir cT = bT A und Q = AT A, dann ist das Problem aquivalent mit

minx∈Rn

f(x) =12xT Qx− cTx.

Q = AT A ist positiv semidefinit und folglich f konvex. Also finden wir:

• x ∈ Rn lost das Regressionsproblem genau dann, wenn gilt:

Qx = c bzw. AT Ax = ATb.

Das Regressionsproblem reduziert sich also auf das Losen des linearen Gleichungs-systems Qx = c.

EX. 3.1 (Interpolation). Wir gehen von einer (unbekannten) Funktion f : R → Raus, deren Werte yi = f(ti) wir bei den Stutzstellen t1, . . . , tn festgestellt haben.Wir suchen eine Linearkombination

f(t) =n∑

j=1

ajfj(t)

von gegebenen Funktionen f1(t), . . . , fm(t), die f an den Stutzstellen bestmoglichinterpoliert. Also suchen wir die beste Losung (in den Unbekannten a1, . . . , an)des linearen Gleichungssystems

a1f1(t1) + a2f2(t1) + . . . + anfn(t1) = y1

a1f1(t2) + a2f2(t2) + . . . + anfn(t2) = y2...

......

...a1f1(tm) + a2f2(tm) + . . . + anfn(tm) = ym

Wahlt man beim Interpolationsproblem {f1(t), f2(t)} = {1, t} so spricht manauch von linearer Regression und nennt

f(t) = a1 + a2t

die Regressionsgerade. Im Fall {f1(t), f1(t), f2(t)} = {1, t, t2} erhalt man dasquadratische Regressionspolynom

f(t) = a1 + a2t + a3t2.


2.3. Lagrange-Dualitat. Ein allgemeines mathematisches Optimierungspro-blem hat die Form

(15) minx∈Rn

f(x) s.d. gi(x) ≤ 0 (i ∈ I).

Dabei ist I ein Indexbereicht und f, gi : Rn → R Funktionen, die wir als konvexund differenzierbar annehmen. Wir nehmen weiter I = {1, . . . , n} an. Wir habenalso ein konvexes Minimierungsproblem uber dem Zulassigkeitsbereich

F = {x ∈ Rn | gi(x) ≤ 0, i ∈ I}

vorliegen. Die zugeordnete Lagrange-Funktion ist definiert als

L(x,y) = f(x) +m∑

i=1

yigi(x) = f(x) + yTg(x).

Lagrange fasst das Minimierungsproblem als ein Spiel mit zwei Spielern auf: Dererste will L(x,y) minimieren und darf x wahlen. Der zweite will L(x,y) maxi-mieren und darf die sog. Lagrange-Multiplikatoren yi ≥ 0 festlegen.

Der erste Spieler betrachtet also die Funktion

L1(x) = maxy≥0

L(x,y)

und sucht ein x ∈ Rn mit der Eigenschaft

(16) L1(x) = minx∈Rn

L1(x) = miny≥0

maxx∈Rn

L(x,y).

Der zweite Spieler betrachtet die Funktion

L2(y) = minx∈Rn

L(x,y)

und sucht ein y ≥ 0 mit der Eigenschaft

(17) L2(y) = maxy≥0

L2(y) = maxy≥0

minx∈Rn

L(x,y).

2.3.1. Das primale Problem. Wir beobachten

L1(x) = maxy≥0

f(x) +m∑

i=1

yigi(x) ={

f(x) wenn x ∈ F+∞ wenn x /∈ F .

Also wird der erste Spieler sein x in F wahlen. Das Problem (16) ist somit aqui-valent zum Ausgangsproblem:

minx∈Rn

L1(x) = minx∈F

f(x).


2.3.2. Das duale Problem. Zu einem gegebenen y ≥ 0 stellte die Berech-nung von L2(y) eine konvexes Minimierungsproblem dar. Also gilt die GleichheitL2(y) = L(x,y) genau dann, wenn x ∈ Rn die Optimalitatsbedingung

(18) ∇xL(x,y) = ∇f(x) +m∑

i=1

yi∇gi(x) = 0T .

erfullt. Fur den zweiten Spieler stellt sich damit das duale Problem

(19) maxy≥0

f(x) +m∑

i=1

yigi(x) s.d. ∇f(x) +m∑

i=1

yi∇gi(x) = 0T .

LINEARE PROGRAMME. Wir betrachten als Beispiel das lineare Programmierpro-blem

max cTx s.d. aTi x ≤ bi (i = 1, . . . ,m)

als primales Problem. Sei f(x) = −cTx und gi(x) = aTi x − bi. Fassen wir die

Zeilenvektoren aTi in der Matrix A zusammen, lautet das duale Problem

maxy≥0−cTx + yT (Ax− b) s.d. − cT + yT A = 0T .

Einsetzen von yT A = cT in die duale Zielfunktion ergibt somit die folgende Formdes dualen Problems:

max (−bTy) s.d. ATy = c,y ≥ 0.

Dieses ist aquivalent zu dem sog. dualen linearen Programm

(20) minbTy s.d. ATy = c, y ≥ 0

2.3.3. Schwache Dualitat. Sei x eine zulassige (aber nicht notwendig optima-le) Losung des primalen und y ≥ 0 eine zulassige (aber nicht notwendig optimale)Losung des dualen Lagrangeproblems, d.h.

∇f(x) +m∑

i=1

yi∇gi(x) = 0T .

Dann gilt naturlich fur die entsprechenden Zielfunktionswerte

(21) L1(x) = f(x) ≥ f(x) +m∑

i=1

yigi(x) = L2(y).

Dies ist als das Phanomen der schwachen Dualitat bekannt.


EX. 3.2. Im Fall des linearen Programms

max cTx s.d. Ax ≤ b

mit der zu minimierenden Zielfunktion f(x) = −cTx ergibt die schwache Dualitatwegen cT = yT A:

f(x) = −cTx ≥ −cTx + yT (Ax− b) = −yTb

bzw.

cTx ≤ bTy

2.3.4. Die KKT-Bedingungen. Fassen wir die primalen und dualen Restriktio-nen aus dem Lagrange-Ansatz zusammen, so suchen wir einen Punkt x ∈ Rn zudem ein y ≥ 0 existiert mit den Eigenschaften

(22)

∇f(x) +m∑

i=1

yi∇gi(x) = 0T

m∑i=1

yigi(x) = 0

gi(x) ≤ 0 (i = 1, . . . ,m)y ≥ 0

Ein solches x heisst Karush-Kuhn-Tucker-Punkt (KKT-Punkt) bzgl. des Optimie-rungsproblems

min f(x) s.d. gi(x) ≤ 0 (i = 1, . . . ,m)

und (22) sind die sog. KKT-Bedingungen.

PROPOSITION 3.2. Sei x∗ ein KKT-Punkt mit zugehorigem y∗ ≥ 0. Dann ist x∗

eine Optimallosung des konvexen Minimierungsproblems (15).

Beweis. x∗ erfullt alle Restriktionen gi(x∗) ≤ 0 und minimiert die konvexe Funk-tion

L(x,y∗) = f(x) +n∑

i=1

y∗i gi(x) ≤ f(x) (wegen y∗ ≥ 0).

Aus (y∗)Tg(x∗) = 0 folgt f(x∗) = L(x∗,y∗). D.h. f(x∗) ist minimal.�

BEMERKUNG. Die KKT-Bedingungen sind bei allgemeinen (nicht-konvexen) ma-thematischen Optimierungsproblemen weder hinreichend noch notwendig fur Op-timalitat.


2.4. Lineare Nebenbedingungen. Wir betrachten hier den Fall linearer (ei-gentlich: affiner) Restriktionsfunktionen gi(x) = aT

i x−bi, sodass die Nebenbedin-gungen in kompakter Matrixschreibweise die Form Ax ≤ b haben. Der Zulassig-keitsbereich ist das Polyeder

F = P (A,b) = {x ∈ Rn | aTi x ≤ bi, i = 1, . . . ,m}.

Sei x ∈ F . Um Optimallosung zu sein, muss gelten

∇f(x)h ≥ 0 wenn x + h ∈ F , d.h. aTi x + aT

i h ≤ bi (i = 1, . . . ,m).

Sei J(x) die Menge der Indizes i mit aTi x = bi. Dann muss also die Implikation

AJ(x)h = 0 =⇒ −∇f(x)h ≤ 0

erfullt sein. Folglich (nach dem Farkas-Lemma) muss −∇f(x) eine nichtnegativeLinearkombination der Zeilen von AJ(x) sein. Mit anderen Worten: Es existiert einy ≥ 0 so, dass

−∇f(x) =n∑

i∈J(x)

yiaTi .

OBdA konnen im Fall i /∈ J(x) die Gleichheit yi = 0 voraussetzen. Dann ergibtsich auch

yT (Ax− b) =m∑

i=1

yi(aTi x− bi) = 0.

Damit sind notwendigerweise die KKT-Bedingungen unter linearen Restriktionenerfullt:

∇f(x) + yT A = 0yT (Ax− b) = 0

Ax ≤ by ≥ 0

Wir finden:

SATZ 3.2. Die KKT-Bedingungen sind hinreichend und notwendig dafur, dass x∗

eine Optimallosung eines konvexen Optimierungsproblems folgender Form ist:

minx∈Rn

f(x) s.d. Ax ≤ b.

�

2.4.1. Lineare Programme. Man beachte: Ist f(x) nicht linear, dann ergebendie KKT-Bedingungen (selbst bei linearen Restriktionen) ein nichtlineares(!) Un-gleichungssystem.

Im Fall des linearen Programms

max cTx s.d. Ax ≤ b


ergeben die KKT-Bedingungen jedoch das lineare Ungleichungssystem

ATy = ccTx − bTy = 0Ax ≤ b

y ≥ 0

2.4.2. Starke Dualitat. Wir betrachten das primal-duale Paar linearer Program-me

max cTx s.d. Ax ≤ bmin bTy s.d. ATy = c,y ≥ 0.

Die schwache Dualtitat besagt fur beliebige jeweils zulassige Losungen x und y:

cTx ≤ bTy.

Im Fall von Gleichheit mussen folglich beide Losungen optimal sein. Die KKT-Bedingungen garantieren bei einer optimalen Losung x∗ ein dual zulassiges y∗

mitcTx∗ = bTy∗.

Also schliessen wir

SATZ 3.3 (Starke Dualitat). Genau dann ist die primal zulassige Losung x optimal,wenn es eine dual zulassige Losung y gibt mit der Eigenschaft

cTx = bTy.

In diesem Fall ist y notwendigerweise dual optimal.�

3. Newtons Methode und die Methode innerer Punkte

Die Berechnung von Koordinatenvektoren, welche die KKT-Bedingungen erfullen,erfordert die Berechnung von nichtnegativen Losungen gewisser (meist) nichtli-nearer Gleichungssysteme, die wir in der allgemeinen Form

F (x) = 0,x ≥ 0

notieren. Dabei ist F : Rn → Rm eine Funktion, die aus m Koordinatenfunktionenfi : Rn → R zusammengesetzt ist:

F (x) =

f1(x)...

fm(x)

∈ Rm .

Die exakte Losung einer nichtlinearen Gleichung ist im allgemeinen sehr schwer.Oft genugt aber schon eine ”hinreichend gute“ approximative Losung.

3. NEWTONS METHODE UND DIE METHODE INNERER PUNKTE 45

3.1. Newtons Methode. Zur approximativen Losung der Gleichung

F (x) = 0

geht Newtons Methode iterativ vor. Man beginnt mit einem x0 ∈ Rn und berechnetdann iterativ x1, . . . ,xk, . . .. Man stoppt im Fall

F (xk) ≈ 0.

Ansonsten sucht man sich eine lineare Approximation von F bei xk, d.h. eine Ma-trix Ak derart, dass

F (xk + h) ≈ F (xk) + Akh (wenn ‖h‖ hinreichend klein),

und berechnet eine Losung hk des linearen(!) Gleichungssystems

Akh = −F (xk).

Nun setzt man xk+1 = xk + hk usw.

BEMERKUNG. Wenn F differenzierbar ist, wahlt man gerne die Jacobimatrix, dieals Zeilen gerade die m Gradienten ∇fi(xk) besitzt:

Ak = ∇(xk) =[∂fi(xk)

∂xj

]∈ Rm×n

EX. 3.3. Wir suchen eine Losung der Gleichung

f(x) = x2 − 2 = 0.

Man beginnt mit einem x0. Ist xk schon berechnet, wahlt man z.B. Ak = f ′(xk)und erhalt

f ′(xk)h = −f(xk) d.h. hk =−f(xk)f ′(xk)

=−x2

k + 22xk

und somitxk+1 = xk + hk =

xk

2+

1xk

.

BEMERKUNG. Im allgemeinen hat man keine Garantie, dass das Newtonverfahrentatsachlich zu einer zulassigen Losung der Ausgangsgleichung konvergiert.

3.2. Die Methode der inneren Punkte. Wir wollen ein KKT-Punkt fur daslineare Programm

max cTx s.d. Ax ≤ b (A ∈ Rm×n,b ∈ Rm)

bestimmen. Setzen wir s = b−Ax, dann sind die KKT-Bedinungen

(23)

siyi = µ (i = 1, . . . ,m)Ax + s = b

ATy = cs,y ≥ 0

mit µ = 0 gegeben. Wir relaxieren nun, indem wir einen Parameter µ > 0 wahlenund das resultierende System mit einem Newtonverfahren zu losen versuchen. In


diesem Fall mussen wir immer si > 0 und yi > 0 (d.h. s,y > 0) sicherstellen.Deshalb spricht man von ”inneren Punkten“ (des positiven Quadranten von Rm).

LEMMA 3.3. Sei (xµ,yµ, sµ) eine Losung des Systems (24) zu µ > 0. Dann istxµ eine zulassige Losung des linearen Programms. Und fur jede andere zulassigeLosung x gilt

cTxµ ≥ cTx− ε (mit ε ≤ mµ).

Beweis. Aus der schwachen Dualitat folgt

cTx ≤ bTyµ = (Axµ + sµ)Tyµ = (xµ)ATyµ + sµyµ = cTxµ + mµ.

�Im Fall µ → 0 sind die xµ also annahernd optimale Losungen des ursprunglichenlinearen Programms.

Um (24) mit einem Newtonansatz zu losen, gehen wir davon aus, dass wir Vektoreny > 0 und x schon zur Verfugung haben mit der Eigenschaft

c = ATy und s = b−Ax > 0.

Wir suchen dann ∆x,∆y,∆s so, dass

(24)

(si + ∆si)(yi + ∆yi) = µ (i = 1, . . . ,m)A(x + ∆x) + (s + ∆s) = b

AT (y + ∆y) = cs + ∆s,y + ∆y ≥ 0

Nach unseren Annahmen uber x und y reduziert sich diese Aufgabe auf das Losenvon

(25)

si∆yi + yi∆si + ∆si∆yi = µ− siyi (i = 1, . . . ,m)A∆x + ∆s = 0

AT ∆y = 0s + ∆s,y + ∆y ≥ 0

Das letztere System relaxieren wir nun zu dem linearen Gleichungssystem

(26)si∆yi + yi∆si = µ− siyi (i = 1, . . . ,m)

A∆x + ∆s = 0AT ∆y = 0

Mit dessen Losung datiert man auf:

x+ = x + ∆x,y+ = y + ∆y, s+ = ∆s

und verfahrt nun wie zuvor mit x+ und y+ anstelle von x und y (wobei manin jeder Iteration auch den Parameter µ reduziert), bis man eine hinreichend guteLosung x des Ausgangsproblems gefunden hat.

Man kann zeigen, dass dieses Verfahren funktioniert und (sehr schnell!) gegen eineoptimale Losung des Ausgansproblems konvergiert.

KAPITEL 4

Die Simplexmethode

Unter einem linearen Programm (LP) versteht man ein Optimierungsproblem, dasin der folgenden Form prasentiert werden kann:

(27) max cTx s.d Ax ≤ b.

Dabei sind c ∈ Rn, A = [aij ] ∈ Rm×n und b ∈ Rm problemabhangige Para-meter, die wir uns als gegeben vorstellen. Ein lineares Programm in der Form (27)will also die konvexe Funktion f(x) = −cTx unter linearen Nebenbedingungenminimieren.

EX. 4.1. Ein Optimierungsproblem der Form

min cTx s.d. Ax = b,x ≥ 0

ist ein LP. Denn: es ist aquivalent zu dem linearen Programm

max (−c)Tx s.d. Ax ≤ b,

wobei sich die Matrix A und der Koeffizientenvektor b aus A und b so ergeben:

A =

A−A−I

b =

b−b0

.

(I = Einheitsmatrix entsprechender Dimension.)

Die KKT-Bedingungen fur eine Optimallosung von (27) lauten:

cTx = bTyAx ≤ bATy = cy ≥ 0

Komplementarer Schlupf. Aus der schwachen Dualtitat wissen wir, dass

cTx ≤ bTy

gilt, sofern Ax ≤ b und c = ATy mit y ≥ 0 erfullt sind. In diesem Fall ist dieOptimalitat dann gleichbedeutend mit der Gleichheit

cTx = bTy.

47

48 4. DIE SIMPLEXMETHODE

Diese Bedingungen kann man auch so formulieren. Wir definieren den Vektor svon Schlupfvariablen si als

s = b−Ax (d.h. Ax ≤ b⇔ s ≥ 0).

Dann ergibt sich im Fall c = ATy:

sTy = (b−Ax)Ty = (bT − xT AT )y = bTy − cTx

und somitsTy = 0 ⇐⇒ cTx = bTy.

Bezeichnen wir mit aTi die Zeilenvektoren der Matrix A, so finden wir:

LEMMA 4.1 (”Komplementarer Schlupf“). Genau dann ist x ∈ P (A,b) optimalfur das lineare Programm (27), wenn es ein y gibt mit der Eigenschaft

(i) ATy = c und y ≥ 0;(ii) aT

i x < bi =⇒ yi = 0 (fur alle i = 1, . . . ,m).

Beweis. x ∈ P (A,b) ist es genau dann optimal, wenn es zu x ein y gibt, das denKKT-Bedingungen genugt. Die sind c = ATy = c, y ≥ 0 und

0 = sTy =m∑

i=1

siyi =m∑

i=1

(bi − aTi x)yi.

Wegen s ≥ 0 und y ≥ 0 ist sTy = 0 gleichbedeutend mit siyi = 0 fur allei = 1, . . . ,m. Letzteres ist aber nichts anderes als die Eigenschaft (ii).

�

Lineare Ungleichungssysteme. Die KKT-Bedingungen zeigen, dass die Aufgabe,ein lineares Programm zu losen, darauf zuruckgefuhrt werden kann, ein linearesUngleichungssystem zu losen. Im Prinzip kann man also lineare Programme mitdem FM-Verfahren losen.

Umgekehrt kann naturlich jeder Algorithmus, der ein lineares Programm lost, dazubenutzt werden, ein lineares Ungleichungssystem zu losen. Man braucht ja nur einekunstliche Zielfunktion einfuhren. z.B.

Ax ≤ 0 ←→ max 0Tx s.d. Ax ≤ b.

Also erkennt man:

• Das Losen von linearen Programmen und das Losen von (endlichen)linearen Ungleichungssystemen ist algorithmisch aquivalent.

1. LP-Dualitat

Wir hatten gesehen, dass die Lagrangedualitat als zu (27) ”duales“ Problem fol-gendes Problem ergibt:

(28) minbTy s.d. ATy = c,y ≥ 0.

1. LP-DUALITAT 49

DEFINITION. Seien nun (P ) und (P ′) beliebige lineare Programme. Nehmen wiran, (P ) sei aquivalent mit (27). Wir nennen dann (P ′) zu (P ) dual, wenn (P ′) zu(28) aquivalent ist.

Die in den KKT-Bedingungen gefassten Optimalitatskriterien fur lineare Program-me besagen somit, dass x ∈ P (A,b) genau dann fur (27) optimal ist, wenn es einfur (28) zulassiges y mit dem gleichen Zielfunktionswert

bTy = cTx

gibt. Naturlich ist dann y optimal fur (28). In diesem Sinn bedeutet das Losen eineslinearen Programms, dass das dazu duale gleichzeitig mitgelost wird.

EX. 4.2. Wir betrachten das Problem

min 2x1 − x2 + 13x3

s.d x1 + x2 −2x3 ≥ 13x1 + 4x2 2x3 ≤ 2/3x1 ≥ 0.

Dieses lineare Programm ist aquivalent zu

max −2x1 + x2 − 13x3

s.d −x1 − x2 +2x3 ≤ −13x1 + 4x2 2x3 ≤ 2/3−x1 ≤ 0.

Dual dazu ist das lineare Programm

min −y1 + 23y2

s.d −y1 + 3y2 − y3 = −2−y1 + 4y2 = 12y1 + 2y2 = −1/3y1 , y2 , y3 ≥ 0

Das letzte lineare Programm ist z.B. aquivalent mit

max y1 − 23y2

s.d y1 − 3y2 ≤ 2−y1 + 4y2 = 1−2y1 − 2y2 = 1/3y1 , y2 ≥ 0

1.1. Das lineare Produktionsmodell. Wir gehen von einer Situation aus, woBedarfsguter der Typen P1, P2, . . . , Pn produziert werden sollen. Dazu mussenRohstoffe R1, . . . , Rm verwendet werden. Die okonomischen Produktionsparame-ter seien

aij = benotigte Menge von Ri zur Produktion einer Einheit von Pj

cj = Gewinn pro Einheit bei Produktion von Pj

bi = Anzahl Einheiten von Ri im Vorrat


Das Ziel der Gewinnmaximierung ergibt den optimalen Produktionsplan als Opti-mallosung des folgenden linearen Programms:

(29)

max c1x1 + . . . + cnxn

s.d. a11x1 + . . . + a1nxn ≤ b1...

...am1x1 + . . . + amnxn ≤ bm

x1, . . . , xn ≥ 0

Welchen Marktwert haben die Guter Ri? Der Preis sollte sicherstellen, dass zu-mindest die zugekauften Guter bei einer Umwandlung in Produkte ihren Preis alsGewinn wieder einspielen. Also will man das folgende lineare Programm losen:

(30)

min b1y1 + . . . + bmym

s.d. a11y1 + . . . + am1ym ≥ c1...

...a1ny1 + . . . + amnym ≥ cn

y1, . . . , ym ≥ 0

Problem (29) ist in Matrixschreibweise

max cTx s.d.[

A−I

]x ≤

[b0

]Das dazu duale Problem ist

minbTy s.d. ATy − Iz = c, y ≥ 0, z ≥ 0.

Wegen z ≥ 0 ist letzteres aber aquivalent mit (30):

minbTy s.d. ATy ≥ c,y ≥ 0.

BEMERKUNG. Die Preise y∗1, . . . , y∗m, die sich als Optimallosung von (30) ergeben,

sind die sog. Schattenpreise der Guter R1, . . . , Rm.

2. Die Simplexmethode

Wir gehen von einem Optimierungsproblem der Form

(31) min cTx s.d. Ax = b,x ≥ 0

aus, wobei die Problemparameter c ∈ Rn,b ∈ Rm und A = [aij ] ∈ Rm×n

gegeben seien. OBdA nehmen wir an, dass A vollen Zeilenrang m = rg A hat.Wir stellen uns vor, dass unser Optimierungsproblem gewisse ”Kosten“ minimierenwill beziehen uns deshalb auf c als den Vektor von Kostenkoeffizienten.

Die KKT-Bedingungen lauten

cTx = bTyAx = bATy ≤ cx ≥ 0

2. DIE SIMPLEXMETHODE 51

Ein KKT-Paar (x∗,y∗) liefert gleichzeitig eine optimale Losung des Problems

(32) max bTy s.d. ATy ≤ c.

Wir nennen (31) in diesem Zusammenhang das primale und (32) das duale Pro-blem.

Die zentrale Idee des Simplexalgorithmus ist, die Ecken (d.h. die Basislosungen)der beiden Zulassigkeitsbereiche

P = {x ∈ Rn | Ax = b,x ≥ 0}P ∗ = {y ∈ Rm | ATy ≤ c}

zu untersuchen. Sei also B = {r1, . . . , rm} ⊆ {1, . . . , n} eine Indexmenge derart,dass die aus den entsprechenden Spalten von A gebildete (m×m)-Matrix AB eineSpaltenbasis von A (bzw. AT

B eine Zeilenbasis von AT ) ist. Wir nennen oft kurzauch die Indexmenge B selber eine Basis.

Zur leichteren Notation setzen wir N = {1, . . . , n} \ B und bezeichnen mit cB

den Teilvektor von c, der nur aus den B-Komponenten besteht etc. Wir ordnen Bdie folgenden Kandidaten fur Optimallosungen zu:

x ∈ Rn mit xB = A−1B b, xN = 0N .

y ∈ Rm mit y = (ATB)−1cB.

Dann gilt auf jeden Fall die Gleichheit

cTx = cTBxB + cT

NxN = (ATBy)TxB = yT ABx = yTb.

Ausserdem beobachtet man(Z) x ∈ P ⇐⇒ xB ≥ 0B .

(Z∗) y ∈ P ∗ ⇐⇒ ATNy ≤ cN .

BEMERKUNG. Wegen rg AB = m ist klar, dass die B zugeordneten Punkte mitden Koordinaten x und y Ecken sind, sofern sie zu P bzw. P ∗ gehoren.

Ziel ist es nun, eine Indexmenge B (bzw. eine Spaltenbasis AB) zu bestimmen, diesowohl Zulassigkeit bzgl. P als auch Zulassigkeit bzgl. P ∗ zur Folge hat.

2.1. Das Simplextableau. Traditionell geht man in der Analyse des Simplexal-gorithmus immer von einer Darstellung der Spaltenvektoren bzgl. der gerade be-trachteten Basis AB aus. D.h. anstelle der Restriktion in der Form

Ax = ABxB + ANxN = b

haben wir die Restriktionen in der Form

A−1B Ax = IBx + ANxN = b mit AN = A−1

B AN ,b = A−1B b.

Mit anderen Worten: Setzen wir A = A−1B A, dann erhalten wir eine vollstandig

aquivalente Formulierung des primalen Problems (31) in der Form

min cTx s.d. Ax = b,x ≥ 0.


Bzgl. y = (ATB)−1cB definieren wir die reduzierten Kosten als den dualen Schlupf

c = c−ATy bzw. cT = cT − yT A = cT − cTBA.

Dann haben wir cB = 0B . Das Paar (x,y) erfullt folglich die KKT-Bedingungengenau dann, wenn gilt:

(Z) xB = b ≥ 0;(Z∗) cT

N = cTN − cT

BAN = cTN − yT AN ≥ 0T

N .

Schreiben wir z = cTx, dann bedeutet der Basiswechsel: Von den Ausgangsdaten

z = cTxb = Ax ←→

[0 cT

B cTN

b AB AN

]geht man uber zu dem Koeffizientenschema

(33)[−z 0T

B cTN

b IB AN

]mit z = cT

Bb = cTx = cTBA−1

B b = bTy.

Das Parameterschema (33) ist das sog. Simplextableau bzgl. der Indexmenge B.Rechnerisch ist es sehr einfach zu ermitteln:

• Man fuhrt auf den Ausgangsdaten Pivotoperationen (elementareZeilenoperationen) aus, bis in den B-Spalten die Teilmatrix[

0TB

IB

]erreicht ist.

MAN BEACHTE: In der linken oberen Ecke des Simplextableaus steht der negativeZielfunktionswert bzgl. der gerade betrachteten Basisvektoren x und y! Um diesen

”Schonheitsfehler“ auszugleichen, findet man in der Literatur das Simplextableauoft mit den negativen Kostenkoeffizienten angegeben:[

0 −cTB −cT

Nb AB AN

]−→

[z 0T

B −cTN

b IB AN

](Man kann diese zweite Version des Simplextableaus naturlich auch direkt von derDarstellung

z −cTx = 0Ax = b

her motivieren, wenn man mochte.)

TERMINOLOGIE. Die Variablen xi mit Index i ∈ B heissen Basisvariablen (bzgl.B). Die xj mit j ∈ N sind die Nichtbasisvariablen.

NOTA BENE. Bei einem Simplextableau gehen wir immer von einer Problem-formulierung vom Typ (31) aus. Insbesondere unterstellen wir automatisch, dasssamtliche Variablen xj nichtnegativ sein sollen.


2.2. Die primale Strategie. Wir nehmen an, wir hatten (irgendwie) eine BasisB gefunden derart, dass das zugehorige Simplextableau primal zulassig ist, d.h.

b = A−1B b = xB ≥ 0B.

Mit Aj bezeichnen wir den jten Spaltenvektor von A. Im Fall

cj = cTBAj = cT

BA−1B Aj ≥ 0 fur alle j ∈ N

ist eine Optimallosung gefunden. Seien also cj < 0 fur ein j ∈ N . Wir wollen eink ∈ B bestimmen, sodass

B′ = (B ∪ {j}) \ {k}

eine primal zulassige Basis ist. Der einfachen Notation wegen nehmen wir an, wirhatten die Indices so (um)numeriert, dass

B = {1, . . . ,m}

gilt. Wir suchen nun in der Spalte Aj einen Koeffizienten akj > 0 mit der Eigen-schaft

(34)bk

akj= min

i

{bi

aij| aij > 0

}TERMINOLOGIE. Das nach (34) bestimmte Element akj heisst Pivotelement.

LEMMA 4.2. Gilt aij ≤ 0 fur i = 1, . . . ,m, dann ist das Problem (31) unbe-schrankt und besitzt keine Optimallosung. Ist der Index k gemass der Pivotregel(34) definiert, dann ist B′ = (B ∪ {j}) \ {k} primal zulassig.

Beweis. Im Fall Aj ≤ 0 betrachten wir ein beliebiges λ > 0 und setzen

x′j = λ

x′i = bi − aijλ (i ∈ B)x′` = 0 (` ∈ N \ {j}).

Aus dem Simplextableau ist klar, dass das entsprechende x′ ∈ Rn primal zulassigist. Der Zielfunktionswert ist

cTx′ = cTBb− cT

BAjλ + cjλ = cTBb + cjλ → −∞ (wenn λ→ +∞).

Im zweiten Fall fuhren wir elementare Zeilenoperationen auf dem Simplextableauaus, welche die jte Spalte in den kten Einheitsvektor uberfuhren. Alle Spalten bzgl.B \ {k} bleiben dann Einheitsvektoren und die Aufdatierung von b ergibt

b′k = bk/akj ≥ 0

b′i = bi − aijbk/akj ≥ 0 .

�

Algorithmus. Wenn einmal eine primal zulassige Basis zur Verfugung steht, danniteriert man nach der Regel (34) solange, bis man zu einer Basis B gekommen


ist, bei der alle reduzierten Kosten nichtnegativ sind. Eine Optimallosung ist danngefunden mit

xB = b und xN = 0N .

Ist die Regel (34) nicht anwendbar, so weiss man, dass das Ausgangsproblem keineOptimallosung besitzt. Die Suche nach einer solchen erubrigt sich dann.

BEMERKUNG. An dieser Stelle bleiben noch zwei Fragen offen:

1. Wie findet man eine primal zulassige Basis uberhaupt?2. Terminiert die primale Strategie nach endlich vielen Iterationen?

Auf beide Fragen wird spater noch eingegangen.

2.3. Die duale Strategie. Wir nehmen nun an, die momentane Basis B istdual zulassig, d.h. die reduzierten Kosten c` sind alle nichtnegativ bzw. der Vektory ist eine Ecke von P ∗.

Ist Optimalitat noch nicht gegeben, existiert ein bk < 0. Wir suchen nun ein Pivot-element akj (in der k-Zeile der gegenwartigen Simplextableaus) derart, dass

B′ = (B \ {k}) ∪ {`}

wieder eine dual zulassige Basis ist. Wir wahlen die Spalte j (und folglich dasPivotelement akj < 0) nach der Pivotregel

(35)cj

akj= max

`

{c`

ak`| ak` < 0

}

LEMMA 4.3. Gilt ak` ≥ 0 fur ` = 1, . . . , n, dann besitzt Problem (31) keinezulassige Losung. Ist der Index j gemass der Pivotregel (35) bestimmt, dann istB′ = (B ∪ {j}) \ {k} dual zulassig.

Beweis. Ein zulassige Losung x1, . . . , xn ist nichtnegativ, also hatte man im Fallak` ≥ 0:

0 > bk =n∑

`=1

ak`x` ≥ 0,

was nicht sein kann. Sei nun akj gemass (35) gewahlt. Datieren wir das Simplex-tableau wieder so auf, dass die jte Spalte zum jten Einheitsvektor wird, so ergibtsich die erste Zeile des aufdatieren Tableaus so:

• Subtrahiere cj mal die neue Zeile k vom reduzierten Kostenvektor cT ≥0T .

Der Koeffizient in Spalte ` ist also

c′` = c` − cjak`/akj ≥ 0.

�


2.4. Die revidierte Simplexmethode. Bei der Organisation der notwendigenRechenschritte stellt sich heraus, dass es nicht notwendig ist, immer das gesamteSimplextableau zu berechnen. Zu der Basis B ⊆ {1, . . . , n} kann man immer dienotwendige Information direkt aus den Ausgangsparametern gewinnen:

• Berechne b = A−1B b als Losung der Gleichung ABx′ = b.

• Berechne yT = cTBA−1

B als Losung der Gleichung ATBy′ = cB .

Dann erhalten wir fur die reduzierten Kosten

cj < 0 ⇐⇒ cj − yT Aj < 0 d.h. cj <m∑

i=1

yiaij .

Nun kann z.B. bei der primalen Strategie sofort ein Pivotelement akj nach derRegel (34) in der Spalte Aj = A−1

B Aj gewonnen und die Basisaufdatierung

B → B′ = (B ∪ {j}) \ {k}

durchgefuhrt werden. Diese frugale Version der Simplexmethode ist als revidierteSimplexmethode bekannt.

BEMERKUNG. Oft gibt es mehrere Kandidaten, die als Pivotspalten (bzw. -elemente)infrage kommen. Es ist keine Regel bekannt, die in solchen Fallen (mathematischbeweisbar) immer ”die beste Wahl“ trifft.

2.4.1. Das Schnittmusterproblem. Es seien Stoffballen der Lange ` gegeben.Davon sollen bi Schnittstucke der Breite ì (i = 1, . . . ,m) gewonnen werden,sodass insgesamt moglichst wenig Ballen angeschnitten werden.

Zur Modellierung des Problems definieren wir als Schnittmuster einen Vektora1...

am

mit ai ∈ N undm∑

i=1

aiì ≤ `.

Sei A die Matrix, deren Spalten samtliche moglichen Schnittmuster sind. Mit derNotation 1T = [1, 1, . . . , 1] ergibt sich das Schnittmusterproblem dann in Matrix-form:

min1Tx s.d Ax = b,x ≥ 0 und ganzzahlig.

Wegen der Ganzzahligkeitsrestriktion ist dieses Problem kein lineares Programm.Wir deshalb statt dessen die zugeordnete LP-Relaxierung

(36) min1Tx s.d Ax = b,x ≥ 0,

die zumindest eine Untergrenze fur den gesuchten Optimalwert liefert. Die Losunghat typischerweise Komponenten, die nicht ganzzahlig sind. Durch Runden erhaltman daraus meist eine recht gute praktische Losung.

Da A sehr viele Spalten haben kann, ist ein explizites Auflisten nicht erstrebens-wert. Wir losen (36) darum mit der revidierten Simplexmethode.


Haben wir schon eine Basis B von Schnittmustern gefunden und den entsprechen-den Vektor y berechnet, so ergibt die Suche nach einem Schnittmuster mit negati-ven reduzierten Kosten das Problem, a1, . . . , am ∈ N zu ermitteln mit der Eigen-schaft

(37) 1 <m∑

i=1

yiai undm∑

i=1

aiì ≤ `.

BEMERKUNG. Problem (37) ist (wegen der Ganzzahligkeitsbedingung) ein sog.NP-schweres Problem, also theoretisch schwierig. In der Praxis lasst es sich abersehr gut losen.

3. Die Zweiphasenmethode

Es soll nun gezeigt werden, dass die Simplexmethode so implementiert werdenkann, dass nur endlich viele Iterationen stattfinden. Wir betrachten hier die primaleStrategie. (Mit der dualen Strategie kann man analog verfahren, wenn man will.)

Der Kern der Methode besteht darin, (unabhangig von der Zielfunktion) eine pri-mal zulassige Basis zu zu bestimmen. Von dieser Basis lasst sich dann in einerweiteren algorithmischen Phase bezuglich der eigentlichen Zielfunktion weiter-rechnen.

3.1. Phase 1. Wir betrachten das System

(38) Ax = b,x ≥ 0 (A ∈ Rm×n,b ∈ Rm)

und suchen eine Basis B derart, dass xB = A−1B b ≥ 0. OBdA durfen wir b ≥ 0

annehmen (sonst multipliziert man entsprechnede Zeilen mit (−1)). Nun erwei-tern wir das Problem um die nichtnegativen Variablen z1, . . . , zm und wollen daslineare Programm

(39) minm∑

i=1

zi s.d. Iz + Ax = b,x ≥ 0, z ≥ 0

losen. Offensichtlich besitzt (38) genau dann eine zulassige Losung, wenn (39)eine Optimallosung (x, z) mit Zielfunktionswert 0, d.h.

z1 = . . . = zm = 0

besitzt. Die Basis B einer solchen Optimallosung ergibt b als nichtnegative Line-arkombination von linear unabhangigen Spalten von A. Diese konnen folglich zueiner zulassigen Spaltenbasis AB von A erweitert werden. Damit ist das gesuchteB gefunden (sofern (38) uberhaupt losbar ist).

Wir beobachten, dass (wegen b ≥ 0) die Teilmatrix I der ersten m Spalten vonD = [I|A] trivialerweise eine primal zulassige Spaltenbasis bzgl. (39) ist. Wirbeginnen die primale Strategie mit dieser Basis und wahlen die weiteren Pivotele-mente nach einer modifizierten primalen Pivotregel.

Dazu bezeichnen wir in jeder Iteration des Simplexalgorithmus mit

αi = (bi, di1, . . . , dim) (i = 0, 1, . . . ,m)

3. DIE ZWEIPHASENMETHODE 57

die aus b und den Anfangsstucken der Lange m der Zeilen des Simplextableausgebildeten Vektoren. Zu Beginn haben wir also

α0

α1...

αm

=

b0 0 . . . 0b1 1 . . . 0...

.... . .

...bm 0 . . . 1

mit − b0 = b1 + . . . + bm.

Wir nennen einen Koordinatenvektor x lexikographisch positiv, wenn die erste(von links gelesen) Koordinate 6= 0 positiv ist. y ist lexikgraphisch grosser als x,wenn der Differenzvektor y−x lexikographisch positiv ist. Z.B. sind die Vektorenα1, . . . , αm alle lexikographisch positiv.

Die lexikographische (primale) Pivotregel bestimmt das Pivotelement dkj in derSpalte j des Simplextableaus nun so, dass

(40)αk

dkj

= lex-min{

αi

dij

| dij > 0.

}

LEMMA 4.4. Sind α1, . . . , αm lexikographisch positiv, dann auch die entsprechen-den α′1, . . . , α

′m nach dem Pivotieren gemass (40).

Beweis. Division durch eine positive Zahl erhalt die lexikographische Positivitat.Also ist α′k = αk/dkj lexikographisch positiv. Fur i 6= k ergibt sich die Behaup-tung aus

α′i = αi −dij

dkj

αk (lex. pos., falls dij ≤ 0)

= dij

[αi

dij

− αk

dkj

](lex. pos., falls dij > 0).

�

SATZ 4.1. Die lexikographische Pivotregel garantiert, dass keine Basis wiederholtwird (und folglich die Anzahl der Iterationen endlich ist).

Beweis. Der reduzierte Kostenkoeffizient cj ist negativ und αk lexikographischpositiv. Also ist

α′0 = α0 − cjαk

immer lexikographisch grosser als α0. Das heisst, dass alle Vektoren α0 vonein-ander verschieden sind. Folglich mussen auch die zugehorigen Basen voneinanderverschieden sein. (Denn ein Simplextableau wird eindeutig von der zugehorigenBasis bestimmt.)

�BEMERKUNG. Die lexikographische Regel ist nicht die einzige, die Endlichkeitdes Simplexverfahrens garantiert. Sie ist aber mathematisch am einfachsten zu be-weisen.


3.2. Phase 2. In der Phase 1 stellen wir entweder fest, dass das lineare Pro-gramm (31) keine zulassige Losung besitzt, oder wir konnen (z.B. mit der lexiko-graphischen Regel) eine zulassige Basis B berechnen.

Haben wir B, dann konnen wir nun das Simplextableau zur tatsachlichen Ziel-funktion aufstellen und weiterrechnen. Um Endlichkeit zu garantieren, kann manwieder die lexikographische Regel verwenden (nun relativ zur Startbasis B undnicht mehr zu I).

Damit erkennen wir:

SATZ 4.2. Ein lineares Programm ist entweder unzulassig oder unbeschrankt oderbesitzt eine (optimale) Basis, die primal und dual zulassig ist.

Beweis. Wenn der Simplexalgorithmus stoppt, ist genau eine der im Satz behaup-teten Eigenschaften nachgewiesen.

�

3.3. Sensitivitatsanalyse. Sei B eine primal zulassige Basis fur das lineareSystem

Ax = b,x ≥ 0.

FRAGE: Fur welche Zielfunktionsparameter c ∈ Rn ist die zu B gehorige Ba-sislosung x optimal?

Wir wissen: B ist optimal, wenn die reduzierten Kosten nichtnegativ sind:

cTN = cT

N − cTBA−1

B AN ≥ 0TN bzw. (A−1

B AN )TcB − INcN ≤ 0N .

Die dieser Ungleichung genugenden c sind genau die Elemente des polyedrischenKegels

P ([A−1B AN )T | − IN ],0).

Man kann daraus ablesen, welche Veranderungen der Zielfunktionsparameter zu-lassig sind, wenn man weiterhin die Optimalitat einer gefundenen Losung garan-tieren will.

Ist B dual zulassig bzgl. den festen Zielfunktionsparametern c, so stellt sich dualdie

FRAGE: Fur welche Restriktionsparameter b ∈ Rm ist die zu B gehorige Ba-sislosung x optimal?

nach der primalen Zulassigkeit von b = A−1B b ≥ 0. Wieder erhalten wir einen

polyedrischen Kegel:

P (−A−1B ,0).

4. DIE PRIMAL-DUALE METHODE 59

4. Die primal-duale Methode

Wieder betrachten wir ein Paar dualer linearer Programme:

min cTxAx = bx ≥ 0

←→max bTy

ATy ≤ c

Wir mochten nun das Konzept des komplementaren Schlupfes ausnutzen, um zueiner Optimallosung zu kommen.

ANNAHME: Wir haben schon (irgend)eine dual zulassige Losung y zur Verfugungund kennen einen Vektor x = [x1, . . . , xn]T ≥ 0 mit der Eigenschaft

xj > 0 =⇒ yT Aj =m∑

i=1

yiaij = cj (j = 1, . . . , n).

(Z.B. hat x = 0 trivialerweise diese Eigenschaft.) Dann wissen wir vom komple-mentaren Schlupf: Im Fall Ax = b ist x primal zulassig und folglich optimal.

Sei oBdA b ≥ 0. Im Fall b = 0 ist x = 0 optimal. Wir unterstellen deshalbm∑

i=1

bi > 0.

Sei A die Teilmatrix aller Spalten Aj von A mit der Eigenschaft

yT Aj =m∑

i=1

aijyi = cj .

Wir betrachten das zugeordnete linearer Optimierungsproblem

(41)min 1Tz

Au + Iz = bu, z ≥ 0

Dieses Problem (41) hat immer I als primal zulassige Anfangsbasis und kann somitmit der primalen Strategie gelost werden. Sei (u∗, z∗) eine Optimallosung.

Im Fall ζ∗ = 1Tz∗ = 0, ist x = (u∗, z∗) = (u∗,0) primal zulassig fur dasAusgangsproblem. Nach Wahl von A erfullt x die komplementaren Schlupfbedin-gungen und ist folglich optimal.

Im Fall ζ∗ > 0 betrachten wir die dual optimale Losung w von (41). Diese erfullt

ζ∗ = bTw und ATw ≤ 0,w ≤ 1.

Fur jede Spalte A` der Ausgangsmatrix A, die nicht zu A gehort, haben wir nachDefinition von A:

AT` y < 0.

Also erfullt der Vektor y′ = y + εw die duale Zulassigkeitsbedingung

ATy′ ≤ c fur ein genugend kleines ε > 0,


aber liefert einen besseren Zielfunktionswert als y:

bty′ = bTy + εbTw = bTy + εζ∗ > bTy.

Wir konnen nun in gleicher Weise mit y′ anstelle von y verfahren.

FAZIT: Eine Iteration der primal-dualen Methode liefert entweder eine Optimallosung(Fall ζ∗ = 0) oder eine dual zulassige Losung mit echt besserem Zielfunktionswert(Fall ζ∗ > 0).

BEMERKUNG. Es bleibt die Frage, wie man zu Anfang der primal-dualen Methodeein dual zulassiges y erhalt. Das hangt von der Matrix A und dem Vektor c ab. ImFall c ≥ 0 kann man z.B. trivialerweise mit y = 0 starten.

KAPITEL 5

Ganzzahlige lineare Programme

Wir betrachten nun Optimierungsprobleme vom Typ

(42) min cTx s.d. Ax = b,x ≥ 0,x ganzzahlig,

wobei die Matrix A ∈ Rm×n und die Vektoren c ∈ Rn,b ∈ Rm gegeben seien.Wir setzen

P = {x ∈ Rn | Ax = b,x ≥ 0}.Das mathematische Optimierungsproblem (42) ist kein lineares Programm im stren-gen Sinn, da der Zulassigkeitsbereich

F = {x ∈ P | x ∈ Nn}

eine diskrete Menge und im allgemeinen kein Polyeder ist. IstF endlich und setzenwir PI = conv F , so ist (42) aquivalent zu dem Problem

min cTx s.d. x ∈ PI .

Ware eine Matrix A′ und ein Vektor b′ mit PI = P (A′,b′) bekannt, so konnteman das Ausgangsproblem (42) z.B. dadurch losen, indem man

min cTx s.d. A′x ≤ b′

mit der Simplexmethode lost.

VEREINBARUNG. In diesem Kapitel nehmen wir durchweg an, dass samtliche Pro-blemparameter A, c,b rational sind. OBdA durfen (und werden) wir bei der Pro-blemanalyse deshalb sogar Ganzzahligkeit annehmen:

A ∈ Zm×n, c ∈ Zn, b ∈ Zm.

1. Schnittebenen

Es seien A ∈ Zm×n und b ∈ Zm gegeben und

P = P (A,b) = {x ∈ Rn | Ax ≤ b}

das entsprechende rationale Polyeder. Wir interessieren uns fur die Menge

PI = conv {x ∈ P | x ∈ Zn}.

PROPOSITION 5.1. Ist P eine rationales Polyeder, dann ist auch PI ist ein ratio-nales Polyeder.

61

62 5. GANZZAHLIGE LINEARE PROGRAMME

Beweis. Im Fall PI = ∅ ist nichts zu beweisen. Sei also PI 6= ∅. Nach demDekompositionssatz von Weyl-Minkowski existieren endliche Mengen V,W ⊆Qn so, dass


Nach geeigneter Skalierung durfen wir die Vektoren w ∈W oBdA dabei als ganz-zahlig annehmen. Ein beliebiges x ∈ P kann in der Form

x = V s + W t mit s, t ≥ 0,1T s = 1

dargestellt werden. Bezeichen wir mit btc der ganzzahlig nach unten gerundetenKomponenten von t und setzen t = t− btc ≥ 0, dann erhalten wir

x = (V s + W t) + W btc = x + W btc

mit dem ganzzahligen btc und x in dem Polytop(!)

P = {V s + W t | s ≥ 0,1T s = 1,0 ≤ t ≤ 1}.

Wegen W btc ∈ Zn finden wir

x ∈ Zn ⇐⇒ x ∈ Zn

und deshalb

P ∩ Zn = P ∩ Zn + {Wz | z ≥ 0 ganzzahlig}.

Da P ein Polytop (und somit beschrankt) ist, ist P ∩ Zn eine endliche Menge.Wegen

(43) PI = conv (P ∩ Zn) + cone W

erkennen wir PI somit als Polyeder.�

Im Prinzip konnte man aus der Darstellung (43) (z.B. mit Fourier-Motzkin) eine li-neare Beschreibung von PI durch Ungleichungen ableiten. Fur das Optimierungs-problem (42) ist dies jedoch nicht interessant, da ein solches Vorgehen bedeutet,dass man ohnehin zuerst samtliche ganzzahligen Vektoren in P (darunter auch dieOptimallosung von (43) ) auflisten musste.

1.1. Das Verfahren von Gomory. Um eine lineare Beschreibung von PI zuerzielen, gehen wir von gultigen Ungleichungen fur das Polyeder P = P (A,b)aus. Gemass dem Lemma von Farkas betrachten wir deshalb ein beliebiges ratio-nales y ≥ 0 und cT = yT A. Dann ist cTx ≤ z mit z = yTb eine gultige Un-gleichung fur P . Wir durfen y als ganzzahlig annnehmen. Der springende Punktist dann die Beobachtung

• cT = yT A ist ganzzahlig und

cTx ≤ z′ mit z′ = byTbc ∈ Z

eine gultige Ungleichung fur PI , da sie von allen ganzzahligen Vektorenin P erfullt wird.

1. SCHNITTEBENEN 63

Tatsachlich genugt es, sich dabei auf y mit Komponenten yi ∈ [0, 1] zu beschranken.Denn bei allgemeinem y′ ∈ Qn

+ und z ∈ Zn+ mit

0 ≤ y = y′ − z ≤ 1

ist die Ungleichung(zT A)x ≤ zTb ∈ Z

ja ohnehin schon von Ax ≤ b impliziert. Fur ganzzahliges x ∈ P (A,b) gilt darum

(y′)T Ax ≤ b(y′)Tbc ⇐⇒ yT Ax ≤ byTbc.

Damit erhalten wir das Gomory-Polyeder

P ′ = {x ∈ P | (yT A)x ≤ byTbc,y ∈ [0, 1]m,yT A ∈ Zn}.

BEMERKUNG. P ′ ist tatsachlich ein Polyeder, denn es gibt nur endlich viele ver-schiedene Gomory-Schnitte. Das sieht man so: Die Menge {yT A | 0 ≤ y ≤ 1} isteine beschrankte Menge von Zeilenvektoren in Rn und enthalt deshalb nur endlichviele ganzzahlige Vektoren.

Iterieren wir diese Konstruktion, so ergibt sich die Gomory-Folge

P ⊇ P ′ ⊇ P ′′ ⊇ . . . ⊇ PI .

Man bemerke, dass keine der Gomory-Ungleichungen einen ganzzahligen Punktaus P ”abschneidet“. Ausserdem gilt: Sobald bei der Gomory-Folge kein neuesPolyeder konstruiert wird, hat man genugend viele Ungleichungen erzeugt, die PI

festlegen.

Ohne Beweis bemerken wir

SATZ 5.1 (Gomory). Die Gomory-Folge eines rationalen Polyeders P hat endlicheLange und endet mit PI .

�

Der Beweis ist nicht schwer aber etwas aufwendig. Deshalb sei hier darauf ver-zichtet. Wir beweisen nur:

LEMMA 5.1. Sei P ein rationales Polytop mit P = P ′. Dann gilt P = PI .

Beweis. Sei P 6= PI . Dann besitzt P eine Ecke v mit (mindestens) einer Kompo-nente vj /∈ Z. Ausserdem existiert ein c ∈ Zn derart, dass die Funktion f(x) =cTx uber P genau von v maximiert wird. Seien v(1), . . . ,v(k) die ubrigen Eckenvon P und

max`=1,...,k

(cTv − cTv(`)) = ε > 0

maxx∈P|x1|+ . . . + |xn| = M <∞.

Sei K ∈ N so gewahlt, dass Kε > 2M erfullt ist. Dann maximiert v auch dieFunktion f(x) = cTx uber P , mit

cT = [Kc1, . . . ,Kcj + 1, . . . ,Kcn] = KcT + eTj .


Denn fur jede andere Ecke v(` von P gilt

K(cTv(`)) + v(`)j < K(cTv − ε) + M < KcTv −M < KcTv + vj .

Wegen cTv − KcTv = vj /∈ Z ist entweder cTv oder cTv keine ganze Zahl.Also ist

cTx ≤ bcTvc oder cTx ≤ bcTvceine Ungleichung, die zwar fur PI gultig ist aber nicht fur P . D.h. P 6= P ′.

�

Der Satz von Gomory fuhrt zu einem endlichen Algorithmus zur Losung von desganzzahligen Optimierungsproblems

max cTx s.d. Ax ≤ b,x ∈ Zn.

Man lost die LP-Relaxierung

max cTx s.d. Ax ≤ b.

Ist die gefundene Optimallosung x∗ ganzzahlig, dann ist nichts weiter zu tun. An-dernfalls berechnet man das Gomory-Polyeder P ′ und lost

maxx∈P ′

cTx

usw. bis das ganzzahlige Optimum gefunden ist. In der Praxis ist diese Vorgehens-weise typischerweise jedoch hoffnungslos ineffizient.

1.2. Schnittebenenverfahren. Die Idee hinter Schnittebenenverfahren zur Lo-sung ganzzahliger linearer Programme ist wie die des Gomory-Verfahrens: Manlost die LP-Relaxierung des Problems. Ist die gefundene Optimallosung x∗, sofugt man dem LP eine Ungleichung

aTx ≤ b

hinzu, die fur alle x ∈ P ∩ Zn gilt und von x∗ verletzt wird. Die entsprechendeHyperebene

H(a, b) = {x ∈ Rn | aTx = b}heisst Schnittebene (bzgl. P und PI ). Unter der Ausnutzung der speziellen kom-binatorischen Struktur, die das Optimierungsproblem haben mag, lassen sich inder Praxis oft gezielt Schnittebenen bestimmen, die zu effizienteren Algorithmenfuhren als das Allzweck-Gomoryverfahren. Ein Schnittebenen-Verfahren geht nachfolgendem Prinzip zur Losung des Problems

max cTx s.d. Ax ≤ b,x ∈ Zn

vor:(SE0) Lose das relaxierte LP-Problem

max cTx s.d. Ax ≤ b.

Ist die gefundene Optimallosung x∗ ganzzahlig, STOP.

1. SCHNITTEBENEN 65

(SE1) Bestimme im Fall x∗ /∈ Zn eine Schnittebenenungleichung aTx ≤ bfur PI , die von x∗ verletzt wird (d.h. aTx∗ > b) und fuge diese denRestriktionen hinzu. Lose nun

max cTx s.d. Ax ≤ b,aTx ≤ b.

Ist die gefundene Optimallosung x ganzzahlig, STOP.(SE2) Bestimme im Fall x /∈ Zn eine Schnittebenenungleichung aTx ≤ b fur

PI , die von x′ verletzt wird (d.h. aTx > b) und fuge diese den bisherigenRestriktionen hinzu usw.

1.2.1. Quadratische boolesche Optimierung. Als Beispiel betrachten wir zugegebenen Paramentern qij ∈ R das Problem

maxn∑

i=1

n∑j=1

qijxixj , xi ∈ {0, 1}.

Sei V = {1, . . . , n} und E die Menge aller Paarmengen {i, j}. Zu e = {i, j}setzen wir

di = qii und ce = qij + qji.

Wegen x2i = xi und ye = xixj ∈ {0, 1} erhalten wir eine Formulierung als

ganzzahliges LP:

(44)

max∑i∈V

dixi +∑e∈E

ceye

s.d. ye − xi ≤ 0 e ∈ E, i ∈ exi + xj − ye ≤ 1 e = {i, j}

xi, ye ≤ 1−xi,−ye ≤ 0

xi, ye ganzzahlig.

BEMERKUNG. Man kann sich dieses Problem vorstellen als die Aufgabe, im vollstandi-gen Graphen Kn mit Knotenmenge V und Kantenmenge E einen vollstandigenUntergraphen maximalen Gesamtgewichts zu wahlen. Dabei sind die Knoten i ∈V mit di und die Kanten e ∈ E mit ce gewichtet.

Als Schnittebenen fur das von den ganzzahligen Losungen von (44) erzeugte Poly-top PI kommen alle Ungleichungen in frage, die von den ganzzahligen Losungs-vektoren erfullt werden. Beispiele sind etwa die Dreiecksungleichungen

xi + xj + xk − ye − yf − yg ≤ 1

fur jeweils drei Knoten i, j, k ∈ V und die dazugehorigen Kanten e, f, g ∈ E desentsprechenden ”Dreiecks“ {i, j, k}.

Dieses Beispiel kann verallgemeinert werden. Dazu setzen fur S ⊆ V mit |S| ≥ 2

x(S) =∑i∈S

xi und y(S) =∑

e∈E(S)

ye,


wobei E(S) die Menge aller Paarmengen e = {i, j} ⊆ S ist. Zu α ∈ N definierenwir die entsprechende Cliquenungleichung als

αx(S)− y(S) ≤ α(α + 1)/2.

LEMMA 5.2. Jede zulassige (0, 1)-Losung (x,y) von (44) erfullt jede Cliquenun-gleichung.

Beweis. Sei C = {i ∈ S | xi = 1} und s = |C| ≤ |S|. Dann gilt x(S) = s undy(S) = s(s− 1)/2. Also finden wir

α(α + 1)/2− αx(S)− y(S) = [α(α + 1)− 2αs + s(s− 1)]/2= (α− s)(α− s + 1)/2.

Da α und s ganze Zahlen sind, ist der letzte Ausdruck immer nichtnegativ.�

Es gibt allein schon 2n − n− 1 Cliquenungleichungen. Diese genugen noch nicht,um PI vollstandig zu beschreiben. Bei nicht zu grossen booleschen Problemen(n ∼ 40) kommt man damit aber in der Praxis schon recht weit.

2. Unimodularitat

Wir gehen das Ganzzahligkeitsproblem nun von einer anderen Seite an und suchennach Bedingungen fur die Matrix A ∈ Zm×n, die garantieren, dass jede Ecke desPolyeders

P = {x ∈ Rn | Ax = b,x ≥ 0}ganzzahlige Ecken hat, sofern b ganzzahlig ist. OBdA nehmen wir wieder m =rg A an. Wir nennen A unimodular, wenn jede (m ×m)-Basisteilmatrix AB vonA die Eigenschaft |det AB| = 1 besitzt.

Sei AB eine Basismatrix mit zugeordneter Basislosung x. Nach der CramerschenRegel ergeben sich die Komponenten als

xj =det AB(j,b)

det AB(j ∈ B),

wobei AB(j,b) aus AB hervorgeht, indem die Spalte j durch den Vektor b ersetztwird. Im Fall b ∈ Zm ist det AB(j,b) eine ganze Zahl. Folglich finden wir

A unimodular =⇒ xj ∈ Z fur alle b ∈ Zm.

PROPOSITION 5.2. Sei A ∈ Zm×n eine unimodulare Matrix vom Rang m = rg Aund b ∈ Zm. Dann gilt fur jedes c ∈ Rn: Entweder hat das lineare Programm

min cTx s.d. Ax = b,x ≥ 0

keine Optimallosung oder es existiert eine optimale Losung x∗ mit ganzzahligenKomponenten x∗j .

2. UNIMODULARITAT 67

Beweis. Simplexalgorithmus.�

Fur viele Anwendungen ist es geschickt, den Begriff der Unimodularitat zu verscharfen.Wir nennen eine Matrix A total unimodular, wenn fur jede quadratische TeilmatrixA′ von A unimodular ist, d.h.

det A′ ∈ {−1, 0,+1}.Insbesondere gilt aij ∈ {−1, 0 + 1} fur alle Koeffizienten der total unimodularenMatrix A = [aij ].

EX. 5.1. Die Matrix A =[1 11 2

]ist unimodular aber nicht total unimodular.

Bevor wir Beispiele von total unimodularen Matrizen diskutieren, geben wir einigewichtige Matrixkonstruktionen an.

LEMMA 5.3. Sei A ∈ Zm×n total unimodular und e ∈ Zm ein Einheitsvektor.Dann gilt:

(a) Wenn man Spalte von A mit 0 oder −1 multipliziert, erhalt man wiedereine total unimodular Matrix.

(b) AT total unimodular.(c) A = [A, e] total unimodular.

Beweis. (a) folgt aus der Tatsache, dass sich die Skalarmultiplikation eine Spalteeiner Matrix in der Skalarmultiplikation der Determinante auswirkt. (b) ergibt sichaus dem Transpositionssatz det C = det CT .

Um (c) einezusehen, betrachten wir eine quadratische Untermatrix A′ von [A, e].OBdA durfen wir annehmen, dass die Spalte e in A′ auftaucht. Wir entwickeln dieDeterminate nach dieser Spalte e und finden

det A′ = ±1 · det A′′,

wobei A′′ eine quadratische Untermatrix von A ist. Also gilt det A′ ∈ {−1, 0+1}.�

PROPOSITION 5.3. Sei A ∈ Zm×n total unimodular, b ∈ Zm und l,u ∈ Zn

derart, dassP = {x ∈ Rn | Ax ≤ b, l ≤ x ≤ u} 6= ∅.

Dann ist P eine Polytop mit ganzzahligen Ecken.

Beweis. P ist die Losungsmenge des total unimodularen Ungleichungssystems AI−I

x ≤

bu−l

�


Intervallmatrizen. Sei M = {1, . . . ,m}. Unter einem Intervall versteht man eineTeilmenge F ⊆M derart, dass Elemente i, j ∈M existieren mit der Eigenschaft

F = {k ∈M | i ≤ k ≤ j}.Eine (0, 1)-Matrix A heisst Intervallmatrix, wenn die Zeilen von A in einer solchenReihenfolge angeordnet werden konnen, dass jede Spalte der (0, 1)-Inzidenzvektoreines Intervalls der Zeilenindices ist.

Es ist klar, dass jede quadratische Untermatrix einer Intervallmatrix selber eineIntervallmatrix ist. Es gilt

LEMMA 5.4. Jede Intervallmatrix A ist total unimodular.

Beweis. OBdA sei A = [aij ] quadratisch und

a1j ={

1 fur j = 1, . . . , k0 fur j = k + 1, . . . , n.

Ausserdem entspreche die erste Spalte von A dem kleinsten Intervall, das 1 enthalt.

Im Fall k = 1 ist die erste Zeile ein Einheitsvektor. Entwicklung der Determinantenach der ersten Zeile liefert dann die Behauptung per Induktion wie bei Netzwerk-matrizen.

Im Fall k ≥ 2 subtrahiert man die erste Spalte von den Spalten 2, . . . , k. Dieresultierende Matrix ist wieder eine Intervallmatrix und die Determinante hat sichnicht geandert. Auf die neue Matrix trifft aber der vorige Fall zu.

�BEMERKUNG. (0, 1)-Inzidenzmatrizen von allgemeinen Familien F von Teilmen-gen einer endlichen Grundmenge M sind typischerweise nicht total unimodular!

KAPITEL 6

Flusse in Netzwerken

Sei nun A ∈ {−1, 0,+1}m×n eine Matrix mit den Eigenschaften

(NM) Jede Spalte von A enthalt hochstens einen Koeffizienten ”−1“ und einenKoeffizienten ”+1“.

LEMMA 6.1. Erfullt A die Bedingung (NM), dann ist A total unimodular.

Beweis. Wir argumentieren per Induktion uber die Anzahl der Koeffizienten 6= 0und betrachten eine beliebige quadratische Untermatrix. OBdA sei A selber dieseMatrix. Hat jede Spalte von A genau 2 Koeffizienten 6= 0, so sind alle Spalten-summen 0. Folglich hat A nicht vollen Rang, d.h. det A = 0. Im Fall det A 6= 0durfen wir somit annehmen, dass mindestens eine Spalte j genau einen Koeffizi-enten aij 6= 0 besitzt. Entwicklung nach dieser Spalte ergibt

|det A| = |aij | · |det A′| mit |det A′| ∈ {0, 1},

da wir die Behauptung fur die Matrix A′ per Induktion als richtig unterstellen.�

Wir nennen die Matrix A vom Typ (NM) eine Netzwerkmatrix, wenn die Spalten-summen in A immer 0 sind (d.h. wenn in jeder Spalte genau eine −1 und genaueine +1 auftreten).

LEMMA 6.2. Eine Matrix A hat die Eigenschaft (NM) genau dann, wenn A auseiner Netzwerkmatrix durch Streichen einer Zeile hervorgeht.

Beweis. Hat A die Eigenschaft (NM), so fugen wir eine neue Zeile hinzu, diegenau die Spaltensummen der Matrix A enthalt. Die erweiterte Matrix ist offenbareine Netzwerkmatrix.

�

EX. 6.1 (Gerichtete Graphen und Inzidenzmatrizen). Eine Netzwerkmatrix A ∈{−1, 0,+1}m×n kann man sich in folgender Weise als algebraische Darstellungeines gerichteten Graphen G = (V,E) vorstellen:

V ist eine Menge von m Knoten, die wir den m Zeilen von A zuordnen. E isteine Menge von n (gerichteten) Kanten, die wir uns als ”Pfeile“ denken und denSpalten von A zuordnen.

69

70 6. FLUSSE IN NETZWERKEN

Die Spalte j besitzt einen Koeffizienten auj = +1 und avj = −1. Wir stellen unsdie entsprechende Kante ej ∈ E als Pfeil vor, der sich vom Knoten v ∈ V zumKnoten u ∈ V erstreckt:

vej−→ u

Man nennt deshalb A auch die (Knoten-Kanten-)Inzidenzmatrix von G = (V,E).

Sei A = [aij ] ∈ Rm×n die Inzidenzmatrix des Graphen G = (V,E). Dann re-prasentiert ein Koordinatenvektor x ∈ Rn einen Fluss auf dem Graphen G, wobeidie Komponente xj die Quantitat des Flusses x angibt, die durch die von v nach ugerichtete Kante ej ”fliesst“. Im Fall xj > 0 stellt man sich vor, dass die Menge xj

von v and u fliesst. xj < 0 bedeutet, dass die Menge |xj | = −xj von u and v (d.h.in die umgekehrte Richtung) fliesst. Die Quantitat

δv(x) =n∑

j=1

avjxj (v ∈ V )

ist der Nettodurchfluss (= Menge des eingehenden Flusses minus Menge des aus-gehenden Flusses) von x im Knoten v ∈ V . Allgemeiner ist der Vektor

δ(x) = Ax ∈ RV

der Vektor der Nettozuflusse der Knoten von G.

TERMINOLOGIE. Intuitiv nennt man einen Knoten v im Fall δv(x) ≥ 0 eine Senke(bzgl. x). Im Fall δv(x) ≤ 0 eines nichtpositiven Nettozuflusses (d.h. eines nicht-negativen Nettoausflusses) spricht man von v als einer Quelle. Im Fall δv(x) = 0ist v ein sog. Transitknoten (bei dem der Zufluss gleich dem Abfluss ist).

Zu gegebenen Parametern c, l,u ∈ Rn und b ∈ Rm definieren wir das Flusspro-blem auf G als das lineare Optimierungsproblem

(45) min cTx s.d. Ax = b, l ≤ x ≤ u.

Aus der totalen Unimodularitat von A folgt nun sofort

SATZ 6.1. Sind b, l und u ganzzahlig, dann hat das Kosten-Flussproblem ent-weder keine Optimallosung oder es besitzt eine Optimallosung mit ganzzahligenKomponenten.

�

Die Parametervektoren l und u konnen als (untere bzw. obere) Kapazitatsbeschran-kungen der Kanten von G interpretiert werden. Der Wert cjxj gibt die Kosten desFlusses x durch die Kante ej an.

BEMERKUNG. Die Kapazitatsrestriktionen kann man sich etwas allgemeiner alsFunktionen l,u : E → R ∪ {−∞,+∞} vorstellen. Satz 6.1 bleibt offensichtlichauch in dieser Allgemeinheit entsprechend gultig.

Das Kosten-Flussproblem kann z.B. mit dem Simplexalgorithmus gelost werdenund hat – unter den Annahmen von Satz 6.1 – eine ganzzahlige Optimallosung.

2. KURZESTE WEGE 71

Es gibt allerdings auch speziellere Verfahren, die kombinatorische Struktur von Gausnutzen und effizienter sind.

1. Das Matching-Polytop

Seien S und T disjunkte Mengen mit |S| = |T | = n < ∞ und E = S × T . Wirsetzen V = S ∪ T und definieren die Matrix A = [ave] ∈ RV×E uber

ave =

−1 falls e = (v, w)+1 falls e = (w, v)0 sonst

Der Vektor b ∈ RV sei gegeben durch

bv ={−1 falls v ∈ S+1 falls v ∈ T

Ein (S × T )-Matching entspricht einer (0, 1)-Losung x von

Ax = b.

Es liegt hier also ein Flussproblem vor, bei dem alle Knoten in S Quellen und alleKnoten in T Senken sind. Nach Wahl von b erfullt jedes nichtnegative x ∈ RE

automatisch die Bedingung xe ≤ 1 fur alle e ∈ E. A ist eine Netzwerkmatrix unddamit total unimodular. Also gilt

P = {x ∈ RE | Ax = b,x ≥ 0} = PI .

Die zulassigen Basislosungen des Simplexalgorithmus sind Ecken von P und folg-lich ganzzahlig. D.h. diese Basislosungen entsprechen Matchings. Mit anderenWorten: P ist genau das Matching-Polytop.

2. Kurzeste Wege

Sei V eine beliebige (endliche) Menge von Knoten E ⊆ V × V eine Menge von(gerichteten) Kanten eines Graphen G = (V,E). Wieder sei A = [ave] ∈ RV×E

die zugehorige Inzidenzmatrix mit

ave =

−1 falls e = (v, w)+1 falls e = (w, v)0 sonst

Wir wahlen und zwei feste Knoten s, t und definieren b ∈ RV als

bv =

−1 falls v = s+1 falls v = t0 sonst.

Mit anderen Worten: Wir wahlen s als Quelle und t als Senke bzgl. eines zu kon-struierenden Flusses.


LEMMA 6.3. Sei B eine zulassige Basis bzgl. Ax = b,x ≥ 0 und x die zugehorigeBasislosung. Dann enthalt die Menge

P = {e ∈ E | xe > 0}

einen (gerichteten) Weg von s nach t in G.

Beweis. Da der Nettozufluss von s negativ ist, existiert eine Kante (s, v1) ∈ P . Istv1 = t, ist der Weg gefunden. Andernfalls folgt aus dem Nettozufluss δ(x)v1 = 0die Existenz einer Kante (v1, v2) ∈ P usw.

Nach endlich vielen Schritten haben wir entweder t erreicht oder einen Knoten vk,der schon durchlaufen wurde. Letzteres ist aber unmoglich, da sonst die Spaltenvon AB linear abhangig waren.

�

Wir wahlen eine Zeilen-Teilmatrix A′ von A mit vollem Zeilenrang. Dann ist auchA′

B total unimodular und die Koeffizienten einer Basislosung x ergeben sich nachder Cramerschen Regel als

xe =det A′

B,e(b)det A′

B

∈ {0, 1}.

Sei d : E → R+ eine Distanzfunktion auf dem Graphen G = (V,E). Eine opti-male Basislosung des linearen Programms

(46) mindTx =∑e∈E

dexe s.d. Ax = b,x ≥ 0

entspricht also einer Menge von Kanten, die eine Verbindung von s nach t sichertund minimales gesamte Kantenlange hat, also einen kurzesten Weg von s nach tergibt.

2.1. Der Dijkstra-Algorithmus. Kurzeste (s, t)-Wege in G = (V,E) kannman nicht nur mit der Simplexmethode berechnen. Der Algorithmus von Dijkstralost das Problem, indem er vom zu (46) dualen linearen Programm ausgeht:(47)

max yTbs.d. yT A ≤ dT ←→ max yt − ys

s.d. vw − yv ≤ de (e = (v, w) ∈ E)

Man sucht also ein (Knoten)-Potential y : V → R, das die Potentialdifferenzyt − ys maximiert, wobei die ubrigen Potentialdifferenzen wie folgt beschranktsind:

yw − yv ≤ de bzw. yw ≤ yv + de fur alle e = (v, w) ∈ E.

Der Einfachheit halber setzen wir dvw = +∞, wenn (v, w) /∈ E. Der Algorithmusvon Dijkstra baut nun ein optimals Potential sukzessive folgendermassen auf:

(D0) Setze ys ← 0, U ← {s} und yv ← dsv fur alle v ∈ V \ U .

3. ZIRKULATIONEN UND DAS MAX-FLOW-MIN-CUT-THEOREM 73

(D1) Solange U 6= V gilt, wahle ein v ∈ V \ U mit minimalem Potential yv,setze U ← U ∪ {v} und datiere auf:

yw ← min{yw, yv + dvw} fur alle w ∈ V \ U .

Man sieht leicht per Induktion:

LEMMA 6.4. In jedem Stadium des Algorithmus von Dijkstra geben die Potentialeyu der Knoten u ∈ U genau den minimalen Abstand von s nach u. Fur beliebigeKnoten v ∈ V ist yv zumindest eine Obergrenze fur den Abstand von s.

�

Man erkennt: der Dijkstra-Algorithmus berechnet nicht nur den kurzesten Abstandvon s zu t sondern zu allen Knoten v ∈ V und lost damit insbesondere das dualeProblem (47). Aus dieser Losung lasst sich leicht ein kurzester Weg von s nach tdurch ”Zuruckrechnen“ gewinnen:

Man beginnt bei t und sucht ein v1 ∈ V \ {t} mit

yt = yv1 + dv1,t.

Nun sucht man ein v2 ∈ V \ {t, v1} mit

yv1 = yv2 + dv2,v1

usw., bis man bei s angelangt ist.

3. Zirkulationen und das MAX-Flow-MIN-Cut-Theorem

Wir betrachten einen gerichteten Graphen G = (V,E) mit Knoten-Kanten-InzidenzmatrixA = A(G) wie zuvor. Unter einer Zirkulation (oder Stromung) auf G versteht maneinen Fluss x ∈ RE mit Nettozufluss δv(x) = 0 in jedem Knoten v ∈ V . Mit an-deren Worten: Bei einer Zirkulation ist jeder Knoten Transitknoten und wir haben

x ∈ RE ist Zirkulation auf G ⇐⇒ Ax = 0.

Sei nun f = (t.s) ∈ E eine festgewahlte Kante und x eine Zirkulation. Stellenwir uns vor, dass die Kante f in G blockiert wird. Dann stellen die ubrigen Kan-tenflusswerte xe (e 6= f ) einen Fluss auf Gf = (V,E \ {f}) dar, wo in s einNettoabfluss und bei t ein Nettozufluss in Hohe von xf stattfindet. Mit anderenWorten:

• Die Einschrankung von x auf Gf beschreibt den Transport eines ”Gu-tes“ der Quantitat xf von der Quelle s zur Senke t entlang den Kantenvon Gf , wobei bei keinem Knoten v 6= s, t etwas verloren geht oderhinzugewonnen wird.


Unter der Annahme dass jede Kante e ∈ E \ {f} einer Kapazitatsschranke ce ≥ 0unterliegt, sucht man im Ford-Fulkerson-Problem nach einer nichtnegativen Zir-kulation x, die den Wert xf maximiert:

(48)max xf

s.d. δv(x) = 0 fur alle v ∈ V0 ≤ xe ≤ ce fur alle E ∈ e \ {f}

In Matrixschreibweise und mit zusatzlichen nichtnegativen Schlupfvariablen s ≥ 0haben wir aquivalent mit dem f ∈ E entsprechenden Einheitsvektor ef :

min −eTf x

s.d. Ax = 0Ix + Is = cx, s ≥ 0

Dazu ist das duale lineare Programm

max yT0 + zTcs.d. yT A + zT ≤ −eT

f

zT ≤ 0Tbzw.

min − zTcs.d. yT A − zT ≥ eT

f

−zT ≥ 0T

Letzteres ist aquivalent mit

(49)

min∑e∈E

ceze

s.d. yw − yv + ze ≥ 0 fur alle z = (v, w) ∈ Eys − yt + zf ≥ 1

ze ≥ 0.

Augmentierende Wege. Sei nun x ≥ 0 eine zulassige Losung von (48). Wir su-chen diese um ein gewisses ε > 0 zu verbesseren. Dazu definieren wir einen Hilfs-graphen G(x) auf V mit Kanten

(v, w) wenn e = (v, w) ∈ E \ {f} und xe < ce (”Vorwartskante“)(w, v) wenn e = (v, w) ∈ E \ {f} und xe > 0 (”Ruckwartskante“)

Sei ε > 0 so, dass xe + ε ≤ ce gilt, wenn e eine Vorwartskante ist, und xe − ε ≥ 0auf den Ruckwartskanten e erfullt ist. Dann ist klar:

• Existiert ein Weg P von s nach t im Hilfsgraphen G(x), dann kann derFluss x um mindestens ε > 0 verbessert werden.

Wir erhohen namlich einfach den Flusswert um ε auf den Vorwartskanten von P(und auf der Kante f = (t, s)) und erniedrigen ihn um ε auf den Ruckwartskan-ten von P . Offensichtlich ist der resultierende Fluss nichtnegativ, respektiert dieKapazitatsgrenzen und genugt den Knotendurchflussbedingungen.

Sei S die Menge aller Knoten, die in G(x) von s aus auf einem gerichteten Wegerreicht werden konnen. Dann wissen wir also: Im Fall t ∈ S kann x verbessertwerden.

3. ZIRKULATIONEN UND DAS MAX-FLOW-MIN-CUT-THEOREM 75

Schnitte. Sei allgemein S ⊆ V eine Knotenmenge mit s ∈ S. Dann bestimmt Seinen sog. s-Schnitt

[S : V \ S] = {(v, w) ∈ E | v ∈ S, w /∈ S}der Kapazitat

c[S : V \ S] =∑

e∈[S:V \S]

ce ≥ 0.

LEMMA 6.5 (Schnittlemma). Sei x eine zulassige Zirkulation auf G und [S : V \S]ein beliebiger s-Schnitt. Dann gilt

xf ≤ c[S : V \ S].

Beweis. Wir setzen yv = 1 fur alle v ∈ S und yv = 0 fur v /∈ S. Ausserdemwahlen wir ze = 1 fur e ∈ [S : V \ S] und ze = 0 sonst.

Dann erhalten wir eine zulassige Losung des dualen Problems (49) mit Zielfunkti-onswert ∑

e∈E

ceze = c[S : V \ S].

Die schwache Dualitat der linearen Programmierung impliziert damit die behaup-tete Ungleichung.

�Sei wie vorher x ≥ 0 eine zulassige Zirkulation und S die Menge aller von s inG(x) erreichbaren Knoten. Im Fall t /∈ S ergibt sich nach Definition von G(x) undder Knotenmenge S fur eine Kante e = (v, w) ∈ E \ {f}:

xe ={

ce wenn v ∈ S und w ∈ V \ S0 wenn v ∈ V \ S und w ∈ S.

Also schliessen wir, dass x optimal ist. Denn

xf =∑

e∈[S:V \S]

xe = c[S : V \ S].

SATZ 6.2 (Ford-Fulkerson). Eine zulassige Zirkulation x ist optimal fur (48) genaudenn, wenn es im Hilfsgraphen G(x) keinen augmentierenden Weg von s nach tgibt.

�

Das lineare Programm (48) hat auf jeden Fall x = 0 als zulassige Losung. Alsoerhalten wir unter den obigen Voraussetzungen eine kombinatorische (graphen-theoretische) Form der LP-Dualitat:

KOROLLAR 6.1 (MAX-Flow-MIN-Cut).

max{xf | x ist zulassig fur (48)} = min{c[S : V \ V ] | s ∈ S ⊆ V }.�


4. Der Algorithmus von Ford-Fulkerson

Die vorangegangene Analyse des Ford-Fulkerson-Problems (48) legt folgendenAlgorithmus nahe:

(FF0) Beginne mit x = 0 als Startlosung und suche im Hilfsgraphen G(x)einen augmentierenden Weg P von s nach t.

(FF1) STOP, wenn P nicht existiert: x ist optimal.(FF2) Wenn P existiert, modifiziere x entlang P zu einem verbesserten zulassi-

gen Fluss x′ mit x′f = xf + ε und iteriere nun mit x′ anstelle von x.

Sind die Kapazitaten ce ganzzahlig, so ist klar, dass der FF-Algorithmus nur ganz-zahlige Losungen x produziert und in jeder Iteration der Flusswert xf um ein ganz-zahliges ε ≥ 1 verbessert wird.

Man kann zeigen, dass der FF-Algorithmus hochstens |V | · |E| Iterationen (Aug-mentierungen) erfordert, wenn man immer einen augmentierenden Weg P mit sowenig Kanten wie moglich wahlt (was z.B. automatisch der Fall ist, wenn man Pmit dem Dijkstra-Algorithmus berechnet). (Wir beweisen dies hier nicht, da wirspater noch einen anderen Netzwerkfluss-Algorithmus analysieren werden.)

4.1. Das bipartite Matching- und Uberdeckungsproblem. Wir gehen vonendlichen disjunkten Mengen S und T und einer Teilmenge E ⊆ S × T aus undnennen den Graphen G = (S∪T,E) bipartit. Ein (nicht notwendigerweise perfek-tes) Matching ist eine Teilmenge M ⊆ E von paarweise nichtinzidenten Kanten:

(s1, t1), (s2, t2) ∈M =⇒ s1 6= s2, t1 6= t2.

Die Aufgabe, ein maximales Matching zu berechnen erweist sich als ein Spezialfalldes FF-Problems. Dazu betrachten wir den Graphen G = (V,E), mit zwei neuenKnoten s0, t0, d.h. V = (S ∪ T ∪ {s0, t0}, E, und Kantenmenge

E = E ∪ {(s0, s) | s ∈ S} ∪ {(t, t0) | t ∈ T} ∪ {(t0, s0}

Beschranken wir nun die Kapazitat der Kanten vom Typ (s0, s) und (t, t0) auf 1(und ”+∞“ sonst) , so berechnet der FF-Algorithmus einen Vektor x ∈ {0, 1}Emit maximalem Flusswert

x(t0,s0) =∑e∈E

xe.

Folglich ist M = {e ∈ E | xe = 1} ein maximales Matching in G.

Unter einer (Kanten-)Uberdeckung von G = (S ∪ T,E) versteht man eine Mengevon Knoten(!) C ⊆ S ∪ T mit der Eigenschaft

(v, w) ∈ E =⇒ v ∈ C oder w ∈ C.

C muss mindestens die Machtigkeit eines beliebigen Matchings M haben, dennjede Kante aus M muss ja durch C abgedeckt sein:

|C| ≥ |M |.

5. DER PRAFLUSS-MARKIERUNGSALGORITHMUS 77

Sei andererseits M ein maximales Matching, das nach dem FF-Algorithmus kon-struiert wurde und C der Schnitt aller Knoten die von s0 noch erreichbar sind.Wegen

c[C : V \ C] = |M | <∞,

kann es kein e ∈ E geben, das von S ∩ C nach T \ C verlauft. Also ist

C = (S \ C) ∪ (T ∩ C)

eine Uberdeckung und hat Machtigkeit

|C| = |S \ C|+ |T ∩ C| = c[C : V \ C] = |M |.

SATZ 6.3 (Konig). Sei G = (S ∪ T,E) bipartit. Dann gilt

max{|M | |M Matching} = min{|C| | C Uberdeckung.}

�

BEMERKUNG. Das Matching- und Uberdeckungsproblem kann sinnvoll auch imFall T = S (d.h. E ⊆ S × S) formuliert werden. Wahrend das Matchingproblem(mit etwas mehr Aufwand) noch effizient losbar bleibt, ist in dieser Allgemein-heit kein effizienter Algorithmus fur das analoge Uberdeckungsproblem bekannt.Insbesondere gilt der Satz von Konig in diesem Rahmen nicht mehr.

5. Der Prafluss-Markierungsalgorithmus

Wir betrachten wieder das Ford-Fulkerson-Problem in der Form

(50)max δt(x)s.d. δv(x) = 0 fur alle v ∈ V \ {s, t}

0 ≤ xe ≤ ce fur alle E

(mit Kapazitaten ce ∈ R+ ∪ {+∞}). Dabei soll der Nettozufluss in die Senke tmaximiert werden. Bei einer zulassigen Losung x gilt

δs(x) = −δt(x)

da die Summe aller Nettozuflusse null sein muss:

0 = 0Tx = 1T Ax =∑v∈V

δv(x) = δs(x) + δt(x).

Also konnten wir xf = δs(x) auf der Kante f = (t, s) verschicken, um bei allenKnoten v den Nettozufluss δv(x) = 0 zu erreichen. Der Einfachheit halber nehmenwir deshalb an:

E = {(v, w) ∈ V × V \ {t, s} | v 6= w, }

(Eine ”nicht zur V erfugung stehende “ Kante (v, w) kann ja immer durch die Ka-pazitatsrestriktion cvw = 0 simuliert werden.) Wir wollen einen weiteren Typ vonAlgorithmus fur dieses Problem diskutieren, der von Goldberg und Tarjan vorge-schlagen wurde.


Dazu bezeichnen wir einen Fluss x ∈ RE als Prafluss, wenn in jedem ”Zwischenk-noten“ v einen nichtnegativen Nettozufluss bewirkt:

δv(x) =∑z 6=v

xzv −∑w 6=v

xvw ≥ 0 fur alle v ∈ V \ {s, t}.

Jeder Zwischenknoten v ist also eine Senke. Im Fall δv(x) > 0 heisst der Knotenv aktiv. Der Prafluss x wird zulassig genannt, wenn er den Kapazitatsschrankengenugt:

0 ≤ xe ≤ ce fur alle e ∈ E.

Die Sende-Operation. Ist x ein zulassiger Prafluss. Wie im Ford-Fulkerson-Algorithmussei G(x) der entsprechende Hilfsgraph. (v, w) ist also eine Kante von G(x) genaudann, wenn

xvw < cvw oder xwv > 0.

Man kann alsocvw = cvw − xvw + xwv > 0

zusatzliche Flusseinheiten von v nach w schicken ohne die Kapazitatsrestriktionenzu verletzen. Ist v aktiv, so kann man also den Fluss von v nach w um

ε = min{δv(x), cvw} > 0

erhohen und hat weiterhin einen zulassigen Prafluss. Die Grundidee des Algorith-mus ist nun einfach: Man fuhre solange Sende-Operationen durch, bis eine Opti-mallosung vorliegt. Um dies systematisch zu tun, benutzt man Knotenmarkierun-gen.

Zulassige Markierungen. Unter einer zulassigen Markierung bzgl. x versteht maneine Bewertung d : V → Z+ ∪ {+∞} der Knoten derart, dass

(ZM1) d(v) ≤ d(w) + 1 fur alle (v, w) ∈ G(x);(ZM2) d(s) = |V | und d(t) = 0.

SATZ 6.4 (Goldberg-Tarjan). Sei x ∈ RE ein zulassiger Prafluss mit einer zulassi-gen Markierung d, dann existiert eine Menge S ⊆ V mit s ∈ S und t /∈ S derart,dass fur alle (v, w) ∈ [S : V \ S] gilt:

xvw = cvw und xwv = 0.

Beweis. Wegen |V \ {s, t}| = |V | − 2 muss es ein 0 < k < |V | geben mitk 6= d(v) fur alle v ∈ V . Sei

S = {v ∈ V | d(v) > k}.Dann haben wir s ∈ S und t /∈ S. Ist v ∈ S und (v, w) ∈ G(x), dann haben wir

d(w) ≥ d(v)− 1 ≥ (k + 1)− 1 = k d.h. d(w) > k

und folglich w ∈ S. Keine Kante von G(x) fuhrt also aus S heraus, was die Be-hauptung impliziert.

�Aus dem Korollar des Satzes von Ford-Fulkerson schliessen wir somit:

5. DER PRAFLUSS-MARKIERUNGSALGORITHMUS 79

KOROLLAR 6.2. Jede zulassige Zirkulation x, die eine zulassige Markierung ge-stattet, ist eine Optimallosung fur (48).

�

Sei x ein zulassiger Prafluss mit zulassiger Markierung d. Existiert bzgl. x keineaktiver Knoten, dann ist x eine Optimallosung von (50). Wir wollen nun zeigen,wie man im anderen Fall einen aktiven Knoten wahlen und eine Sendeoperati-on durchfuhren kann, sodass man hinterher wieder einen zulassigen Prafluss mitzulassiger Markierung erhalt.

Sei v ein beliebiger aktiver Knoten. Weil d zulassig ist, gilt d(v) ≤ d(w) + 1 furjede Kante (v, w) ∈ G(x). Wir unterscheiden zwei Falle.

1. Fall: Es gibt eine Kante (v, w) ∈ G(x) mit d(v) = d(w) + 1.

Wenn wir nun eine Sendeoperation entlang (v, w) durchfuhren, ist d auch fur denneuen Prafluss x′ zulassig. Denn die einzige mogliche neue Kante in G(x′) ist(w, v), wofur ja schon d(w) ≤ d(v) + 1 gilt.

2. Fall: Fur alle Kanten (v, w) ∈ G(x) gilt d(v) ≤ d(w).

Wir modifizieren nun die Markierung d zu d′:

d′(v) = min{d(w) + 1 | (v, w) ∈ G(x)}.Wegen d′(v) > d(v) ist d′ offenbar auch eine zulassige Markierung. Ausserdembefinden wir uns bzgl. d′ wieder im 1. Fall!

Algorithmus. Man beginnt mit einem zulassigen Prafluss x und einer zulassigenMarkierung d. Zum Beispiel folgendermassen:

xe ={

ce wenn e von der Form e = (s, v)0 sonst.

d(v) ={|V | wenn v = s0 sonst.

Nun fuhrt man Sendeoperationen durch, die zu zulassigen Praflussen mit zulassi-gen Markierungen fuhren, bis ein zulassiger Fluss (gemass Korollar 6.2) erreichtist.

5.1. Laufzeitanalyse. Wieviele Sendeoperationen fuhrt der Prafluss-Markie-rungsalgorithmus durch? Zur Analyse setzen wir n = |V |. Wir betrachten x einenzulassiger Prafluss mit zulassiger Markierung d.

LEMMA 6.6. Ist v ∈ V aktiv bzgl. x, dann existiert ein gerichteter Weg P von vnach s in G(x).

Beweis. Sei R die Menge aller von v in G(x) erreichbarer Knoten. Im Fall s /∈ Rhatten wir einen echt positiven Nettozufluss aus V \R nach R:∑

w∈R

δw(x) > 0.


Also muss es mindestens eine Kante (z.w) ∈ [V \ R,R] existieren mit xzw > 0.Aber dann ware z von v in G(x) erreichbar, ein Widerspruch!

�Wir konnen annehmen, dass der Weg P von v nach s in G(x) hochstens n − 1Kanten durchlauft. Entlang einer Kante in P andert sich die d-Markierung umhochstens den Wert 1. Also finden wir

d(v) < d(s) + n = 2n

und schliessen:

LEMMA 6.7. Im Algorithmus tritt der 2. Fall (Ummarkierung) bei einer Sendeope-ration weniger als 2n2 mal auf.

Beweis. Der 2. Fall tritt nur bei aktiven Knoten v auf und bewirkt eine Erhohungder Markierung, die aber den Wert 2n nie uberschreitet. Also tritt dieser Fall beijedem der n Knoten weniger als 2n mal ein.

�Wenn wir bei einem aktiven Knoten v Sendeoperationen durchfuhren bis entwederder Knoten nicht mehr aktiv oder der 2. Fall eingetreten ist, durchlaufen wir den1. Fall weniger als n mal (da es nur n − 1 weitere Knoten gibt, zu denen einUberschuss von v gesendet werden kann). Also erkennen wir:

PROPOSITION 6.1. Der Prafluss-Markierungsalgorithmus kann so ausgefuhrt wer-den, dass weniger als 2n3 Sendeoperationen stattfinden.

�

Date post:	29-Sep-2020
Category:	Documents
Upload:	others
View:	2 times
Download:	0 times

Ulrich Faigle - zaik.uni-koeln.de · Konvexe Funktionen 35 1. Differenzierbare konvexe Funktionen...

Documents