Lösningsförslag tentament TMA945 Tillämpad optimeringslära 980309

1 a) Variabler:

x_{j} = \{ \begin{matrix}1, & om maskin j används \\ 0, & annars \end{matrix} j = 1, …, k

y_{j}= antal enheter som tillverkas i maskin j, j = 1, …, 4.

Modell:

minimera f(x, y) = 400x_{1} + 1000x_{2} + 600y_{3} + 300y_{4} + 4y_{1} + 6y_{2} + 2y_{3} + 5y_{4}

då

y_{1} ≤ 2000x_{1}
y_{2} ≤ 4000x_{2}
y_{3} ≤ 1000x_{3}
y_{4} ≤ 3000x_{4}
0.9y_{1} + 0.95y_{2} + 0.85y_{3} + 0.92y_{4} ≥ 5000
x_{j} ∈ {0, 1}, j = 1, …, 4
y_{j} ≥ 0, heltal,j − 1, …, 4

b) (Ett exempel) Vi kan tänka oss att när vi observerar utfallet i andelen defekta enheter producerar vi några extra enheter i samma maskin, alternativt köps det resterande behovet in utifrån. Det senare alternativet kan modelleras sålunda:

Låt ξ_{j} vara sannolikheten för defekt produkt i maskin j, och inför en ny variabel, z, som anger det ytterligare antalet enheter som behöver köpas in. Vi antar att varje variabel ξ_{j} är oberoende och att vektorn ξ tillhör någon mängd W av möjliga utfall w. Vi skriver ξ_{j} = ξ_{j}(w). Vi antar att varje enhet som måste köpas in kostar q kronor. Eftersom också z är en stokastisk variabel är den extra kostnaden q(w) · z(w). Följande modell uppfyller efterfrågan med sannolikhet 1, till lägsta förväntade kostnad.

Minimera f(x, y, z) = 400x_{1} + 1000x_{2} + 600x_{3} + 300x_{4} + 4y_{1} + 6y_{2} + 2y_{3} + 5y_{4} + E_{ξ}[q(w)z(w)] då y_{1} ≤ 2000x_{1} y_{2} ≤ 4000x_{2} y_{3} ≤ 1000x_{3} y_{4} ≤ 3000x_{1} [1 − ξ_{1}(w)]y_{1} + [1 − ξ_{2}(w)]y_{2} + [1 − ξ_{3}(w)]y_{3} + [1 − ξ_{4}(w)]y_{4} + z(w) = 5000

x_{j} ≥ {0, 1}, j = 1, … 4 y_{j} ≥ 0, heltal, j = 1, … 4 z(w) ≥ 0, heltal

Med en lämplig diskretisering av utfallsrummet W kan detta sedan konverteras till ett vanligt heltalsproblem, där olika utfall ges olika sannolikheter.

2a) Se sats 6.1, sid. 150 i Nash & Sofer.

b) Se sektion 5.3.4 i Nash & Sofer.

c) (⇒) trivialt (⇐) Antag att det finns en lösning till olikhetssystemet som uppfyller

∑_{j=1}^{n} a_{ij}x_{j} < b_{i}, för något i. Adderas olikheterna till varandra fås då att

∑_{i=1}^{m} ∑_{j=1}^{n} a_{ij}x_{ij} < ∑_{i=1}^{m} b_{i}, vilket är en motsägelse.

3. f(x) := 4x_{1} + 6x_{2} − 2x_{1}^{2} − 2x_{1}x_{2} − 2x_{2}^{2} har Hessian-matris ∇^{2}f(x) = [ \begin{matrix}−4 & −2 \\ −2 & −4 \end{matrix} ], som är negativt definit. Eftersom f därmed är (strikt) konvex, och det tillåtna området, S = {x ∈ ℝ^{2}|x_{1} + 2x_{2} ≤ 2; x_{1}, x_{2} ≥ 0] är en polyeder (en konvex mängd), gäller olikheten

