Chalmers/GU Matematiska institutionen TENTAMEN

TMA945 TILLÄMPAD OPTIMERINGSLÄRA

Datum:  00–05–24
Tid:  8^{45}–13^{45}
Hjälpmedel:  Typgodkänd räknedosa
Antal uppgifter:  7; för godkänd uppgift krävs 2 poäng av 3.

Uppgifterna är inte ordnade efter svårighetsgrad.

CTH: För godkänt krävs 8 poäng och tre godkända uppgifter. GU: För godkänt krävs 11 poäng och tre godkända uppgifter.

Examinator:  Michael Patriksson
Jourhavande lärare:  Per Hörfelt, tel. 0740-479626
Resultat anslås senast: 00–06–05

Kortfattade lösningsförslag anslås vid skrivningstidens slut på anslagstavlan för optimeringslära vid matematiska institutionen.

Tentamensinstruktioner

När Du löser uppgifterna

Redovisa lösningsmetodik och beräkningar. Använd generellt giltiga metoder, t.ex. de som genomgåtts i kursen.

Skriv endast på ena sidan av lösningsbladen. Använd inte rödpenna. Behandla ej fler än en huvuduppgift på varje blad.

Vid skrivningens slut

Sortera Dina lösningsblad i uppgiftsordning. Markera på omslaget de uppgifter Du behandlat. Kontrollräkna antalet inlämnade blad och fyll i antalet på omslaget.

TENTAMEN

Uppgift 1

(Linjärprogrammering)

Betrakta LP-problemet

minimera z = 2x_{1} + x_{2},
då  3x_{1} + 2x_{2} ≥ 3,
x_{2} ≤ 1,
x_{1} , x_{2} ≥ 0.

(2p) a) Lös detta problem med hjälp av Fas I och II av simplexmetoden.

(1p) b) Antag att högerledsvektorn b = (3, 1)^{T} ändras till b(α) := (3, 1)^{T} + α(1, 2)^{T}, för α ∈ ℜ. För vilka värden på α ∈ ℜ existerar en tillåten lösning till det resulterande problemet? Uttryck det optimala målfunktionsvärdet för det parametriskt givna problemet, som en funktion av α. (Lös, om så önskas, LP-problemen som uppstår i denna deluppgift geometriskt.)

Uppgift 2

(Modellering)

En maskinist reducerar överflödig metall från en rund maskindel genom att låta 42 cm av maskindelens längd passera ett skärverktyg i en svarv. För en svarv som roterar med N varv per minut och med ett verktyg som avancerar med hastigheten f cm per varv har man empiriskt beräknat verktygets livslängd till

L(N, f) = (\frac{5}{N · f^{0.60}} )^{6.667}

minuter. Varje gång ett verktyg blir utslitet måste ett nytt installeras, vilket tar 6 minuter. Ingenjörer i verkstadsföretaget vill bestämma en maskinmässig tillverkningsplan som minimerar den totala kostnaden, då en timmes maskinisttid kostar 520 kronor, och ett verktyg kostar 870 kronor. Rotationshastigheten måste vara mellan 200 och 600 varv per minut och hastigheten hos skärverktyget mellan 0.001 och 0.005 cm per varv.

(2p) a) Beskriv optimeringsproblemet med hjälp av en olinjär optimeringsmodell.

(1p) b) Uppfyller den tillåtna planen (N, f) := (200, 0.001) KKT-villkoren?

Uppgift 3

(Frank–Wolfe)

Betrakta optimeringsproblemet

minimera f(x) := −5x_{1} + x_{1}^{2} − 8x_{2} + 2x_{2}^{2}
då 3x_{1} + 2x_{2} ≤ 6,
x_{1} ≥ 0, x_{2} ≥ 0.

(2p) a) Starta i punkten x^{0} = (0, 0)^{T} och genomför två iterationer med algoritmen av Frank och Wolfe på problemet. Redovisa alla stegen noga. (Gör inte beräkningarna med hjälp av Figur 1; den är till för att Ni ska kunna kontrollera resultaten.) Med ledning bara av Dina beräkningar under dessa iterationer, ange inom vilket intervall det optimala målfunktionsvärdet befinner sig. Motivera! Använd slutligen Figur 1 för att beskriva på ett ungefär var de fortsatta iterationspunkterna hamnar och utrön geometriskt ungefär var optimum bör befinna sig. (En förstorad version av bilden är med på sista bladet i tentamen. Lämna gärna in det.)

