Blatt 11 - TU Dortmund

Prof. Dr. Christoph Buchheim
M.Sc. Anna Ilyina
Sommersemester 2016
11. Übung
zur Vorlesung
Optimierung
Abgabe: Dienstag, 5. Juli bis 12 Uhr in den jeweiligen Briefkasten.
Besprechung: Montag, 11. Juli bzw. Dienstag, 12. Juli.
Bitte schreiben Sie die Nummer Ihrer Übungsgruppe auf Ihre Abgaben.
Aufgabe 1 (4 Punkte)
Sei A eine schiefsymmetrische n×n-Matrix, d.h. A = −AT . Betrachten Sie das lineare Programm
min cT x
(P )
s.t. Ax ≥ −c
x ≥ 0.
Zeigen Sie:
(a) Das zugehörige duale Problem (D) ist äquivalent zu (P), d.h. eine zulässige Lösung von
(P) ist genau dann optimal für (P), wenn sie optimal für (D) ist.
(b) Falls die zulässige Menge von (P) nichtleer ist, dann besitzt (P) einen Optimierer und der
Zielfunktionswert ist Null.
Aufgabe 2 (4 Punkte)
Betrachtet wird im Folgenden ein Polyeder P = {x ∈ Rn | Ax = b, x ≥ 0} in Standardform.
(a) Beweisen oder widerlegen Sie mittels eines Gegenbeispiels: Seien xB und xB0 Basisvektoren
bzgl. zweier Basen B und B 0 von A. Sind die Basen B und B 0 verschieden, dann sind die
Basisvektoren xB und xB0 verschieden.
(b) Beweisen Sie: Wenn zwei verschiedene Basen existieren, für die derselbe Vektor x der
zugehörige Basisvektor ist, dann sind die beiden Basen degeneriert.
(c) Zeigen oder widerlegen Sie die folgende Umkehrung von (b): Sei B eine degenerierte Basis,
dann existiert eine andere Basis mit demselben zugehörigen Basisvektor.
1
Aufgabe 3 (4 Punkte)
Sei

x1 +2x2




2x1 −x2

2
2x2
P = x∈R 

3x1



x2
≤
≤
≤
≥
≥

4


3

1 .

0



0
(a) Skizzieren Sie P .
(b) Transformieren Sie P in Standardform.
(c) Ermitteln Sie für alle Basen von P den dazugehörigen Basisvektor und stellen Sie fest,
welche davon zulässig sind.
Aufgabe 4 (4 Punkte) Betrachten Sie das folgende lineare Programm (LP):
min
s.t.
x1
+ x3
x1 + 2x2
≤5
x2 + 2x3 = 6
x1 , x2 , x3 ≥ 0
(a) Finden Sie auf beliebigem Weg eine optimale Lösung von (LP).
(b) Stellen Sie das zu (LP) duale Programm (DP) auf.
(c) Beweisen Sie mithilfe der komplementären Schlupfbedingungen die Optimalität Ihrer
Lösung aus (a).
Homepage: http://www.mathematik.tu-dortmund.de/lsv/teaching/opt16/index.html
2

Download Report