f(x) ≤ f(y) + ∇f(y)^{T} (x − y) ∀x, y ∈ S,

som används för uppskattningar av det optimala målfunktionsvärdet i Frank-Wolfe metoden.

Iteration 1: x_{0} = [ \begin{matrix}1/2 \\ 1/2 \end{matrix} ]; ∇f(x_{0}) = [ \begin{matrix}4 − 4x_{1} − 2x_{2} \\ 6 − 2x_{1} − 4x_{2} \end{matrix} ] = [ \begin{matrix}1 \\ 3 \end{matrix} ] och

f(x_{0}) = 31/2. Lös

\begin{aligned}max z_{1}(y) = f(x_{0}) + ∇f(x_{0})^{T} (y − x_{0}) & = 31/2 + [ \begin{matrix}1 \\ 3 \end{matrix} ]^{T} [ [ \begin{matrix}y_{1} \\ y_{2} \end{matrix} ] − [ \begin{matrix}1/2 \\ 1/2 \end{matrix} ] ] \\ & = 3/2 + y_{1} + 3y_{2} \end{aligned}

⇒ y = [ \begin{matrix}0 \\ 1 \end{matrix} ]; z_{1}(y) = 41/2.

∵ Optimala målfunktionsvärdet tillhör intervallet [3\frac{1}{2}, 4\frac{1}{2}].

p_{1} = y_{1} − x_{0} = [ \begin{matrix}0 \\ 1 \end{matrix} ] − [ \begin{matrix}1/2 \\ 1/2 \end{matrix} ] = [ \begin{matrix}−1/2 \\ 1/2 \end{matrix} ]

f(x_{6} + ℓp_{1}) = f(\frac{1 − ℓ}{2}, \frac{1 + ℓ}{2}) = 31/2 + ℓ − \frac{ℓ^{2}}{2} = φ(ℓ)

ℓ′(ℓ) = 1 − ℓ = 0 ⇒ ℓ1. x_{1} = [ \begin{matrix}0 \\ 1 \end{matrix} ] .

Iteration 2: f(x_{1}) = 4 ∵ f(x_{∗}) ∈ [4, 41/2].

∇f(x_{1}) = [ \begin{matrix}2 \\ 2 \end{matrix} ].

Lös

\begin{aligned}max_{b∈S} z_{2}(y) & = f(x_{1}) + ∇f(x_{1})^{T} (y − x_{1}) = 4 + [ \begin{matrix}2 \\ 2 \end{matrix} ]^{T} [ \begin{matrix}y_{1} − 0 \\ y_{2} − 1 \end{matrix} ] \\ & = 2 + 2y_{1} + 2y_{2} \end{aligned}

⇒ y_{2} = [ \begin{matrix}2 \\ 0 \end{matrix} ]; z_{2}(y) = 6

p_{2} = y_{2} − x_{1} = [ \begin{matrix}2 \\ 0 \end{matrix} ] − [ \begin{matrix}0 \\ 1 \end{matrix} ] = [ \begin{matrix}2 \\ −1 \end{matrix} ]

f(x_{1} + ℓ_{1/2}) = f(2ℓ, 1 − ℓ) = 4 + 2ℓ − 6ℓ^{2} = φ(ℓ) φ′(ℓ) = 2 − 12ℓ = 0 ⇒ ℓ = 1/6 x_{2} = (1/3, 5/6)^{T}. Iteration 3: f(x_{2}) = 41/6 ∵ f(x_{k}) ∈ [41/6, 41/2].

∇f(x_{2}) = [ \begin{matrix}1 \\ 2 \end{matrix} ].

Lös

max_{y∈S} z_{3}(y) = f(x_{2}) + ∇f(x_{2})^{T} (y − x_{2}) = 21/6 + y_{1} + 2y_{2}

