Prof. Dr. H. Maurer WS 88/89

Optimierung 1

Übungsblatt 2 , Abgabe: 31.10.1988 , 10.00 Uhr

Aufgabe 5: (4 Punkte) Eine Fabrik hat zwei Maschinen, M_{1} und M_{2} zur Herstellung zweier Produkte P_{1} und P_{2}. Welches Herstellungsprogramm ergibt maximalen Gewinn pro Stunde bei Belegungszeiten und Preisen nach folgender Tabelle? (Man nimmt an, da es keine Rolle spielt, ob die Maschinen ganzzeitig ausgenutzt werden oder nicht.)

P_{1} P_{2}
Belegungszeit (min) M_{1} 6 1
M_{2} 3 4
Gewinn (DM)  30 20

Formulieren Sie das lineare Optimierungsproblem und lösen Sie es graphisch.

Aufgabe 6: (4 Punkte) Der Besitzer einer kleinen Schuhfabrik will je ein Modell eines Damen- und eines Herrenschuhs herstellen. Seine Belegschaft von 40 Angestellten und der Maschinenpark von 10 Maschinen sollen so eingesetzt werden, da der Gewinn maximal wird. Die Herstellung der Schuhe unterliegt bestimmten Nebenbedingungen, die in der folgenden Tabelle enthalten sind:

Damenschuh Herrenschuh verfügbar
Herstellungszeit (h)  20  10  8000
Maschinenbearbeitung (h)  4  5  2000
Lederbedarf (dm^{2})  6  15  4500
Reingewinn  16  32

Formulieren Sie das lineare Optimierungsproblem und lösen Sie es graphisch.

Aufgabe 7: (4 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 3000 kcal/m^{3} und einem Schwefelgehalt S von höchstens 3 g/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_{i} und formulieren Sie das lineare Optimierungsproblem.

Aufgabe 8: (3 Punkte)

Zeigen Sie: Die Menge der optimalen Lösungen eines linearen Optimierungsproblems der Form

min {c^{T} x | Ax = b, x ≥ 0}

ist konvex.

Optimierung 1

Übungsblatt 2 , Abgabe: 31.10.1988 , 10.00 Uhr

Aufgabe 5: (5 Punkte) Zeige:

i) Sind K_{1} ⊂ R^{n} und K_{2} ⊂ R^{n} konvex, so ist

αK_{1} + βK_{2} := {αx + βy | x ∈ K_{1}, y ∈ K_{2}} , α, β ∈ R

konvex.

ii) K ⊂ R^{n} konvex ⇒ das topologische Innere K^{∘} und der topologische Abschluß \overline{K} sind konvex. iii) Ist K konvex, x ∈K^{∘}, y ∈ \overline{K}, so gilt

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

Aufgabe 6: (4 Punkte)

a) Sei K ⊂ R^{n} konvex, x^{0},…, x^{k} ∈ K .
\underline{Beh.:}
∑_{i=0}^{k} α_{i}x^{i} ∈ K,  α_{i} ≥ 0,  ∑_{i=0}^{k} α_{i} = 1
b) Fr x^{0},…, x^{k} ∈ R^{n} gilt:
co(x^{0},…, x^{k}) = {∑_{i=0}^{k} α_{i}x^{i} | α_{i} ≥ 0,  ∑_{i=0}^{k} α_{i} = 1}
c) Fr M ⊂ R^{n} gilt:

co(M) = ⋃_{k∈N,x0,...,xk∈M} co(x^{0},…, x^{k})

Aufgabe 7: (4 Punkte) Sei M ⊂ R^{n} konvex. Zeige:

p ∈ M  ist extremal ⟺ M \ {p}  ist konvex

