Prof. Dr. H. Maurer WS 92

Übungen zur Vorlesung “Optimierung I”

Übungsblatt 1, Abgabe: \underline{23.10.1992}, 11.00 Uhr

Aufgabe 1: (4 Punkte) Ein Fabrikant stellt zwei Sorten Whisky her. Der Gewinn pro Flasche bei Sorte A beträgt 4 DM, bei Sorte B 3 DM. Der Flaschenlieferant kann pro Woche für Sorte A 400, für Sorte B 700 Flaschen liefern. Die Produktionskapazität bei Beschränkung auf eine Sorte beträgt bei Sorte A 500 Flaschen pro Woche, bei Sorte B 1000 Flaschen pro Woche. Unser Whiskyfabrikant hat von der staatlichen Aufsichtsbehörde eine Konzession für die Herstellung von 800 Flaschen Whisky pro Woche bekommen, und er will seinen Gewinn maximieren. Formulieren Sie das lineare Optimierungsproblem und lösen Sie es graphisch.

Aufgabe 2: (4 Punkte) In einer Möbelwerkstatt werden Tische und Stühle hergestellt. 3 Schreiner arbeiten je 8 Stunden pro Tag. Die Einzelteile für die Möbel werden erst zugesägt, dann gehobelt und schließlich zusammengesetzt. Die Säge schafft pro Tag maximal 80 Stühle oder 20 Tische, die Möbelmaschine 90 Tische oder 60 Stühle. Pro Stuhl müssen 7,2 Minuten, pro Tisch 96 Minuten Arbeitszeit aufgebracht werden. Ein Tisch bringt 160 DM Gewinn, ein Stuhl 40 DM.

i) Welchen Gewinn kann die Werkstatt maximal erzielen?

ii) Die Werkstatt möchte maximalen Gewinn machen.

Wieviel komplette Eßgruppen bestehend aus einem Tisch und 4 Stühlen kann sie dabei täglich maximal herstellen?

Aufgabe 3: (3 Punkte) Drei Gase mit den in der folgenden Tabelle angeführten Konstanten sollen so gemischt werden, daß ein möglichst billiges Mischgas mit einem Heizwert H von über 3000kcal/m^{3} und einem Schwefelgehalt S von höchstens 3g/m^{3} entsteht.

Gas-Nr.  1  2  3 Einheit
Preis P_{i}  10 30 20 DM/1000 m^{3}
Heizwert h_{i} 1000 3000 6000 kcal/m^{3}
Schwefel s_{i}  8  1  2 g/m^{3}

Bezeichnen Sie die Mengenanteile der einzelnen Gase pro m^{3} Mischgas mit x_{j} und formulieren Sie das lineare Optimierungsproblem.

Aufgabe 4: (3 Punkte) Bringen Sie das folgende LP auf Standardform:

Minimiere x + |y| + |z|

unter

x + y ≤ 1
2x + 3z = 2
3x + 2y ≥ 1
x ≥ 0

Übungen zur Vorlesung “Optimierung I”

Übungsblatt 2, Abgabe: \underline{30.10.1992}, 11.00 Uhr

Aufgabe 5: (6 Punkte) Beweisen Sie die folgenden Aussagen:

(i) Die konvexe Hülle co(K) einer Teilmenge K ⊂ IR^{n} ist gegeben durch

co(K) = {∑_{i=1}^{k} α_{i}x_{i} | x_{i} ∈ K , α_{i} ≥ 0 , ∑_{i=1}^{k} α_{i} = 1, k ∈ IN}

(ii) Ist K ⊂ IR^{n} konvex und x ∈K^{∘}, y ∈ \overline{K}, so gilt

(1 − α)x + αy ∈K^{∘} für 0 ≤ α < 1 .

(iii) Für eine konvexe Menge K mit K^{∘}≠ ∅ gilt int \overline{K} = intK.

Aufgabe 6: (5 Punkte) Beweisen Sie die folgenden Aussagen über konvexe Kegel:

(i) Eine Teilmenge K ⊂ IR^{n} ist genau dann ein konvexer Kegel, wenn gilt

αK + βK ⊂ K für alle α, β ≥ 0 .

(ii) Ist K ⊂ IR^{n} ein konvexer Kegel und x ∈ K, so ist die konische Hülle von K bzgl. x gegeben durch

K(x) = K + IRx = {y + αx | y ∈ K , α ∈ IR} .

Für K = IR_{−}^{n} gilt insbesondere

K(x) = {y ∈ IR^{n} | y_{i} ≤ 0 , falls x_{i} = 0, i = 1, …, n} .

Aufgabe 7: (3 Punkte) Seien K_{1}, K_{2} ⊂ IR^{n} konvexe Mengen mit K_{1} ∩ K_{2} = ∅. Zeigen Sie, daß K_{1} und K_{2} trennbar sind. \underline{Hinweis:} Betrachten Sie K_{1} − K_{2} = \{y − x | y ∈ K_{1}, x ∈ K_{2}\}.

Aufgabe 8: (5 Punkte) Beweisen Sie den \underline{Satz von CARATHEODORY:} Sei K ⊂ IR^{n}. Dann gibt es zu x ∈ co(K) bereits n + 1 Punkte x_{1}, …, x_{n+1} ∈ K und Zahlen α_{1}, …, α_{n+1} ≥ 0, mit

