D. Garbe: Mathematik III für Naturwissenschaftliche Informatik Abgabe: 7. 2. 2003

Übungsblatt 39

Aufgabe 191: Sei min c^{t}x; Ax+Ey = b; e^{t}y+z = 0; x ≥ 0; y ≥ 0; z ≥ 0 das Hilfs-LP zum Standard-LP min c^{t}x; Ax = b; x ≥ 0, wobei e^{t} := (11 … 1) sei. Beweise: Wenn (x′, y′, z′) optimale Lösung des Hilfs-LP ist, so ist x′ optimale Lösung des Standard-LP.

Aufgabe 192: Die Nomenklatur sei wie in Aufgabe 191. Beweise: Wenn das Hilfs-LP unbeschränkt ist, so ist das Standard-LP unbeschränkt.

Aufgabe 193: Löse über Phase I und II :

min 2ξ_{1} + ξ_{2} + 3ξ_{3} − ξ_{4} bezüglich der Restriktionen 2ξ_{1} + 3ξ_{2} − ξ_{3} + ξ_{4} − ξ_{5} = 2, 4ξ_{1} + 6ξ_{2} − 2ξ_{3} + 2ξ_{4} = 4,

⋀_{i=1}^{5} ξ_{i} ≥ 0.

Aufgabe 194: Gib für Ax = b mit A = ( \begin{matrix}1 & 1 & 3 & 4 \\ 3 & 2 & 1 & 1 \\ 2 & 3 & 2 & 3 \end{matrix} ), x ∈ ℝ^{4},

b = ( \begin{matrix}18 \\ 10 \\ 16 \end{matrix} ) alle Basislösungen an. Welche sind zulässig?

Ermittle den optimalen Wert für das durch min 4ξ_{1} −2ξ_{2} +3ξ_{3}, Ax = b, x ≥ 0 bestimmte LP.

Aufgabe 195: Löse das LP max 6ξ_{1} + 10ξ_{2} + 8ξ_{3} + 12ξ_{4} bezüglich

3ξ_{1} + 2ξ_{2} − ξ_{3} + 2ξ_{4} ≤ 60 ,
ξ_{1} + ξ_{2} + 2ξ_{3} + ξ_{4} ≤ 45 ,
2ξ_{1} − 4ξ_{2} − 3ξ_{3} + 4ξ_{4} ≤ 90 ,
4ξ_{1} − 6ξ_{2} + 4ξ_{3} + 3ξ_{4} ≤ 120 ,
ξ_{1} + 2ξ_{2} − 2ξ_{3} + 2ξ_{4} ≤ 30 ,
ξ_{i} ≥ 0 (i = 1, 2, 3, 4) .