Tentamen TMA045 Tillämpad optimering 000524

1 a) Betrakta problemet

\begin{matrix}min z = 2x_{1} + x_{2} \\ då & \begin{matrix}3x_{1} + 2x_{2} ≥ 3 \\ x_{2} ≤ 1 \\ x_{1}, x_{2} ≥ 0 \end{matrix} \end{matrix}

Skriv på standardform med hjälp av slackvariabler s_{1} och s_{2}

\begin{matrix}min z = 2x_{1} + x_{2} \\ då & \begin{matrix}3x_{1} + 2x_{2} − s_{1} = 3 \\ x_{2} + s_{2} = 1 \\ x_{1}, x_{2}, s_{1}, s_{2} ≥ 0 \end{matrix} \end{matrix}

Inför en artificiell variabler i bivillkor 1 för att lösa fas-I problemet och hitta en tillåten bas till fas-II.

\begin{matrix}min w = a_{1} \\ då & \begin{matrix}3x_{1} + 2x_{2} − s_{1} + a_{1} = 3 \\ x_{2} + s_{2} = 1 \\ x_{1}, x_{2}, s_{1}, s_{2}a_{1} ≥ 0 \end{matrix} \end{matrix}

Ställ upp simplextablån med basen s_{1}, a_{1}

x_{1} x_{2} s_{1} s_{2} a_{1}
0 0 0 0 1 0 ← −1
a_{1} 3 2 −1 0 1 3  samt genomför
s_{2} 0 1 0 1 0 1  “price out”
x_{1} x_{2} s_{1} s_{2} a_{1} −w
−3 −2 1 0 0 −3 ← 3 Vi väljer x_{1} som inkommande
a_{1} 3 2 −1 0 1 3 ← 13 pga mest negativ reducerad kostnad.
s_{2} 0 1 0 1 0 1  MR-test ger a_{1} utgående

x_{1} x_{2} s_{1} s_{2} −w
0 0  0  0 0 Stryk a_{1} och sätt in
x_{1} 1 2/3 −1/3 0 1 Z som målfunktion.
s_{1} 0 1  0  1 1

x_{1} x_{2} s_{1} s_{2} −z  Genomför “Price out” vilket
2 1  0  0 0 ← −2 är ekvivalent med att
x_{1} 1 2/3 −1/3 0 1  ersätta kostnadsraden
s_{1} 0 1  0  1 1  med c − c_{B}^{T}B^{−1}A

x_{1} x_{2}  s_{1} s_{2} −z
0 −1/3 2/3 0 −2 ← 1/3 Välj x_{2} som inkommande
x_{1} 1 2/3 −1/3 0 1 ← −2/3 (p.g.aṁest negativ reducerad
s_{1} 0  1  0  1 1  kostnad). Utgående blir s_{1}

x_{1} x_{2} s_{1}  s_{2}  −z Optimal ty inga
0 0 2/3 1/3 −5/3 negativa reducerande
x_{1} 1 0 −1/3 −2/3 1/3 kostnader. Optimal
x_{2} 0 1  0  1  1 punkt x_{1} = 1/3, x_{2} = 1, z = 5/3

Kontroll! Sätt in i ursprungsproblem.

z = 2x_{1} + x_{2} = 2 · 1/3 + 1 = 5/3 OK
Bivilk. 1 Bivilk. 2 \begin{matrix}3x_{1} + 2x_{2} = 3 · 1/3 + 2· ≥ 3 OK \\ x_{2} = 1 ≥ 1 OK \\ x_{1}, x_{2} ≥ 0 OK \end{matrix}

b) Titta på dualvariablerna till problemet

\begin{matrix}min 2x_{1} + x_{2} \\ då & \begin{matrix}3x_{1} + 2x_{2} − s_{1} = 3 \\ x_{2} + s_{2} = 1 \\ x_{1}, x_{2}, s_{1}, s_{2} ≥ 0 \end{matrix} \end{matrix}

Den optimala basen var x_{1}, x_{2} ⇒ basmatris B = [ \begin{matrix}3 & 2 \\ 0 & 1 \end{matrix} ]

⇒ B^{−1} = \begin{matrix}1/3 & −2/3 \\ 0 & 1 \end{matrix} y = c_{B}^{T}B^{−1} = [2 1] [ \begin{matrix}1/3 & −2/3 \\ 0 & 1 \end{matrix} ] = 2/3 − 1/3

Detta ger att då vi ändrar högerledet med α [ \begin{matrix}1 \\ 2 \end{matrix} ] ändras mållfunktionens värde med y α [ \begin{matrix}1 \\ 2 \end{matrix} ] = 0, under förutsättning att vi ej byter bas. Högerledet med bas

