Lösningsförslag till tentamen TMA946/MAN280 Tillämpad optimeringslära 010523

1 a) Inför slackvariabler

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

Inför en artificiell variabel och lös fas I

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

På matrisform:

min a

då [ \begin{matrix}2 & 1 & −1 & 0 & 1 \\ −1 & 1 & 0 & 1 & 0 \end{matrix} ] [ \begin{matrix}x_{1} \\ x_{2} \\ s_{1} \\ s_{2} \\ a \end{matrix} ] = [ \begin{matrix}3 \\ 2 \end{matrix} ]

[ \begin{matrix}min c^{T} x \\ Då Ax = b \end{matrix} ]

Välj a, s_{2} som bas

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

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

c̄^{T} = [−2 − 1 1].

Lägst reducerad kostnad har x_{1} → x_{1} blir inkommande.

gör min ratio test. y = B^{−1}A_{ink} = [ \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ] [ \begin{matrix}2 \\ −1 \end{matrix} ] = [ \begin{matrix}2 \\ −1 \end{matrix} ]

utg = argmin_{k,k>0} \frac{(B^{−1}b)k}{y_{k}} ⇒ första basvariabeln

är utgående c är första basvar) Vi får ny bas s_{2}, x_{2}. Då a ej är kvar i basen har vi a = 0 ⇒ vi har en tillåten bas. Åter till ursprungsproblemet.

\begin{matrix}min 2x_{1} − x_{2} \\ Då [ \begin{matrix}2 & 1 & −1 & 0 \\ −1 & 1 & 0 & 1 \end{matrix} ] [ \begin{matrix}x_{1} \\ x_{2} \\ s_{1} \\ s_{2} \end{matrix} = [ \begin{matrix}3 \\ 2 \end{matrix} ] \end{matrix}

Vi har basen x_{1}, s_{2} ⇒

\begin{aligned}c_{B}^{T} & = [2 0]B = [ \begin{matrix}2 & 0 \\ −1 & 1 \end{matrix} ] B^{−1} = \frac{[ \begin{matrix}1 & 0 \\ 1 & 2 \end{matrix} ]}{2}c_{N}^{T} = [ \begin{matrix}(x_{2} s_{1}) \\ [ − 1 0] \\ B^{−1}b = \frac{1}{2} [ \begin{matrix}3 \\ 7 \end{matrix} ] \end{matrix} ] \\ c̄^{T} & = c_{N}^{T} − c^{T} BB^{−1}N = [−1 0] − [2 0]\frac{1}{2} [ \begin{matrix}1 & 0 \\ 1 & 2 \end{matrix} ] [ \begin{matrix}1 & −1 \\ 1 & 0 \end{matrix} ] = [−3 2] \end{aligned}

⇒ x_{2} blir inkommande.

y = B^{−1}A_{ink} = \frac{1}{2} [ \begin{matrix}1 & 0 \\ 1 & 2 \end{matrix} ] [ \begin{matrix}1 \\ 1 \end{matrix} ] = \frac{1}{2} [ \begin{matrix}2 \\ 3 \end{matrix} ]

Gör min ratio, ut = argmin_{k,y_{k}>0} \frac{(B^{−1}b)_{k}}{y_{k}} ⇒ ut = 2ty \frac{7}{3} < 3 ⇒ basvar 2, dvs s_{2} är utgående. Ny bas x_{1}, x_{2}

c_{B}^{T} = [2 − 1]B = [ \begin{matrix}2 & 1 \\ −1 & 1 \end{matrix} ] c_{N}^{T} − [0 0]B^{−1} = \frac{1}{3} [ \begin{matrix}1 & −1 \\ 1 & 2 \end{matrix} ]
B^{−1}b = \frac{1}{3} [ \begin{matrix}1 \\ 7 \end{matrix} ]

c̄^{T} = c_{N}^{T} − c_{B}^{T}B^{−1}N = [0 0] − [2 − 1]\frac{1}{3} [ \begin{matrix}1 & −1 \\ 1 & 2 \end{matrix} ] [ \begin{matrix}−1 & 0 \\ 0 & 1 \end{matrix} ] = \frac{1}{3}[1 4]

c̄^{T} ≥ 0 ⇒ basen är optimal. Vi får

x_{B} = B^{−1}b = \frac{1}{3} [ \begin{matrix}1 \\ 7 \end{matrix} ] , s_{1}, s_{2} = 0.

med z = c_{B}^{T}B^{−1}b = [2 − 3]\frac{1}{3} [ \begin{matrix}1 \\ 7 \end{matrix} ] = \frac{−5}{3}

Kontroll:

2x_{1} + x_{2} = 2 · \frac{1}{3} + \frac{7}{3} = \frac{9}{3} = 3 ≥ 3 OK med s_{1} = 0
−x_{1} + x_{2} = −\frac{1}{3} + \frac{7}{3} = \frac{6}{3} = 2 ≤ 2 OK med s_{2} = 0.

b) Ersätt första högerledet med α. Vi får

