Optimierung 1 ¨Ubungsblatt 3

Optimierung 1
Übungsblatt 3
Laurent Pfeiffer, Universität Graz
18. März 2016
Aufgabe 1 (Anwendungsproblem). Eine Firma besitzt verschiede Produktionslagen, in denen
sie verschiedene Produkte herstellen kann. Die Firma bekommt eine Bestellung. Um den Auftrag
zu erfüllen dürfen die Produktionslagen über verschiedene Zeiträume betrieben werden. Die
folgenden Daten sind gegeben:
• Aji : maximale Menge des Produktes j, das in der Firma i pro Tag hergestellt werden kann
• ci : Produktionskosten pro Tag in der Firma i (für alle Produkte)
• bj : bestellte Menge des Produktes j.
1. Bezeichnen Sie mit xi die Anwendungszeit der Fabrik i. Modellieren Sie die Aufgabe einen
Produktionsplan zu finden, der die Kosten minimiert.
2. Die Firma möchte nun die Produkte so schnell wie möglich herstellen, ohne die Produktionskosten zu berücksichtigen. Wie soll der Produktionsplan aussehen?
Aufgabe 2 (Kanonische Form). Der Simplex-Algorithmus ermöglicht das Lösen linearer Probleme der sogenannten kanonischen Form:
min c⊤ x,
x∈Rn
u.d.N. Ax = b, x ≥ 0,
wobei c ∈ Rn , A ∈ Rm×n und b ∈ Rm , b ≥ 0 gegeben sind. Genauer gesagt kann man mit dem
Simplex-Algorithmus herausfinden, welcher dieser drei Fälle zutrifft:
• die zulässige Menge ist leer
• der Wert des Problems ist −∞: In diesem Fall ist die zulässige Menge nicht leer und es
gibt einen Vektor y ∈ Rn , so dass y ≥ 0, y ∈ Ker(A) und c⊤ y < 0
• das Problem hat (mindestens) eine Lösung x.
Wie sollten die folgenden Probleme umgeschrieben werden, damit man sie mit dem SimplexAlgorithmus lösen kann? In den folgenden Problemen ist b ≥ 0.
1. minx∈Rn c⊤ x, u.d.N. Ax = b̂, x ≥ 0, wobei b̂ beliebig ist
2. minx∈Rn c⊤ x, u.d.N. Ax ≤ b, x ≥ 0
3. minx∈Rn c⊤ x, u.d.N. Ax ≥ b, x ≥ 0
4. minx∈Rn c⊤ x, u.d.N. Ax = b
5. minx∈Rn f (x), u.d.N. Ax = b, x ≥ 0, wobei: f (x) = maxi=1,...,k c⊤
i x+di und wobei c1 ,...,ck ∈
Rn und d1 ,...,dk ∈ R gegeben sind
1
6. minx∈Rn c⊤ x, u.d.N. g(x) ≤ 0, x ≥ 0, wobei: g(x) = maxi=1,...,k p⊤
i x + qi und wobei
p1 ,...,pk ∈ Rn und q1 ,...,qk ∈ R gegeben sind.
Wie kann mann das folgende Problem umschreiben:


x1 + 2x2 ≤ 2





 x1 + 3x3 ≤ −1
u.d.N.
x1 ≥ 0



x2 ≤ 0




x2 ≥ −5
min |x1 | + 2x2 + x3 ,
x∈R3
um es mit dem Simplex-Algorithmus zu lösen?
Aufgabe 3 (Optimalitätsbedingungen). Wir betrachten das folgende Problem:
min c⊤ x,
x∈Rn
wobei: ∀i = 1, ..., m, bi > 0, und

u.d.N. Ax = b, x ≥ 0,
1
0 . . . 0 a1,m+1 . . . a1,n

.
..
..
.
 0 . . . . . ..
.
.
A=
 .. . . . .
..
..
 .
.
. 0
.
.
0 . . . 0 1 am,m+1 . . . am,n



.


Wir nehmen an, dass c = [0, ..., 0, cm+1 , ..., cn ]⊤ .
1. Finden Sie eine Bedingung für die Koeffizienten cm+1 ,...,cn , die erfüllt ist, genau dann
wenn x̄ = [b1 , ..., bm , 0, ..., 0] eine Lösung des Problems ist.
2. Wir nehmen nun an, dass es einen Index j ∈ {m + 1, ..., n} gibt, so dass gilt: ∀i = 1, ..., m,
aij ≤ 0 und cj < 0. Hat das Problem eine Lösung?
3. Sei d ∈ Rn beliebig. Finden sie einen Vektor dˆ ∈ Rn und eine Zahl z, so dass gilt:
h
i
dˆ1 = ... = dˆm = 0 und ∀x ∈ Rn , Ax = b und x ≥ 0 =⇒ dˆ⊤ x + z = d⊤ x.
Aufgabe 4 (Transportproblem (1)). Eine Firma besitzt N Fabriken und M Läden, wo sie
ein Produkt herstellen bzw. verkaufen kann. Wir bezeichnen mit ai die hergestellte Menge des
Produktes in der Fabrik i und mit bj die Nachfrage nach dem Produkt im Laden j. Wir nehmen
an, dass
M
N
X
X
bj .
ai =
j=1
i=1
Wir bezeichnen mit xij die transportierte Menge vom Produkt von der Fabrik i bis zum Laden
j. Die Transportkosten von der Fabrik i bis zum Laden j betragen cij pro Produktseinheit.
1. Modellieren Sie die Aufgabe einen Auslieferungsplan zu finden, der die Kosten minimiert.
2. Lösen Sie das Problem für die folgenden Daten:
 
2
3
2
3
1
a=
, b =  1 , c =
.
4
1 1 5
4
Verwandeln Sie das Problem in ein Problem mit Optimierungsvariablen x11 und x22 . Lösen
Sie das neue Problem graphisch. Die anderen Variablen können eliminiert werden, dank
der Gleichungsnebenbedingungen: Man kann z.B. x21 mit b1 − x11 ersetzen.
2
Aufgabe 5 (Transportproblem (2)). Diese Aufgabe ist die Fortsetzung der Aufgabe 4.
1. Sei x̄ eine Lösung des Transportproblems. Zeigen Sie: Für alle i1 , i2 ∈ {1, ..., N }, für alle
j1 , j2 ∈ {1, ..., M },
h
i
x̄i1 ,j1 > 0 und x̄i2 ,j2 > 0 =⇒ ci1 ,j1 + ci2 ,j2 ≤ ci1 ,j2 + ci2 ,j1 .
2. Wir nehmen nun an, dass cij = |j − i|2 . Zeigen Sie: Für alle i1 , i2 ∈ {1, ..., N }, für alle
j1 , j2 ∈ {1, ..., M },
h
i
i1 < i2 und x̄i1 ,j1 > 0 und x̄i2 ,j2 > 0 =⇒ j1 ≤ j2 .


2
1
 1 
N ×M , so dass die obige Bedingung

Seien a =  3  und b = 
 0 . Finden Sie x ∈ R
2
3
erfüllt ist.


3

Download Report