Aufgabe 8: (4 Punkte) Aus Rosinen, Nüssen und Puffreis soll Studentenfutter hergestellt werden. Die Mischung soll mindestens \frac{1}{3} Rosinen, mindestens halbsoviel und hchstens ebensoviel Nüsse wie Rosinen, mindestens halbsoviel Puffreis wie Rosinen und mindestens halbsoviel Nüsse wie Puffreis enthalten. Die Preise sind fr Rosinen 1, 40DM, Puffreis 1, 10DM, Nüsse 1, 80DM jeweils pro Kilogramm. Es soll eine Mischung hergestellt werden, die den aufgefhrten Bedingungen genügt und deren Preis minimal ist. Man setze r-Anteil der Rosinen pro Kilogramm, n und p analog. Benutzen Sie die Gleichung 1 = p+n+r, um eine Variable zu eliminieren und lsen Sie das Problem graphisch.

Optimierung 1

Übungsblatt 3 , Abgabe: 07.11.1988 , 10.00 Uhr

Aufgabe 9: (2 Punkte) Man zeige: Es gibt keine Lösung x ≥ 0 von

( \begin{matrix}1 & 3 & −5 \\ 1 & −4 & −7 \end{matrix} ) x = ( \begin{matrix}2 \\ 3 \end{matrix} )

Aufgabe 10: (3 Punkte) Seien K_{1}, K_{2} ⊂ R^{n} konvexe Mengen, K_{1} ∩ K_{2} = 0. Zeige: K_{1} und K_{2} sind trennbar. \underline{Hinweis:} Definiere

K := ⋃_{y∈K_{2}}{y − x | x ∈ K_{1}} = K_{2} − K_{1}

und zeige: K ist konvex. Wende dann den Trennbarkeitssatz an.

Aufgabe 11: (4 Punkte)

a.) Sei K eine konvexe Menge in R^{n}, K^{∗} eine konvexe Menge in R^{m}. Sei A : K → K^{∗} eine affin lineare Abbildung mit der Eigenschaft: ∀x^{∗} ∈ K^{∗} gibt es ein eindeutig bestimmtes x ∈ K mit Ax = x^{∗}.

\underline{Zeige:} Es existiert eine eindeutige Beziehung zwischen den Extremalpunkten von K und K^{∗}.

b.) Beweise mit Hilfe von a) Lemma 3.8 der Vorlesung.

Aufgabe 12: (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 fr Gefriertruhen kann in einem Monat höchstens 600 Gefriertruhen montieren.

c.) Die Montageabteilung fr Kühlschrnke kann in einem Monat höchstens 800 Kühlschränke montieren.

d.) Die Abteilung fr 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. Bestimmen Sie sämtliche Ecken der zulässigen Menge und berechnen Sie die optimale Ecke.

Aufgabe 13: (4 Punkte) Gegeben seien die Nebenbedingungen

\begin{aligned}3x_{1} & + & x_{2} & − & 2x_{3} & + & x_{4} & = & 5 \\ x_{1} & − & 2x_{2} & − & x_{3} & + & x_{5} & = & 1 \\ x_{1} & + & 2x_{2} & + & 2x_{3} & + & x_{6} & = & 3 \\ x_{1} & + & 2x_{2} & − & x_{3} & + & x_{7} & = & 4 \end{aligned}

x_{i} ≥ 0 i = 1,…, 7.

Berechne die Basislösungen zu

i) B = (4, 5, 6, 7)

ii) B = (1, 2, 4, 6)

iii) B = (2, 3, 4, 7)

Welche davon sind zulässig?

Optimierung 1

Übungsblatt 4 , Abgabe: 14.11.1988 , 10.00 Uhr

