Download pdf - Lineare Optimierung Winfried Hochstättler · OutlineLineares Programm (LP) in StandardformDualitätDer Simplexalgorithmus Lineares Programm (LP) in Standardform max c>x so dass Ax

Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus

Studientag zur Algorithmischen MathematikLineare Optimierung

Winfried Hochstättler

Diskrete Mathematik und OptimierungFernUniversität in Hagen

1. Juli 2012


Outline

Lineares Programm (LP) in Standardform

Dualität

Der Simplexalgorithmus


Lineares Programm (LP) in Standardform

max c>xso dass Ax = b

x ≥ 0

mit b ≥ 0, A ∈ Rm×n, b ∈ Rm, c ∈ Rn.


Umformung in Standardform


x ≥ 0

• min c>x

−max(−c)>x

• bi < 0 multipliziere Zeile i mit (−1)• a>x ≤ bi a>x + si = bi , si ≥ 0 (si Schlupfvariable)• a>x ≥ bi a>x − si = bi , si ≥ 0 (si Schlupfvariable)• beliebiges xi (ohne xi ≥ 0) xi = x+

i − x−i , x+i , x

−i ≥ 0

Aufspalten der Variablen




x ≥ 0

• min c>x −max(−c)>x

• bi < 0

multipliziere Zeile i mit (−1)• a>x ≤ bi a>x + si = bi , si ≥ 0 (si Schlupfvariable)• a>x ≥ bi a>x − si = bi , si ≥ 0 (si Schlupfvariable)• beliebiges xi (ohne xi ≥ 0) xi = x+

i − x−i , x+i , x

−i ≥ 0





x ≥ 0

• min c>x −max(−c)>x• bi < 0

multipliziere Zeile i mit (−1)

• a>x ≤ bi a>x + si = bi , si ≥ 0 (si Schlupfvariable)• a>x ≥ bi a>x − si = bi , si ≥ 0 (si Schlupfvariable)• beliebiges xi (ohne xi ≥ 0) xi = x+

i − x−i , x+i , x

−i ≥ 0





x ≥ 0

• min c>x −max(−c)>x• bi < 0 multipliziere Zeile i mit (−1)

• a>x ≤ bi

a>x + si = bi , si ≥ 0 (si Schlupfvariable)• a>x ≥ bi a>x − si = bi , si ≥ 0 (si Schlupfvariable)• beliebiges xi (ohne xi ≥ 0) xi = x+

i − x−i , x+i , x

−i ≥ 0





x ≥ 0

• min c>x −max(−c)>x• bi < 0 multipliziere Zeile i mit (−1)• a>x ≤ bi

a>x + si = bi , si ≥ 0 (si Schlupfvariable)

• a>x ≥ bi a>x − si = bi , si ≥ 0 (si Schlupfvariable)• beliebiges xi (ohne xi ≥ 0) xi = x+

i − x−i , x+i , x

−i ≥ 0





x ≥ 0

• min c>x −max(−c)>x• bi < 0 multipliziere Zeile i mit (−1)• a>x ≤ bi a>x + si = bi , si ≥ 0 (si Schlupfvariable)

• a>x ≥ bi

a>x − si = bi , si ≥ 0 (si Schlupfvariable)• beliebiges xi (ohne xi ≥ 0) xi = x+

i − x−i , x+i , x

−i ≥ 0





x ≥ 0

• min c>x −max(−c)>x• bi < 0 multipliziere Zeile i mit (−1)• a>x ≤ bi a>x + si = bi , si ≥ 0 (si Schlupfvariable)• a>x ≥ bi

a>x − si = bi , si ≥ 0 (si Schlupfvariable)

• beliebiges xi (ohne xi ≥ 0) xi = x+i − x−i , x+

i , x−i ≥ 0





x ≥ 0

• min c>x −max(−c)>x• bi < 0 multipliziere Zeile i mit (−1)• a>x ≤ bi a>x + si = bi , si ≥ 0 (si Schlupfvariable)• a>x ≥ bi a>x − si = bi , si ≥ 0 (si Schlupfvariable)

• beliebiges xi (ohne xi ≥ 0)

