MAT-41122 Matemaattinen optimointiteoria 1
Tentti
1.3.2011
Ei muistiinpanoja, kirjallisuutta tai taulukoita esillä. Laskin sallittu.
Kaavakokoelmat 1 ja 2 jaetaan.
Jos uusit 1.välikokeen, ratkaise tehtävät 1-4.
Jos uusit 2. välikokeen, ratkaise tehtävät 5-8.
Tentti: ratkaise tehtävät 1, 2, 4, 7 ja 8
1, Tarkastellaan tehtävää
max 2=x,+2x,
n 520
0) NNN
a +, 21
x,%, 20
1
a) Osoita, että x, = [s] on käypä kantaratkaisu.
b) Ratkaise tehtävä simplex-algoritmilla alkuratkaisusta x, aloittaen.
2 a) Mitä on kaksivaihetekniikka probleemaan
min z=c'x
(2) Ax=b
x20
sovellettuna?
b) Onko mahdollista, että vaiheen I probleeman kohdefunktion 2 arvot ovat
alhaalta rajoittamattomia (inf 2 =-), vaikka alkuperäisen probleeman
(2) optimiratkaisu on äärellinen?
3. — 4) Selosta kaksi eri menetelmää todeta laskennallisesti lineaarisen
optimointiprobleeman (2) (ks. edellinen tehtävä) käypä joukko tyhjäksi.
b) Määrittele käsite äärisäde.
€) Miten määritellään konveksin monitahokkaan dimensio?
4. — Tarkastellaan probleemaa
min z=clx,+01x, + ex,
3) AX, + 43, + Ax, 2b,
x,,x, 20,x, vapaa
missä c,,x, e R", 4 eR””,beR”.
Muodosta probleeman (3) duaaliprobleema
Unn 1
a) Mikä on jonon x, ri suppenemisen kertaluku?
4
5
2
s
b) Onko hakusuunta d - ] funktion
f(x y) = x- day +4x? + 33?
4
vähenemissuunta pisteessä x, = [s i ?
a) Laske funktiolle f(x, y)=x—-y+2xy+2x*+ y? Newtonin menetelmän
1
mukainen hakusuunta pisteestä x, = [3]
b) Osoita: Jos kahdesti jatkuvasti differentioituvan funktion
Hessen matriisi H,(x,) on pisteessä x, posi
sesti definiitti, niin
Newtonin menetelmän antama hakusuunta pisteestä x, pisteeseen x, ,,
siirryttäessä on vähenemissuunta.
Tarkastellaan probleemaa
min /(x) = (x, 27 +(x, - 1)
vox, <0
0
"5
ehdot. Onko jokin niistä lokaali minimikohta? Entä globaali?
x,+x,-2<0
”
2
oita 1 2
Tutki pisteistä x, = [i] = [a l mitkä niistä toteuttavat KKT-
Sovella sisäistä sakkofunktiomenetelmää inverssiesteellä probleemaan
min f(2) = x
1-x<0
MAT-41122 Matemaattinen optimointiteoria 1
Kaavakokoelma 1
2010-2011
1. GX] +...tep =O & cj+...+=0 > c,=...=0=0.
2. &,T = ey -eB'N
3 min ((xg)/aj5 | 50) = (xg),/a,s
Minimointi
4. Maksimointi &
raj =
muuttuja > 0
muuttuja < 0
muuttuja vapaa
min Ww= we,/X+---+ W, e, x
Ax=b
x20
muuttuja > 0
muuttuja < 0
muuttuja vapaa
raj >
raj <
raj =
w,20,i=1,...,m; $m=1)
i=1
»
min max w; le; = 2]
Ax =
x20
. ||€
min
b
I+
Zo
[a <0,5=1....
>
4
MAT-41122 Matemaattinen optimointiteoria 1
Kaavakokoelma 2
2010-2011
1. WVS(X)+ H Vg,(x')+---+ 4, Vg, (x')=0
WEIX')=0, i=1,....m.
2.
Ty(X) = (d € R"|Vg,(x)' d<0,i=1, m) oja ER" |Vh(x9)'d=0,j=1,...,5)
3. VAIK) + H VEIX )+:-+ Hn VEH(X ) + A Vh (X) ++ 4, Vh(x')=0
WEX')=0, i
4 20,i=1,...,m
x SO)
4. PSE FG)
Kt Th
5 Huth -So)
7 Xa =X—0,Vf,), a, =argmin (x, -aVflx,))
k HKI VSK)
9. dy=-8,=b-0x,,
11.
14.
15.
- B0)=-3m-8(2)). = B00=-5"
Kai = +a,d, ,
a gld,
+ ala,"
da = TBa:1 + Ba, 3
6 = 81,04.
* afoa,
g, =0x,-b.
P(x) = 5 (max(0,2,(x))) , P0)= Y(2.00+ 2)!
i=1
AX, 1) = [(x)+A" h(x) +5 h(x)" h(x)
+.
8.0)
2 g,(%,)= Max g(x,), S, =S$) fale)+ Ve,(x,Y(x—x,)<0
(D Ax<0,cx>0 (xelR")
(11) Aly=c, y>20 (y eR”).
(D) 4Ax<0 —(xeR”)
(m) A'y=0,y20,y70 — (yeR").