x_{1}, x_{2} = B^{−1}b(α) = B^{−1}( [ \begin{matrix}3 \\ 1 \end{matrix} ] + α [ \begin{matrix}1 \\ 2 \end{matrix} ] ) = [ \begin{matrix}1/3 \\ 1 \end{matrix} ] + α [ \begin{matrix}−1 \\ 2 \end{matrix} ]

Vi ser att B^{−1}b(α) ≥ 0. För −\frac{1}{2} ≤ α ≤ \frac{1}{3} för α < −\frac{1}{2} blir problemet olösligt då vi får kraven

x_{2} ≤ 1 + 2α, x_{2} ≥ 0

för α > \frac{1}{3} får vi en ny bas. Sätt α = 1 och lös grafiskt

min z = 2x_{1} + x_{2} ; \begin{matrix}då 3x_{1} + 2x_{2} ≥ 3 + 1(−1) = 2 \\ x_{2} ≤ 1 + 1 · (2) = 3 \\ x_{1} − x_{2} = 0 \end{matrix}

Ur grafen ser man att nybas blir x_{2}, s_{2} då dessa är nollskillda. Vi gör samma beräkning som tidigare

\begin{matrix}B = [ \begin{matrix}2 & 0 \\ 1 & 1 \end{matrix} ] ⇒ B^{−1} = \frac{1}{2} [ \begin{matrix}1 & 0 \\ −1 & 2 \end{matrix} ] \\ y = c_{B}^{T}B^{−1} = [1 0]\frac{1}{2} [ \begin{matrix}1 & 0 \\ −1 & 2 \end{matrix} ] = [1/2 0] \end{matrix}

Kostnadsförändringen då vi ändrar α blir därmed [1/2 0]α [ \begin{matrix}1 \\ 2 \end{matrix} ] = 1/2α

Vi har b̄ = B^{−1}b(α) = \frac{1}{2} [ \begin{matrix}1 & 0 \\ −1 & 2 \end{matrix} ] ( [ \begin{matrix}3 \\ 1 \end{matrix} ] + α [ \begin{matrix}1 \\ 2 \end{matrix} ] ) = [ −\frac{1}{2}^{\frac{3}{2}} ] +

α [ \frac{1}{2} \frac{3}{2} ] B^{−1}b(α) ≥ 0 för α ≥ \frac{1}{3} och basen x_{2}, s_{2} är därmed optimal för α ≥ \frac{1}{3}

z(α) för α ≥ \frac{1}{3} är c_{B}^{T}B^{−1}b(α) − [1 0]( −\frac{1}{2}^{\frac{3}{2}} + α [ \frac{1}{2} \frac{3}{2} ] ) = \frac{3}{2} + \frac{α}{2}

Därmed har vi

z(α) = \{ \begin{matrix}α, & α < −\frac{1}{2} \\ 5/3, & −\frac{1}{2} ≤ α ≤ \frac{1}{3} \\ \frac{3}{2} + \frac{α}{2}, & \frac{1}{3} < α \end{matrix} \}

2 a) Den totala kostnaden per behandlad maskindel minimeras genom att lösa

minimera K(N, f) := 520[\frac{42}{60Nf} + 0.1\frac{N^{5.667}f^{3}}{5^{6.667}} ] + 870\frac{42N^{5.667}f^{3}}{5^{6.667}}

då \begin{matrix}200 ≤ N ≤ 600 \\ 0.001 ≤ f ≤ 0.005 \end{matrix}

b)

∂K/∂N = 520( − \frac{42}{60N^{f}} + 0.5667\frac{N^{4.667}f^{3}}{5^{6.667}} ) + 870 · 5.667 · \frac{42N^{4.667}f^{3}}{5^{6.667}}

∂K/∂f = 520( − \frac{42}{60Nf^{2}} + 0.3\frac{N^{5.667}f^{2}}{5^{6.667}} ) + 870 · 3 · \frac{42N^{5.667}f^{2}}{5^{6.667}}

Låt (N, f) = (200, 0.001); ∇K(N, f) ≗ [ \begin{matrix}239.5642 \\ 2.45˙10^{7} \end{matrix} ].

Sätter man upp KKT för problemet och observerar att de enda aktiva bivillkoren är de undre gränserna finner man att Lagrange multiplikatorerna är lika med ∇K(N, f), som är en positiv vektor. Alltså uppfylls KKtvillkoren.

3 a) f(x) := −5x_{1}+x_{1}^{2}−8x_{2}+2x_{2}^{2}; ∇f(x) = ( \begin{matrix}−5 + 2x_{1} \\ −8 + 4x_{2} \end{matrix} ]; ∇^{2}f(x) = [ \begin{matrix}2 & 0 \\ 0 & 4 \end{matrix} ]