\begin{aligned}v(α) & = c_{B}^{T}B^{−1}b = [2 − 1]\frac{1}{3} [ \begin{matrix}1 & −1 \\ 1 & 2 \end{matrix} ] [ \begin{matrix}α \\ 2 \end{matrix} ] \\ & = \frac{1}{3}[1 − 4] [ \begin{matrix}α \\ 2 \end{matrix} ] = \frac{1}{3}(α − 8) \end{aligned}

Kontroll: för α = 3 (tidigare problemet) får vi z = \frac{1}{3}(3 − 8) = \frac{−5}{3} OK!. Då c^{−T} ej påverkas av b är basen fortsatt optimal om den är fortsatt tillåten.

B^{−1} [ \begin{matrix}α \\ 2 \end{matrix} ] = \frac{1}{3} [ \begin{matrix}α − 2 \\ α + 4 \end{matrix} ] > 0 i en omgivining av α = 3.

högerderivatan är därmed det samma som derivatan: \frac{d}{dα}v(α) = \frac{1}{3}.

2. x = [x_{1}, x_{2}, x_{3}, x_{4}]^{T}

Vi har [ \begin{matrix}min[1.5 1 2 1]x \\ då [ \begin{matrix}[ & \begin{matrix}1 & 0 & 1 & 1 \\ 0 & 1 & 1 & −1 \end{matrix} & ] \\ & x ≥ 0 \end{matrix} ] x ≥ [ \begin{matrix}1 \\ 0.1 \end{matrix} ] \end{matrix} ]

Duala problemet blir

( min [ \begin{matrix}c^{T} x \\ Ax ≥ b \\ x ≥ 0 \end{matrix} ] primalt blir [ \begin{matrix}max b^{T} y \\ A^{T} y ≤ c \\ y ≥ 0 \end{matrix} ] dualt)

[ \begin{matrix}max y_{1} + 0.142 \\ då [ \begin{matrix}[ & \begin{matrix}1 & 0 \\ 0 & 1 \\ 1 & 1 \\ 1 & −1 \end{matrix} & ] \\ & y ≥ 0 \end{matrix} ] [ \begin{matrix}y_{1} \\ y_{2} \end{matrix} ] ≤ [ \begin{matrix}1.5 \\ 1 \\ 2 \\ 1 \end{matrix} ] \end{matrix} ]

Ritar vi upp detta får vi

Vi söker max y_{1} + 0.1 + y_{2} och får optimum i punkten y = (1.5, 0.5). Vi ser att alla duala bivillkor utom no 2 binder. Då det andra duala villkoret ej binder vet vi att x_{2} = 0. Vidare har vi y_{1}, y_{2} > 0 varför de primala villkoren binder.

Optimala mängden ges alltså av lösningen till

\begin{matrix}[ \begin{matrix}1 & 1 & 1 \\ 0 & 1 & −1 \end{matrix} ] [ \begin{matrix}x_{1} \\ x_{3} \\ x_{4} \end{matrix} ] = [ \begin{matrix}1 \\ 0.1 \end{matrix} ] \\ ⇒ [ \begin{matrix}x_{1} \\ x_{3} \\ x_{4} \end{matrix} ] = α [ \begin{matrix}0 \\ 0.55 \\ 0.45 \end{matrix} ] + (1 − α) [ \begin{matrix}0.9 \\ 0.1 \\ 0 \end{matrix} ] c ≤ α ≤ 1 \end{matrix}

b) Vi vet att x_{2} är en icke basvar (ty motsvarande duala villkor binder ej). Kvar finns x_{1}, x_{3}, x_{4} med möjliga baser x_{1}x_{3} x_{1}x_{4} x_{3}x_{4}

x_{1}x_{4} ger B = [ \begin{matrix}1 & −1 \\ 0 & −1 \end{matrix} ] ⇒ B^{−1} = [ \begin{matrix}1 & 1 \\ 0 & −1 \end{matrix} ] ⇒ B^{−1}b = [ \begin{matrix}1.1 \\ −0.1 \end{matrix} ] ≱ 0

⇒ x_{1}, x_{4} ej optimal bas.