x = ∑_{k=1}^{n+1} α_{k}x_{k} , ∑_{k=1}^{n+1} α_{k} = 1 .

\underline{Hinweise:} Zu x ∈ co(K) gibt es m ∈ IN, x_{1}, …, x_{m} ∈ K, α_{i} ≥ 0, mit

x = α_{1}x_{1} + … + α_{m}x_{m} , α_{1} + … + α_{m} = 1 .

Sei m > n + 1 und betrachten Sie die linear \underline{abhängigen} Punkte y_{k} := x_{k} − x_{m}, k = 1, …, m−1. Stellen Sie dann x als konvexe Kombination von m−1 Punkten der x_{k} dar.

Übungen zur Vorlesung “Optimierung I”

Übungsblatt 3, Abgabe: \underline{06.11.1992}, 11.00 Uhr

Aufgabe 9: (2 Punkte) Zeigen Sie: Es gibt keine Lösung des LGS x ∈ IR^{3}, x ≥ 0,

( \begin{matrix}2 & 6 & −10 \\ 2 & −8 & −14 \end{matrix} ) x = ( \begin{matrix}4 \\ 6 \end{matrix} ) (in IR^{+})

Aufgabe 10: (4 Punkte) Eine Firma stellt Gefriertruhen und Kühlschränke her. Bei der Herstellung muß folgendes beachtet werden:

a.) Die Abteilung, die die Gehäuse herstellt, kann in einem Monat höchstens 1000 Gehäuse fertigstellen.

b.) Die Montageabteilung für Gefriertruhen kann in einem Monat höchstens 600 Gefriertruhen montieren.

c.) Die Montageabteilung fΔr Kühlschränke kann in einem Monat höchstens 800 Kühlschränke montieren.

d.) Die Abteilung fΔr die elektrische Installation kann in einem Monat höchstens 800 Gefriertruhen oder 1200 Kühlschränke oder eine entsprechende lineare Kombination im Monat herstellen.

Der Gewinn bei einer Gefriertruhe beträgt 360DM, bei einem Kühlschrank 270DM. Formulieren Sie das zugehörige LP als Standardproblem. Bestimmen Sie sämtliche Ecken der zulässigen Menge und berechnen Sie die optimale Ecke.

Aufgabe 11: (3 Punkte) Zeige: Der Punkt x = (0, 4, 1, 0, 6)^{T} ist eine Lösung des LP maximiere (0, 1, −4, 0, 2)x unter

( \begin{matrix}2 & −2 & −2 & −2 & 0 \\ 2 & 1 & −1 & 1 & 1 \\ 2 & 2 & 0 & 2 & −1 \end{matrix} ) x = ( \begin{matrix}−10 \\ 9 \\ 2 \end{matrix} )

x ≥ 0.

Aufgabe 12: (3 Punkte) Zeigen Sie, daß das LP

maximiere (1, 3, −10, 2, −4)x

unter

( \begin{matrix}−2 & 2 & −10 & 0 & −2 \\ 4 & 0 & 0 & 2 & −2 \end{matrix} ) x = ( \begin{matrix}2 \\ 4 \end{matrix} )

keine Lösung besitzt.

Aufgabe 13: (3 Punkte) Man gebe ein Beispiel an, in dem eine entartete Basis-Lösung optimal ist, ohne daß die Bedingung r_{N} ≤ 0 erfüllt ist.

Übungen zur Vorlesung “Optimierung I”

Übungsblatt 4, Abgabe: \underline{13.11.1992}, 11.00 Uhr

Aufgabe 14: (4 Punkte) Lösen Sie mit dem Simplex-Verfahren das folgende LP

maximiere z(x) = 3x_{1} + x_{2} + 3x_{3}
unter  2x_{1} + x_{2} + x_{3} ≤ 2
x_{1} + 2x_{2} + 3x_{3} ≤ 5
2x_{1} + 2x_{2} + x_{3} ≤ 6
x_{1}, x_{2}, x_{3} ≥ 0

Aufgabe 15: (4 Punkte) Der Barkeeper Ihrer Stammkneipe bittet Sie um Ihre Mithilfe: Er hat folgendes Flaschensortiment auf Lager:

1 quart (32oz.) Old Cambridge (guter Whiskey - Kosten: 8$/quart)
1 quart Joy Juice (ein weiterer guter Whiskey - Kosten: 10$/quart)
1 quart Ma’s Wicked Vermouth (10$/quart)
2 quarts Gil-boy’s Gin (6$/quart)

Da er neu in seinem Metier ist, kann er nur die folgenden Drinks herstellen:

Whiskey Sour 2oz.Whiskey Preis 1$
Manhattan  2oz.Whiskey Preis 2$

1oz.Vermouth

Martini 2oz.Gin Preis 2$

1oz.Vermouth

Pub Special 2oz.Gin  Preis 3$

2oz.Whiskey

Maximieren Sie den Profit der Bar mit Hilfe des Simplex-Verfahrens. (Sind die Kosten fΔr die Flaschen in dieser Formulierung zu beachten?)

