View
215
Download
0
Category
Preview:
Citation preview
Dualitat Zweiphasen-Simplexalgorithmus
Losung allgemeiner linearer Programme
Bisher: Fur Anwendung des Simplexalgorithmus muss eine primaloder eine dual zulassige Basislosung vorliegen.
Fur allgemeine lineare Programme konnen wir dies direktnicht gewahrleisten.
Im Folgenden: Unter Ausnutzung dualer Techniken leiten wir eineMethode her, mit der zu jedem LP, dass eine optimaleLosung hat, eine solche berechnet werden kann.
Peter Becker (H-BRS) Operations Research I Sommersemester 2014 277 / 298
Dualitat Zweiphasen-Simplexalgorithmus
Allgemeine Form
Wir gehen von einem LP mit n Variablen und m Nebenbedingungen aus.Die Zielfunktion habe die Gestalt
min oder max z =nX
j=1
cjxj
unter den Nebenbedingungen
nX
j=1
aijxj
8<
:
�=
9=
; bi fur i = 1, . . . ,m
und Nichtnegativitatsbedingungen
xj � 0 fur einige oder alle j = 1, . . . , n.
Peter Becker (H-BRS) Operations Research I Sommersemester 2014 278 / 298
Dualitat Zweiphasen-Simplexalgorithmus
Anforderungen fur primalen Simplex
zu maximierende Zielfunktion
nur Gleichheitsbedingungen
Nichtnegativitatsbedingungen fur alle Variablen
ein nichtnegativer Vektor auf der rechten Seite
ein primal zulassiges Ausgangstableau in kanonischer Form, d.h. mitm Einheitsvektoren, die eine Basis bilden
Peter Becker (H-BRS) Operations Research I Sommersemester 2014 279 / 298
Dualitat Zweiphasen-Simplexalgorithmus
Zielfunktion, rechte Seite, Vorzeichenbeschrankung
(1) Falls eine zu minimierende Zielfunktion vorliegt, multipliziere diesemit �1 und maximiere �z .
(2) Multipliziere alle Gleichungen und Ungleichungen derNebenbedingungen mit bi < 0 mit dem Faktor �1.
(3) Ersetze jede nicht vorzeichenbeschrankte Variable xj durch zweivorzeichenbeschrankte Variablen x 0j � 0 und x 00j � 0 mit xj = x 0j � x 00j .
Peter Becker (H-BRS) Operations Research I Sommersemester 2014 280 / 298
Dualitat Zweiphasen-Simplexalgorithmus
Damit hat das lineare Programm die Gestalt:
max z =nX
j=1
cjxj
unter den Nebenbedingungen
nX
j=1
aijxj bi fur i = 1, . . . ,m1
nX
j=1
aijxj � bi fur i = m1 + 1, . . . ,m1 +m2
nX
j=1
aijxj = bi fur i = m1 +m2 + 1, . . . ,m1 +m2 +m3
und Vorzeichenbedingungen
xj � 0 fur j = 1, . . . , n
Peter Becker (H-BRS) Operations Research I Sommersemester 2014 281 / 298
Dualitat Zweiphasen-Simplexalgorithmus
Bemerkungen:
n ist die Anzahl der Variablen nach Schritt (1) bis (3).
m1,m2,m3 bezeichnet dabei die Anzahl der -, �- und=-Nebenbedingungen.
m := m1 +m2 +m3
Peter Becker (H-BRS) Operations Research I Sommersemester 2014 282 / 298
Dualitat Zweiphasen-Simplexalgorithmus
Erzeuge Normalform
(4) Wandle jede -Nebenbedingung durch eine Schlupfvariable um ineine Gleichung der Form
nX
j=1
aijxj + xn+i = bi
(5) Wandle jede �-Nebenbedingung durch eine Schlupfvariable um ineine Gleichung der Form
nX
j=1
aijxj � xn+i = bi
Alle Schlupfvariablen xn+i sind vorzeichenbeschrankt, also xn+i � 0. Jetzthaben wir Normalform, aber keine kanonische Normalform und damit nochkein primal zulassiges Tableau.
Peter Becker (H-BRS) Operations Research I Sommersemester 2014 283 / 298
Dualitat Zweiphasen-Simplexalgorithmus
Kunstliche Variablen
(6) Addiere zu jeder ursprunglichen �-Nebenbedingung eine kunstlicheVariable yk � 0, so dass die Nebenbedingung lautet:
nX
j=1
aijxj � xn+i + yk = bi
(7) Addiere zu jeder ursprunglichen =-Nebenbedingung eine kunstlicheVariable yk � 0, so dass die Nebenbedingung lautet:
nX
j=1
aijxj + yk = bi
Peter Becker (H-BRS) Operations Research I Sommersemester 2014 284 / 298
Dualitat Zweiphasen-Simplexalgorithmus
Jetzt haben wir ein Simplextableau in kanonischer Form mit derBasislosung
xm+i = bifur die xm+i von ursprunglichen -Nebenbedingungen und
yk = bkfur die ursprunglichen �- und =-Nebenbedingungen.
Problem: Nur wenn fur alle kunstlichen Variablen yk = 0 gilt, ist diesesLP aquivalent zum ursprunglichen LP.
Peter Becker (H-BRS) Operations Research I Sommersemester 2014 285 / 298
Dualitat Zweiphasen-Simplexalgorithmus
Zweite Zielfunktion
(8) Bilde aus den kunstlichen Variablen die zusatzliche Zielfunktion
minY =m2+m3X
k=1
yk
Entsteht bei der Minimierung Y = 0, dann wird die Erweiterungnivelliert und wir haben eine zulassige Basislosung.
(9) Multipliziere die zusatzliche Zielfunktion mit dem Faktor �1, um eineMaximierung zu erhalten.
max y = �Y =m2+m3X
k=1
�yk
Peter Becker (H-BRS) Operations Research I Sommersemester 2014 286 / 298
Dualitat Zweiphasen-Simplexalgorithmus
(10) Lose alle Gleichungen mit kunstlichen Variablen nach diesen auf
yk = bi �
0
@nX
j=1
aijxj � xm+i
1
A
bzw.
yk = bi �nX
j=1
aijxj
und ersetze sie in der zweiten Zielfunktion durch die gewonnenenAusdrucke.Dieser Schritt dient dazu, dass die Koe�zienten der yk in derZielfunktionszeile zu 0 werden zu lassen, damit ein primal zulassigesTableau vorliegt.
Insgesamt haben wir jetzt ein primal zulassiges Simplextableau vorliegen.
Peter Becker (H-BRS) Operations Research I Sommersemester 2014 287 / 298
Dualitat Zweiphasen-Simplexalgorithmus
Zweiphasen-Simplexalgorithmus
Algorithmus 5.15
Bearbeite das durch die Schritte (1) bis (10) aufgestellte Tableau in zweiPhasen:
1 Ero↵nungsphaseMaximiere die Zielfunktion y = �Y mit Hilfe des primalenSimplexalgorithmus. Transformiere dabei die ursprunglicheZielfunktion z stets mit.
I Gilt fur das Optimum y < 0, dann existiert keine zulassige Losung furdas ursprungliche LP.
I Gilt y = 0, dann streiche die Zeile mit der zweiten Zielfunktion und diekunstlichen Variablen und fahre mit Phase 2 fort.
2 OptimierungsphaseMaximiere die erste Zielfunktion mit dem primalenSimplex-Algorithmus.
Peter Becker (H-BRS) Operations Research I Sommersemester 2014 288 / 298
Dualitat Zweiphasen-Simplexalgorithmus
Bemerkung
In der Ero↵nungsphase nahert man sich schrittweise einer Ecke derMenge X der zulassigen Losungen.
In der Optimierungsphase bestimmt man ausgehend von dergefundenen Ecke aus der Ero↵nungsphase eine optimale Losung desLP.
Peter Becker (H-BRS) Operations Research I Sommersemester 2014 289 / 298
Dualitat Zweiphasen-Simplexalgorithmus
Beispiel: Zweiphasen-Simplexalgorithmus
Beispiel 5.16
Wir betrachten das folgende LP:
minZ = �x1 � 2x2
unter den Nebenbedingungen
x1 + x2 8 (I)2x1 + x2 � 2 (II)x1 � x2 = �3 (III)
x1, x2 � 0
(1)max z = �Z = x1 + 2x2
Peter Becker (H-BRS) Operations Research I Sommersemester 2014 290 / 298
Dualitat Zweiphasen-Simplexalgorithmus
Fortsetzung Beispiel.
(2) Wir multiplizieren (III) mit �1 und erhalten die neue Gleichung (III):
�x1 + x2 = 3
(3) entfallt, alle Variablen sind vorzeichenbeschrankt
(4,5) Wir fuhren fur (I) und (II) Schlupfvariablen ein:
x1 + x2 + x3 = 8 (I)2x1 + x2 � x4 = 2 (II)
(6,7) Kunstliche Variablen fur (II) und (III):
2x1 + x2 � x4 + y1 = 2 (II)�x1 + x2 + y2 = 3 (III)
Peter Becker (H-BRS) Operations Research I Sommersemester 2014 291 / 298
Dualitat Zweiphasen-Simplexalgorithmus
Fortsetzung Beispiel.
(8) Zusatzliche Zielfunktion:
minY = y1 + y2
(9) Optimierungsrichtung der zusatzlichen Zielfunktion herumdrehen:
max y = �Y = �y1 � y2
(10) Wir losen (II) und (III) nach y1 bzw. y2 auf
y1 = 2 � 2x1 � x2 + x4y2 = 3 + x1 � x2
und setzen die Terme der rechten Seiten in die Zielfunktion ein.Hierdurch entsteht
y = �5 + x1 + 2x2 � x4
Peter Becker (H-BRS) Operations Research I Sommersemester 2014 292 / 298
Dualitat Zweiphasen-Simplexalgorithmus
Fortsetzung Beispiel.
Damit konnen wir das 1. Tableau fur die Ero↵nungsphase aufstellen:
BV x1 x2 x3 x4 y1 y2 bx3 1 1 1 0 0 0 8y1 2 1 0 �1 1 0 2y2 �1 1 0 0 0 1 3z �1 �2 0 0 0 0 0y �1 �2 0 1 0 0 �5
Wir maximieren y und wahlen dazu x2 als Pivotspalte. Damit ist y1 diePivotzeile.
Peter Becker (H-BRS) Operations Research I Sommersemester 2014 293 / 298
Dualitat Zweiphasen-Simplexalgorithmus
Fortsetzung Beispiel.
2. Tableau Ero↵nungsphase:
BV x1 x2 x3 x4 y1 y2 bx3 �1 0 1 1 �1 0 6x2 2 1 0 �1 1 0 2y2 �3 0 0 1 �1 1 1z 3 0 0 �2 2 0 4y 3 0 0 �1 2 0 �1
Man beachte, dass auch die Zeile fur die ursprungliche Zielfunktionangepasst wurde.Jetzt bleibt nur x1 als Pivotspalte, dann ist y2 die Pivotzeile.
Peter Becker (H-BRS) Operations Research I Sommersemester 2014 294 / 298
Dualitat Zweiphasen-Simplexalgorithmus
Fortsetzung Beispiel.
3. Tableau Ero↵nungsphase:
BV x1 x2 x3 x4 y1 y2 bx3 2 0 1 0 0 �1 5x2 �1 1 0 0 0 1 3x4 �3 0 0 1 �1 1 1z �3 0 0 0 0 2 6y 0 0 0 0 1 1 0
Damit ist die Ero↵nungsphase abgeschlossen und wir haben mit
x =
0
BB@
0351
1
CCA
eine Startecke fur die Optimierungsphase.
Peter Becker (H-BRS) Operations Research I Sommersemester 2014 295 / 298
Dualitat Zweiphasen-Simplexalgorithmus
Fortsetzung Beispiel.
Wir streichen die kunstlichen Variablen und die zusatzlicheZielfunktionszeile und erhalten damit das 1. Tableau derOptimierungsphase:
BV x1 x2 x3 x4 bx3 2 0 1 0 5x2 �1 1 0 0 3x4 �3 0 0 1 1z �3 0 0 0 6
Es liegt noch keine optimale Losung vor.Pivotspalte wird x1, Pivotzeile x3.
Peter Becker (H-BRS) Operations Research I Sommersemester 2014 296 / 298
Dualitat Zweiphasen-Simplexalgorithmus
Fortsetzung Beispiel.
2. Tableau Optimierungsphase:
BV x1 x2 x3 x4 bx1 1 0 1/2 0 5/2x2 0 1 1/2 0 11/2x4 0 0 3/2 1 17/2z 0 0 3/2 0 27/2
Damit terminiert der Zweiphasen-Simplexalgorithmus.
x =
52
112
!ist eine optimale Losung des originaren LP,
mit Zielfunktionswert Z = �272 .
Peter Becker (H-BRS) Operations Research I Sommersemester 2014 297 / 298
Dualitat Zweiphasen-Simplexalgorithmus
Zusammenfassung
Zu jedem primalen LP gibt es ein korrespondierendes duales LP.
Die Betrachtung sowohl des primalen als auch des dualen LPermoglicht tiefergehende Einblicke in das zu Grunde liegende Problem.
Zueinander duale LPs sind eng miteinander verbunden: gegenseitigeSchranken, Gleichheit der Zielfunktionen in den Optima,Entsprechungen bei Struktur-, Schlupf-, Basis-, undNichtbasisvariablen.
Zwei-Phasen-Simplexalgorithmus zur allgemeinen Losung von linearenProgrammen.
Peter Becker (H-BRS) Operations Research I Sommersemester 2014 298 / 298
Recommended