MATEMATISKA INSTITUTIONEN AVDELNINGEN FÖR OPTIMERINGSLÄRA OCH SYSTEMTEORI

5B1750 OPTIMERINGSLÄRA FÖR E OCH D, VT 2006

EXAMINATOR och FÖRELÄSARE:	Claes Trygger (trygger@math.kth.se) rum 3710, Lindstedtsvägen 25 tel 790 7419
ÖVNINGSASSISTENTER och LABORATIONSANSVARIGA:	Tove Gustavi (gustavi@math.kth.se) rum 3736, Lindstedtsvägen 25 tel 790 6294 Maja Karasalo (karasalo@math.kth.se) rum 3738, Lindstedtsvägen 25 tel 790 7132

KURSMATERIAL:

Jan Lundgren, Mikael Rönnqvist och Peter Värbrand: Optimeringslära, 2a uppl., Studentlitteratur, Lund, 2003. Pris 393-520 kr Säljs i bl.a. Teknologbutiken Exempelsamling i optimeringslära (röd framsida). Pris 60 kr. Extentor i optimeringslära 5B1750 för MMT (gul framsida). Pris 10 kr. Kopior på diverse overheadbilder m.m. (grön framsida). Pris 60 kr. Ovanstående (med undantag av boken) säljs på matematiska institutionens teknologexpedition, Klocktornet, Lindstedtsvägen 25. Eventuellt tillkommer diverse (men ganska få!) lösblad, vilka i så fall bortskänkes under kursen.

KURSINNEHÅLL:

Kapitel 1 och 2 utgör bakgrund och motivering. Kapitel 3 behandlar modellering - en viktig del av denna kurs och en självklar bakgrund till simplexmetoden. Observera att formulering av problem ingår i kursen. Kapitel 4 beskriver simplexmetoden i praktiken och simplexmetodens teori. Kapitel 5 Känslighetsanalys: hur robust är lösningen? Kapitel 6: Dualitetsbegreppet är av stort teoretiskt och praktiskt intresse. Kapitel 8 behandlar flöden i nätverk och formgivning av nätverk. Kapitel 9 innehåller en del nyttig information om konvexa mängder och funktioner. Kapitel 10 och 12 läses kursivt. Kapitel 11 behandlar nödvändiga (under vissa förhållanden även tillräckliga) optimalitetsvillkor för ickelinjära problem. Kapitel 13, 14 och 15 (av vilka kap 14 i huvudsak är kursivt) tar upp modellering och lösning av LP-problem med heltalsrestriktioner. Dessutom ingår sådant material som eventuellt delas ut under kursens gång.

LÄSANVISNINGAR:

HELA kapitlen 1, 2, 3, 4, 5 och 6 ingår. HELA kapitel 8 ingår, med följande undantag: Avsnittet 8.4.3 är kursivt. Avsnittet 8.7 ingår inte. HELA kapitel 9 ingår. Kapitel 10 är i sin helhet kursivt. Kapitel 11 ingår, men med följande undantag: Avsnittet 11.2 ingår inte. Avsnittet 11.4 avnjutes med kritisk blick. Hela kapitel 12 är synnerligen kursivt. HELA kapitel 13 ingår, men avsnitten 13.8 t.o.m. 13.11 är kursiva. Av kapitel 14 ingår endast avsnitten 14.1 och 14.2 Av kapitel 15 ingår endast de tre första avsnitten: 15.1, 15.2 och 15.3. Dessutom ingår sådant material som eventuellt delas ut under kursens gång.

FÖRSLAG TILL SJÄLVVERKSAMHET:

Lämpliga exempel i problemsamlingen är 1.1-1.5 (formuleringsexempel - viktiga att öva på) 1.11, 1.12, 1.14, 1.16, 1.18, 1.20, 1.22 2.11-2.14 3.1-3.5, 3.8, 3.10 och 3.12 4.1, 4.3 och 4.6 6.1, 6.4-6.7, 6.11 och 6.8 eller 6.9 med tillägget "Kontrollera att KKT-villkoren är uppfyllda i dina föreslagna lokala optima", samt 6.15a-e och 6.21. Här finns fler inspirationsfrämjande nyttigheter (modelleringsövningar). Och du - varför inte börja med ett besök bland operationsanalyslänkarna?

DATOR- LABORATIONER:

I kursen ingår två obligatoriska datorlaborationer, vilka skall redovisas skriftligt - och eventuellt även muntligt. Allmänna anvisningar - läs noga! Allt ni behöver till Lab 1 finns här: Här finner ni allmänna instruktioner för laborationerna tillsammans med texten till laboration 1 i postscriptfil respektive i pdfformat. English versions of computer exercise #1 can be found here: postscript file pdf file Här finns även filerna (simplexlösarna) alps.m och simple.m och dokumentation till Simple i postscriptformat och i pdfformat. Slutligen finns ett exempel i MATLAB Sista datum för inlämning är 7 april Rättade laborationsredogörelser kan hämtas fr.o.m. den 17 april Sista datum för inlämnande av eventuell komplettering är den 24 april Material till Lab 2: Lydelse i postscriptfil alternativt pdfformat. English versions of computer exercise #2: postscript file pdf file Därutöver behövs simplexlösarna alps.m och simple.m. För dokumentation: se instruktioner för Lab 1 Vidare behövs heltalslösaren lips.m och trädritningsfunktionerna mytreeplot.m, mytreelayout.m och postorder.m. Glädje kan man ha av ex2.m, vilket är ett exempel i MATLAB Sista datum för inlämning är 5 maj Rättade laborationsredogörelser kan hämtas fr.o.m. den 12 maj Sista datum för inlämnande av eventuell komplettering är den 19 maj Eventuella frågor ställs till Maja eller Tove. Watch this space for more info!

TENTAMINA:

Ordinarie tentamenstillfälle är lördagen den 20 maj kl 8-13. Datum för omtentamen är f.n okänt. Hjälpmedel: Penna, suddgummi och en välvässad hjärna.

PRELIMINÄRT SCHEMA FÖR FÖRELÄSNINGARNA:
TID	INNEHÅLL	AVSNITT I BOKEN
F1 on 15/3, kl 10-12 i sal V2	Allmänna betraktelser. Introduktion till linjärprogrammering (LP).	Kap 1-2 Kap 3-4
F2 fr 17/3, kl 13-15 i sal V2	Konvexa mängder. Geometrisk lösning av LP-problem. Det utvidgade problemet. Motivering av simplexmetodens teori och praktik.	Kap 2 Kap 4
F3 ti 21/3, kl 8-10 i sal V2	Simplexmetoden i praktiken. Komplikationer. Alternativa problemformuleringar.	Kap 4
F4 ti 28/3, kl 8-10 i sal V2	Artificiella variabler och konsten att komma igång: Tvåfasmetoden. Simplexmetoden i sammanfattning.	Kap 4
F5 on 29/3, kl 15-17 i sal D2	Dualitet.	Kap 6
F6 to 30/3, kl 10-12 i sal D3	Komplementaritet. Känslighetsanalys.	Kap 6 Kap 5
F7 ti 4/4, kl 8-10 i sal V2	Flöden i nätverk.	Kap 8
F8 to 6/4, kl 10-12 i sal D3	Flöden i nätverk.	Kap 8

PRELIMINÄRT SCHEMA FÖR FÖRELÄSNINGARNA:
TID	INNEHÅLL	AVSNITT I BOKEN
F9 ti 18/4, kl 8-10 i sal V2	Heltalsprogrammering : formulering. Allmänna betraktelser. Lösning av binära heltalsproblem med Branch & Bound.	Kap 13 Kap 14 & Kap 15
F10 to 20/4, kl 10-12 i sal D3	Mer heltalsprogrammering: rena och blandade heltalsproblem.	Kap 13 & Kap 15
F11 ti 25/4, kl 8-10 i sal D2	Ickelinjär optimering: inledning. Konvexa funktioner. Ickelinjär optimering (NLP) för problem utan bivillkor (teoretiska grunder). Kvadratiska former. Konvexitet.	Kap 9
F12 on 26/4, kl 15-17 i sal D2	NLP utan bivillkor i praktiken. NLP med likhetsbivillkor: Lagranges multplikatorregel.	Kap 10 Kap 11
F13 to 27/4, kl 10-12 i sal V1	Problem med olikhetsbivillkor. Karush-Kuhn-Tucker-villkoren. NLP i praktiken.	Kap 11 Kap 12
F14 ti 2/5, kl 8-10 i sal V2	Avslutande betraktelser över NLP. Tolkning av multiplikatorerna. Ev sammanfattning och överblick.	Kap 11 Kap 12

PRELIMINÄRT SCHEMA FÖR ÖVNINGARNA: Notera: Ö1, Ö2, Ö4, Ö5 och Ö7 äger rum i salarna Q33 och Q34, Ö3 äger rum i V32 och V34 medan Ö6 äger rum i Q34 och Q35.
TID	INNEHÅLL
Ö1 fr 24/3, kl 13-15	LP: Formulering. Simplexmetoden.
Ö2 fr 31/3, kl 13-15	Reviderade simplexmetoden. Dualitet.
Ö3 fr 7/4, kl 13-15	Mer om dualitet. Känslighetsanalys. Flödesproblem.
Ö4 fr 21/4, kl 13-15	Flödesproblem. Heltalsprogrammering.
Ö5 fr 28/5, kl 13-15	Heltalsproblem.
Ö6 on 3/5, kl 15-17	Konvexitet. Icke-linjär optimering utan bivillkor.
Ö7 fr 5/5, kl 13-15	Icke-linjär optimering med bivillkor.

Nyttiga operationsanalyslänkar

/ Claes Trygger