xi = x+i − x−i , x+

i , x−i ≥ 0





x ≥ 0

• min c>x −max(−c)>x• bi < 0 multipliziere Zeile i mit (−1)• a>x ≤ bi a>x + si = bi , si ≥ 0 (si Schlupfvariable)• a>x ≥ bi a>x − si = bi , si ≥ 0 (si Schlupfvariable)• beliebiges xi (ohne xi ≥ 0)

xi = x+i − x−i , x+

i , x−i ≥ 0





x ≥ 0

• min c>x −max(−c)>x• bi < 0 multipliziere Zeile i mit (−1)• a>x ≤ bi a>x + si = bi , si ≥ 0 (si Schlupfvariable)• a>x ≥ bi a>x − si = bi , si ≥ 0 (si Schlupfvariable)• beliebiges xi (ohne xi ≥ 0) xi = x+

i − x−i , x+i , x

−i ≥ 0



Beispiel

min −x1 − x2s.d. x1 − x2 ≥ 3

2x1 + x2 ≤ 8x2 ≥ 0


Beispiel

min −x1 − x2s.d. x1 − x2 ≥ 3

2x1 + x2 ≤ 8x2 ≥ 0

−max x1 + x2s.d. x1 − x2 ≥ 3

2x1 + x2 ≤ 8x2 ≥ 0


Beispiel

min −x1 − x2s.d. x1 − x2 ≥ 3

2x1 + x2 ≤ 8x2 ≥ 0

−max x1 + x2s.d. x1 − x2 − s1 = 3

2x1 + x2 + s2 = 8x2, s1, s2 ≥ 0


Beispiel

min −x1 − x2s.d. x1 − x2 ≥ 3

2x1 + x2 ≤ 8x2 ≥ 0

−max x+1 − x−1 + x2

s.d. x+1 − x−1 − x2 − s1 = 3

2x+1 − 2x−1 + x2 + s2 = 8

x+1 , x

−1 , x2, s1, s2 ≥ 0


Das duale Programm

(P)max c>xs.d. Ax = b

x ≥ 0

primales Programm

(D) min y>bs.d. y>A ≥ c>

duales Programm

• x heißt zulässig für (P), falls x die Nebenbedingungen erfüllt, d.h.Ax = b, x ≥ 0.

• (P) heißt zulässig, wenn es ein zulässiges x für (P) gibt.• (P) heißt beschränkt, wenn der optimale Zielfunktionswert

endlich ist.

Analog definiert man diese Begriffe für (D).


Das duale Programm


x ≥ 0

primales Programm


duales Programm



endlich ist.



Das duale Programm


x ≥ 0

primales Programm


duales Programm



endlich ist.



Das duale Programm


x ≥ 0

primales Programm


duales Programm


• (P) heißt zulässig, wenn es ein zulässiges x für (P) gibt.

• (P) heißt beschränkt, wenn der optimale Zielfunktionswertendlich ist.



Das duale Programm


x ≥ 0

primales Programm


duales Programm



endlich ist.



Das duale Programm


x ≥ 0

primales Programm


duales Programm



endlich ist.



Schwache Dualität


x ≥ 0

primales Programm


duales Programm

Satz:Ist x ≥ 0 zulässig für (P) und y zulässig für (D), so gilt c>x ≤ y>b.

Beweis:

c>x

c> ≤ y>Ax ≥ 0≤ (y>A)x = y>(Ax) Ax=b

= y>b �


Schwache Dualität


x ≥ 0

primales Programm


duales Programm


Beweis:

c>x

c> ≤ y>Ax ≥ 0≤

(y>A)x = y>(Ax) Ax=b= y>b �


Schwache Dualität


x ≥ 0

primales Programm


duales Programm


Beweis:

c>x

c> ≤ y>Ax ≥ 0≤ (y>A)x =

y>(Ax) Ax=b= y>b �


Schwache Dualität


x ≥ 0

primales Programm


duales Programm


Beweis:

c>x

c> ≤ y>Ax ≥ 0≤ (y>A)x = y>(Ax) Ax=b

=

y>b �


Schwache Dualität


x ≥ 0

primales Programm


duales Programm