x_{1}x_{3} ger B = [ \begin{matrix}1 & 1 \\ 0 & 1 \end{matrix} ] B^{−1} = [ \begin{matrix}1 & −1 \\ 0 & 1 \end{matrix} ] ⇒ B^{−1}b = [ \begin{matrix}0.9 \\ 0.1 \end{matrix} ]

⇒ x = [0.9 0 0.1 0] optimal bas enligt ovan.

x_{3}x_{4} ger B = [ \begin{matrix}1 & 1 \\ 1 & −1 \end{matrix} ] ⇒ B^{−1} = \frac{1}{2} [ \begin{matrix}1 & 1 \\ 1 & −1 \end{matrix} ] ⇒ B_{b}^{−1} = [ \begin{matrix}0.55 \\ 0.45 \end{matrix} ]

⇒ x = [0 0 0.55 0.45] optimal enligt ovan. Ökar vi c_{1} till 1.6 kan vi se i figuren att bivillkor 1 slutar att binda, varför vi får att x_{1} = 0 i en optimal lösning, och den optimala basen blir x_{3}x_{4} samt den optimala mängden x = [0 0 0.55 0.45].

3) Vi definierar index: i, i = 1 … 3 Nummer på arbetsplats. k, k = 1 … 2 Nummer på telejack. Samt variabler x_{i}, y_{i} Koordinater för arbetsplats i. t_{i,k} Indikatorvariabel, värdet är 1 om arbetsplats i är ansluten till jack

k. z Längsta avståndet till fönstret. Vi får problemet : Minimera avståndet för sämsta arbetsplatsen:

min z  (1)

Då arbetsplatserna finns i rummet:

\frac{d}{2} ≤ x_{i} ≤ l − \frac{d}{2}, ∀i = 1 … 3  (2)
\frac{d}{2} ≤ y_{i} ≤ b − \frac{d}{2}, ∀i = 1 … 3  (3)

Då arbetsplatserna ej inkräktar på varandra:

(x_{i} − x_{j})^{2} + (y_{i} − y_{j})^{2} ≥ d^{2}, ∀i = 1 … 3, ∀j = 1 … 3, i ≠ j  (4)

Då sladden räcker:

t_{1,k}((x_{i} − \frac{l}{2})^{2} + (y_{i} − 0)^{2}) ≤ a_{i}^{2}, ∀i = 1 … 3  (5)
t_{2,k}((x_{i} − l)^{2} + (y_{i} − \frac{b}{2})^{2}) ≤ a_{i}^{2}, ∀i = 1 … 3  (6)

Vi måste ansluta varje arbetsplats till exakt ett telejack:

t_{i,1} + t_{i,2} = 1, ∀i = 1 … 3  (7)
t_{i,k} ∈ {0, 1} ∀i = 1 … 3, ∀k = 1, 2  (8)

Vi skall se till att z är längre än avståndet till fönstret för den sämsta arbetsplatsen:

b − y_{i} ≥ z, ∀i = 1 … 3  (9)

Hela uppgiften blir då minimera (1) under uppfyllande av (2) - (9) .

4a) Se figuren nedan. b)

\frac{z^{∗} − z^{H}}{z^{∗}} ≤ \frac{z̄ − z^{H}}{z^{∗}} ≤ \frac{z̄ − z^{H}}{z^{H}} = \frac{98 − 88}{88} ≈ 0.114

5a) Problem:

Minimera ∑_{j=i}^{n} f_{j}(x_{j})

Då [ \begin{matrix}∑_{j=1}^{n} x_{j} = k & | & α^{∗} \\ & | \\ x_{j} ≤ 1, ∀j & | & β_{j}^{∗}, ∀j \\ & | \\ x_{j} ≥ 0, ∀j \end{matrix}

KKT-villkoren kan sammanfattas som följer: För varje j = 1, …, n gäller att

x_{j}^{∗} = 0 ⇒ f′_{j}(x_{j}^{∗}) ≥ α^{∗} och β_{j}^{∗} = 0
x_{j}^{∗} ∈ (0, 1) ⇒ f′_{j}(x_{j}^{∗}) = α^{∗} och β_{j}^{∗} = 0
x_{j}^{∗} = 1 ⇒ f;_{j} (x_{j}^{∗}) ≤ α^{∗} och \{ \begin{matrix}f′_{j}(x_{j}^{∗}) + β_{j}^{∗} = α^{∗}, \\ β_{j}^{∗} ≥ 0 \end{matrix} ]

Dessutom: ∑_{j=1}^{n} x_{j}^{k} = k.

Lagrangefunktionen väljs till L(x, α, β) = Σ_{j}f_{j}(x_{j})

−α(Σ_{j}x_{j} − k) + Σ_{j}β_{j}(x_{j} − 1); KKT fås ur

• \frac{∂L(x, α, β)}{∂x_{j}} ≥ 0, \frac{∂L(x, α, β)}{∂x_{j}} · x_{j} = 0, x_{j} ≥ 0

• \frac{∂L(x, α, β)}{∂α} = 0, \frac{∂L(x, α, β)}{∂β_{j}} ≤ 0, \frac{∂L(x, α, β)}{∂β_{j}} · β_{j} = 0, β_{j} ≤ 0

• Σx_{j} = k

b) Antag att brytpunkten, dvs det j för vilket r > k inträffar, är j^{∗}. Det gäller då enligt algoritmen att x_{j}^{∗} = 1 för alla j = 1, 2, …, j^{∗} − 1 och att x_{j^{∗}}^{∗} − k − (j^{∗} − 1).

