Chalmers/GU Matematiska institutionen TENTAMEN

TMA945 TILLÄMPAD OPTIMERINGSLÄRA

Datum:  00–03–06
Tid:  14^{15}–19^{15}
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:  Jakob Hultén, tel. 5323
Resultat anslås senast: 00–03–20

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 = −4x_{1} − 2x_{2} − 4x_{3}
då  2x_{1} − x_{2} + x_{3} ≤ 20,
x_{1} + x_{2} + 2x_{3} = 20,
x_{1} , x_{2} , x_{3} ≥ 0.

(2p) a) Lös problemet på korrekt sätt med hjälp av simplexmetoden, dvs. med hjälp av både Fas I och Fas II.

(1p) b) Beskriv utförligt, algebraiskt, de beräkningar som utförs vid den första pivoteringen med avseende på z. Observera: det är inte alla de beräkningar som utfördes för denna pivotering i a) som behövs! Ange motsvarande, komplementära, duala punkt som nås efter denna pivotering och visa att den är otillåten i det duala problemet.

Uppgift 2

(Olinjär optimering)

(2p) a) Betrakta det olinjära optimeringsproblemet

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

Avgör huruvida punkten x = (0, \frac{1}{2})^{T} uppfyller KKT-villkoren. Obs! Lös inte problemet med någon algoritm för att avgöra saken.

(1p) b) Avgör huruvida punkten x = (0, \frac{1}{2})^{T} är ett globalt minimum. Om svaret är “Ja”, motivera detta väl. Om svaret är “Nej”, motivera detta med ett motexempel. Tips: gör denna uppgift allra sist!

(3p) Uppgift 3

(Optimalitetsvillkor och konvexitetsteori)

Betrakta det linjärt begränsade olinjära optimeringsproblemet

minimera f(x),
då Ax ≥ b,

där f är kontinuerligt differentierbar (en gång) på ℜ^{n} och där A och b tillhör ℜ^{m×n} respektive ℜ^{m}.

(1p) a) Antag att x_{∗} är en tillåten punkt i problemet där ingen tillåten descentriktning existerar. Beskriv algebraiskt vad det betyder för detta problem. Vi antar också att f inte är differentierbar två gånger i x_{∗}. Ange de nödvändiga optimalitetsvillkoren för att x_{∗} skall kunna vara en lokalt optimal lösning till problemet.

(2p) b) Härled optimalitetsvillkoren Du beskrev i a) med hjälp av Farkas Lemma, som uttrycks som följer: precis ett av följande två linjära system har en lösning:

(I) Bx ≥ 0
c^{T} x < 0
(II) B^{T} y = c
y ≥ 0.

(3p) Uppgift 4

(Linjärprogrammering)

Betrakta LP-problemet

minimera z = 100x_{1} + 100x_{2} + 100x_{3}
då  2x_{1} + 6x_{2} + 10x_{3} ≥ 240,
2x_{1} +  x_{2}  ≥ 60,
x_{1} ,  x_{2} ,  x_{3} ≥ 0.

(2p) a) Oraklet i Delfi har talat om för Dig att en optimallösning till detta problem är x_{∗} = (12, 36, 0)^{T}. Din uppgift är att verifiera att oraklet talar sanning. Du får inte lösa LP-problemet från början med simplexmetoden, utan måste utnyttja Dina kunskaper om optimalitet i LP. Om Du av en händelse skulle vilja lösa ett besläktat LP-problem som råkar ha två variabler, så är det tillåtet att lösa detta lilla LP-problem geometriskt.

(1p) b) Bestäm samtliga optimala lösningar till LP-problemet ovan. Du får inte heller här lösa LP-problemet från början med simplexmetoden.

Uppgift 5

(Obegränsad optimering)

Antag att Du vill lösa det obegränsade optimeringsproblemet att

minimera_{x∈ℜ^{n}} f(x),

där f är en två gånger kontinuerligt differentierbar funktion. Du är intresserad av att lösa problemet med hjälp av Newtons metod (med linjesökningar).

(1p) a) I en given iteration k får du felutskriften “Steglängden är noll”. Vilken/vilka möjliga orsaker kan det finnas till detta?

(1p) b) I en given iteration k får du felutskriften “Sökriktning saknas”. Vilken/vilka möjliga orsaker kan det finnas till detta?

(1p) c) Beskriv minst ett sätt att modifiera Newtons metod så att ingen felutskrift av de typer som beskrivs i a) och b) kan förekomma.

(3p) Uppgift 6

(Lagrangedualitet)

Betrakta LP-problemet

minimera f(x) := x_{1} + x_{2},
då 3x_{1} + 2x_{2} ≥ 4,  (1)
0 ≤ x_{1} ≤ 1,
0 ≤ x_{2} ≤ 1.

Bilda det Lagrangeduala problemet genom att Lagrangerelaxera det övergripande bivillkoret (1). Ange det Lagrangeduala problemets målfunktion explicit, gärna med en graf som stöd. Lös det Lagrangeduala problemet. Använd den optimala Lagrangeduala lösningen för att härleda den optimala lösningen till det ursprungliga LP-problemet.

(3p) Uppgift 7

(Matematisk modellering—personalplanering)

Data för antalet medarbetare, r_{t}, som behövs varje månad t inom ett 10 månader långt projekt i ett företag anges i en tabell nedan. Ingen underbemanning tillåts i någon månad. Företaget kan projektanställa i början av varje månad för att uppfylla behovet i den månaden eller någon senare månad. Det är en fix kostnad s_{t} kronor associerad med att rekrytera i en viss månad t, som är oberoende av hur många som rekryteras då (en fix kostnad uppstår för annonsering, kostnader för att ordna med intervjuer, etc.). Varje person som är anställd under en månad t utöver behovet i månaden belastar företaget med en extra kostnad på c_{t} kronor under månaden. En person som rekryterats en viss tidsperiod måste av fackliga skäl få behålla sin anställning i minst tre månader, eller till projektets slut om han/hon anställs när det är mindre än tre månader kvar av perioden. Antag att ingen personal finns till hands vid tiden t = 0.

\begin{matrix}Månad & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ r_{t} & 79 & 34 & 52 & 61 & 25 & 89 & 56 & 29 & 48 & 34 \\ s_{t} & 728 & 705 & 698 & 714 & 708 & 739 & 695 & 704 & 689 & 712 \\ c_{t} & 15 & 12 & 16 & 14 & 16 & 12 & 15 & 17 & 12 & 13 \end{matrix}

Den totala kostnaden består av den fixa kostnaden för rekrytering av personal och den extra kostnaden för en för stor mängd anställd personal. Formulera ett optimeringsproblem för att finna antalet personer som i varje månad skall projektanställas eller avskedas, så att den totala kostnaden minimeras.