Exam text content

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").