OptimierungsAlgorithmen
Algorithmen und
Datenstrukturen 2
Petra Mutzel
Technische Universität Wien
Institut für Computergraphik und Algorithmen
Überblick
• Lineare Programmierung
• Dualität
• Simplex Algorithmus
• Grundlagen der Polyedertheorie
• Kombinatorische vs. Ganzzahlige Optimierung
• Exakte Lösungsmethoden für ILPs
• Branch-and-Bound
• Schnittebenenverfahren
• Branch-and-Cut
Lineare Programmierung
Für den Zulässigkeitsbereich P eines Linearen
Programms gibt es drei verschiedene Möglichkeiten:
P=  es existiert keine einzige zulässige Lösung
 LP ist unlösbar
P≠ und inf{cTx | xP} existiert nicht (z.B. 0x≥-1) 
LP ist lösbar, aber es gibt keine optimale Lösung
P≠ und min{cTx | xP} existiert  LP ist lösbar und
hat eine endliche Lösung x* mit cTx*=min{cTx | xP},
x* ist die optimale Lösung
Dualität der Linearen Programmierung
Es ist vorteilhaft, Schranken für Lineare Programme
angeben zu können
Ein Punkt, der (2)-(4) erfüllt, erfüllt auch die
Ungleichung: 2(2)+(3) sowie (2)+(4)
Wir suchen die besten Schranken: Dualität
Dualität der Linearen Programmierung
Primales Programm:
Duales Programm:
Dualität der Linearen Programmierung
Primales Programm (P):
Duales Programm (D):
Schwacher Dualitätssatz:
Sei x´ein zulässiger Punkt für (P) und y´
zulässig für (D).
Dann gilt: y´T b ≤ cT x´
Dualität der Linearen Programmierung
Primales Programm (P):
Duales Programm (D):
Korollar: Ist (P) unbeschränkt, dann ist (D)
unlösbar.
Sei x´ein zulässiger Punkt für (P) und y´
zulässig für (D).
Dann gilt: y´T b ≤ cT x´
Dualität der Linearen Programmierung
Primales Programm (P):
Duales Programm (D):
Starker Dualitätssatz:
Sei x* ein zulässiger Punkt für (P) und y*
zulässig für (D). Dann gilt:
y*Tb=cTx*  beide Lösungen x* und y* sind
optimal
Einblick in den Simplex-Algorithmus
max
5x1 + 4x2 + 3x3
subject to 2x1 + 3x2 + x3  5
4x1 + x2 + 2x3  11
3x1 + 4x2 + 2x3  8
x1, x2, x3  0.
Simplex-Algorithmus
Einführung von Schlupf-Variablen um
Gleichungen zu erhalten
max
5x1 + 4x2 + 3x3
subject to 2x1 + 3x2 + x3 + x4
4x1 + x2 + 2x3
3x1 + 4x2 + 2x3
= 5
+ x5
= 11
+ x6 = 8
x1, x2, x3, x4, x5, x6  0.
Simplex-Algorithmus
Start
Zunächst setzen wir x1=x2=x3=0, und schreiben das
System um, so dass die Nicht-Null Elemente links
stehen; nun können wir direkt die Werte der anderen
Variablen ablesen: x4=5, x5=11, x6=8, z=0.
z =
5x1 + 4x2 + 3x3
x4 = 5 - 2x1 - 3x2 - x3
x5 = 11 - 4x1 - x2 - 2x3
x6 = 8 - 3x1 - 4x2 - 2x3
Simplex-Algorithmus
Erste Iteration
Wir wollen den Wert z erhöhen, mometan ist er 0.
Erhöhe z.B. den Wert von x1. Wie weit können wir
erhöhen?
z =
5x1 + 4x2 + 3x3
x4 = 5 - 2x1 - 3x2 - x3
x5 = 11 - 4x1 - x2 - 2x3
Wir setzen:
x1=5/2
x4=0
x6 = 8 - 3x1 - 4x2 - 2x3
x4  0  5 – 2x1  0  5  2x1  x1  5/2
x5  0  11 – 4x1  0  11  4x1  x1  11/4
x6  0  8 – 3x1  0  8  3x1  x1  8/3
Simplex-Algorithmus
Zweite Iteration
Wir wollen den Zielfunktionswert weiter erhöhen.
Dies geht momentan nur durch Erhöhung von x3.
z = 25/2 - 7/2x2 + 1/2x3 - 1/2x4
x1 =
x5 =
x6 =
5/2 - 3/2x2 - 1/2x3 - 1/2x4
1 + 5x2
+ 2x4
1/2 + 1/2x2 - 1/2x3 + 3/2x4
x1  0  5/2 – 1/2x3  0  5/2  1/2x3  x3  5
x5  0 
x3 unbeschränkt
x6  0  1/2 – 1/2x3  0  1/2  1/2x3  x3  1
Simplex-Algorithmus
Optimal!!!
z =
13 - 3x2 -
x4 - x6
x1 =
2 - 2x2 - 2x4 + x6
x5 =
1 + 5x2 + 2x4
x3 =
1 + x2 + 3x4 - 2x6
Denn: die Koeffizienten des z-Vektors sind alle kleiner gleich 0.
Es kann also zu keiner Verbesserung der Zielfunktion kommen.
Simplex-Algorithmus
Graphische Interpretation
Max
Subject to
3x1 + 2x2 + 2x3
x1 +
x3  8
x1 + x2
 7
x1 + 2x2
 12
x1, x2, x3  0
Simplex-Algorithmus
Max z = 3x1 + 2x2 + 2x3
x3
(0,0,8)
(0,6,8)
(2,5,6)
Optimal!
z = 28
(0,6,0)
z=0
(2,5,0)
(7,0,1)
z = 23
(7,0,0)
x1
x2
z = 21
Typischer Beispiellauf (CPLEX)
Log started (V8.2.0a1) Tue Apr
8 21:59:46 2003
Problem name: supply_chain.lp.gz
Constraints
: 10810259
Variables
: 19916187
Reduced LP has 3140439 rows, and 7314332 variables.
Presolve time = 339.43 sec.
Iteration log . . .
Iteration:
0
Iteration: 1247301
Infeasibility =
Infeasibility =
1534390803.049594
437397607.938387
...
Iteration: 2348954
Infeasibility =
10965.599999
Elapsed time = 3776.48 sec. (2349000 iterations)
Iteration: 2349222
Objective
= 1775629743606097400.000000
...
Elapsed time = 5396.65 sec. (2687000 iterations)
Iteration: 2687616
Objective
= 1403833763253068800.000000
Removing shift (10).
Primal simplex - Optimal: Objective =
1.4038337633e+18
Solution time = 5410.00 sec. Iterations = 2687616 (2348954)
Überblick
• Lineare Programmierung
• Dualität
• Simplex Algorithmus
• Grundlagen der Polyedertheorie
Siehe pdf-file

x - Technische Universität Wien