Raul Kangro, Liivi 2-408, rkangro@ut.ee
Eksamid: 7. ja 24. jaanuaril 2000 a. kell 9:00-12:00 Liivi 2-104
Konsultatsioonid: 6. jaanuaril kell 11:00 Liivi 2-208 ja 23. jaanuaril kell 11:00 Liivi 2, ruum selgub hiljem.
Kursuse materjalid dvi formaadis
Dvi faile saab vaadata unix/linux masinas xdvi programmiga, Windowsi masinas näiteks PCTeX abil, lisaks saab vajalikku tarkvara siit
Eelmisel nädalal antud kodutöid korjatakse neljapäevastes loengutes tõenäosusega 0,25
Kodutöö nr. 1. Tähtaeg 16. september 1999.
Leida xi+1 avaldis Schmidti meetodi kasutamise korral.
Kodutöö nr. 2. Tähtaeg 23. september 1999.
1) Eeldame, et funktsioon f on alt tõkestatud ning konstandiga L
Lipschitz pideva gradiendiga. Näidata, et kui gradiendimeetodis valida ai=1/L,
siis grad f(xi) koondub nullvektoriks.
2) Näidata, et kumera funktsiooni iga lokaalne miinimum on selle funktsiooni
globaalseks miinimumiks. Tõestada, et rangelt kumeral funktsioonil saab olla
ülimalt üks lokaalne miinimumkoht.
3) Leida kiireima laskumise meetodiga x1, kui x0=(-1,1)
ja f(x)=x12-x1x2+2x22.
Kodutöö nr. 3. Tähtaeg 30. september 1999.
1) Näidata, et ruutfunktsiooni f(x)=(1/2)Ax*
x-b* x korral langeb üldise
funktsiooni jaoks antud kaasgradientide meetod kokku ruutfunktsiooni jaoks
defineeritud meetodiga.
2) Lahendada Lagrange'i kordajate meetodiga ülesanne min(x1+2x2
: x12+4x22=1)
3) Näidata, et ruumi Rn iga lõik on kumer hulk
4) Lahendada graafiliselt ülesanne max{x1+x2: x1-x2<=2,
-x1+2x2<=4, 2x1+x2<= 7, x>=
0}.
Kodutöö nr. 4. Tähtaeg 7. oktoober 1999.
1) Teisendada ülesanne
min{2x1-3x3: x1+x2<=4, x1+x3+x5=6,
2x1-x2+x3+x4>= 2, x1>=0,
x2<= -1, x3>=1, x4>=0}
kanoonilisele kujule.
2) Näidata, et (LP) ülesande sihifunktsiooni iga lokaalne maksimum lubataval
hulgal on globaalseks maksimumiks sellel hulgal.
Kodutöö nr. 5. Tähtaeg 14. oktoober 1999.
1) Lahendada simpleksmeetodiga ülesanne
max{2x1+x2: x1+x2<=5, x1+3x2<=9,
0<=x1<= 4, x2>= 0}.
Kodutöö nr. 6. Tähtaeg 21. oktoober 1999
1) Lahendada duaalse simpleksmeetodiga ülesanne
min{x1+x2: x1+2x2>=1, 2x1+x2>=1,
x1>=0, x2>= 0}.
Kodutöö nr. 7. Tähtaeg 28. oktoober 1999
1) Lahendada kunstliku baasi meetodiga ülesanne
min{x1-2x2+x3+2x4: x1-2x2+x3+x4=8,
2x1+x2-x3-2x4=-2, x>= 0}.
2) Lahendada leksikograafilise duaalse simpleksmeetodiga ülesanne
min{x1+x2 : x1-x2<=1, -2x1-x2<=-4,
2x1+3x2<=18, x>= 0}.
Kodutöö nr. 8. Tähtaeg 4. november 1999
a) Sõnastada ülesandega
max{2x1+x2: 3x1-x2<=3, x1-2x2>=-4,
2x1+x2>=2, x>= 0}
duaalne ülesanne.
b) Leida mõlema ülesande lahendid.
Kodutöö nr. 9. Tähtaeg 11. november 1999
Lahendada Gomory I algoritmi abil ülesanne
max{3x1+4x2: 0<=x1<=2, 2x1+3x2<=6,
x2>= 0, x1, x2 on täisarvud}.
Kodutöö nr. 10. Tähtaeg 18. november 1999
Lahendada harude ja tõkete meetodiga ülesanne
max{2x1+x2: x2-x1>=-1, 2x1+3x2<=6,
x1+x2>= 1, x>= 0, x1, x2
on täisarvud}.
Kodutöö nr. 11. Tähtaeg 25. november 1999
1) Tõestada, et kumera hulga sulund on kumer hulk
2) Olgu X ja Y mingid ruumi Rn alamhulgad.
Defineerime Z={x-y: x kuulub
hulka X, y kuulub hulka Y}
a) Tõestada, et kui x0 on mingi hulga X sisepunkt
ning y0 kuulub hulka Y, siis x0-y0
on hulga Z sisepunkt.
b) Näidata, et kui X ja Y on kumerad, siis ka Z on kumer.
Hindamisest. Kursuse lõpuhinde määramiseks summeeritakse kodutööde (kuni 10p), kahe kontrolltöö (kumbki kuni 25p) ja kirjaliku lõpueksami (kuni 55p) eest saadud punktid.
''A''>=90p
80p<= ''B''<90p
70p<= ''C''<80p
60p<= ''D''<70p
50p<= ''E''<60p
''F''<50p
Kahest kontrolltööst ühte on soovi korral võimalik kursuse lõpus ümber teha..
Kui esimesel katsel eksamiga kursusest läbi ei saa, siis järeleksamil tuleb E saamiseks saada 50-65% punktidest ning "D" saamiseks 66-100% punktidest (kontrolltööd ja kodutööd enam arvesse ei lähe). "D"-st paremat hinnet järeleksamil ei ole võimalik saada.
Kirjandus
Ü. Kaasik, L.Kivistik, Operatsioonianalüüs, 1982
E. Übi, Planeerimise ja juhtimise matemaatika, 1998
E. Polak, Optimization. Algorithms and Consistent Approximation. Applied Mathematical Sciences 124, Springer-Verlag 1997.
F. L. Vasilev, Chislennye metody resheniya ekstremalnykh zadach, 1980