Lösningar till tentamen TMA946 010305

1 a) På matrisform med slackvariabler s_{1}, s_{2} får vi

\begin{matrix}min z = c^{T} x \\ då & \begin{matrix}Ax = b \\ x ≥ 0 \end{matrix} \end{matrix}

med c^{T} = [−1 2 0 0], b = [ \begin{matrix}1 \\ 1 \end{matrix} ] , x = [x_{1} x_{2} s_{1} s_{2}]

A = [ \begin{matrix}2 & 1 & −1 & 0 \\ 1 & −1 & 0 & 1 \end{matrix} ] .

Då ingen uppenbar bas finnes löser vi fas I med en artificiell variabel tillhörande bivilkor 1. Vi får problemet

max ĉ^{T} x̂
då Âx̂ = b, x̂ ≥ 0
med \begin{matrix}ĉ^{T} = [0 0 0 0 0 1] \\ Â = [A| [ \begin{matrix}1 \\ 0 \end{matrix} ] , x̂ = [x_{1} x_{2} s_{1} s_{2} 9] \end{matrix}

Vi har den uppenbara basen s_{2}, q. Denna bas ger oss B = [ \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ]. Med reducerad kostnad ¯ ĉ får vi

\begin{matrix}¯ĉ = ĉ − ĉ_{B}B^{−1}A \\ = [0 0 0 0 1] − [0 1] [ \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ] [ \begin{matrix}2 & 1 & −1 & 0 & 1 \\ 1 & −1 & 0 & 1 & 0 \end{matrix} ] = [−2 − 1 1 0 0] \end{matrix}

Inkommande blir x_{1}.

Vi beräknar y = B^{−1}A^{x_{1}} = [ \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ] [ \begin{matrix}2 \\ 1 \end{matrix} ] = [ \begin{matrix}1 \\ 2 \end{matrix} ] samt b̄ = B^{−1}b =

[ \begin{matrix}1 \\ 1 \end{matrix} ].

Vi får utgånende som argmin_{i,y_{i}>0} \frac{b̄_{i}}{y_{i}} = 2 Den andra basvariabeln (a) blir utgående. Vi har nu en tillåten bas x_{1}, s_{2}. a är icke-basvar ⇒ a = 0 → vi är klara med fas I. Åter till fas II.

Vår bas x_{1}, s_{2} ger oss B = [ \begin{matrix}2 & 0 \\ 1 & 1 \end{matrix} ] , c_{B}^{T} = [−1 0], B^{−1} = \frac{1}{2} [ \begin{matrix}1 & 0 \\ −1 & 2 \end{matrix} ]

Vi beräknar reducerad kostnad

\begin{matrix}c̄^{T} = c^{T} − c_{B}^{T}B^{−1}A = \\ = [−1 2 0 0] − [−1 0]\frac{1}{2} [ \begin{matrix}1 & 0 \\ −1 & 2 \end{matrix} ] [ \begin{matrix}2 & 1 & −1 & 0 \\ 1 & −1 & 0 & 1 \end{matrix} ] = [0 2.5 − 0.5 0] \end{matrix}

Detta ger oss att s_{1} blir inkommande, ty s_{1} har störst negativ reducerad kostnad.

Vi beräknar y = B^{−1}A^{s_{1}} = \frac{1}{2} [ \begin{matrix}1 & 0 \\ −1 & 2 \end{matrix} ] [ \begin{matrix}−1 \\ 0 \end{matrix} ] = [ −\frac{1}{2}_{\frac{1}{2}} ]

b̄ = B^{−1}b = \frac{1}{2} [ \begin{matrix}1 & 0 \\ −1 & 2 \end{matrix} ] {1 \atop 1} = [ \frac{1}{2} \frac{1}{2} ]

min ratio ger utgående argmin_{i,y_{i}>0} \frac{b̄_{i}}{y_{i}} = 2 Vår andra basvariabel, s_{2} blir utgående. Ny bas blir x_{1}, s_{1}. Beräkna reducerad kostnad

\begin{matrix}(B = [ \begin{matrix}2 & −1 \\ 1 & 0 \end{matrix} ] B^{−1} = [ \begin{matrix}0 & 1 \\ −1 & 2 \end{matrix} ] ) \\ c̄ = c − c_{B}^{T}B^{−1}A = [−1 2 0 0] − [−1 0] [ \begin{matrix}0 & 1 \\ −1 & 2 \end{matrix} ] [ \begin{matrix}2 & 1 & −1 & 0 \\ 1 & −1 & 0 & 1 \end{matrix} ] \end{matrix}

c̄ = [0 0 1 0 1]. c̄ ≥ 0, dvs basen är optimal.

Basvariablernas värde blir [ \begin{matrix}x_{1} \\ s_{1} \end{matrix} ] = B^{−1}b = [ \begin{matrix}0 & 1 \\ −1 & 2 \end{matrix} ] {1 \atop 1} = {1 \atop 1}

Kontroll! Insättning ger

2x_{1} + x_{2} − s_{1} = 2 + 0 − 1 + 0 = 1 OK!
x_{1} − x_{2} + s_{2} = 1 + 0 + 0 = 1 OK!
z = c_{B}^{T}B^{−1}b = −1

b) Beräkna reducerad kostnad (varning för förvirrande c!)