Aufgabe 16: (4 Punkte) Sei A = (a_{ij}) eine m×n Matrix. Für die Basis B = (i_{1}, …, i_{m}) gelte A_{B} = I und a_{i_{p}j_{s}} ≠ 0 für ein i_{p} ∈ B, j_{s} ∈ N. Erzeugen Sie mittels elementarer Zeilenoperationen den Einheitsvektor e_{i_{p}} in Spalte j_{s}. Wie lauten die Elemente der neuen Matrix A′ = (a_{ij})? Machen Sie sich die Transformationen anhand der Basis B = (1, …, m) klar.

Aufgabe 17: (Programmieraufgabe) Schreiben Sie ein Programm zum Simplex-Verfahren auf Seite 4.19 ff. Testen Sie die Korrektheit Ihres Programmes an dem LP aus Aufgabe 14. Lösen Sie das folgende LP, bei dem die Herstellung von 8 Produkten aus 11 Rohstoffen optimiert wird:

max {cx | Ax ≤ b, x ≥ 0} mit

\begin{aligned}c & = & (15, 15, 30, 20, 20, 40, 25, 18) \\ b & = & (150, 250, 100, 300, 200, 400, 500, 550, 350, 385, 200)^{T} \end{aligned}

A = ( \begin{matrix}0.2 & 0.1 & 2 & 0 & 0 & 1.5 & 2 & 0 \\ 1 & 0 & 1 & 0 & 0 & 2 & 3 & 1 \\ 0 & 1.2 & 1 & 0.5 & 0.4 & 3 & 3 & 1 \\ 0.5 & 0.4 & 1.5 & 1 & 1.5 & 3.2 & 1 & 0 \\ 0.3 & 0 & 0.5 & 1 & 1.4 & 4 & 1 & 0 \\ 0 & 0.9 & 0 & 2 & 1.5 & 4 & 0 & 2 \\ 1.5 & 1.2 & 1.1 & 1.3 & 2 & 1.5 & 1 & 1 \\ 0 & 0 & 0.7 & 1.5 & 2 & 0 & 0.5 & 0 \\ 0.7 & 0.6 & 0.5 & 2.5 & 2 & 0 & 0.2 & 0 \\ 0.5 & 0 & 2 & 1.5 & 3 & 0 & 0 & 5 \\ 0.4 & 0.5 & 0.5 & 1 & 1 & 0 & 0 & 2 \end{matrix} )

Berechnen Sie die optimale Lˇ sung mit Ihrem Programm und lassen Sie das optimale Tableau ausdrucken. Der Zielfunktionswert ist z = 6289.28.

Übungen zur Vorlesung “Optimierung I”

Übungsblatt 5, Abgabe: \underline{20.11.1992}, 11.00 Uhr

Aufgabe 18: (5 Punkte) Lˇ sen Sie das LP maximiere \frac{3}{4}x_{1} − 150x_{2} + \frac{1}{50}x_{3} − 6x_{4} unter

\frac{1}{4}x_{1} − 60x_{2} − \frac{1}{25}x_{3} + 9x_{4} ≤ 0
\frac{1}{2}x_{1} − 90x_{2} − \frac{1}{5}x_{3} + 3x_{4} ≤ 0
x_{3} ≤ 1
x ≥ 0, x ∈ IR^{4}

mit dem Simplex-Verfahren und der lexikographischen Zeilenauswahlregel (4.23).

Aufgabe 19: (4 Punkte) Berechnen Sie mit der Zweiphasenmethode die Lösung des LP

minimiere z(x) = 2x_{1} − 3x_{2}
unter  2x_{1} − x_{2} − x_{3} = 3
x_{1} + x_{2} + x_{3} = 2
x_{i} ≥ 0 , i = 1, 2, 3 .

Aufgabe 20: (4 Punkte) Prüfen Sie nach, ob das System

x_{1} + 2x_{3} − 2x_{4} + 3x_{5} ≤ 60,
x_{1} + 3x_{2} + x_{3} + x_{5} = 12,
x_{2} + x_{3} + x_{4}  = 10,
2x_{1} + 2x_{3}  ≥ 30,
x ≥ 0,

eine Lösung besitzt.

Aufgabe 21: (Programmieraufgabe) Benutzen Sie Ihr Programm zum Simplex-Verfahren und berechnen Sie die Lösung des folgenden LP mit der Zweiphasenmethode: Eine Öl-Raffinerie möchte aus Roh-Öl verschiedene Produkte herstellen und dabei die Produktionskosten ($)

z(x) = 16.5x_{1} + 5.25x_{3} + 5.25x_{4} + 3x_{13} , x ∈ IR^{16}

minimieren unter den folgenden Restriktionen

(a)

Höchstgrenze für Roh-Öl:

x_{1} ≤ 750 000

(b)

Massen-Bilanz der Komponenten:

0.178x_{1} − x_{2} − x_{3}  = 0
0.048x_{1} − x_{4} − x_{5} − x_{6} = 0
0.069x_{1} − x_{7} − x_{8} − x_{9} = 0
0.184x_{1} − x_{10} − x_{11} − x_{12} = 0
0.241x_{1} − x_{13} − x_{14}  = 0
0.266x_{1} − x_{15} − x_{16}  = 0