Aufgabe 14: (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 15: (3 Punkte) Man zeige, da das LP maximiere (4, 2, −11, 2, −3)x unter

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

x ≥ 0, x ∈ R^{5}

keine Lösung besitzt.

Aufgabe 16: (2 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.

Aufgabe 17: (4 Punkte) Lse das LP maximiere z(x) = 2x_{1} + 3x_{2} unter

\begin{aligned}5x_{1} & + & 12x_{2} & + & x_{3} & = & 30 \\ 20x_{1} & + & 10x_{2} & + & x_{4} & = & 50 \\ 20x_{1} & + & 20x_{2} & + & x_{5} & = & 60 \end{aligned}

x_{i} ≥ 0, i = 1,…, 5

mit dem Simplex-Verfahren.

Aufgabe 18: (4 Punkte) Sei A = (a_{ij}) eine m × n Matrix, B = (1,…, m), A_{B} = I, p ∈ B, s ∈ N eine Basis mit a_{ps} ≠ 0. Erzeuge mittels elementarer Zeilenoperatoren den Einheitsvektor e_{p} ∈ R^{m} in Spalte s. Wie lauten die Elemente der neuen Matrix A′ = (aij^{′})?

Optimierung 1

Übungsblatt 5 , Abgabe: 21.11.1988 , 10.00 Uhr

Aufgabe 19: (4 Punkte) Lsen Sie das LP maximiere z = 6x_{1} + 14x_{2} + 13x_{3} unter

\frac{1}{2}x_{1} + 2x_{2} + x_{3} ≤ 24
x_{1} + 2x_{2} + 4x_{3} ≤ 60
x ≥ 0

mit dem Simplex-Verfahren.

Aufgabe 20: (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, benutzt er nur die folgenden Drinks:

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 fr die Flaschen in dieser Formulierung zu beachten?)

Aufgabe 21: (5 Punkte) Lsen 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 ∈ R^{4}

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

Aufgabe 22: (4 Punkte) Lsen Sie das folgende LP mit Hilfe der Zweiphasenmethode:

maximiere  (1, 2, 3)x  unter

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

x ≥ 0, x ∈ R^{3}

Optimierung 1

Übungsblatt 6 , Abgabe: 28.11.1988 , 10.00 Uhr

Aufgabe 26: (4 Punkte) Hat 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 Lsung? \underline{Hinweis:} Benutzen Sie das Simplex-Verfahren.

Aufgabe 27: (4 Punkte) Das in Aufgabe 3 betrachtete Problem einer kostenminimalen Gasmischung fhrt auf das LP minimiere z = 10x_{1} + 30x_{2} + 20x_{3}

unter x_{1} + 3x_{2} + 6x_{3} ≥ 3
8x_{1} + x_{2} + 2x_{3} ≤ 3
x_{1} + x_{2} + x_{3} = 1
x ≥ 0 .

Man lse das Problem mit der Zweiphasenmethode.

Aufgabe 28: (4 Punkte) Lsen Sie mit Hilfe des revidierten Simplex-Verfahrens das Problem

maximiere 3x_{1} + x_{2} − x_{3} + 2x_{4}
unter x_{1} + x_{4} + x_{5} ≤ 6
2x_{2} − x_{3} + 3x_{4} + x_{5} ≤ 12
x_{1} − 4x_{3}  ≤ 8
x ≥ 0 .

Optimierung 1

Übungsblatt 7 , Abgabe: 05.12.1988 , 10.00 Uhr

Aufgabe 30: (4 Punkte)

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

(b) Berechnen Sie das duale Problem zu

min {cx | A_{1}x ≥ b_{1}, A_{2}x = b_{2}, x ≥ 0}

mit Matrizen A_{1}, A_{2} passender Dimension.

∗Aufgabe 31: (5 Punkte) Bei der Lsung des Problems

(P) min {cx | Ax ≥ b, x ≥ 0} , c ≥ 0

mit dem dualen Simplex-Verfahren lst man

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

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

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

erhlt man aus dem optimalen Tableau folgendermaen:

(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 Lsung λ^{∼} des dualen Problems von (P_{1}) und der Lsung λ von (P^{∗}) die Beziehung λ = − λ^{∼} gilt.

Aufgabe 32: (4 Punkte) Lsen Sie

minimiere 6x_{1} + 18x_{2} + 15x_{3} + 12x_{4}
unter x_{1} + 3x_{2} + x_{4} ≥ 1
x_{1} + x_{2} + x_{3} + x_{4} ≥ 5
x_{1} + 2x_{2} + 3x_{3}  ≥ 2
x_{2}  + 2x_{4} ≥ 2
2x_{2} + x_{3} + x_{4} ≥ 1
x ≥ 0

mit dem dualen Simplex-Verfahren. Bestimmen Sie die optimale Lsung des dualen Problems und verifizieren Sie die Aussage in Korollar (7.4).

Aufgabe 33: (5 Punkte) Ein Nikolaus hat Lakritzstangen der Lnge 20 cm auf Lager. Zur Bescherung bentigt er

mindestens 4000 Lakritzstangen der Lnge 9 cm,
mindestens 5000 Lakritzstangen der Lnge 8 cm,
mindestens 3000 Lakritzstangen der Lnge 6 cm .

Wie mu der Nikolaus die 20 cm langen Lakritzstangen zuschneiden, damit der Abfall mglichst gering wird? \underline{Hinweis:} Es gibt 6 Strategien (Begrndung), die 20 cm langen Stangen zuzuschneiden. Setze x = (x_{1},…, x_{6})^{T}, wobei x_{i} die Anzahl der Stangen ist, die nach Strategie i zugeschnitten werden. Lse das Problem mit dem dualen Simplex-Verfahren.

Optimierung 1

Übungsblatt 8 , Abgabe: 12.12.1988 , 10.00 Uhr

Aufgabe 30: (6 Punkte) Lsen 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}.

Aufgabe 31: (4 Punkte) Sei x ∈ R^{n} optimal fr das LP

(P) min {cx | Ax = b, x ≥ 0}

zur Basis B bzw. Nichtbasis N. Man zeige:

(a) r_{N} < 0 ⇒ x eindeutig

(b) r_{N} ≤ 0, r_{j} = 0 fr ein j ∈ N, x_{B} > 0 ⇒ (P) mehrdeutig lsbar

Aufgabe 32: (2+3 Punkte) Man berechne smtliche optimalen Lsungen der folgenden primalen und der dazu dualen LP:

(a)

max 2x_{1} + 4x_{2}
unter x_{1} + x_{2} ≤ 4
x_{1} + 2x_{2} ≤ 6
x ≥ 0

Man lse diese Aufgabe graphisch.

(b)

min  x_{1} + 3x_{2} + 2x_{3}
unter x_{1} + 2x_{2} + 2x_{3} ≥ 10
2x_{1} + x_{2} + 2x_{3} ≥ 5
2x_{1} + 2x_{2} + x_{3} ≥ 20
≥ 0

Optimierung 1

Übungsblatt 9 , Abgabe: 19.12.1988 , 10.00 Uhr

Aufgabe 33: (4 Punkte) Sei w : R^{k} → \overline{R} die Optimalwert-Funktion

w(t) = inf_{x∈R^{n}} {c(t)x | Ax = b, x ≥ 0} , t ∈ R^{k} ,

c(t) affin linear ,

eines parametrischen LP. Man zeige:

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

(b) Die Funktion w : D → R ist konvex.

Aufgabe 34: (5 Punkte) Man lse das parametrische LP

maximiere z(t) = (2 + t)x_{1} + (2 − t)x_{2} + 4x_{3}
unter  2x_{1} +  3x_{2} +  x_{3} ≤ 20
3x_{1} +  x_{2} +  7x_{3} ≤ 35
x_{1} +  4x_{2} +  6x_{3} ≤ 56

fr alle t ∈ R.

Aufgabe 35: (5 Punkte) Man lse das parametrische LP

maximiere z = 20x_{1} + 10x_{2} + 30x_{3}
unter 2x_{1} + x_{2} + x_{3} ≥ 5 − 2t
x_{1} − x_{2} + 2x_{3} ≥  2t + 2

und das dazu duale LP fr alle t ∈ R.

Optimierung 1

Übungsblatt 10 , Abgabe: 16.1.1989 , 10.00 Uhr

Aufgabe 36: (2+1+2+3 Punkte) Sei D ⊂ R^{n} konvex.

(a) Man zeige: f ∈ Conv(D) genau dann, wenn

epi(f) = {(x, r) ∈ R^{n} × R | f(x) ≤ r}

konvex ist.

(b) Man zeige: Gilt f ∈ Conv(D) und ist g : R ⟶ R monoton wachsend und konvex, so gilt: g ∘ f ∈ Conv(D)

(c) Man zeige: Gilt f_{i} ∈ Conv(D) fr i ∈ I, I Indexmenge.

D_{0} := {x ∈ D | sup_{i∈I} f_{i}(x) < ∞},

so gilt

(i) D_{0} ist konvex. (ii)

f := sup_{i∈I} f_{i} ∈ Conv(D_{0}).

(d) Fr x ∈ R^{n} sei:

∥ x ∥_{1} := ∑_{i=1}^{n} |x_{i}|
∥ x ∥_{2} := (∑_{i=1}^{n} x_{i}^{2})^{1/2}
∥ x ∥_{∞} := max_{i≤i≤n} |x_{i}|

Man zeige:

(i) Alle drei Normen ∥ · ∥_{1}, ∥ · ∥_{2}, ∥ · ∥_{∞} sind konvexe Funktionen von R^{n} nach R. (ii) Sind x, y ∈ R^{n} linear unabhngig, so gilt:

∥ αx + (1 − α)y ∥_{2}< α ∥ x ∥_{2} +(1 − α) ∥ y ∥_{2}, 0 < α < 1

(strikt konvex) (iii) Aussage (ii) gilt nicht fr ∥ · ∥_{1} und ∥ · ∥_{∞}.

Aufgabe 37: (2+3 Punkte)

(a) Man bestimme die grte konvexe Menge D ⊂ R^{2}, so da

f(x, y) = (x + y)^{2} + \frac{1}{3}(x + y)^{3}

konvex bzw. strikt konvex auf D ist.

(b) Zeigen Sie, da die Funktion

f(x, y) = (x + y)^{3} − ∫_{−∞}^{x−y} exp(−t^{2}/2)dt

strikt konvex fr 2 ≤ x ≤ 4, −1 ≤ y ≤ 0 ist. Aufgabe 38: (3+3+2 Punkte)

(a) Seien D ⊂ R^{n} konvex, f ∈ Conv(D), x ∈ int(D) und f differenzierbar in x. Man zeige: ∂f(x) = {f′(x)}

(b) Sei D = [−1, 1] ⊂ R und sei f(x) = |x| fr x ∈ D. Man berechne ∂f(x) fr alle x ∈ D.

(c) Sei f(x) = max{x^{2}, x + 2} fr x ∈ R. Man zeige, da f konvex ist (Skizze !) und berechne ∂f(x) fr alle x ∈ R.

Aufgabe 39: (4 Punkte) Bestimmen Sie die Lsung (\overline{x}, \overline{y}) des folgenden Optimierungsproblems auf grafischem Wege:

min{f(x, y) = (x − 2)^{2} + (y − 1)^{2} | g_{1}(x, y) = x + y − 2 ≤ 0, g_{2}(x, y) = x^{2} − y ≤ 0} Zeichnen Sie die Gradienten

▽f(\overline{x}, \overline{y}), ▽g_{1}(\overline{x}, \overline{y}), ▽g_{2}(\overline{x}, \overline{y})

und berechnen Sie λ = (λ_{1}, λ_{2}) ≥ 0 mit ▽f(\overline{x}, \overline{y}) + λ_{1} ▽ g_{1}(\overline{x}, \overline{y}) + λ_{2} ▽ g_{2}(\overline{x}, \overline{y}) = 0.

Wir wnschen allen bungsteilnehmern ein FROHES WEIHNACHTSFEST und ein GUTES NEUES JAHR 1989

Optimierung 1

Übungsblatt 11 , Abgabe: 23.01.1989 , 10.00 Uhr

Aufgabe 4: (5 Punkte) Man zeige: Ist f_{1}, f_{2} ∈ Conv(R^{n}), so gilt

∂(f_{1} + f_{2})(x) = ∂f_{1}(x) + ∂f_{2}(x) fr allex ∈ R^{n}.

\underline{Hinweis:} Zum Nachweis von ∂(f_{1} + f_{2})(x) ⊂ ∂f_{1}(x) + ∂f_{2}(x) betrachte man fr μ ∈ ∂(f_{1} + f_{2})(x) die konvexen Mengen in R^{n} × R:

\begin{aligned}C_{1} & := & \{(y, f_{1}(x + y) − f_{1}(x) + r_{1}) & | & y ∈ R^{n}, r_{1} ≥ 0\}, \\ C_{2} & := & \{(z, μz − f_{2}(x + z) + f_{2}(x) − r_{2}) & | & z ∈ R^{n}, r_{2} > 0\}. \end{aligned}

Man zeige C_{1} ∩ C_{2} = ∅ und wende den Trennungssatz (A.6) an. Beachten Sie, da die Abschtzung im Trennungssatz fr alle y, z ∈ R^{n} gilt!

Aufgabe 5: (2+2 Punkte) Sei D eine positiv definite, symmetrische (n, n)-Matrix, A eine (m, n) - Matrix mit m < n, rang(A) = m, N := A^{T} (n, m) - Matrix.

(a) Fr y ∈ R^{n} berechne man die Lsung des gewichteten linearen Ausgleichsproblems

min_{u∈Rm} f(u) = (y − Nu)^{T} D^{−1}(y − Nu)

in der Form u = N^{∗}y mit einer (m, n)-Matrix N^{∗} (\underline{Pseudoinverse} von N bzgl. D).

(b) Sei c ∈ R^{n}, b ∈ R^{m}. Berechnen Sie den Sattelpunkt \overline{x} ∈ R^{n}, \overline{λ} ∈ R^{m} fr das quadratische Optimierungsproblem

min\{cx + \frac{1}{2}x^{T} Dx | Ax = b\}

mittels der Pseudoinversen N^{∗} zu N = A^{T}.

\underline{Hinweis:} \overline{x}, \overline{λ} gengen n + m linearen Gleichungen.

Aufgabe 6: (2+2+2 Punkte) Sei \overline{x} ∈ R^{2} die optimale Lsung des Problems

(P) 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}

(a) Man zeige, da (P) ein konvexes Optimierungsproblem ist und bestimme die Lage von \overline{x} auf grafischem Wege.

(b) Reduzieren Sie das aus (a) resultierende nichtlineare Gleichungssystem auf ein Iterationsverfahren in R und berechnen Sie \overline{x} numerisch auf 5 Dezimalen.

(c) Man berechne den zu \overline{x} gehrigen LAGRANGE-Multiplikator \overline{λ} ∈ R^{3} aus den KUHN / TUCKER - Bedingungen.

Prof. Dr. H. Maurer WS88/89

Programmieraufgaben zur Optimierung 1

Übungsblatt 1 , Abgabe: 12.12.1988 , 10.00 Uhr

I. Simplex-Verfahren Implementieren Sie das im Skript S. 4.19 ff angegebene Simplex-Verfahren in einer in der numerischen Mathematik gebruchlichen Programmiersprache (d. h. FORTRAN, PASCAL, PL/1).

Aufgabe 1: berprfen Sie die Korrektheit Ihres Programms anhand von Aufgabe 19.

Aufgabe 2: Die optimale Herstellung von 8 Produkten aus 9 Rohstoffen fhrt auf das folgende LP:

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)^{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 \end{matrix} )