Sätt α^{∗} = −cj^{∗}. Vi uppfyller därmed att j = 1, …, j^{∗} − 1: x^{∗} = 1 och f′_{j}(x_{j}^{∗}) = c − c_{j} ≤ α^{∗}, dvs c_{j} ≥ c_{j^{∗}} för j < j^{∗}

(följer ur sorteringen).

j = j^{∗}:  x_{j^{∗}} ∈ [0, 1] och f′_{j}(x_{j}^{∗}) = −c_{j^{∗}} = −α^{∗}

j = j^{∗}: x_{j}^{∗} = 0 och f′_{j}(x_{j}^{∗}) = −c_{j} ≥ α^{∗} = −c_{j}^{∗}. dvs c_{j} ≤ c_{j^{∗}} för j > j^{∗} (följer ur sorteringen).

För [ \begin{matrix}j > j_{j^{∗}}, sätt β_{j}^{∗} = 0 \\ j = 1, …, j^{∗} − 1, sätt β_{j}^{∗} = α^{∗} − f′_{j}(x_{j}^{∗}) = −c_{j^{∗}} + c_{j} ≥ 0 \\ j = j^{∗}, sätt β_{j}^{∗} = 0 \end{matrix} ]

Vi xxxx därmed samtliga KKT-villkor!

6a) ∇f(x^{∗}) = 0^{∗}

b) Det existerar λ_{∗} ≥ 0^{m} med

• ∇f(x^{∗}) = A^{∗}λ_{∗}

• λ_{∗}^{T} (Ax − b) = 0

samt Zx_{∗} ≥ b.

7. LP-dualen är: minimera w = b^{T} π

då [ \begin{matrix}A^{∗}π ≥ c \\ π ≥ 0 \end{matrix} ].

Starka dualsatsen: Om ett av de två problemen (primalen eller dualsatsen) har en optimallösning, så har det andra det också, och de har samma optimala målfunktionsvärde.

Beräk. Vi utgör från att primala har ett optimum. Den har då en aoptimal

tillåten beaslösning (sats 4.1-3). Vi skriver den som x^{∗} = [ \begin{matrix}x_{B} \\ x_{N} \end{matrix} ], med

A = (B N) och C = [ \begin{matrix}c_{C} \\ c_{N} \end{matrix} ]. Då är x_{B} = B^{−1}b. x^{∗} är optimal om och

endast om c_{N}^{T} − c_{B}^{T}B^{−1}N ≤ 0^{T}, dvs c_{B}^{T}B^{−1}N ≥ C_{N}^{T}.

Sätt π^{∗} = (B^{−1})^{T} c_{B}, dvs (π^{∗})^{T} = c_{B}^{T}B^{−1}. Är π^{∗} tillåten i dualen? (π^{∗})^{T} A = C_{B}^{T}B^{−1}(B N) = (C_{B}^{T} c_{B}^{T}B^{−1}N) ≥ (c_{B}^{T} c_{N}^{T}) = c^{T}, dvs A^{∗}n̄^{∗} ≥ c. Gäller π^{∗} ≥ 0? För primalen stackvariabler gäller att

c̄_{s} ≤ 0, dvs 0 − c_{B}^{T}B^{−1}I^{m} = −c_{B}^{T}B^{−1} = −(π^{∗})^{T} ≤ 0.

∵ π^{∗} är tillåten i dualen. Gäller b^{T} π^{∗} = c^{T} x^{∗} Ja, ty

e^{∗} = c^{T} x^{∗} = c_{B}^{T}B^{−1}b = (π^{∗})^{T} b = w^{∗}.

Corollary 6.2 till svaga dualsatsen (Sats 6.1) ger att x^{∗} och π^{∗} är optimala i primalen respektive draker.