Blatt 9 - TU Dortmund

Prof. Dr. Christoph Buchheim
M.Sc. Anna Ilyina
Sommersemester 2016
9. Übung
zur Vorlesung
Optimierung
Abgabe: Dienstag, 21. Juni bis 12 Uhr in den jeweiligen Briefkasten.
Besprechung: Montag, 27. Juni bzw. Dienstag, 28. Juni.
Bitte schreiben Sie die Nummer Ihrer Übungsgruppe auf Ihre Abgaben.
Aufgabe 1 (4 Punkte)
Welche der folgenden Mengen sind Polyeder? Begründen Sie Ihre Entscheidung.
P
P
(a) M1 := {x ∈ Rn | x ≥ 0, 1> x = 1, ni=1 xi ai = b1 , ni=1 xi a2i = b2 }, mit a1 , ..., an , b1 , b2 ∈ R
Hierbei bezeichne 1 den Vektor im Rn , dessen Komponenten alle gleich 1 sind;
(b) M2 := {y1 a1 + y2 a2 | −1 ≤ y1 ≤ 1, −1 ≤ y2 ≤ 1}, mit a1 , a2 ∈ Rn ;
(c) M3 := {x ∈ Rn | x ≥ 0, x> y ≤ 1 für alle y mit ||y||2 = 1}.
Aufgabe 2 (4 Punkte)
Ein Polyeder P (A, b) = {x ∈ Rn : Ax ≤ b} sei durch folgenden Ungleichungen gegeben:
4x1 − 2x2 ≤ 2
−x1 ≤ 1
−x2 ≤ 1
− 12 x1
−
3
2 x2
≤ − 72
x1 + 4x2 ≤ 14
7x1 − 3x2 ≤ 5
x1 ≤ 3
(a) Überführen Sie P (A, b) in ein Polyeder der Form P (D, d) = {x ∈ Rp : Dx = d, x ≥ 0}.
(b) Bestimmen Sie alle nicht-trivialen Seitenflächen von P (A, b), und geben Sie jeweils eine
gültige Ungleichung an, durch welche die Seitenfläche induziert wird.
Aufgabe 3 (4 Punkte)
Sei P ⊆ Rn ein Polytop. Betrachten Sie die Menge P̃ := P × [0, 1]k , also
P̃ = {(x, y) ∈ Rn × Rk | x ∈ P, 0 ≤ y ≤ 1}.
Zeigen Sie:
(a) Die Menge P̃ ist wieder ein Polytop.
P
(b) Jede lineare Ungleichung ni=1 ai xi ≤ b, die gültig für P ist, ist auch gültig für P̃ .
1
(c) Jede lineare Ungleichung
eine Facette von P̃ .
Pn
i=1 ai xi
≤ b, die eine Facette von P induziert, induziert auch
Aufgabe 4 (4 Punkte)
Betrachten Sie das Polyeder P := {x ∈ Rn | a>
i x ≤ bi , i = 1, . . . , m}. In P soll eine Kugel Br
mit Mittelpunkt xc ∈ P und möglichst großem Radius r > 0 eingeschrieben werden, d.h.
Br := {xc + u | ||u||2 ≤ r} ⊂ P.
Formulieren Sie dieses Problem als ein lineares Optimierungsproblem.
Homepage: http://www.mathematik.tu-dortmund.de/lsv/teaching/opt16/index.html
2

Download Report