\begin{aligned}c̄ & = c − c_{B}^{T}B^{−1}A = [c 2 0 0] − [c 0] [ \begin{matrix}0 & 1 \\ −1 & 2 \end{matrix} ] [ \begin{matrix}2 & 1 & −1 & 0 \\ 1 & −1 & 0 & 1 \end{matrix} ] \\ c̄ & = [0, 2 + c, 0, −c] \end{aligned}

Vi ser att c̄ ≥ 0 för −2 ≤ c ≤ 0.

Föregående bas är därför optimal för −2 ≤ c ≤ 0.

2 a) x lokalt minimum ⇒ ∇f(x) = 0^{n}

c) Motiv: Antag ∇f(x) ≠ 0^{n}. Låt p = −∇f(x). Då gäller att p^{T} ∇f(x) = −∥∇f(x)∥_{2}^{2} < 0, d.v.s. p är en descentriktning för f i x. Detta motsäger lokal optimalitet.

b) x lokalt minimum ⇒ ∇f(x) = o^{n} och ∇^{2}f(x) positivt semidefinit.

c) Motive: Antag ∇f(x) = 0^{n} och ∇^{2}f(x) indefinit. Då existerar ett p så att ∇^{2}f(x)p = λp, där λ är ett negativt egenvärde och p motsvėgenvecktor. p^{T} ∇^{2}f(x)p = λp^{T} p = λ∥p∥_{2}^{2} < 0 fås. Ur Taylorutvecklingen av f i riktning

p fås att f(x + ℓp) ≈ f(x) + \underbrace{∇f9x)^{T} pℓ}_{=0} +\frac{φ^{2}}{2} \underbrace{p^{T} ∇^{2}f(x)p}_{<0} +O(ℓ^{3}) dvs, f(x +

ℓp) < f(x) för alla små ℓ > 0. Alltså är p en descentiriktning.

3 a)

minimera d^{T} x.
då \begin{matrix}Ax ≥ b \\ c^{T} x ≤ c^{T} x^{∗} \\ x ≥ 0^{n} \end{matrix}

där x^{∗} är en godtycklig optimalllösning till ursprungsproblemet.

b) x^{∗} är en optimalllösning till LP-problemet om det finns en dual lösning y^{∗} ∈ ℝ^{m} så att

i) \begin{matrix}Ax^{∗} ≥ b \\ x^{∗} ≥ 0^{n} \end{matrix} \} Primal tillåtenhet.

ii) \begin{matrix}A^{∗}y^{∗} ≤ c \\ y^{∗} ≥ 0^{m} \end{matrix} \} Dual tillåtenhet.

iii) \begin{matrix}(y^{∗})^{T} (Ax^{∗} − b) = 0 \\ (x^{∗})^{T} (A^{T} y^{∗} − c) = 0 \end{matrix} \} Komplementaritet.

Antag att (x^{∗}, y^{∗}) uppfyller i) - iii). Från i) - ii) fås svag dualitet:b^{T} y^{∗} ≤ c^{T} x^{∗}. Från iii) fås att

b^{t}y^{∗} = (y^{∗})^{T} Ax^{∗} = c^{t}x^{∗}, d.v.s. stark dualitet. Då måste x^{∗} lösa primalen och y^{∗} lösa dualen, eftersom b^{T} y = c^{T} x gäller för alla tillåtna par (x, y) [följdsats].

