Chalmers/GU Matematiska institutionen TENTAMEN

TMA945 TILLÄMPAD OPTIMERINGSLÄRA

Datum:  98–03–09

Tid:

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.

För godkänt krävs 8 poäng och tre godkända uppgifter

Examinator:  Michael Patriksson
Jourhavande lärare:  Patrik Andersson, 0740-479626
Resultat anslås senast: 98–03–18

Tentamensinstruktioner

När Du löser uppgifterna

Motivera och redovisa noga 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

(2p) a) 5000 fungerande enheter av en diskret produkt skall tillverkas under en dag. Det finns fyra tillgängliga maskiner för att tillverka produkten, men deras produktionshastighet, -kostnad och förväntad andel defekta produkter varierar mellan dem. (Data ges i nedanstående tabell.) Formulera en matematisk modell för problemet att finna en produktionsplan som (förväntat) uppfyller efterfrågan till lägsta kostnad. Klassificera modellen.

Maskin Uppstartnings-  Produktions-  Kapacitet Andel defekta
kostnad (kr) kostnad (kr/enhet) (enheter) produkter (%)
1  400  4  2000  10
2  1000  6  4000  5
3  600  2  1000  15
4  300  5  3000  8

(1p) b) Andelen defekta produkter hos en maskin är naturligtvis inte känd med säkerhet, utan är bara ett medelvärde hos en stokastisk variation. Om den verkliga felprocenten överstiger den förväntade, kan följden bli att efterfrågan inte kan tillgodoses, med förlorade kontrakt, stämningar, etc., som följd. Vi är alltså intresserade av en produktionsplan som, så långt det är möjligt, tillgodoser efterfrågan, dock fortfarande till en minimal kostnad.

Diskutera någon utvidgning av modellen i a) som medger ett säkrare uppfyllande av efterfrågan, dock utan att därför öka kostnaderna astronomiskt.

Uppgift 2

(1p) a) Formulera och bevisa svaga dualsatsen för linjärprogrammering.

(1p) b) Beskriv de ekvationssystem som löses i en iteration av den reviderade simplexmetoden, och ange iterationens totala komplexitet.

(1p) c) Visa att ekvationssystemet

∑_{j=1}^{n} a_{ij}x_{j} = b_{i},  i = 1, …, m

är ekvivalent med de m + 1 olikhetsvillkoren

∑_{j=1}^{n} a_{ij}x_{j} ≤ b_{i},  i = 1, …, m,

∑_{i=1}^{m} (∑_{j=1}^{n} a_{ij}x_{j}) ≥ ∑_{i=1}^{m} b_{i}.

(3p) Uppgift 3

Betrakta problemet

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

Med start i x_{0} = (1/2, 1/2)^{T}, lös problemet med Frank–Wolfe-algoritmen. Ange i varje iteration ett intervall däri det optimala målfunktionsvärdet ligger. Varför är uppskattningarna giltiga för detta problem?

(3p) Uppgift 4

Lös följande LP-problem med simplexmetoden (tvåfasmetoden).

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

Uppgift 5

Betrakta LP-problemet

max z = 3x_{1} + 2x_{2} + 5x_{3}
då  x_{1} + 2x_{2} + x_{3} ≤ 500,
3x_{1}  + 2x_{3} ≤ 460,
x_{1} + 4x_{2}  ≤ 420,
x_{1} , x_{2} , x_{3} ≥ 0.

(1p) a) Ange dess LP-dual. Utan att lösa vare sig det primala eller det duala problemet, ange ett intervall för det optimala målfunktionsvärdet.

(2p) b) Visa, med hjälp av optimalitetsvillkoren för LP, att y^{∗} = (0, 5/2, 1/2)^{T} är en optimal duallösning.

Uppgift 6

(2p) a) Betrakta optimeringsproblemet

min f(x),
då x ∈ X,

där f är kontinuerligt differentierbar och där

X = { x ∈ ℜ^{n} |∑_{j=1}^{n} x_{j} = r; x_{j} ≥ 0, j = 1, …, n } ,

där r > 0. Antag att x_{∗} är ett lokalt minimum till detta problem. Visa att

x_{∗j} > 0 ⟹ \frac{∂f(x_{∗})}{∂x_{j}} ≤ \frac{∂f(x_{∗})}{∂x_{i}}, i, j = 1, …, n,

dvs. att nollskilda variabler har samma (och lägsta) partiella derivata.

(1p) b) Betrakta ett olinjärt optimeringsproblem, där målfunktionen inte är känd explicit, utan måste beräknas för varje variabelvektor genom att utföra någon numerisk beräkning. Denna beräkning är dyr, för övrigt. Antag också att inget är känt om denna målfunktion i form av dess deriverbarhet eller konvexitet, annat än att den (troligen) är kontinuerlig i variabelvektorn, som är av storleken 100, och att den förväntas ha ett litet antal lokala minima. Vidare är problemet begränsat av ett fåtal (c:a 10) olinjära bivillkor, som ger upphov till en icke-konvex mängd. Vi är intresserade av att lösa problemet approximativt; speciellt kan det tolereras att man bryter något mot bivillkoren. Diskutera hur Du skulle angripa problemet.

Uppgift 7

(2p) a) Betrakta optimeringsproblemet

min f(x),
då g_{i}(x) ≥ 0,  i = 1, …, m,

där samtliga funktioner är kontinuerligt differentierbara på ℜ^{n}. Ange KKT-villko-ren för problemet och beskriv deras geometriska betydelse. Ange egenskaper hos problemet under vilket de är nödvändiga för lokal optimalitet hos en punkt, och (oberoende av föregående) egenskaper hos problemet under vilket de är tillräckliga för global optimalitet hos en punkt. Bevisa det sistnämnda.

(1p) b) Betrakta optimeringsproblemet ovan. Antag att f är konvex på ℜ^{n}, och att samtliga funktioner g_{i} är konkava på ℜ^{n}. Beskriv den logaritmiska barriärfunktionen till detta problem, och visa att funktionen är strikt konvex på det inre av mängden av tillåtna lösningar. (Vi antar att den mängden inte är tom.) Varför är den egenskapen av intresse?