→ y_{3} = [ \begin{matrix}0 \\ 1 \end{matrix} ] eller [ \begin{matrix}2 \\ 0 \end{matrix} ]; z_{3}(y) = 41/6. ∵ f(x_{2}) = 41/6

Optimum: x_{∗} − (1/3, 5/6)^{T}; f(x_{∗}) = 41/6.

4. Fas I: Inför slackvariabler s_{1}, s_{2}, s_{3} ≥ 0 och artificiella variabler q_{1}, a_{2} ≥ 0. Minimera w = a_{1} + a_{2}. Startbas: s_{1}, a_{1}, a_{2}; w = 7 Basbyte: s_{1}, a_{1}, x_{1} : w = 5/2 Basbyte: s_{1}, x_{2}, x_{3}; w = 0. Red kostn. ≥ 0. Byte till fas II: maximera z = x_{1} − 3x_{2} Startbas: s_{1}, x_{2}, x_{1}; z = −1 Basbyte: s_{3}, x_{2}, x_{1}; z = 0 Red kostn. ≤ 0. x_{∗} = (3, 1)^{T}; z_{∗} = 0.

5a) min w = 500y_{1} + 460y_{2} + 420y_{3}

då \begin{matrix}y_{1} + 3y_{2} + y_{3} ≥ 3 \\ 2y_{1}  + 4y_{3} ≥ 2 \\ y_{2} + 2y_{2}  ≥ 5 \\ y_{1}, y_{2}, y_{3} ≥ 0 \end{matrix}

T.ex.

y = (5, 0, 0)^{T} → w = 2500
y = (3, 1, 0)^{T} → w = 1960
y = (0, 5/2, 1/2)^{T} → w = 1360
x = (460/3, 0, 0) → z = 460
x = (0, 0, 230) → z = 1150
x = (0, 105, 230) → z = 1360

b) ^{∗} = (0, 5/2, 1.2).

I. (Dual tillåtenhet) \begin{matrix}y_{1}^{∗} + 3y_{2}^{∗} + y_{3}^{∗} = 8 > 3 \\ 2y_{1}^{∗} + + 4y_{3}^{∗} = 2 \\ y_{1}^{∗} + 2y_{2}^{∗} = 5 \\ y^{∗} ≥ 0. OK \end{matrix}

II. (Komplementaritet) x_{1}^{∗}(y_{1}^{∗} + 3y_{2}^{∗} + y_{3}^{∗} − 3) = 0 ⇒ x_{1}^{∗} = 0 x_{2}^{∗}(2y_{1}^{∗} + 4y_{3}^{∗} − 2) = 0 → −− x_{3}^{∗}( y_{1}^{∗} + 2y_{2}^{∗} − 5) = 0 → −− y_{1}^{∗}( x_{3}^{∗} + 2x_{2}^{∗} − x_{3}^{∗} − 500) = 0 ⇒ −− y_{2}^{∗}(3x_{1}^{∗} + 2x_{3}^{∗} − 460) = 0 → x_{3}^{∗} = 230 y_{3}^{∗}( x_{2}^{∗} + 4x_{2}^{∗} − 420) = 0 → x_{2}^{∗} = 105. OK

III. (Primal tillåtenhet)

\begin{matrix}x_{1}^{∗} + 2x_{2}^{∗} + x_{3}^{∗} = 440 ≤ 500 OK \\ x^{∗} ≥ 0. Klart \end{matrix}

6 a) For differentierbara funktioner f och konvexa mängder x gäller följande.

x_{∗} lokalt min till f på x ⇒ ∇f(x_{∗})^{T} (x − x_{∗}) ≥ 0 ∀x ∈ X.

Låt x_{∗j} > 0, och välj godtyckligt j ≠ i. Bilda den tillåtna lösningen

