Prof. Dr. F. Natterer WS 1995/96

Übungen zur Vorlesung NUMERISCHE MATHEMATIK I

Übungsblatt 5 , Abgabe: 28.11.1995 , 11.00 Uhr

Aufgabe 17: (4 Punkte) Sei A eine reelle (m, n)-Matrix, c ∈ IR^{n}, b ∈ IR^{m}. Wir betrachten die Optimierungsaufgaben

Minimiere c^{∗}x in M = {x ∈ IR^{n} : x ≥ 0 , Ax = b} .
Maximiere b^{∗}y in N = {y ∈ IR^{m} : A^{∗}y ≤ c} .
Zeigen Sie : (a) Ist x ∈ M und y ∈ N, so ist b^{∗}y ≤ c^{∗}x.
(b) Gilt in (a) sogar “ = ”, so sind x, y Lösungen der

jeweiligen Probleme.

Aufgabe 18: (4 Punkte) Sei A eine reelle (m, n)-Matrix und b ∈ IR^{m}. Sei

M = {x ∈ IR^{n} : Ax ≤ b} .

Zeigen Sie: x ∈ M ist genau dann Ecke von M, wenn die Zeilen von A, in denen in Ax ≤ b Gleichheit auftritt, einen n-dimensionalen Unterraum aufspannen.

Aufgabe 19: (8 Punkte)

(a) Schreiben Sie ein Programm zur Lösung der Optimierungsaufgabe

Minimiere ∑_{j=m+1}^{m+n} c_{j}x_{j} in M ,

M = {x ∈ IR^{n+m} : x ≥ 0, x_{i} = b_{i} + ∑_{j=m+1}^{m+n} a_{ij}x_{j} , i = 1, …, m} .

Dabei sei b_{i} > 0, i = 1, …, m.

(b) Testen Sie Ihr Programm an dem Beispiel aus §II.2.1.

(c) Bestimmen Sie mit Hilfe des Programms eine nichtnegative Lösung von

x_{1}  − 2x_{3} ≤ 0
x_{1} − 2x_{2}  ≤ 0
−x_{1} + x_{2}  ≤ 0
− 2x_{2} + x_{3} ≤ 0
3x_{1}  ≥ 1
x_{1} + x_{2} + x_{3} = 1

(d) Minimieren Sie

\frac{6}{5}x_{1} + \frac{9}{5}x_{2} + x_{3}

unter den Bedingungen (c) und x_{i} ≥ 0.