(c)

Produktions-Anforderungen:

\begin{aligned}x_{2} + 0.865x_{3} + 0.85x_{4} + 0.373x_{13} & = & 124 400 \\ x_{5} + x_{7} + x_{10} & = & 18 800 \\ x_{8} + x_{11} + x_{16} & = & 90 700 \\ x_{6} + x_{9} + x_{12} + 0.331x_{13} + x_{14} + x_{15} & = & 291 600 \end{aligned}

(d)

Qualitäts-Anforderungen:

\begin{aligned}15x_{2} − 6.75x_{3} − 8.5x_{4} − 5.97x_{13} & ≤ & 0 \\ 10x_{8} + 10x_{11} − 90x_{16} & ≤ & 0 \\ −25.7x_{6} − 25.7x_{9} − 16.1x_{12} − 4.4x_{13} − 5.1x_{14} & ≤ & 0 \end{aligned}

Übungen zur Vorlesung “Optimierung I”

Übungsblatt 6, Abgabe: \underline{27.11.1992}, 11.00 Uhr

Aufgabe 22: (4+3 Punkte) Gegeben sei das folgende LP mit den beiden freien Variablen x_{1}, x_{2}:

maximiere z(x) = −3x_{1} + 2x_{2} − x_{3} + 4x_{4}
unter  x_{1} + x_{2} − 4x_{3} + 2x_{4} ≥ 4
−3x_{1} + x_{2} − 2x_{3}  ≤ 6
x_{2}  −x_{4} = −1
x_{1} + x_{2} − x_{3}  = 0
x_{3}, x_{4} ≥ 0

(a) Eliminieren Sie die Variablen x_{1}, x_{2} und berechnen Sie die Lösung

(1) auf graphischem Wege.

(2) mit der Zweiphasen-Methode.

(b) Substituieren Sie x_{i} = u_{i} − v_{i}, u_{i} = x_{i}^{+}, v_{i} = x_{i}^{−} (i = 1, 2) und lösen Sie das resultierende LP mit der Zweiphasen-Methode.

Aufgabe 23: (2 Punkte) Mit den Bezeichnungen von S6 seien die Basen B = (1, …, m), \overline{B} = (1, …, p − 1, s, p + 1, …, m) gegeben. Für die m × m Matrix S mit

Se_{i} = e_{i} (i ≠ p) , Sã_{s} = e_{p}

zeige man

A−1 ; \overline{B} = SA_{B}^{−1} .

Aufgabe 24: (4 Punkte) Lösen Sie mit Hilfe des revidierten Simplexverfahrens das Problem

Maximiere 3x_{1} + x_{2} + 3x_{3}
unter  2x_{1} + x_{2} + x_{3} ≤ 2
x_{1} + 2x_{2} + 3x_{3} ≤ 5
2x_{1} + 2x_{2} + x_{3} ≤ 6
x_{i} ≥ 0  = 1, 2, 3 .

Übungen zur Vorlesung “Optimierung I”

Übungsblatt 7, Abgabe: \underline{04.12.1992}, 11.00 Uhr

Aufgabe 25: (5 Punkte)

(a) Zeigen Sie: Das duale Problem zum dualen Problem ist das primale Problem.

(b) Berechnen Sie das duale Programm zu

min {c_{1}x_{1} + c_{2}x_{2} | A_{11}x_{1} + A_{12}x_{2} ≥ b_{1} ,
A_{21}x_{1} + A_{22}x_{2} = b_{2} , x_{1} ≥ 0}

mit Vektoren x_{1}, x_{2} und Matrizen A_{11}, A_{12}, A_{21}, A_{22} passender Dimension.

Aufgabe 26: (3 Punkte) Berechnen Sie mit dualen Simplex-Verfahren die Lösung des LP

minimiere 10x_{1} + 15x_{2} + 20x_{3}
unter  2x_{1} + x_{2} ≥ 2
−x_{1} + 2x_{3} ≥ −3
3x_{2} − 2x_{3} ≥ 5
x ≥ 0

Aufgabe 27: (5 Punkte) Ein Nikolaus hat Lakritzstangen der Länge 20 cm auf Lager. Zur Bescherung benötigt er

mindestens 4000 Lakritzstangen der Länge 9 cm,
mindestens 5000 Lakritzstangen der Länge 8 cm,
mindestens 3000 Lakritzstangen der Länge 6 cm .

Wie muŒ der Nikolaus die 20 cm langen Lakritzstangen zuschneiden, damit der Abfall möglichst gering wird? \underline{Hinweis:} Es gibt 6 Strategien (Begründung), die 20 cm langen Stangen zuzuschneiden. Setzen Sie x = (x_{1}, …, x_{6})^{T}, wobei x_{i} die Anzahl der Stangen ist, die nach Strategie i zugeschnitten werden. Lösen Sie das Problem mit dem dualen Simplex-Verfahren.

\underline{b.w.} Aufgabe 28: (Programmieraufgabe) Programmieren Sie das duale Simplex-Verfahren (7.12). Testen Sie Ihr Programm an den folgenden beiden LP‘s:

(a) Fünf Metallteile sollen aus einheitlichen Blechtafeln geschnitten werden. Hierzu gibt es 10 Schnittpläne. Das Problem, bei vorgegebener Mindestzahl für jedes der fünf Metallteile möglichst wenig Blechtafeln zu verbrauchen, führt auf das folgende LP:

min {cx | Ax ≥ b, x ≥ 0}

mit

\begin{aligned}c & = & (1, 1, 1, 1, 1, 1, 1, 1, 1, 1) ∈ IR^{10} \\ b & = & (600, 350, 475, 700, 850)^{T} ∈ IR^{5} \\ A & = & ( \begin{matrix}2 & 3 & 0 & 2 & 0 & 0 & 3 & 4 & 2 & 0 \\ 1 & 2 & 5 & 6 & 3 & 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 4 & 0 & 5 & 7 & 1 & 0 & 0 & 7 \\ 1 & 0 & 3 & 4 & 0 & 2 & 0 & 7 & 6 & 3 \\ 8 & 6 & 2 & 1 & 2 & 1 & 5 & 3 & 5 & 2 \end{matrix} ) \end{aligned}

Der optimale Zielfunktionswert beträgt: z = 241.147

(b) Beim Einsatz verschiedener Technologien zur Herstellung zweier Produkte sollen die Kosten minimiert werden:

minimiere 3x_{1} + 2x_{2} + 4x_{3} + 8x_{4} + 7x_{5} + 5x_{6}

unter

2x_{1} + 2x_{2} + x_{3} + 3x_{4} + 6x_{5} + 8x_{6} ≤ 30
4x_{1} + 3x_{2} + 4x_{3} + 5x_{4} + 8x_{5} + 9x_{6} ≤ 35
x_{1} + 2x_{2} + x_{3} + 2x_{4} + 5x_{5} + 5x_{6} ≤ 35
3x_{1} + 2x_{2} + 4x_{3} + 4x_{4} + 7x_{5} + 9x_{6} ≤ 30
x_{1} + x_{2} + x_{3}  ≥ 5
x_{4} + x_{5} + x_{6} ≥ 2
x ≥ 0

Abgabe von Aufgabe 28: 11.12.92, 8^{15}.

Prof. Dr. H. Maurer WS 92

Übungen zur Vorlesung “Optimierung I”

Übungsblatt 8, Abgabe: \underline{11.12.1992}, 11.00 Uhr

∗Aufgabe 29: (6 Punkte) Bei der Lösung des Problems (P) min {cx | Ax ≥ b, x ≥ 0} , c ≥ 0 mit dem dualen Simplex-Verfahren löst man

(P_{1})  min {cx | − Ax + y = −b, x ≥ 0, y ≥ 0}

vom “dualen Standpunkt”. Die optimale Lösung sei nicht entartet. \underline{Zeigen Sie:} Die optimale Lösung λ des dualen Problems

(P^{∗})  max {λb | λA ≤ c, λ ≥ 0}

erhält man aus dem optimalen Tableau folgendermaŒen:

(a) y_{j} Basis-Variable ⇒ λ_{j} = 0,

(b) y_{j} Nicht-Basis-Variable ⇒ λ_{j} = −r_{k_{j}}, r_{k_{j}} ist der unter y_{j} stehende Koeffizient. \underline{Hinweis:} Zeigen Sie, daß zwischen der Lösung λ^{∼} des dualen Problems von (P_{1}) und der Lösung λ von (P^{∗}) die Beziehung λ = − λ^{∼} gilt.

(c) Überprüfen Sie die Aussage in (a) und (b) an der Lösung des LP min{x_{1} + x_{2} | 2x_{1} + x_{2} ≥ 12, 5x_{1} + 8x_{2} ≥ 74, x_{1} + 6x_{2} ≥ 28, x ≥ 0}

Aufgabe 30: (5 Punkte) Lösen Sie das LP

minimiere  4x_{2} − 3x_{3} − 2x_{4} + 8x_{5}
unter 3x_{1} + x_{2} + 2x_{3} + x_{4} = 3
x_{1} − x_{2}  + x_{4} − x_{5} ≥ 2
x ≥ 0

folgendermaßen:

(1) Bestimmen Sie das duale LP und lösen Sie es graphisch.

(2) Bestimmen Sie mittels der dualen Lösung diejenigen primalen Variablen, welche den Wert Null in der optimalen Lösung haben.

\underline{Hinweis:} Komplementarität, Sätze (7.7), (7.8).

(3) Berechnen Sie die optimale primale Lösung.

Aufgabe 31: (5 Punkte) Lˇ sen Sie das LP

Maximiere  x_{1} + 2x_{2} + x_{3} + 3x_{4} + x_{5}
unter  x_{1} + x_{2}  + x_{4}  ≤ 6,
x_{1}  + x_{4}  ≥ 1,
− 2x_{1}  + x_{3} − x_{4} + 2x_{5} ≥ 4,
x_{2} + 2x_{3}  + 2x_{5} = 11,
x_{1} + x_{2}  + x_{4} + x_{5} = 6,
x ≥ 0,

mit der Dreiphasenmethode. Der optimale Wert ist z_{0} = 16\frac{3}{4}.

Prof. Dr. H. Maurer WS 92

Übungen zur Vorlesung “Optimierung I”