Berechnen Sie die optimale Lsung mit Ihrem Programm und lassen Sie das optimale Tableau ausdrucken. Der Zielfunktionswert ist z = 6346.53.

Aufgabe 3: Der optimale Zuschnitt von 100 000 m^{3} Eichenstammholz fhrt auf das folgende LP: maximiere 1440x_{1} + 1920x_{2} + 1720x_{3} + 1666x_{4} + 1802x_{5}

unter \begin{aligned}x_{1} & + & x_{2} & + & x_{3} & + & x_{4} & + & x_{5} & = & 100000 \\ 0.1x_{1} & + & 0.1x_{4} & + & 0.05x_{5} & & & & & ≥ & 1000 \\ 0.3x_{1} & + & 0.3x_{4} & + & 0.25x_{5} & & & & & ≥ & 5000 \\ 0.4x_{2} & + & 0.15x_{5} & & & & & & & ≤ & 20000 \\ 0.1x_{2} & + & 0.5x_{3} & + & 0.15x_{4} & + & 0.12x_{5} & & & ≥ & 5000 \\ 0.1x_{2} & + & 0.5x_{3} & + & 0.15x_{4} & + & 0.12x_{5} & & & ≤ & 10000 \\ 0.4x_{1} & + & 0.5x_{2} & + & 0.5x_{3} & + & 0.41x_{4} & + & 0.43x_{5} & ≤ & 45000 \end{aligned}