Antag att x^{∗} är en optimallösning till vårt LP-problem. Speciellt är då i) sann. Angtag att x^{∗} är en optimal extrempunkt. Till den finner då en motsvarande optimal baslösning (x_{B}, x_{N}) ≥ (0, 0). Att denna är optimal innebär att c̄^{T} := c^{T} − c_{B}^{T}B^{−1}A ≥ 0^{T}. För x-variablerna fås särskilt, med (y^{∗})^{T} = c_{B}^{T}B^{−1}, att c̄_{x}^{T} = c_{x}^{T} − (y^{∗})^{T} A ≥ 0^{T}, d.v.s. A^{T} y^{∗} ≤ c. För slackvariablerna fås att c̄_{s}^{T} = 0^{T} − (y^{∗})^{T} I ≥ 0^{T}, d.v.s. y^{∗} ≥ 0. Alltså är y^{∗} := (c_{B}^{T}B^{−1})^{T} tillåten i dualen, så för (x^{∗}, y^{∗}) är också ii) uppfyllt. Återstår iii). Från svag dualitet: b^{T} y^{∗} ≤ (y^{∗})^{T} Ax^{∗} = (x^{∗})^{T} A^{T} y^{∗} ≤ c^{T} x^{∗}. Vi har också c^{T} x^{∗} = c_{B}^{T}x_{B} = c_{B}^{T}B^{−1}b = b^{T} y^{∗}, dvs stark dualitet. Likhet ovan ger iii). Klart [Om x^{∗} ej extrempunkt görs ovanstående för en konvexkombination av optimala extrempunkter.]

4. Vi Lagrangerelaxerar x_{1} + x_{2} ≥ 5 ⇔ x_{1} + x_{2} − 5 ≥ 0 och får α(x, λ) = 2x_{1} + x_{2} − λ(x_{1} + x_{2} − 5). Det duala problemet blir

max_{λ≥0} α_{∗}(λ) = max_{λ≥0}\{ min_{\begin{matrix}0≤x_{1}≤4 \\ 0≤x_{2}≤4 \end{matrix}} 2x_{1} + x_{2} − λ(x_{1} + x_{2} − 5)\}

= max_{λ≥0}{5λ + min_{0≤x_{1}≤4}(2 − λ)x_{1} + min_{0≤x_{2}≤4}(1 − λ)x_{2}}.

För λ = 0, 1, 2, 3 får vi därför

λ = 0 ⇒ x_{1} = 0, x_{2} = 0, α_{∗}(λ) = 0
λ = 0 ⇒ x_{1} = 0, x_{2} =?, α_{∗}(λ) = 5
λ = 2 ⇒ x_{1} =?, x_{2} = 4, α_{α}(λ) = 6
λ = 3 ⇒ x_{1} = 4, x_{2} = 4, α_{∗}(λ) = 3

λ = 2 ger bäst dual lösning. Om x^{∗} är den primalt optimala punkten, så vet vi att α_{∗}(2) ≤ f(x^{∗}), d.v.s. t ≤ f(x^{∗}) för λ = 2 så ser vi att om vi väljer x_{1} = 1 så får vi λg(x) = 0, dvs komplementaritet. Prövar vi med x = [1, 4] så får vi x_{1} + x_{2} ≥ 5, 0 ≤ x_{1,2} ≤ 4 samt f(x) = 6. Då x tillåten vet vi att f(x^{∗}) ≤ f(x) = 6. Vi har därför en övre gräns på 6.

5. Vi definierar variabler:

X_{mni} = Mängd varor av typ i som skickas fån central n till kund m,
Y_{nk} = 1 om vi bygger en central av typ k på plats n, 0 annars.
Z_{mn} = 1 om vi skickar en bil från n till m, 0 annars.
U_{mi} = Mängd behov av vara i som ej tillfredställs hos kund m.
V_{m} = 1 om kund m ej får vad de vill ha, 0 annars.

Vi får målfunktion:

minimera ∑_{m=1}^{M} ∑_{n=1}^{N} ∑_{i=1}^{3} X_{mni}q_{mni} (rörlig transportkostnad)
+ ∑_{m=1}^{M} ∑_{n=1}^{N} Z_{mn}p_{mn} (kostnad för att skicka bilar)
+ ∑_{n=1}^{N} ∑_{k=1}^{K} Y_{nk}d_{k} (kostnad för att bygga centraler)
+ ∑_{m=1}^{M} ∑_{i=1}^{3} U_{mi}s_{i} (rörligt straff för att ej uppfylla behov)
+ ∑_{m=1}^{M} V_{m}t (fast straff för att ej uppfylla behov)

Då

∑_{m=1}^{M} x_{mni} ≤ ∑_{k=1}^{K} Y_{nk}d_{ki}, ∀n, i

(vi får ej skicka för mycket från våra centraler)

∑_{k=1}^{K} Y_{n}k ≤ 1 ∀n

(max en central per plats)

X_{mni} ≤ Z_{mn}b_{mi} ∀m, n, i

(vi måste skicka en bil om vi skall transporterna något)

∑_{n=1}^{N} X_{mni} + U_{mi} ≥ b_{mi} ∀m, i