Übungsblatt 9, Abgabe: \underline{18.12.1992}, 11.00 Uhr

Aufgabe 32: (3 Punkte) Sei w : IR^{k} → \overline{IR} die Optimalwert-Funktion des parametrischen LP P (t) min{c(t)x | Ax = b , x ≥ 0} , t ∈ IR^{k}, mit einer affin-linearen Funktion c : IR^{k} → IR^{n}. Zeigen Sie:

(a) Die Menge D = {t ∈ IR^{k} | w(t) ∈ IR} ist konvex.

(b) Die Funktion w : D → IR ist konkav.

Aufgabe 33: (4 Punkte) Ein Produktionsmodell führt auf das LP

maximiere 5x_{1} + 4.5x_{2} + 6x_{3}
unter  6x_{1} + 5x_{2} + 8x_{3} ≤ 60
10x_{1} + 20x_{2} + 10x_{3} ≤ 150
x ≥ 0

Die optimale Lösung ist x_{1} = 45/7, x_{2} = 30/7, x_{3} = 0, z_{0} = 51\frac{3}{7} zur Basis B = (1, 2). Die zweite Produktionsbeschränkung werde parametrisiert durch

10x_{1} + 20x_{2} + 10x_{3} ≤ 150 + t , t ∈ IR .

Für welche Werte t ist die Basis B = (1, 2) optimal? Berechnen Sie x_{B}(t).

Aufgabe 34: (4+4 Punkte) Das Produktionsmodell

maximiere z = 6x_{1} + 14x_{2} + 13x_{3}
unter  0.5x_{1} + 2x_{2} + x_{3} ≤ 24
x_{1} + 2x_{2} + 4x_{3} ≤ 60
x_{1} , x_{2} , x_{3} ≥ 0

hat die optimale Lösung x_{1} = 36, x_{2} = 0, x_{3} = 6 mit Basis B = (1, 3).

(a) Bestimmen Sie die optimalen Lösungen zu dem parametrischen Zielfunktional

z = (6 + t)x_{1} + (14 + 2t)x_{2} + (13 + 2t)x_{3}

für alle t ∈ IR. Skizzieren Sie die Optimalwert - Funktion w : IR → \overline{IR}.

(b) Berechnen Sie die optimalen Lösungen zur parametrischen rechten Seite

b(t) = ( \begin{matrix}24 + t \\ 60 − t \end{matrix} )

für alle t ∈ IR. Skizzieren Sie die Optimalwert - Funktion w : IR → \overline{IR}.

Übungen zur Vorlesung “Optimierung I”

Übungsblatt 10, Abgabe: \underline{15.01.1993}, 11.00 Uhr

Aufgabe 35: (5 Punkte) Berechnen Sie für alle ε ∈ IR die Minimalstelle x = x(ε) des Optimierungsproblems

min f(x, ε) , x ∈ IR^{n} (ε ∈ IR)

für die in (a) und (b) angegebenen Funktionen f(x, ε). Berechnen Sie jeweils dx(ε)/dε

(1) auf explizite Weise,
(2) nach Satz (1.7) (4), Kap. III .

(a) f(x, ε) = x^{3} − εx

(b) f(x, ε) = x_{1}^{2} + εx_{2}^{2} − εx_{1}x_{2} + x_{2} Überprüfen Sie den Fall ε = 2 explizit.

Aufgabe 36: (4 Punkte) Bestimmen Sie die optimale Lösung \overline{x} ∈ IR^{2} des Optimierungsproblems

maximiere exp [(x_{1} − 1)^{2} + (x_{2} − 2)^{2}]
unter  x_{2}^{2} ≤ x_{1} , e^{−x_{1}} ≤ x_{2} , 2(x_{1} − 1)^{2} ≤ x_{2}

auf grafischem Wege. Reduzieren Sie das nichtlineare Gleichungssystem für \overline{x} auf ein Iterationsverfahren in IR und berechnen Sie \overline{x} numerisch auf 5 Dezimalen.

Aufgabe 37: (6 Punkte)

(a) Seien f : IR^{n} × IR^{k} → IR und g : IR^{n} × IR^{k} → IR^{n} C^{1}-Abbildungen mit det(g_{x}(x, y)) ≠ 0 für (x, y) ∈ IR^{n} × IR^{k}. Sei (\overline{x}, \overline{y}) ∈ IR^{n} × IR^{k} optimal für das Optimierungsproblem

\begin{matrix}min \\ (x, y) ∈ IR^{n} × IR^{k} \end{matrix} \{f(x, y) | g(x, y) = 0\} .

\underline{Zeigen Sie:} Es gibt einen Zeilenvektor \overline{λ} ∈ IR^{n}, so daß die Multiplikatorenregel von LAGRANGE gilt:

(∗) f_{x}(\overline{x}, \overline{y}) + \overline{λ}g_{x}(\overline{x}, \overline{y}) = 0, f_{y}(\overline{x}, \overline{y}) + \overline{λ}g_{y}(\overline{x}, \overline{y}) = 0 .

\underline{Hinweis:} Wenden Sie den Satz (1.6) über Implizite Funktionen an und betrachten Sie ein geeignetes Optimierungsproblem in der Variablen y.