Figur 1: Nivåkurvor för funktionen f samt tillåtet område

(1p) b) Den vanliga beskrivningen av Frank–Wolfealgoritmen ges under antagandet att den polyedriska mängd som optimeras över är begränsad. Antag att polyedern inte är begränsad för ett problem som vi vill lösa. Besvara följande naturliga undran: Måste algoritmen omdefinieras på något ställe, i så fall var, hur och varför? Vad händer med den så användbara existensen av en undre gräns av det optimala målfunktionsvärdet (antag att målfunktionen är konvex)? Vad krävs av problemet för att den (möjligen) modifierade metoden ska vara konvergent? (För att få en poäng behöver man inte säkert besvara alla frågorna.)

Uppgift 4

(Kappsäcksproblemet)

Ett binärt kappsäcksproblem definieras som

maximera ∑_{j=1}^{n} c_{j}x_{j},  (1)

då ∑_{j=1}^{n} a_{j}x_{j} ≤ b,  (2)
x_{j} ∈ {0, 1}, j = 1, …, n,  (3)

där c_{j} motsvarar nyttan av föremål j, a_{j} dess vikt och b den största sammanlagda vikt man kan bära. Variablerna definieras som

x_{j} = \{ \begin{matrix}1, & om föremål j tas med, \\ 0, & annars. \end{matrix}

Vi antar att c_{j} > 0 och 0 < a_{j} < b för j = 1, …, n samt att ∑_{j=1}^{n} a_{j} > b.

Om heltalsvillkoren (3) relaxeras till

0 ≤ x_{j} ≤ 1,  j = 1, …, n  (4)

kan det resulterande kontinuerliga kappsäcksproblemet lösas med hjälp av girighetsalgoritmen, enligt följande:

i) Sortera föremålen enligt sjunkande ordning av kvoterna \frac{c_{j}}{a_{j}}, vilket leder till följande relationer: \frac{c_{j_{1}}}{a_{j_{1}}} ≥ \frac{c_{j_{2}}}{a_{j_{2}}} ≥ ⋯ ≥ \frac{c_{jn}}{a_{jn}}.

ii) Bestäm k sådant att

∑_{i=1}^{k−1} a_{j_{i}} ≤ b < ∑_{i=1}^{k} a_{j_{i}}.

ii) Lösningen till problemet (1)–(2), (4) ges av

x̄_{j_{i}} = \{ \begin{matrix}1, & i = 1, …, k − 1, \\ \frac{1}{a_{j_{k}}} (b − ∑_{i=1}^{k−1} a_{j_{i}}) , & i = k, \\ 0, & i = k + 1, …, n. \end{matrix}

(1p) a) Låt z^{∗} och z̄ beteckna målfunktionsvärdena för optimallösningarna till (1)–(3) respektive (1)–(2), (4). Vilken relation gäller mellan z̄ och z^{∗}?

Givet att vi har hittat en lösning x̄ till det kontinuerliga problemet (1)–(2), (4), hur kan man, utgående från denna lösning, hitta en tillåten lösning till det binära problemet (1)–(3)? Om du vill kan du förklara med hjälp av exemplet i b)-uppgiften nedan.

Kalla målfunktionsvärdet för den tillåtna lösningen z^{H}. Vilken relation råder mellan z^{H} och z̄? Mellan z^{H} och z^{∗}?

(2p) b) Beskriv Branch–and–Bound-algoritmen tillämpad på det binära kappsäcksproblemet, som utnyttjar girighetsalgoritmen ovan. Specificera de fyra begreppen relaxering, förgreningsstrategi, trädsökningsstrategi och nodkapningskriterium för din algoritm. Hur kan tillåtenhetsheuristiken i a)-uppgiften utnyttjas i B&Balgoritmen?

Studera följande instans av kappsäcksproblemet:

maximera 9x_{1} + 7x_{2} + 4x_{3} + 2x_{4},
då  15x_{1} + 12x_{2} + 7x_{3} + 4x_{4} ≤ 23,
x_{1}, x_{2}, x_{3}, x_{4} ∈ {0, 1}.

Utnyttja girighetsalgoritmen ovan för att lösa detta problem med hjälp av B&Balgoritmen.

Uppgift 5

(Myter i optimering)

Följande tre påståenden är alla falska, även om de kanske kan verka rimliga vid en första anblick. Er uppgift är att förklara varför påståendena är falska, med ett motexempel eller en förklaring.

(1p) a) I ett LP-problem finns alltid minst en optimal hörnpunkt.

(1p) b) Den optimala lösningen till ett linjärt heltalsoptimeringsproblem är en avrundning av lösningen till en LP-relaxation av det.

(1p) c) Om man löser optimeringsproblemet att minimera f : ℜ^{n} ↦ ℜ över mängden X ∩ { x ∈ ℜ^{n} | g(x) ≤ b }—där X är konvex och g : ℜ^{n} ↦ ℜ är en konvex funktion—och den globala optimallösningen, x^{∗}, är sådan att g(x^{∗}) < b, så är bivillkoret g(x) ≤ b redundant.

Uppgift 6

(Obegränsad optimering)

Betrakta det obegränsade optimeringsproblemet att minimera funktionen

f(x) := 0.1x_{1}x_{2} + 0.01(x_{1} − 2)^{4} + 0.009(x_{2} − 5)^{4}, x ∈ ℜ^{2}.

En konturplot av funktionen inom intervallen (x_{1}, x_{2}) ∈ [1, 4] × [2, 8] ges i Figur 2.

Figur 2: Nivåkurvor för funktionen f

(2p) a) Med start i punkten x^{0} := (3, 7), genomför en iteration med brantaste lutningsmetoden i figuren. (En förstorad version av bilden är med på sista bladet i tentamen. Lämna gärna in det.) Bekräfta (utan hjälp av figuren) att det närmevärde av x^{1} som Ni har funnit är rimligt.

(1p) b) Med start i punkten x^{0} := (3, 7), genomför en iteration med Newtons metod. Använd någon lämplig linjesökningsmetod (ej steget 1).

(3p) Uppgift 7

(Strikt komplementaritet i linjärprogrammering)

Betrakta primal–dualparet

(P) min z = c^{T}x
då  Ax ≥ b
x ≥ 0^{n}

(D) max w = b^{T}y
då  A^{T}y ≤ c
y ≥ 0^{m}

Bevisa följande påstående, som också brukar kallas teoremet om existensen av strikt komplementära optimala lösningar.

Antag att de två problemen (P) och (D) har tillåtna lösningar. Då existerar minst ett par (x^{∗}, y^{∗}) av optimala lösningar som uppfyller

(Ax^{∗} − b) + y^{∗} > 0^{m} och (c − A^{T} y^{∗}) + x^{∗} > 0^{n}.

Med andra ord är paret (x^{∗}, y^{∗}) sådant att för varje par av variabel–bivillkor i komplementvillkoren gäller att slack (dvs. en variabel är positiv respektive ett bivillkor är uppfyllt med strikt olikhet) existerar i precis ett av dem.

(Kommentar: Betrakta det primal–duala paret (P) och (D) och de duala relationerna mellan primala variabler (bivillkor) och duala bivillkor (variabler):

\begin{aligned}a_{i}x ≥ b_{i} & ⟷ & y_{i} ≥ 0, & i = 1, …, m, \\ x_{j} ≥ 0, & ⟷ & (a^{j})^{T} y ≤ c_{j}, & j = 1, …, n. \end{aligned}

En följd av resultatet är: att ett godtyckligt valt bivillkor av dessa i något av problemen skall ha ett slack (vara uppfyllt med strikt olikhet) i någon optimal lösning är ekvivalent att motsvarande bivillkor i det andra problemet är aktivt (är uppfyllt med likhet) i varje optimal lösning.)

Figur 1: Nivåkurvor för funktionen f samt tillåtet område Figur 2: Nivåkurvor för funktionen f