View
7
Download
0
Category
Preview:
Citation preview
1
1 Petra Mutzel Alg. & Dat. WS 08/09
Kap. 4.2: Simplex-Algorithmus
Professor Dr. Petra Mutzel
Lehrstuhl für Algorithm Engineering, LS11
Fakultät für Informatik, TU Dortmund
14.-16. VO A&D WS 08/09 2.12.-11.12.2008
2 Petra Mutzel Alg. & Dat. WS 08/09
Literatur für diese VO
• V. Chvatal: Linear Programming
• D. Bertsimas: Linear Programming
3 Petra Mutzel Alg. & Dat. WS 08/09
Überblick 4.2 Der Simplex-Algorithmus
– Einführung – Tableau-Methode (Standard-Simplex) – Revidierte Simplex-Methode – Auswahlregeln – Terminierung – Analyse der Laufzeit
4 Petra Mutzel Alg. & Dat. WS 08/09
Lineare Programme werden in der Praxis mit Hilfe des Simplex-Algorithmus gelöst [Dantzig 1955].
Max 3x1 + 2x2 + 2x3 Subject to x1 + x3 ≤ 8 x1 + x2 ≤ 7 x1 + 2x2 ≤ 12 x1, x2, x3 ≥ 0
3.2 Der Simplex-Algorithmus
x1
x2
x3
(0,0,8) (0,6,8)
(2,5,6)
(0,6,0)
(2,5,0) (7,0,1)
(7,0,0)
Max z = 3x1 + 2x2 + 2x3
z = 0
z = 21
z = 23
Optimal!
z = 28
Visualisierung des Simplex-Algorithmus Simplex-Algorithmus
Gegeben: LP mit Lösungspolyeder P (1) Bestimme einen beliebige Ecke (Initialecke) v von P. (2) Falls es keine verbessernde Kante inzident zu v gibt
stop: v ist optimal. (3) Folge einer beliebigen verbessernden Kante e von v. Falls
e unbeschränkt ist, d.h. keinen anderen Endpunkt hat stop: Das LP ist unbeschränkt.
(4) Sei u der andere Endpunkt von e. Setze v=u. Gehe zu (2)
2
Offene Fragen zu Simplex-Algorithmus
Wie wird das Polyeder abgespeichert? • Man speichert das durch die Restriktionen beschriebene
Gleichungssystem in Form eines Tableaus ab. In jedem Simplexschritt verändert sich das Tableau und die ausgehenden Kanten des aktuellen Ecke können aus dem Tableau berechnet werden.
Teste, ob die aktuelle Ecke optimal ist? Falls nicht, welche verbessernde Kante wählt man? Terminiert der Algorithmus?
• s. Vorlesung: gleich
Wie findet man eine Initialecke v von P? • Bei zulässigen LPs in Standardform mit nicht-negativen aij und bi ist
der Ursprung (Punkt 0) immer ein Knoten von P. Ansonsten verwendet man ein Preprocessing (Phase 1), das an einem Schnittpunkt evtl. außerhalb von P startet und durch ähnliche Basisaustauschschritte zu einer Ecke in P läuft.
Definitionen • Gegeben sei ein Gleichungssystem Ax=b mit A∈Rm×n, m<n,
b∈Rm , rang(A)=m. • Sei B=(p1,p2,...,pm)∈{1,2,...,n}m Spaltenindexmenge und
N=(q1,q2,...,qn-m)∈{1,2,...,n}n-m Spaltenindexmengen mit B∪N={1,2,...,n} und B∩N=∅.
• Für J⊆{1,2,...n}: AJ ist die Untermatrix von A nach Streichen der Spalten aus {1,2,...,n} \ J. Wir schreiben AB statt AB und AN statt AN.
• Ist AB regulär (=invertierbar), so heißt AB Basismatrix oder Basis von A und B Basisindexvektor oder Basis von A; analog AN, N Nichtbasisindexvektor.
• Der Vektor x∈Rn mit xN=0, xB=AB-1b heißt Basislösung von
Ax=b zur Basis AB.
Definitionen
• Ist AB eine Basis, so heißen die Variablen xj, j∈B, Basisvariablen und die xj, j∈N Nichtbasisvariablen.
• Ist AB Basis und gilt AB-1b≥0, so heißen AB, B und die
zugehörige Basislösung x zulässig, sonst unzulässig. • Eine zulässige Basislösung x zur Basis AB heißt nicht-
degeneriert, falls (xB)i=(AB-1b)i>0 für alle i∈B, sonst
degeneriert.
• Ist AB regulär (=invertierbar), so heißt AB Basismatrix oder Basis von A und B Basisindexvektor oder Basis von A; analog AN, N Nichtbasisindexvektor.
• Der Vektor x∈Rn mit xN=0, xB=AB-1b heißt Basislösung von
Ax=b zur Basis AB.
Simplex-Gleichungsschema und Simplex Tableau
• max cTx s.t. Ax=b, x≥0
Zielfunktionswert:
Simplex-Gleichungsschema:
€
maxcBcN
T xBxN
s.t. (AB ,AN )xBxN
= b,
xBxN
≥ 0
€
z = cBT xB + cN
T xN = cBT (AB
−1b − AB−1AN xN ) + cN
T xN =
= cBT AB
−1b + (cNT − cB
T AB−1AN )xN
€
AB xB + AN xN = b ⇔ xB = AB−1b − AB
−1AN xN
€
xB = AB−1b − AB
−1AN xN z = cB
T AB−1b + (cN
T − cBT AB
−1AN )xN
Simplex-Gleichungsschema und Simplex Tableau
Simplex-Gl.schema:
Simplex-Tableau:
€
xB = AB−1b − AB
−1AN xN z = cB
T AB−1b + (cN
T − cBT AB
−1AN )xN
€
cBT AB
−1b cNT − cB
T AB−1AN
AB−1b AB
−1AN
- Zielfunktionswert reduzierte
Kosten
Werte der Basisvariablen
Basisaustauschsatz Beispiel, s. Tafel
3
14 Petra Mutzel Alg. & Dat. WS 08/09
Beweis: (a)
(b1)
15 Petra Mutzel Alg. & Dat. WS 08/09
(b2) AB! entsteht aus AB durch Ersetzen der r-ten Spalte durch A·qs .Es gilt AB! = AB · F , wobei
F =
!
""""""""""#
1 0 0 a1s
. . ....
0 0 1 ar!1,s
ars
ar+1,s 1 0 0...
. . .ams 0 0 1
$
%%%%%%%%%%&
Denn: Wir haben A·s = A!1B A·qs und deshalb ist die
s-te Spalte von AB · F gleich ABA·s = AB · A!1B A·s = A·qs
und alle anderen Spalten bleiben wie in AB .
Es gilt ars > 0, also ist F regular und somit ist AB! eine Basis.
16 Petra Mutzel Alg. & Dat. WS 08/09
r-te Spalte
Weiterhin ist xB! = A!1B! b = F!1A!1
B b = F!1xB = F!1b mit
F!1 =
!
"""""""""""#
1 0 0 ! a1sars
. . ....
0 0 1 ! ar"1,s
ars1
ars
! ar+1,s
ars1 0 0
.... . .
! amsars
0 0 1
$
%%%%%%%%%%%&
Also gilt fur i " 1, 2, ...,m:Falls ais > 0: x"pi
= bi ! aisars
br # bi ! aisais
bi = 0insbesondere fur i = r: x"pr
= br ! arsars
br = 0 (neue Nichtbasisvariable)Falls ais $ 0: x"pi
= bi ! aisars
br # bi # 0 und x"qs= br
ars# 0
(neue Basisvariable)Also ist x" zulassige Basislosung zur Basis B".
17 Petra Mutzel Alg. & Dat. WS 08/09
(b3) nicht-degenerierter Fall: λ0>0:
✔
Simplex-Algorithmus
(1) Start mit einer zulässigen Basis (2) Iterierte Anwendung des Satzes:
(a) STOP, Optimalität (b1) STOP, Unbeschränktheit
(b2) Basiswechsel: Pivot mit Pivotspalte s und Pivotzeile r
2 Varianten: • Tableau-Methode (Standard-Simplex) • Revidierte Methode
Tableau-Methode
€
cBT AB
−1b cNT − cB
T AB−1AN
AB−1b AB
−1AN
- Zielfunktionswert reduzierte
Kosten
Werte der Basisvariablen
t00 t01 ... t0n
t10 t11 ... t1n
... ... ... ... tm0 tm1 ... tmn
Das Tableau ist zulässig falls ti0≥0 für alle i∈{1,2,...,m}. Das Tableau ist optimal falls t0j≤0 für alle j∈{1,2,...,n}.
4
20 Petra Mutzel Alg. & Dat. WS 08/09
Rechenregeln (aus Basisaustausch-Satz)
Daraus ergeben sich die folgenden Rechenregeln:
Berechnung von A! = A"1B! AN ! :
A"1B! AN ! = (AB · F )"1 · AN ! = F"1(A"1
B · AN !)
AN ! unterscheidet sich von AN nur durch die r-te Spalte(gehort zur Variablen mit Index pr).
Zur Neuberechnung von A! muss A also im Wesentlichenmit F"1 multipliziert werden;Ausnahmen bilden die r-te Spalte sowie die s-te Zeile.Dasselbe gilt fur die Berechnung von b! und c!.Das Element ars wird als Pivotelement bezeichnet.
Rechenregeln (aus Basisaustausch-Satz)
Beispiel Beispiel ff
Beispiel fff Beobachtungen zum Simplex-Algorithmus
• In jeder Iteration wird eine Basislösung durch eine andere ersetzt.
• Zur Berechnung der neuen Basislösung xB‘ wird nur ein sehr kleiner Teil des Tableaus benutzt: man benötigt AB
-1, b=xB und c sowie die s-te Spalte von A.
• Idee: Statt jedes Mal die ganze Matrix zu berechnen, berechne nur den Teil, der wirklich gebraucht wird, und dies direkt aus den Originaldaten
revidierte Simplexmethode
− − −
5
Revidierte Simplex-Methode
Beispiel ENDE
Beispiel Gleiches Beispiel wie vorhin mit B = (4, 5) und N = (1, 2, 3), also
AB =!
1 00 1
", xB =
!x4
x5
"=
!35
", A =
!2 2 1 1 01 2 4 0 1
"
1. Iteration:
yT AB = cTB : yT ·
!1 00 1
"= (0 0) ! y =
!00
"
Fur x2 sind die reduzierten Kosten
c2 " yT ·!
22
"= c2 = 5.
x2 tritt ein
ABd = a ! d =!
22
"
t = 32 und x4 raus.
Beispiel
x2 =32
xB :=!
x4
x5
"=
!35
"! 3
2
!22
"=
!02
"
B = (2, 5)N = (1, 4, 3)
xB :=! 3
2
2
"
AB = AB · F =!
1 00 1
" !2 02 1
"=
!2 02 1
"
Beispiel 2. Iteration
yT
!2 02 1
"= (5, 0)! y =
! 52
0
"
Reduzierte Kosten:
x1 : 3" (52, 0)
!21
"= "2 # 0
x4 : 0" (52, 0)
!10
"= "5
2# 0
x3 : 4" (52, 0)
!14
"=
32
x3 rein
Beispiel
ABd = a :!
2 02 1
"d =
!14
"! d =
! 12
3
".
t = 23 und x5 raus.
x3 =23
xB :=!
x2
x5
"=
! 32
2
"" 2
3
! 12
3
"=
! 76
0
"
B = (2, 3)N = (1, 4, 5)
xB :=! 7
623
"
AB = AB · F =!
2 02 1
" !1 1
20 3
"=
!2 12 4
"
6
Beispiel 3. Iteration:
yT
!2 12 4
"= (5 4) ! y =
!212
"
Reduzierte Kosten:
x1 : 3"!
2,12
" !21
"= "3
2# 0
x4 : 0"!
2,12
" !10
"= "2 # 0
x5 : 0"!
2,12
" !01
"= "1
2# 0
Optimal!
Eta-Faktorisierung der Basis
Beispiel
Eta-Faktorisierung der Basis
Z.B. Losen von yT AB4 = cTB : (((yT E1)E2)E3)E4 = cT
B :uT E4 = cT
B , vT E3 = uT , wT E2 = vT , yT E1 = wT .Losen von AB4d = a: E1(E2(E3(E4d))) = aE1u = a, E2v = u, E3w = v, E4d = w.
Speicherung der Eta-Matrizen: jeweils nur die Spalte und die Position.Eta-File: E1, E2, ..., Ek.
Bemerkung zur Eta-Faktorisierung
• Mit der Eta-Faktorisierung hat man zwar mehr Gleichungssysteme zu lösen, da diese aber sehr dünn besetzt ist, ist dies mit sehr geringem Aufwand verbunden:
• Wenn die Eta-Spalte k Nicht-Nullen besitzt, dann werden hierzu nur k-1 Multiplikationen, k-1 Additionen und 1 Division benötigt.
Periodische Refaktorisierung
• In jeder Iteration kommt eine neue Eta-Matrix hinzu • Problem: Zunehmende Ineffizienz, da immer mehr
Gleichungssysteme zu lösen sind und damit auch neben dem Zeitfaktor numerische Fehler verbunden sind
• Lösung: periodische Refaktorisierung: berechne alle h Iterationen (Chvatal empfiehlt h=20) eine neue Triangulations-Zerlegung von ABk (z.B. LU-Zerlegung) und setze diese als neues AB0.
Vorteile der revidierten Methode
• Rechenaufwand ist bei einer großen und dünn besetzten Matrix deutlich kleiner als bei Tableau-Methode
• Spalten werden nur bei Bedarf generiert • Eta-Faktorisierung (und Refaktorisierung) statt
Speicherung der inversen Matrix • Rechengenauigkeit ist deutlich besser, denn man
kann die inverse Basismatrix regelmäßig neu berechnen.
Simplexalgorithmus läßt noch einige Freiheiten, z.B. bei Zeilen und Spaltenauswahl, denn es können jeweils mehrere Kandidaten existieren.
7
38 Petra Mutzel Alg. & Dat. WS 08/09
Spaltenauswahlregeln • Kleinster-Index-Regel: Wähle die Spalte mit
kleinstem Index • Kleinster-Variablenindex-Regel: Wähle die Spalte
mit dem kleinsten Variablenindex • Steilster-Anstieg-Regel: Wähle diejenige Spalt mit
den größten reduzierten Kosten • Größter-Fortschritt-Regel: Berechne den neuen
Zielfunktionswert über alle möglichen Spalten aus und wähle dann diejenige Spalte, die den größten Wert bringt.
• Lexikographische Spaltenauswahlregel: Betrachte jeweils die Vektoren der in Frage kommenden Spalten und wähle den lexikographisch kleinsten aus.
39 Petra Mutzel Alg. & Dat. WS 08/09
Zeilenauswahlregeln
• Kleinster-Index-Regel: Wähle die Zeile mit kleinstem Index
• Kleinster-Variablenindex-Regel: Wähle die Zeile mit dem kleinsten Variablenindex
• Lexikographische Zeilenauswahlregel: Betrachte jeweils die Vektoren der in Frage kommenden Zeilen und wähle den lexikographisch kleinsten aus.
Diese Regeln werden dann angewendet, falls es mehrere Kandidaten zur Auswahl gibt
40 Petra Mutzel Alg. & Dat. WS 08/09
Terminierung Problem: Man kann Beispiele konstruieren, für die sich
eine Basis wiederholt: Phänomen des Zykelns (nur bei Degenerität) keine Terminierung
Lösung: Es gibt Spalten- bzw. Zeilenauswahlregeln, von denen man zeigen kann, dass in diesem Fall der Simplex-Algorithmus terminiert.
Terminierung
Bemerkungen: • Wendet man die kleinste Indexregel auf nur eine
Spalten- oder Zeilenauswahl an, dann kann man Beispiele konstruieren, bei denen das Verfahren nicht terminiert.
• Es gibt aber auch Regeln (z.B. die lexikographische Zeilen- bzw. Spaltenauswahlregel), die nur auf eines der beiden angewendet werden müssen um Terminierung zu erhalten.
Satz (Bland, 1977): Bei der Anwendung von Bland´s Regel terminiert der Simplexalgorithmus.
Bland´s Regel: Eintretende und austretende Variable ist immer diejenige mit dem kleinsten Index.
Bemerkungen
Achtung: • Bland´s Regel verhindert zwar das Zykeln, aber in der
Praxis hat sich gezeigt, dass i.A. die Anzahl der Pivotoperationen bei Anwendung der Bland-Regel wesentlich höher liegt als z.B. bei der Steilster Anstieg-Regel.
• In der Praxis wird daher meist die steilste Anstieg Regel zur Spaltenauswahl verwendet.
Laufzeit
Worst Case: • Zu fast allen bekannten Pivotauswahlregeln kennt
man heute eine Klasse von Polyedern und Zielfunktionen, so dass der Simplexalgorithmus bei Anwendung einer zugehörigen Auswahlregel durch alle Ecken des Polyeders läuft.
• Da die Anzahl der Ecken dieser Polyeder exponentiell mit der Anzahl der Variablen wächst exponentielle worst-case Laufzeit.
Laufzeit pro Iteration: s. nächste VO
8
Laufzeitvergleich Tableau vs. Revidierter Simplexalgorithmus
Laufzeit pro Iteration: • TODO
Recommended