x_{i} ≥ 0, i = 1,…, 5

Berechnen Sie die Lsung dieses LP’s mit Ihrem Programm und lassen Sie das optimale Tableau, sowie das Starttableau fr Phase 2 ausdrucken. Die (ganzzahlige gerundete) optimale Lsung ist: x = (12121, 27273, 0, 0, 60606).

Programmieraufgaben zur Optimierung 1

Übungsblatt 2 , Abgabe: 23.01.1989 , 10.00 Uhr

II. Duales Simplex-Verfahren

Lsen Sie die beiden folgenden Aufgaben mit dem Simplex-Verfahren. Programmieren Sie entweder das duale Simplex-Verfahren (7.12) oder benutzen Sie das Simplex-Verfahren (4.20) fr das duale Problem.

Aufgabe 4: Fnf Metallteile sollen aus einheitlichen Blechtafeln geschnitten werden. Hierzu gibt es 10 Schnittplne. Das Problem, bei vorgegebener Mindestzahl fr jedes der fnf Metallteile mglichst wenig Blechtafeln zu verbrauchen, fhrt auf das folgende LP:

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

mit

\begin{aligned}c & = & (1, 1, 1, 1, 1, 1, 1, 1, 1, 1) \\ b & = & (600, 350, 475, 700, 850)^{T} \\ 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 betrgt: z = 241.147