(vi måste tillgodose kundens behov eller ta straffet.)

U_{mi} ≤ b_{mi}V_{m} ∀m, i

(om kunden ej får vad de vill ha måste vi betala det fasta straffet.)

6. Iteration 1: x^{0} = (0, 0)^{T}. f(x^{0}) = 0. [LBD, UBD] = (−∞, 0]. ∇f(x^{0}) = (−24, −20). Lös min_{y∈X} ∇f(x^{0})^{T} y = −24y_{1} − 20y_{2}. Optimum i y_{LP}^{0} = (6, 2)^{T}. f är konvex, så f(x^{0}) + ∇f(x^{0})^{T} (y_{LP}^{∗} − x^{0}) = 0 + (−24, −20)(6, 2) = −172 ≤ f^{∗}. [LBD, UBD] = [−172, 0]. Sökriktning: p^{0} = y_{LP}^{0} − x^{0} = (6, 2)^{T}.

Linjesökning: min_{ℓ∈[0,1]} f(x^{0} + ℓpp^{0}) = f [ \begin{matrix}6ℓ \\ 2ℓ \end{matrix} ] = … = 80ℓ^{2} − 184ℓ = φ(ℓ).

φ′(ℓ) = 160ℓ − 184 = 0 → ℓ = 184/160 > 1 ⇒ Sätt ℓ_{0} = 1. x^{1} = x^{0} + ℓ_{o}p^{0} = (6, 2)^{T}. Iteration 2: f(x^{1}) = φ(1) = −104. [LBD, UBD] = [−172, −104]. ∇f(x^{1}) = (0, −12)^{T}. Lös min_{y∈X} ∇f(x^{0})^{T} y = −12y_{2}. Optimum i y_{LP}^{2} = /(t.ex.)/ = (2, 6)^{T}. f(x^{0}) + ∇f(x^{1})^{T} (y_{LP}^{1} − x^{1}) = −104 + (0, −12)((2, 6)^{T} − (6.2)) = −152. [LBD, UBD] = [−152, 104]. Sökriktning: p^{1} = y_{LP}^{T} − x^{1} = (−4, 4)^{T}. Linjesökning min_{ℓ=[0,1]} f(x^{1} + ℓp^{1}) = f((6 − 4ℓ, 2 + 4ℓ)^{T}) = … = 64ℓ^{2} − 48ℓ − 104 = φ(ℓ). φ′(ℓ) = 128ℓ − 48 = 0 → ℓ_{1} = 3/8. x^{2} = x^{1} +ℓ_{1}p^{1} = (9/2, 7/2)^{T}. f(x^{2}) = −113. [LBD, UBD] = [−152, −113].

7 a) T (f) = ∑_{a∈d} ∫_{0}^{f_{a}} t_{a}(s)ds →

∇T (f) = t(f), där t är vektorn och element t_{a}. Eftersom t är monoton (t_{a} är strikt växande), så är integralen av t, dvs T, konvex.

b) Om (3b) insätts i ingegralen, dvs f_{a} elimineras, fås problemet att minimera

∑_{a∈d} ∫_{0}^{∑_{r,r} ∑_{r} δ_{ra}h_{r}} t_{a}(s)ds,

då \begin{matrix}∑_{r} h_{r} = d_{rq}, ∀Ip, q), \\ h_{r} ≥ 0, ∀r, ∀(p, q) \end{matrix} | π_{pq} Lagr.mult. γ_{r}

KKT:

1. Dual tillåatenhet: ∇_{h}L(h, n̄, γ) = 0, γ ≥ 0

2. Komplementaritet: h_{r} · γ_{r} = 0 ∀r

3. Primal tillåtenhet: h_{r} ≥ 0, Σh_{r} = d_{pq} ∀c(p, q)

L(h, π, γ) = ∑_{a∉A} ∫_{0}^{∑_{(p,q)} ∑_{r} δ_{ra}h_{r}} t_{a}(s)dr− ∑_{(r+q)} π_{pq}(∑_{r} h_{r}−d_{pq})−∑_{(p,q)} ∑_{r} γ_{r}h_{r}

\underline{γ_{r} = c_{r}(h) − n̄_{pq}}. ∵ γ_{r} ≥ 0 ⇔ \underline{c_{r}(h) ≥ π_{pq}∀(p, q)} (nr.1) nr 2: \underline{h_{r} · (c_{r}(h) − π_{pq}) = 0}, ∀(p, q). Detta är precis Wardges villkor (2a)- (2b) i tesen, och 3 motsvaras av kravet (1) i tesen.