Beweis:

c>x

c> ≤ y>Ax ≥ 0≤ (y>A)x = y>(Ax) Ax=b

= y>b �


Dualitätssatz

Satz:Ist (P) zulässig und beschränkt, so ist auch (D) zulässig undbeschränkt, und es gibt Optimallösungen x von (P) und y von (D) mitc>x = y>b.

BeweisideeSei x Optimallösung von (P), d.h. von

(P)−min −c>x

s.d. Ax = bx ≥ 0

Nach Kuhn-Tucker existieren dann notwendigerweise λ ∈ Rm undµ ∈ Rn, µ ≤ 0 mit

1.2.

�


Dualitätssatz



(P)−min −c>x

s.d. Ax = bx ≥ 0


1.2.

�


Dualitätssatz



(P)−min −c>x

s.d. Ax = bx ≥ 0

∇f = −c>

∇h = A∇g = −In


1.2.

�


Dualitätssatz



(P)−min −c>x

s.d. Ax = bx ≥ 0

∇f = −c>

∇h = A∇g = −In


1. −c> = λ>A− µ>In2. µ>x = 0

�


Dualitätssatz



(P)−min −c>x

s.d. Ax = bx ≥ 0



1. c> ≤ (−λ>)A2. ((−λ>)A− c>)x = 0

�


Dualitätssatz



(P)−min −c>x

s.d. Ax = bx ≥ 0



1. c> ≤ (−λ>)A2. ((−λ>)A− c>)x = 0 (−λ>)b = (−λ>)Ax = c>x .

�


Dualitätssatz (ausführliche Version)

• Entweder (P) und (D) sind beide zulässig und beschränkt.

Dannhaben Sie den gleichen Zielfunktionswert

• oder (P) ist zulässig und unbeschränkt und (D) ist unzulässig• oder (P) ist unzulässig und (D) ist zulässig und unbeschränkt• oder (P) und (D) sind beide unzulässig.



• Entweder (P) und (D) sind beide zulässig und beschränkt. Dannhaben Sie den gleichen Zielfunktionswert





• oder (P) ist zulässig und unbeschränkt und (D) ist unzulässig

• oder (P) ist unzulässig und (D) ist zulässig und unbeschränkt• oder (P) und (D) sind beide unzulässig.




• oder (P) ist zulässig und unbeschränkt und (D) ist unzulässig• oder (P) ist unzulässig und (D) ist zulässig und unbeschränkt

• oder (P) und (D) sind beide unzulässig.






Dualisieren

Manchmal ist es hilfreich, duale Programme von Problemenaufzustellen, die nicht in Standardform gegeben sind.


Dualisieren


(P) max c>xs.d. Ax ≤ b


Dualisieren


(P)max c>x+ − c>x−

s.d. Ax+ − Ax− + s = bx+, x−, s ≥ 0


Dualisieren



s.d. Ax+ − Ax− + s = bx+, x−, s ≥ 0

(D)

min y>bs.d. y>A ≥ c>

−y>A ≥ −c>

y>A ≥ 0


Dualisieren



s.d. Ax+ − Ax− + s = bx+, x−, s ≥ 0

(D)

min y>bs.d. y>A ≥ c>

−y>A ≥ −c>

y>A ≥ 0

(P) max c>xs.d. Ax ≤ b (D)

min y>bs.d. y>A = c>

y>A ≥ 0


Geometrische Interpretation der Schritte desSimplexalgorithmus

gestrichelt: Zulässigkeitsbereich.

BlauePfeile: Pivotschritte in Phase I.Rote Pfeile: Pivotschritte in Phase II.



gestrichelt: Zulässigkeitsbereich.BlauePfeile: Pivotschritte in Phase I.

Rote Pfeile: Pivotschritte in Phase II.



gestrichelt: Zulässigkeitsbereich.BlauePfeile: Pivotschritte in Phase I.Rote Pfeile: Pivotschritte in Phase II.



gestrichelt: Zulässigkeitsbereich.BlauePfeile: Pivotschritte in Phase I.Rote Pfeile: Pivotschritte in Phase II.


Lösung linearer Programme mit demSimplexalgorithmus

