View
0
Download
0
Category
Preview:
Citation preview
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
Outline
Lineares Programm (LP) in Standardform
Dualität
Der Simplexalgorithmus
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.
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Umformung in Standardform
max c>xso dass Ax = b
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
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Umformung in Standardform
max c>xso dass Ax = b
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
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Umformung in Standardform
max c>xso dass Ax = b
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
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Umformung in Standardform
max c>xso dass Ax = b
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
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Umformung in Standardform
max c>xso dass Ax = b
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
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Umformung in Standardform
max c>xso dass Ax = b
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
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Umformung in Standardform
max c>xso dass Ax = b
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
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Umformung in Standardform
max c>xso dass Ax = b
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
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Umformung in Standardform
max c>xso dass Ax = b
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
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Umformung in Standardform
max c>xso dass Ax = b
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
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Beispiel
min −x1 − x2s.d. x1 − x2 ≥ 3
2x1 + x2 ≤ 8x2 ≥ 0
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Beispiel
min −x1 − x2s.d. x1 − x2 ≥ 3
2x1 + x2 ≤ 8x2 ≥ 0
−max x1 + x2s.d. x1 − x2 ≥ 3
2x1 + x2 ≤ 8x2 ≥ 0
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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).
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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).
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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).
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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 Zielfunktionswertendlich ist.
Analog definiert man diese Begriffe für (D).
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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).
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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).
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Schwache Dualität
(P)max c>xs.d. Ax = b
x ≥ 0
primales Programm
(D) min y>bs.d. y>A ≥ c>
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 �
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Schwache Dualität
(P)max c>xs.d. Ax = b
x ≥ 0
primales Programm
(D) min y>bs.d. y>A ≥ c>
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 �
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Schwache Dualität
(P)max c>xs.d. Ax = b
x ≥ 0
primales Programm
(D) min y>bs.d. y>A ≥ c>
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 �
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Schwache Dualität
(P)max c>xs.d. Ax = b
x ≥ 0
primales Programm
(D) min y>bs.d. y>A ≥ c>
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 �
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Schwache Dualität
(P)max c>xs.d. Ax = b
x ≥ 0
primales Programm
(D) min y>bs.d. y>A ≥ c>
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 �
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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.
�
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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.
�
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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
∇f = −c>
∇h = A∇g = −In
Nach Kuhn-Tucker existieren dann notwendigerweise λ ∈ Rm undµ ∈ Rn, µ ≤ 0 mit
1.2.
�
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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
∇f = −c>
∇h = A∇g = −In
Nach Kuhn-Tucker existieren dann notwendigerweise λ ∈ Rm undµ ∈ Rn, µ ≤ 0 mit
1. −c> = λ>A− µ>In2. µ>x = 0
�
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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
(D) min y>bs.d. y>A ≥ c>
Nach Kuhn-Tucker existieren dann notwendigerweise λ ∈ Rm undµ ∈ Rn, µ ≤ 0 mit
1. c> ≤ (−λ>)A2. ((−λ>)A− c>)x = 0
�
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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
(D) min y>bs.d. y>A ≥ c>
Nach Kuhn-Tucker existieren dann notwendigerweise λ ∈ Rm undµ ∈ Rn, µ ≤ 0 mit
1. c> ≤ (−λ>)A2. ((−λ>)A− c>)x = 0 (−λ>)b = (−λ>)Ax = c>x .
�
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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.
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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.
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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.
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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.
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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.
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Dualisieren
Manchmal ist es hilfreich, duale Programme von Problemenaufzustellen, die nicht in Standardform gegeben sind.
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Dualisieren
Manchmal ist es hilfreich, duale Programme von Problemenaufzustellen, die nicht in Standardform gegeben sind.
(P) max c>xs.d. Ax ≤ b
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Dualisieren
Manchmal ist es hilfreich, duale Programme von Problemenaufzustellen, die nicht in Standardform gegeben sind.
(P)max c>x+ − c>x−
s.d. Ax+ − Ax− + s = bx+, x−, s ≥ 0
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Dualisieren
Manchmal ist es hilfreich, duale Programme von Problemenaufzustellen, die nicht in Standardform gegeben sind.
(P)max c>x+ − c>x−
s.d. Ax+ − Ax− + s = bx+, x−, s ≥ 0
(D)
min y>bs.d. y>A ≥ c>
−y>A ≥ −c>
y>A ≥ 0
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Dualisieren
Manchmal ist es hilfreich, duale Programme von Problemenaufzustellen, die nicht in Standardform gegeben sind.
(P)max c>x+ − c>x−
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
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Geometrische Interpretation der Schritte desSimplexalgorithmus
gestrichelt: Zulässigkeitsbereich.
BlauePfeile: Pivotschritte in Phase I.Rote Pfeile: Pivotschritte in Phase II.
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Geometrische Interpretation der Schritte desSimplexalgorithmus
gestrichelt: Zulässigkeitsbereich.BlauePfeile: Pivotschritte in Phase I.
Rote Pfeile: Pivotschritte in Phase II.
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Geometrische Interpretation der Schritte desSimplexalgorithmus
gestrichelt: Zulässigkeitsbereich.BlauePfeile: Pivotschritte in Phase I.Rote Pfeile: Pivotschritte in Phase II.
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Geometrische Interpretation der Schritte desSimplexalgorithmus
gestrichelt: Zulässigkeitsbereich.BlauePfeile: Pivotschritte in Phase I.Rote Pfeile: Pivotschritte in Phase II.
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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.
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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.
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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.
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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.
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Der Simplexalgorithmus
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 .
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Der Simplexalgorithmus
Ggb. zulässige Basis B.0 . . . 0 cN − c>B A−1
.B A.N c>B A−1.B b
IB 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 .
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Der Simplexalgorithmus
Finde Aufstiegsrichtung.0 . . . 0 cN − c>B A−1
.B A.N c>B A−1.B b
IB 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 .
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Der Simplexalgorithmus
Finde begrenzende Nichtne-gativitätsrelation.
0 . . . 0 cN − c>B A−1.B A.N c>B A−1
.B b
IB 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 .
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Der Simplexalgorithmus
Pivotiere auf (A−1.B A)ij .
0 . . . 0 cN − c>B A−1.B A.N c>B A−1
.B b
IB 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 .
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Der Simplexalgorithmus
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
IB 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 .
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Der Simplexalgorithmus
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
IB 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 .
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Der Simplexalgorithmus
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
IB 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 .
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Phase I
Falls keine zulässige Startbasis bekannt ist, lösen wir mit demSimplexalgorithmus das Hilfsproblem
max −∑
yiAx + y = b
x , y ≥ 0
0 . . . 0 −1 . . .− 1 0
A In b
• 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
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Phase I
Falls keine zulässige Startbasis bekannt ist, lösen wir mit demSimplexalgorithmus das Hilfsproblem
max −∑
yiAx + y = b
x , y ≥ 0
e>A 0 . . . 0 e>b
A In b
• 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
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Phase I
Falls keine zulässige Startbasis bekannt ist, lösen wir mit demSimplexalgorithmus das Hilfsproblem
max −∑
yiAx + y = b
x , y ≥ 0
e>A 0 . . . 0 e>b
A In b
• 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
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Phase I
Falls keine zulässige Startbasis bekannt ist, lösen wir mit demSimplexalgorithmus das Hilfsproblem
max −∑
yiAx + y = b
x , y ≥ 0
e>A 0 . . . 0 e>b
A In b
• 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
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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.
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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.
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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.
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
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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.
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
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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.
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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.
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
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.
Outline Lineares Programm (LP) in Standardform Dualität Der Simplexalgorithmus
Veranschaulichung der Schritte
1 2 3 4 5 6
1
2
3
4
5
6
7
8
Recommended