∇^{2}f(x) är positivt definit för alla x (speciellt alla tillåtna x) så f är en (strikt) konvexfunktion. För konvexa och kontinuerligt differentierbara funktioner på en konvex mängd X gäller att (x^{∗} är optimal):

f(x) ≥ f(x^{∗}) ≥ f(x) + ∇f(x)^{T} (x^{∗} − x) ≥ f(x) + min_{y∈X}{∇f(x)^{T} (y − x)}.

d.v.s. det optimala målfunktionsvärdet tillhör intervallet [f(x)+min_{y∈X}{∇f(x)^{T} (y− x)}, f(x)] för varje x ∈ X.

Iteration 1: x^{0} = [ \begin{matrix}0 \\ 0 \end{matrix} ]; f(x^{0}) = 0; ∇f(x^{0}) = [ \begin{matrix}−5 \\ −8 \end{matrix} ].

Lös min_{y∈X} φ^{0}(y) := f(x^{0}) + ∇f(x^{0})^{T} (y − x^{0}) = −5y_{1} − 8y_{2} = −24

för y^{0} = [ \begin{matrix}0 \\ 3 \end{matrix} ]. f^{∗} ∈ [−24, 0]. p^{0} = y^{0} − x^{0} = [ \begin{matrix}0 \\ 3 \end{matrix} ]. x_{ℓ} =

x^{0} + ℓp^{0} = ℓ · [ \begin{matrix}0 \\ 3 \end{matrix} ], ℓ ∈ [0, 1] tillåtna steg.

f(x_{ℓ}) = −24ℓ + 28ℓ^{2} =′′ ψ^{0}(ℓ) ψ′^{0}(ℓ) = 36ℓ − 24 = 0 ⇒ ℓ = 2/3 ≤ 1. Med ℓ = 2/3 :

Iteration 2: x^{1} = x^{0} + 2/3p^{0} = [ \begin{matrix}0 \\ 2 \end{matrix} ]; f(x^{1}) = ψ(2/3) = −8; ∇(x^{1}) = [ \begin{matrix}−5 \\ 0 \end{matrix} ].

Lös min_{y∈X} φ^{1}(y) := f(x^{1})+∇f(x^{1})^{T} (y−x^{1}) = −8−5y_{1} = −18 för y^{1} =

[ \begin{matrix}2 \\ 0 \end{matrix} ]. f^{∗} = [−18, −8]. p^{1} = y^{1} − x^{1} = [ \begin{matrix}2 \\ 0 \end{matrix} ] − [ \begin{matrix}0 \\ 2 \end{matrix} ] = [ \begin{matrix}2 \\ −2 \end{matrix} ].

x_{ℓ} = x^{1} + ℓp^{1} = [ \begin{matrix}0 \\ 2 \end{matrix} ] + ℓ([ \begin{matrix}2 \\ −2 \end{matrix} ] = [ \begin{matrix}2ℓ \\ 2 − 2ℓ \end{matrix} ] , ℓ ∈ [0, 1].

f(x_{ℓ}) = −10ℓ + 4ℓ^{2} − 16 + 16ℓ + 8 − 16ℓ + 8ℓ^{2} = −8 − 10ℓ + 12ℓ^{2} =: ψ^{1}(ℓ) ψ′^{1}(ℓ) = −10 + 24ℓ = 0 → ℓ = \frac{5}{12} ≤ 1. Med ℓ = \frac{5}{12} : x^{2} =

x^{1} + \frac{5}{12}p^{1} = [ \begin{matrix}5/6 \\ 7/6 \end{matrix} ]; f(x^{2}) = −\frac{121}{12}.

∵ f^{∗} ∈ [−18, −\frac{121}{12}] 3 b) Om polyedern X inte är begränsad är det inte garanterat att min_{y∈x}{∇f(x)^{T} (y−

x)} har en ändlig optimallösning för alla x ∈ X. Om simplexmetoden användes kommer i så fall en extremriktning p i x_{0} med egenskapen av ∇f(x)^{T} p < 0, att identifieras. Givet ett aktuellt iterat x^{k}, om vi identifierar en sådan extremriktning, p^{k}, förändras algoritmen som följer:

1. p^{k} är en descentriktning, ty ∇f(x^{k})^{T} p^{k} < 0. Utför en linjesökning i riktningen p^{k}, där steglängden här får vara obegränsat stor.

2. Den undre gränsen kommer att bli −∞ i denna iteration. Den enda effekten av det är att den bästa känka undre gränsen inte kommer att uppdateras.