max c>xAx = b (≥ 0)

x ≥ 0

Begriffe:

Basis: Indexmenge von m linear unabhängigen Spalten von A.

Ecke: Zu Basis B gehört eine Ecke xB = A−1.B b, xN = 0.

zulässige Basis: B heißt zulässig, wenn x ≥ 0.

Starte von zulässiger Basis (Ecke) und gehe in Aufstiegsrichtung, solange es möglich ist.




x ≥ 0

Begriffe:

Basis: Indexmenge von m linear unabhängigen Spalten von A.Ecke: Zu Basis B gehört eine Ecke xB = A−1

.B b, xN = 0.

zulässige Basis: B heißt zulässig, wenn x ≥ 0.





x ≥ 0

Begriffe:


.B b, xN = 0.zulässige Basis: B heißt zulässig, wenn x ≥ 0.





x ≥ 0

Begriffe:


.B b, xN = 0.zulässige Basis: B heißt zulässig, wenn x ≥ 0.




Ggb. zulässige Basis B.0 . . . 0 cN − c>B A−1

.B A.N c>B A−1.B b

A−1.B A.B A−1

.B A.N A−1.B b

• Finde Aufstiegsrichtung: cj − c>B A−1.B A.j > 0

• Finde begrenzende Nichtnegativitätsrelation:

i = argmin{ A−1.B b

(A−1.B A)ij

| (A−1.B A)ij > 0}.

• Pivotiere auf (A−1.B A)ij .



Ggb. zulässige Basis B.0 . . . 0 cN − c>B A−1


IB A−1.B A.N A−1

.B b




(A−1.B A)ij

| (A−1.B A)ij > 0}.




Finde Aufstiegsrichtung.0 . . . 0 cN − c>B A−1



.B b




(A−1.B A)ij

| (A−1.B A)ij > 0}.




Finde begrenzende Nichtne-gativitätsrelation.

0 . . . 0 cN − c>B A−1.B A.N c>B A−1

.B b


.B b




(A−1.B A)ij

| (A−1.B A)ij > 0}.




Pivotiere auf (A−1.B A)ij .

0 . . . 0 cN − c>B A−1.B A.N c>B A−1

.B b


.B b




(A−1.B A)ij

| (A−1.B A)ij > 0}.




Falls keine Aufstiegsrichtungexistiert, ist (c>B A−1

.B )A ≥ c.

0 . . . 0 cN − c>B A−1.B A.N c>B A−1

.B b


.B b




(A−1.B A)ij

| (A−1.B A)ij > 0}.




Falls keine Aufstiegsrichtungexistiert, ist (c>B A−1

.B )A ≥ c. Al-so ist c>B A−1

.B zulässig für (D)und c>B A−1

.B b = c>B xB = c>x .

0 . . . 0 cN − c>B A−1.B A.N c>B A−1

.B b


.B b




(A−1.B A)ij

| (A−1.B A)ij > 0}.




Falls es keine begrenzendeNichtnegativitätsrelation gibt,so ist das Problem unbe-schränkt.

0 . . . 0 cN − c>B A−1.B A.N c>B A−1

.B b


.B b




(A−1.B A)ij

| (A−1.B A)ij > 0}.



Phase I

Falls keine zulässige Startbasis bekannt ist, lösen wir mit demSimplexalgorithmus das Hilfsproblem

max −∑

yiAx + y = b

x , y ≥ 0

• Wenn Lösung Zielfunktionswert 0 hat, d.h. alle y = 0, dann kannman künstliche Zeilen streichen und hat zulässige Basis

• ansonsten hat ursprüngliches Problem keine zulässige Lösung


Phase I


max −∑

yiAx + y = b

x , y ≥ 0




Phase I


max −∑

yiAx + y = b

x , y ≥ 0

0 . . . 0 −1 . . .− 1 0

A In b




Phase I


max −∑

yiAx + y = b

x , y ≥ 0

e>A 0 . . . 0 e>b

A In b




Phase I


max −∑

yiAx + y = b

x , y ≥ 0

e>A 0 . . . 0 e>b

A In b




Phase I


max −∑

yiAx + y = b

