weitere Klausur

Aufgabe 1:
Untersuchen Sie, ob die Funktion f : R2 → R, f (x, y) := −xy + 2x2 + y 2 konvex ist.
Aufgabe 2:
Gegeben sei das lineare Programm

max



s.t.
(LP )




5x1 + 8x2
x1 + x 2 ≤ 8
−x1 + 2x2 ≤ 4
x1 , x2 ≥ 0.
(a) Zeichnen sie den Zulässigkeitsbereich P von (LP). Lesen Sie die Ecken von P aus der
Zeichnung ab.
(b) Formulieren Sie die KKT-Bedingungen für (LP).
(c) Verifizieren Sie (algebraisch) für jede Ecke von P , ob dort die KKT-Bedingungen erfüllt
sind.
Aufgabe 3:
(a) Beweisen Sie: Jedes Polytop ist die konvexe Hülle seiner Ecken.
(b) Beweisen oder widerlegen Sie die Aussage aus (a) für allgemeine Polyeder.
Aufgabe 4:
(a) Beweisen oder widerlegen Sie:
Seien c ∈ Rn , A ∈ Rm×n , b ∈ Rm . Ist ein Problem der Form max{c> x | Ax = b, x ≥ 0}
unbeschränkt, dann gibt es einen Index k, sodass das Problem max{ck xk | Ax = b, x ≥
0} unbeschränkt ist.
(b) Gilt die Umkehrung der Aussage aus (a)?
(D.h. ist das Problem max{c> x | Ax = b, x ≥ 0} beschränkt, dann ist auch das Problem
max{c>
k xk | Ax = b, x ≥ 0} für alle k beschränkt.) Beweisen oder widerlegen Sie dies.
Aufgabe 5:
Eine Intervallmatrix M ∈ {0, 1}m×n ist eine Matrix in der in jeder Zeile alle 1-Einträge
aufeinanderfolgend vorkommen, d.h. für jede Zeile i gilt:
∀j, k, l mit j ≤ k ≤ l : Falls Mij = 1 und Mil = 1, dann ist auch Mik = 1.
Beweisen Sie: Jede Intervallmatrix ist total unimodular.
Hinweis: Benutzen Sie geeignete elementare Spaltenumformungen

Download Report