Blatt 10 - TU Dortmund

Prof. Dr. Christoph Buchheim
M.Sc. Anna Ilyina
Sommersemester 2016
10. Übung
zur Vorlesung
Optimierung
Abgabe: Dienstag, 28. Juni bis 12 Uhr in den jeweiligen Briefkasten.
Besprechung: Montag, 4. Juli bzw. Dienstag, 5. Juli.
Bitte schreiben Sie die Nummer Ihrer Übungsgruppe auf Ihre Abgaben.
Aufgabe 1 (4 Punkte)
Beweisen Sie, dass die Summe P = P1 + P2 zweier Polyeder P1 , P2 ⊆ Rn wieder ein Polyeder ist.
Aufgabe 2 (4 Punkte)
Gegeben seien die Mengen
X := {x ∈ Rn | xi ∈ [0, 1] ∀i = 1, ..., n} und Y := {x ∈ Rn | xi ∈ [−1, 1], ∀i = 1, ..., n}.
Berechnen Sie explizit die zu X und Y polaren Mengen X ∗ und Y ∗ . Zeichnen Sie die polaren
Mengen für den Fall n = 2.
Aufgabe 3 (4 Punkte)
(a) Betrachten Sie das folgende lineare Programm:
min
s.t.
x1
+ x3
x1 + 2x2
≤5
x2 + 2x3 = 6
x1 , x2 , x3 ≥ 0
Lösen Sie das Problem graphisch. Stellen Sie das dazugehörige duale Problem auf und
verifizieren Sie mithilfe der KKT-Bedingungen die Optimalität Ihrer Lösung.
(b) Gegeben sei das folgende lineare Programm:
min
s.t.
−2x1 + 3x2
−x1 + x2 − x3
3x1 − x2 + x4
x1 , x3
x2 , x4
=
≥
≥
∈
1
8
0
R
Benutzen Sie die schwache Dualität, um eine Optimallösung des Problems zu bestimmen.
1
Aufgabe 4 (4 Punkte)
Ist der Punkt x∗ = (0, 43 , 23 , 35 , 0)> eine Optimallösung des folgenden linearen Programms?
max
s.t.
7x1 + 6x2 + 5x3 − 2x4 + 3x5
x1 + 3x2 + 5x3 − 2x4 + 2x5
4x1 + 2x2 − 2x3 + x4 + x5
2x1 + 4x2 + 4x3 − 2x4 + 5x5
3x1 + x2 + 2x3 − x4 − 2x5
x1 , x2 , x3 , x4 , x5
≤
≤
≤
≤
≥
4
3
5
1
0
Beantworten Sie die Frage mithilfe der KKT-Bedingungen.
Homepage: http://www.mathematik.tu-dortmund.de/lsv/teaching/opt16/index.html
2

Download Report