(b) Lösen Sie das Optimierungsproblem

min \{\frac{1}{2} (\frac{x^{2}}{a^{2}} + \frac{y^{2}}{b^{2}} ) | xy = c\} , c > 0 ,

grafisch und analytisch. Bestimmen Sie den Multiplikator \overline{λ} in (*).

Aufgabe 38: (3 Punkte) Zeigen Sie, daß der Tangentialkegel T (S, \overline{x}) einer Menge S im Punkte \overline{x} ∈ S ein abgeschlossener Kegel ist.

Wir wünschen allen Übungsteilnehmern ein frohes Weihnachtsfest und ein gutes Neues Jahr

Übungen zur Vorlesung “Optimierung I”

Übungsblatt 11, Abgabe: \underline{22.01.1993}, 11.00 Uhr

Aufgabe 39: (3+2 Punkte) Seien f : IR^{n} → IR differenzierbar, K ⊂ IR^{n} konvex, A eine m × n-Matrix und b ∈ IR^{m}.

(a) Zeigen Sie:

T (K, \overline{x}) = cℓK(\overline{x}) .

Berechnen Sie T (K, \overline{x}) und L(S, \overline{x}) im Falle K = \{x ∈ IR^{n} | Ax = b\}.

(b) Beweisen Sie: Ist \overline{x} eine lokale Minimalstelle des Problems

min {f(x) | Ax = b} ,

so gibt es λ ∈ IR^{m} mit f′(\overline{x}) + λA = 0.

\underline{Hinweis:} Benutzen sie Satz (3.5) und (a).

Aufgabe 40: (1+3 Punkte) Die Mengen S_{α} seien gegeben durch

S_{α} = {x ∈ IR^{2} | x_{2} − x_{1}^{α} ≤ 0, −x_{2} − x_{1}^{α} ≤ 0} , α ≥ 1.

(a) Skizzieren Sie S_{α} fΔr α ≥ 1.

(b) Berechnen Sie die Kegel T (S_{α}, \overline{x}) und L(S_{α}, \overline{x}) fΔr \overline{x} = (0, 0)^{T}, α ≥ 1. FΔr welche α ≥ 1 ist \overline{x} regulΞr?

Aufgabe 41: (5 Punkte) Ein Investor hat 5000 DM zur Verfügung, die er in zwei Objekte investieren kann. Mit x_{i} (i = 1, 2) sei der Anteil (in 1000 DM), den er in Objekt i investiert, bezeichnet. Objekt 1 bzw. 2 erbringt einen jährlichen Gewinn von 20% bzw. 16%. Das Risiko bei Investition in Objekt 1 und 2 wird durch die Varianz des Gewinns gemessen und beträgt 2x_{1}^{2} + x_{2}^{2} + (x_{1} + x_{2})^{2}. Der Investor möchte seinen Gewinn maximieren und sein Risiko minimieren. Mit einem Wichtungsfaktor α > 0 löst er das Optimierungsproblem

minimiere α(2x_{1}^{2} + x_{2}^{2} + (x_{1} + x_{2})^{2}) − 20x_{1} − 16x_{2}
unter  x_{1} + x_{2} ≤ 5 , x_{1}, x_{2} ≥ 0 .

Berechnen Sie für alle α > 0 die optimale Lösung x(α) ∈ IR^{2}. Bestimmen Sie zunächst die unbeschränkte Lösung und skizzieren Sie das Problem graphisch.

Aufgabe 42: (3 Punkte) Bestimmen Sie auf der Fläche S = {(x, y, z) ∈ IR^{3} | z − xy − 5 = 0} die Punkte kleinster euklidischer Norm.

Übungen zur Vorlesung “Optimierung I”

Übungsblatt 12, Abgabe: \underline{29.01.1993}, 11.00 Uhr

Aufgabe 43: (2+3+3 Punkte) Ein “Allokationsproblem” führt auf ein separables Optimierungsproblem der Form

min{ ∑_{k=1}^{n} f_{k}(x_{k}) | ∑_{k=1}^{n} a_{k}x_{k} = b , x_{k} ≥ 0}

mit C^{1}-Funktionen f_{k} : [0, ∞) → IR und Konstanten a_{k} > 0, b > 0.

(a) Diskutieren Sie die KUHN-TUCKER Bedingungen.

(b) Berechnen Sie die optimale Lösung \overline{x} ∈ IR_{+}^{n} und den LAGRANGE - Multiplikator \overline{λ} ∈ IR für den Fall

f_{k}(x) = c_{k}x + \frac{d_{k}}{x} , x > 0 , c_{k} > 0 , d_{k} > 0 .

Zeigen Sie dazu, daß \overline{λ} die Nullstelle einer nichtlinearen Gleichung ist. Bestimmen Sie \overline{λ} explizit im Falle c_{k} = ca_{k} (k = 1, …, n), c > 0.

(c) Bestimmen Sie für n = 2 und n = 3 die optimale Lösung im Falle

f_{k}(x) = ℓn (kx + \frac{1}{k} ) , x ≥ 0 , a_{k} = 1 , b = 1 .

Aufgabe 44: (3 Punkte) Für das Optimierungsproblem

max{x + 3y + 20z | x^{2} + 3y^{2} − 20z^{2} + c^{2} = 0} , c > 0 ,