x , y ≥ 0

e>A 0 . . . 0 e>b

A In b




Beispiel

max x+1 − x−1 + x2

s.d. x+1 − x−1 − x2 − s1 = 3

2x+1 − 2x−1 + x2 + s2 = 8

x+1 , x

−1 , x2, s1, s2 ≥ 0

Wir haben mit s2 schon einen Einheitsvektor, deswegen benötigenwir nur noch eine künstliche Schlupfvariable und erhalten folgendesHilfstableau.


Beispiel

max x+1 − x−1 + x2

s.d. x+1 − x−1 − x2 − s1 = 3

2x+1 − 2x−1 + x2 + s2 = 8

x+1 , x

−1 , x2, s1, s2 ≥ 0



Beispiel

max x+1 − x−1 + x2

s.d. x+1 − x−1 − x2 − s1 = 3

2x+1 − 2x−1 + x2 + s2 = 8

x+1 , x

−1 , x2, s1, s2 ≥ 0


0 0 0 0 0 −1 01 −1 1 0 0 0 01 −1 −1 −1 0 1 32 −2 1 0 1 0 8


Beispiel

max x+1 − x−1 + x2

s.d. x+1 − x−1 − x2 − s1 = 3

2x+1 − 2x−1 + x2 + s2 = 8

x+1 , x

−1 , x2, s1, s2 ≥ 0


1 −1 −1 −1 0 0 31 −1 1 0 0 0 01 −1 −1 −1 0 1 32 −2 1 0 1 0 8


Beispiel

1 −1 −1 −1 0 0 31 −1 1 0 0 0 0

1 −1 −1 −1 0 1 32 −2 1 0 1 0 8

0 0 0 0 0 −1 00 0 2 1 0 −1 −31 −1 −1 −1 0 1 30 0 3 2 1 −2 2

künstlicher Zielfunktionswert ist 0 =⇒ zulässige Basis gefunden

0 0 2 1 0 −31 −1 −1 −1 0 30 0 3 2 1 2


Beispiel

1 −1 −1 −1 0 0 31 −1 1 0 0 0 0

1 −1 −1 −1 0 1 32 −2 1 0 1 0 8

0 0 0 0 0 −1 00 0 2 1 0 −1 −31 −1 −1 −1 0 1 30 0 3 2 1 −2 2


0 0 2 1 0 −31 −1 −1 −1 0 30 0 3 2 1 2


Beispiel

1 −1 −1 −1 0 0 31 −1 1 0 0 0 0

1 −1 −1 −1 0 1 32 −2 1 0 1 0 8

0 0 0 0 0 −1 00 0 2 1 0 −1 −31 −1 −1 −1 0 1 30 0 3 2 1 −2 2


0 0 2 1 0 −31 −1 −1 −1 0 30 0 3 2 1 2


Beispiel

1 −1 −1 −1 0 0 31 −1 1 0 0 0 0

1 −1 −1 −1 0 1 32 −2 1 0 1 0 8

0 0 0 0 0 −1 00 0 2 1 0 −1 −31 −1 −1 −1 0 1 30 0 3 2 1 −2 2


0 0 2 1 0 −31 −1 −1 −1 0 30 0 3 2 1 2


Beispiel

0 0 0 − 13 − 2

3 − 133

1 −1 0 − 13

13

113

0 0 1 23

13

23

Tableau ist final, Optimallösung (x+1 , x

−1 , x2, s1, s2) = ( 11

3 ,0,23 ,0,0),

optimaler Zielfunktionswert = 133

Also ist 13 (11,2) Optimallösung des Ausgangsproblems.


Beispiel

0 0 0 − 13 − 2

3 − 133

1 −1 0 − 13

13

113

0 0 1 23

13

23


−1 , x2, s1, s2) = ( 11

3 ,0,23 ,0,0),




Beispiel

0 0 0 − 13 − 2

3 − 133

1 −1 0 − 13

13

113

0 0 1 23

13

23


−1 , x2, s1, s2) = ( 11

3 ,0,23 ,0,0),




Veranschaulichung der Schritte

1 2 3 4 5 6

1

2

3

4

5

6

7

8