Chalmers/GU Matematiska institutionen TENTAMEN

TMA945 TILLÄMPAD OPTIMERINGSLÄRA

Datum:  99–03–08
Tid:  14^{45}–19^{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:  Ola Helenius, tel. 5336
Resultat anslås senast: 99–03–22

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

Sju sorters paket skall levereras med hjälp av fem bilar. Det finns tre paket av varje sort. Bilarna har kapacitet att leverera 6, 4, 5, 4 respektive 3 paket. I varje bil kan lastas högst ett paket av vardera sort.

(2p) a) Formulera en optimeringsmodell som beskriver problemet att avgöra huruvida det är möjligt att utföra hela leveransen. Vilken typ av nätverksmodell har du formulerat? Lös ej!!

(1p) b) Antag att inte alla bilar kan transportera alla sorters paket. Låt × på plats (i, j) markera att bil i inte kan leverera paket av typ j:

Pakettyp 1 2 3 4 5 6 7
Bil 1  ×  ×
Bil 2  ×  ×
Bil 3 ×  ×

Bil 4

Bil 5  ×  ×

Genomför de ändringar som krävs i din modell. Av vilken typ är den nya modellen? Lös ej!!

Uppgift 2

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

min z = 3x_{1} + 2x_{2} + x_{3}
då 2x_{1} + x_{3} ≥ 3,
2x_{1} + 2x_{2} + x_{3} = 5,
x_{1} , x_{2} , x_{3} ≥ 0.

(1p) b) Har problemet en unik optimal lösning?

Uppgift 3

Betrakta följande system av linjära ekvationer:

x_{1} + x_{2} = 1
x_{1} − x_{2} = 2
x_{1} − 2x_{2} = 0.

Detta system är överbestämt och saknar lösning.

(1p) a) Formulera ett obegränsat optimeringsproblem för att bestämma en lösning som minimerar kvadratavvikelsen från en lösning.

(1p) b) Beskriv (generellt) det iterativa förfarandet hos Newtons metod, och lös problemet i a) med dess hjälp. Starta i origo.

(1p) c) Beskriv (generellt) det iterativa förfarandet hos brantaste lutningsmetoden, och lös problemet i a) med dess hjälp. Starta i origo och utför två iterationer.

Uppgift 4

Studera problemet

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

då ∑_{j=1}^{n} x_{j}^{2} ≤ 1,  (1)
x_{j} ≥ 0,  j = 1, …, n.  (2)

(1p) a) Visa att (P) är ett konvext problem.

(1p) b) Antag att min_{j∈{1,... ,n}}{c_{j}} < 0 och låt λ ≤ 0 och μ_{j} ≥ 0, j = 1, …, n, vara Lagrange-

multiplikatorer för bivillkoren (1) respektive (2). Vidare, låt

\overline{λ} = −\frac{1}{2} (∑_{j=1}^{n} (min\{0; c_{j}\})^{2})^{\frac{1}{2}} ; \overline{x}_{j} = \frac{min\{0; c_{j}\}}{2\overline{λ}}, \overline{μ}_{j} = max\{0; c_{j}\}, j = 1, …, n.

Visa att punkten (\overline{x}, \overline{λ}, \overline{μ}) är en KKT-punkt för problemet (P).

(1p) c) Visa att punkten \overline{x} är den enda optimallösningen till problemet (P).

(3p) Uppgift 5

Betrakta LP-problemet (A är en m × n-matris)

[P] min f(x) := c^{T}x,

då Ax = b,
x ≥ 0^{n}.

Formulera och bevisa starka dualsatsen.

(3p) Uppgift 6

Lös följande problem på enklaste sätt genom att utnyttja linjär dualitetsteori. Använd inte simplexmetoden.

max z = 6x_{1} − 12x_{2} + 20x_{3}
då  4x_{1} + 8x_{2} + 10x_{3} + x_{4} ≤ 60
3x_{1} + 4x_{2} + x_{3} − 2x_{4} ≥ 20
x_{1}, x_{2}, x_{4} ≥ 0
x_{3} ≤ 0

Uppgift 7

Betrakta det obegränsade optimeringsproblemet

[P] min f(x) := q^{T}x + \frac{1}{2}x^{T}Qx,

då x ∈ ℜ^{n},

där Q är positivt semidefinit men inte positivt definit. Vi angriper problemet med en Levenberg–Marquardt-strategi, dvs. vi använder en Newton-liknande metod där vi i det kvadratiska subproblemet adderar en multipel γ > 0 av enhetsmatrisen till Hessianen av f (dvs. till matrisen Q) för att garantera att systemet blir lösbart. Det betyder att, givet en iterationspunkt x_{t}, sökriktningen p_{t} bestäms genom att lösa det linjära systemet

[∇^{2}f(x_{t}) + γI]p = −∇f(x_{t}),  (1)

dvs.

[Q + γI]p = −(Qx_{t} + q).

(1p) a) Betrakta den algoritmiska formeln

x_{t+1} := x_{t} + p_{t},  t = 0, 1, …,  (2)

dvs. den algoritm som fås då man använder den Newtonliknande sökriktningen p_{t} från (1) och steglängden 1 i alla iterationer. Visa att det är ekvivalent med att låta x_{t+1} ges av lösningen till problemet

[P’(x_{t})] min f(y) + \frac{γ}{2} ∥y − x_{t}∥_{2}^{2},

då y ∈ ℜ^{n}.

(2p) b) Antag att en optimal lösning existerar till problemet [P]. Antag också att sekvensen {x_{t}} som genereras av algoritmen (2) konvergerar mot en punkt x_{∞}. (Detta kan visas.) Visa att x_{∞} är en optimal lösning till [P].