Då x är begränsad är det garanterat att problemet har en optimal lösning (Weierstrass sats). Om X är obegränsad måste målfunktionen ha någon ytterligare egenskap, bland annat måste den vara nedåt begränsad på X. För att säkerhetställa att linjesökningarna kommer att ge en lösning måste vi till och med kräva att f antar ett minsta värde längs varje möjlig riktning, och det garanteras t.exȯm f har egenskapen att f(x) → ∞ då ∥x∥ → ∞.

(Ett exempel ges av uppgiften, om bivillkoret 3x_{1} + 2x_{2} ≤ 6 stryks.)

5 a) Falskt ty det finns LP-problem som saknar tilåtna lösningar och det finns LP-problem som saknar ändliga optimala lösningar.

b) Falskt via motexempel: ingen avrundning (uppåt elleer nedåt) är ens tillåten; inte ens den närmaste tillåtna punkten är optimal! c) Falskt om inte f är konvex:

Här är x^{∗} ett globalt min, där g(x^{∗}) = x^{∗} < b. Men om bivilkoret tas bort är x̂ ett globalt min och f(x̂) < f(x^{∗}), så bivillkoret är inte redundant.

6.

\begin{aligned}f(x) & = 0.1x_{1}x_{2} + 0.01(x_{1} − 2)^{4} + 0.009(x_{2} − 5)^{4}; \\ ∇f(x) & = [ \begin{matrix}0.04(x_{1} − 2)^{3} + 0.1x_{2} \\ 0.037(x_{2} − 5)^{3} + 0.1x_{1} \end{matrix} ] \\ ∇^{2}f(x) & = [ \begin{matrix}0.12(x_{2} − 2)^{2} & 0.1 \\ 0.1 & 0.111(x_{2} − 5)^{2} \end{matrix} ] \end{aligned}

a) x^{0} = (3, 7)^{T}; ∇f(x^{0}) = (0.74, 0.596)^{T}; p^{0} = (−0.74, −0.596)^{T} x_{ℓ} = x^{0} + ℓp^{0}

\begin{matrix}ℓ & 0 & 0.5 & 1 & 1.5 & 2 & 2.5 & 3 & 3.5 & 4 & 4.5 & 5 & … \\ f(x_{ℓ}) & 2.25 & 1.81 & 1.38 & 0.95 & 0.56 & 0.27 & 0.196 & 0.46 & 1.26 & 2.78 & 5.29 & … \end{matrix}

Sätt ℓ = 0.5, detta ger x^{1} = (−0.1072, 7.0286)^{T} , f(x^{0}) = 0.196 Optimum: x^{∗} ≈ (−0.48, 6.1)^{T}; f(x^{∗}) ≈ 0.1

7. Antag att x_{j^{∗}}^{∗} = 0 för varje optimal lösning till (P). Låt z^{∗} vara det optimala värdet för (P) [och (D)]. Motsvarande duala optimala slack t_{j}^{∗} = 0 om och endast om

max e_{j}^{T} t
då \begin{matrix}−b^{T} y ≤ −z^{∗} \\ y ≥ 0, t ≥ 0 \end{matrix} (e_{j} = j : te enhetsvektorn)

har optimalt målfunktionsvärde 0. Men via stark dualitet gäller då att

\begin{matrix}min c^{T} x − λz^{∗} \\ då & \begin{matrix}Ax − λb ≥ 0 \\ x ≥ e_{j} \\ λ ≥ 0 \end{matrix} \end{matrix}

har en optimal lösning med c^{T} x − λz^{∗} = 0. Om λ = 0 gäller att c^{T} x = 0, Ax ≥ 0, x ≥ e_{j} har en lösning. Alltså finns en optimal lösning med x_{j}^{∗} ≥ 1. Om λ > 0 gäller att c^{T} x = z^{∗}, Ax ≥ b, x ≥ λe_{j} har en lösning, d.v.s. återigen har vi en optimal lösning med x_{j}^{∗} > 0.

Vi låter ur (x^{∗}(j), s^{∗}(j)) och (y^{∗}(j), t^{∗}(j)) vara optimala lösningar motsvarande paret (x_{j}^{∗}, t_{j}^{∗}) som är strikt komplementärt, och på samma sätt (x^{∗}(n + i), s^{∗}(n + i)) och (y^{∗}(n + i), t^{∗}(n + i)) för ett par (y ∗ ∗_{i}, s_{i}^{∗}) [via symmetri]. Med vikterna \frac{1}{m+n} bildar sedan konvexkonbinationen av dessa, vilket är den sökta lösningen.