x = \{ \begin{matrix}0 & for index i \\ x_{j}^{∗} + x_{i}^{∗} & for index j \\ x_{k}^{∗} & for övriga index k \end{matrix}

Från ovanstående fås då att [\frac{∂f(x^{∗})}{∂x_{j}} − \frac{∂f(x^{∗})}{∂x_{i}}]x_{i}^{∗} ≥ 0, d.v.s.

\frac{∂f(x^{∗})}{∂x_{i}} ≤ \frac{∂f(x^{∗})}{∂x_{j}}.

b) Vi noterar att (1) funktionsberäkningar är dyra, att (2) otillåtenhet är acceptabelt. En möjlig metod är att välja en tillräckligt stor straffparameter för bivilloren och på det obegränsade. Straffade problemet, använda en Newton-likhande descentmetod, där (1) derivator beräknas numeriskt m.h.aḋifferenskvoter, och (2) “Hessianen” justeras så att den är positivt definit.

7 a) KKT-villkoren:

\begin{aligned}∇f(x) − ∑_{i=1}^{m} λ_{i}∇t_{i}(x) & = 0 \\ λ_{i} & ≥ 0, i = 1, …, m \\ λ_{i}g_{i}(x) & = 0, i = 1, …, m \\ g_{i}(x) & ≥ 0, i = 1, …, m \end{aligned}

Dessa är nödvändiga fär lokalt optimum om t.e.xḋet existerar en inre punkt (ett x med g_{i}(x) > 0, ∀i).

De är tillräckliga för globalt optimum om f är konvex och g_{i}, i = 1, …, m, är konkava, d.v.s. problemet är konvext.

Bevis: Låt (x^{∗}, λ^{∗}) uppfylla KKT-villkoren, och välj en godtycklig tillåten lösning, x. Då följer:

f(x) ≥ f(x^{∗}) + ∇f(x^{∗})^{T} (x − x^{∗})  (f konvex)
f(x^{∗}) + ∑_{i=1}^{m} λ_{i}^{∗}∇t_{i}(x)^{∗})^{T} (x − x^{∗})  (KKT 1)
≥ f(x^{∗}) + ∑_{i=1}^{m} λ_{i}^{∗}[g_{i}(x) − g_{i}(x^{∗})]  (g_{i} \begin{matrix}konkava \\ λ^{∗} ≥ 0 \end{matrix} )
= f(x^{∗}) + ∑_{i=1}^{m} λ_{i}^{∗}g_{i}(x)  (λ^{∗} ≥ 0, x tillåten)
≥ f(x^{∗}). ■

b) Den logaritmiska barriärfunktioen är

f(x) − μ ∑_{i=1}^{m} log(g_{i}(x)), μ > 0.

Låt x^{1}, x^{2} vara sådana att g_{i}(x^{1}) > 0, g_{i}(x^{∗}) > 0, ∀i. Välj λ ∈ [0, 1]. g_{i} konkav ⇒ g_{i}(λx^{1} + (1 − λ)x^{2}) ≥ λg_{i}(x^{1}) + (1 − λ)g_{i}(x^{2}) Låt ϕ_{i}(s) = − log(s).

ϕ_{i} är avtagande ⇒ \begin{matrix}ϕ_{i}[g_{i}(λx^{1} + (1 − λ)x^{2}] \\ ≤ \\ ϕ_{i}[λg_{i}(x^{1}) + (1 − λ)g_{i}(x^{2})]. \end{matrix}

ϕ_{i} är strikt konvex ⇒

\begin{matrix}ϕ_{i}[λg_{i}(x^{1}) + (1 − λ)g_{i}(x^{2})] < \\ λϕ_{i}(g_{i}(x^{1})) + (1 − λ)ϕ_{i}(g_{i}(x^{2})), \begin{matrix}λ ∈ (0, 1), \\ g_{i}(x^{1}) + g_{i}(x^{2}) \end{matrix} \end{matrix}

Anledningen att konvexiteten hos barriärfunktionen är av intresse är att den ska minimeras för olika värden på μ: dess stationaritet är tillräcklig för globalt min för funktionen, och stationaritet är vad standardmetoder garanterar.