bestimme man

(a) sämtliche Punkte (x, y, z, λ), die den Bedingungen von KUHN-TUCKER genügen.

(b) die lokale Maximalstelle.

Aufgabe 45: (5 Punkte) Mit x_{1}, …, x_{n} ∈ IR^{n} sei das Problem

maximiere f(x_{1}, …, x_{n}) = det(x_{i}^{T} x_{j})_{i,j=1,...,n}

unter

g(x_{1}, …, x_{n}) = ( x_{1}^{T} x_{1} − 1 ; ⋮ ; x_{n}^{T}x_{n} − 1 ) = O ∈ IR^{n}

zu lösen.

(a) Zeigen Sie: Es gibt eine globale Maximalstelle \overline{x} = (\overline{x}_{1}, …, \overline{x}_{n}) ∈ IR^{n·n} des Problems mit (1) f(\overline{x}) = 1, (2) \{\overline{x}_{1}, …, \overline{x}_{n}\} ist ONS.

\underline{Hinweis:} Berechnen Sie f′(\overline{x})v + λg′(\overline{x})v für v ∈ IR^{n·n}.

(b) Folgern Sie aus (a) die HADAMARD’sche Determinantenungleichung

| det(x_{i}^{T} x_{j})| ≤ ∏_{i=1}^{n} x_{i}^{T} x_{i} für alle (x_{1}, …, x_{n}) ∈ IR^{n·n} .

Prof. Dr. H. Maurer WS 92

Übungen zur Vorlesung “Optimierung I”

Übungsblatt 0, Abgabe: \underline{Februar 1993}, 11.00 Uhr Aufgabe 1: (3+3 Punkte)

Gegeben sei das LP (P) max { ∑_{j=1}^{n} c_{j}x_{j} | ∑_{j=1}^{n} a_{j}x_{j} = b , x ≥ 0} mit Konstanten

c_{j} ≥ 0, a_{j} > 0 (j = 1, …, n) und b > 0.

(a) Berechnen Sie die optimale Lösung von (P) und geben Sie die optimale Basis B, die Nicht-Basis N und r_{N} an.

(b) Bestimmen Sie das duale Problem (P^{∗}) und berechnen Sie die duale Lösung λ ∈ IR direkt. Verifizieren Sie die Schattenpreisformel explizit.

Aufgabe 2: (1+3+3 Punkte) Lösen Sie das LP

max{2x_{1} + x_{2} | − x_{1} + 2x_{2} ≥ 3 , x_{1} + x_{2} ≤ 4 , x ≥ 0}

(a) auf graphischem Wege.

(b) mit der Zweiphasenmethode.

(c) mit der Dreiphasenmethode.

Aufgabe 3: (4+2 Punkte) Gegeben sei das von einem Parameter t ∈ IR abhängige LP

maximiere x_{1}  2x_{2}
unter  2x_{1} + x_{2} ≤ 14
x_{1} + x_{2} ≤ 10
x_{1}  ≤ 1 + 2t
x_{2} ≤ 8 − t
x_{1} , x_{2} ≥ 0 .

(a) Bestimmen Sie alle Parameter t ∈ IR, für die eine zulässige Lösung existiert. Berechnen Sie das zu t = 0 gehörende kritische Intervall KR(0).

(b) Berechnen Sie das kritische Intervall KR(t_{1}^{+}) für t_{1} = 1.

Aufgabe 4: (6 Punkte) Sei f : IR^{n} → IR eine differenzierbare Abbildung und sei T (s, \overline{x}) der Tangentialkegel einer Menge S ⊂ IR^{n} in \overline{x} ∈ S. Beweisen Sie die folgende hinreichende Bedingung erster Ordnung: Gilt

f′(\overline{x})v > 0 für alle v ∈ T (s, \overline{x}) , v ≠ 0 ,

so gibt es c > 0 und r > 0 mit

f(x) ≥ f(\overline{x}) + c∥x − \overline{x}∥ für alle x ∈ S mit ∥x − \overline{x}∥ ≤ r .

\underline{Hinweis:} Indirekter Beweis.

Aufgabe 5: (7 Punkte) Gegeben sei das Optimierungsproblem

min{x^{2} + 2xy + y^{2} − 10x − 10y | x^{2} + y^{2} ≤ 2 , 3x + y ≤ 4} .

Bestimmen Sie alle Lösungen \overline{x}, \overline{λ} der KUHN-TUCKER-Bedingungen. Geben Sie die globale Minimalstelle an. \underline{Hinweis:} Diskutieren Sie die Fälle λ_{1} = 0, λ_{1} > 0, λ_{2} = 0, λ_{2} > 0.

Aufgabe 6: (3+4 Punkte) Eine Blechdose in Zylinderform (Radius r und Höhe h) mit 1ℓ Volumen soll so hergestellt werden, daß dabei möglichst wenig Blech verbraucht wird.

(a) Formulieren Sie das zugehörige zweidimensionale Optimierungsproblem in den Variablen r und h und berechnen Sie die Lösung der KUHN-TUCKER-Bedingungen.

(b) Prüfen Sie die hinreichenden Bedingungen zweiter Ordnung nach.