Chalmers/GU Matematiska institutionen TENTAMEN

TMA945 TILLÄMPAD OPTIMERINGSLÄRA

Datum:  99–05–28
Tid:  8^{45}–13^{45}, Väg och vatten
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:  Michael Patriksson, tel. 5327
Resultat anslås senast: 99–06–11

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 de standardmetoder som genomgåtts på föreläsningar och lektioner.

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

Betrakta problemet

min − x_{1} + 2x_{2} + x_{3}
då  2x_{1} + x_{2} − x_{3} ≤ 7
− x_{1} + 2x_{2} + 3x_{3} ≥ 3
x_{1}  x_{2}  x_{3} ≥ 0.

(2p) a) Lös problemet med användande av simplexmetodens båda faser.

(1p) b) Antag att problemets andra högerled ersätts med 3+ϵ, där ϵ är ett litet (positivt eller negativt) tal. Hur förändrar detta det optimala måfunktionsvärdet? (Frågan skall besvaras utan att problemet löses om från början!) Förklara hur information om denna förändring kan fås ur lösningen till a).

Uppgift 2

Sex kamrater, vilka tröttnat på det hårda studentlivet, har beslutat sig för att öppna ett café. Caféet skall ha öppet tisdag–söndag och nu återstår problemet att fördela arbetsdagarna så att alla arbetar lika mycket. Bemanningen av caféet kräver att fyra personer arbetar samtidigt. Dock har endast två av kamraterna lyckats att lära sig att sköta den extremt komplicerade espressomaskinen (en manuell La Pavoni från 1921), som kräver en persons ständiga uppsikt. Man har kommit överens om att ingen skall behöva arbeta fler än fyra dagar i veckan.

För att fördela arbetsdagarna så gott det går enligt allas önskemål har man skapat ett system där var och en får poängsätta dagarna med tillsammans 100 poäng, där fler poäng representerar ett önskemål om att hellre arbeta den dagen. Om till exempel person A helst arbetar tisdag men helst inte onsdag och torsdag skulle denne kunna ge dagarna följande poäng:

Veckodag Poäng
Tisdag  40
Onsdag  0
Torsdag  0
Fredag  20
Lördag  20
Söndag  20

(2p) a) Formulera problemet att lägga ett schema vilket maximerar kompanjonernas sammanlagda lycka (lycka definieras som antalet uppfyllda poäng) och samtidigt tillgodoser caféets krav på bemanning. Modellen skall vara en linjär heltalsmodell.

(1p) b) Antag att caféägarna bestämmer sig för att vara solidariska, och i stället som målsättning anger en maximal lycka hos den person som blir mest olycklig, för att på så vis balansera lyckan inom gruppen. Formulera om modellen från a) för att uppnå detta mål. Observera att den slutliga modellen fortfarande skall vara en linjär heltalsmodell (de vill ju kunna lösa problemet också!)

Uppgift 3

Om maxflödesproblemet

(1p) a) Givet är ett nätverk med noder i i en nodmängd N och riktade bågar (i, j) i en bågmängd E, vardera bågar med flödeskapaciteter u_{ij} ≥ 0. Formulera problemet att skicka ett maximalt flöde från en nod s i N till en annan nod t i N genom nätverket (N , E).

(2p) b) Formulera LP-dualen till problemet formulerat i deluppgift a). Beskriv maxflödesminsnittsteoremet, både generellt och med ett illustrativt (icke-trivialt) eget exempel.

Uppgift 4

Betrakta problemet att minimera funktionen f över ℜ^{2}, där

f(x) := (x_{1} + 2x_{2} − 3)^{2} + (x_{1} − 2)^{2}.

(2p) a) Utför en iteration med brantaste lutningsmetoden, med start i x_{0} = (0, 0)^{T}. I den uppnådda punkten, x_{1}, ange vilka riktningar som är avtagande. Är x_{1} en optimal lösning till problemet? Varför/varför inte?

(1p) b) Utför en iteration med Newtons metod (inklusive linjesökning), med start i x_{0} = (0, 0)^{T}. I den uppnådda punkten, x_{1}, ange vilka riktningar som är avtagande. Är x_{1} en optimal lösning till problemet? Varför/varför inte?

Uppgift 5

Betrakta LP-problemet

v(b) = max c^{T} x,
då Ax ≤ b,
x ≥ 0.

Antag att problemet har en optimal lösning för högerledsvektorn b. När vi utför känslighetsanalys av optimallösningen och dess målfunktionsvärde för förändringar i vektorn b utnyttjar vi resultatet att skuggpriset för ett bivillkor i (det vill säga för bivillkoret “∑_{j=1}^{n} a_{ij}x_{j} ≤ b_{i}”) är lika med det optimala värdet av dualvariabeln, y_{i}, för detta bivillkor.

(2p) a) Antag att problemet ovan har en unik optimal duallösning, y^{∗}. Visa att tekniken beskriven ovan är korrekt, det vill säga att y_{i}^{∗} är lika med den förändring av v som fås om högerledet ökas med en enhet.

(1p) b) Antag att det duala problemet har multipla optimala lösningar. (Detta inträffar typiskt när problemet ovan är degenererat i optimum.) Är tekniken beskriven ovan fortfarande giltig? Om inte, hur måste den förändras för beräkning av ett korrekt skuggpris?