Aufgabe 5: Die Geschftsleitung einer groen Gemeinschaftskche hat beschlossen, das Speiseprogramm so zu bestimmen, da unter Einhaltung der pro Kopf vorgeschriebenen Nhrstoffe die Menge der hierzu bentigten Rohmaterialien minimal sei. Die Nhrstoffgehalte der verwendeten Rohstoffe sowie der tgliche Bedarf eines Menschen sind in der folgenden Tabelle zusammengefat:

Ferner mu man bercksichtigen:

1. 60 g Eiwei mssen aus tierischem Eiwei gedeckt werden.

2. Der tgliche Zuckerverbrauch darf nicht hher als 100 g sein.

3. Der monatliche Verbrauch an Hlsenfrchten darf 1000 g nicht berschreiten.

4. Der monatliche Verbrauch an Obst mu mindestens 4000 g sein.

\underline{Teil (A):} Lsen Sie das Problem mit der Zielfunktion

z = cx = ∑_{i=1}^{15} x_{i}.

Fr die mit dem dualen Simplex-Verfahren berechnete, optimale Lsung gilt:

z = 1.4244; 4, 2, 14, 5, 6, 7, 9, 10, 13 ∈ N.

\underline{Teil (B):} Man betrachte die Zielfunktion

z_{j} = (1 − t)x_{j} + ∑_{i=1, i≠j}^{15} x_{i} , c_{j} = 1 − t

fr j ∈ N ∩ {1, 2,…, 15}, 0 ≤ t ≤ 1, N wie in Teil (A). Man zeige r_{j}(t) = r_{j} +t und folgere, da fr −r_{j} < t ≤ −r_{j} +δ, δ > 0 gengend klein, die Variable x_{j} Basis-Variable wird. Man lse das Problem mit

\begin{aligned}(a) & j & = & 6 & , & t & = & 0.25 & , & c_{6} & = & 0.75 & ; \\ (b) & j & = & 7 & , & t & = & 0.2 & , & c_{7} & = & 0.8 & ; \\ (c) & j & = & 10 & , & t & = & 0.05 & , & c_{10} & = & 0.95 & . \end{aligned}