(3p) Uppgift 6

I Ert första uppdrag som optimerare ställs Ni inför problemet att modellera och lösa ett problem åt ett företag inom stålindustrin. Det handlar om att tillverka en syreproduktionsenhet som skall användas i en masugn. De fyra variabler x_{1}, …, x_{4} Ni deklarerar definierar produktionshastigheten av syre, trycket i tanken, kompressorstyrkan och tankens volym. Enligt företagets ekonomer och ingenjörer kan kostnaden för operationen av denna maskin under en produktionscykel beskrivas med uttrycket

f(x) := 61.8 + 5.72x_{1} + 0.0175(x_{3})^{0.85} + 0.0094(x_{4})^{0.75} + 0.006t_{1}x_{3},  (1)

där t_{1} (som här kan sättas lika med 0.6) är tiden för den första delen av produktionscykeln. Bivillkoren som deklareras i samarbete med ingenjörerna är följande fyra:

t_{2}x_{1} ≥ d_{1}t_{1} + d_{2}(t_{2} − t_{1}),  (2a)

som uttrycker syreefterfrågan, där t_{2} = 1.0 är längden av den andra delen av produktionscykeln och d_{1} = 2.5 och d_{2} = 40 är efterfrågan av syre i respektive del av produktionscykeln;

x_{2} ≥ p_{0}  (2b)

uttrycker kravet på ett minsta tryck (här kan p_{0} = 200 sättas);

x_{3} = 36.25\frac{(d_{2} − x_{1})(t_{2} − t_{1})}{t_{1}} ln (\frac{x_{2}}{p_{0}} )  (2c)

beskriver den fysikaliska relationen mellan kompressorns effekt och trycket i tanken den genererar;

x_{4} = 348,300\frac{(d_{2} − x_{1})(t_{2} − t_{1})}{x_{2}}  (2d)

beskriver slutligen relationen mellan volymen hos tanken och trycket som måste vidmakthållas i den för att kunna behålla den mängd syre som maximalt kan behövas. Vi har sedan naturligtvis de fysikaliska villkoren

x_{1}, x_{2}, x_{3}, x_{4} ≥ 0.  (2e)

Problemet att minimera funktionen f beskriven i (1) under bivillkoren beskriva i (2) matar Ni in i en kommersiell programvara, som ger följande utskrift:

         Optimal solution:
         x1 = 17.5   x2 = 473.7   x3 = 468.8   x4 = 6618
         Optimal cost:
         f = 173.7

Programmet som har använts skriver alltid ut att den lösning som nås är optimal, men det kontrollerar inte att ett problem som matas in är snällt nog; om numeriska problem uppstår har också programmet ibland en tendens att avbryta sökningen i förtid och ändå skriva att resultatet är optimalt. Er viktiga uppgift är att verifiera huruvida programmet gav en rimlig lösning. Motivera Er slutsats.

Uppgift 7

Betrakta problemet

minimera f(x),  (1a)
då g_{i}(x) ≤ 0, i = 1, …, m, (1b)
x ∈ X,  (1c)

där f : ℜ^{n} ↦ ℜ och g_{i} : ℜ^{n} ↦ ℜ är godtyckliga funktioner och X ⊂ ℜ^{n} är en godtycklig mängd. Betrakta också dess Lagrangefunktion,

L(x, y) := f(x) + ∑_{i=1}^{m} y_{i}g_{i}(x), y ≥ 0^{m},

och Lagrangeduala målfunktion,

L(y) := inf_{x∈X} {f(x) + ∑_{i=1}^{m} y_{i}g_{i}(x)} .

(2p) a) För detta problem bevisade Everett (1963) följande intressanta resultat:

Antag att x̄ löser det Lagrangeduala subproblemet för ett givet ȳ ≥ 0^{m}, det vill säga, L(ȳ) = L(x̄, ȳ). Då gäller att x̄ löser optimeringsproblemet

minimera f(x),
då g_{i}(x) ≤ b_{i},  i = 1, …, m,
x ∈ X,

där

b_{i} \begin{cases}= g_{i}(x̄), & då ȳ_{i} > 0, \\ ≥ g_{i}(x̄), & då ȳ_{i} = 0. \end{cases}

Bevisa detta resultat. Ledning: Tänk på sadelpunkter.

Under vilka omständigheter kan man motivera att x̄ är en acceptabel lösning till problemet (1)?

(1p) b) Ett annat resultat, bevisat av samme Everett, är följande:

Antag att x̄ löser det Lagrangeduala subproblemet för ett givet ȳ ≥ 0^{m}, och att dessutom x̄ är tillåten i problemet (1), det vill säga, g_{i}(x̄) ≤ 0, i = 1, …, m. Låt f^{∗} vara det optimala målfunktionsvärdet till problemet (1). Då gäller att

f(x̄) − f^{∗} ≤ − ∑_{i=1}^{m} ȳ_{i}g_{i}(x̄).

Med andra ord kan man begränsa avståndet i målfunktionsvärde till det optimala med ett (beräkningsbart) mått på avvikelsen från uppfyllandet av komplementvillkoren.

Bevisa detta resultat.

Med hjälp av denna nyvunna insikt, formulera villkor som är tillräckliga för global optimalitet hos x̄ i problemet (1). Beskriv också deras släktskap med KKTvillkoren.