MATEMATISKA INSTITUTIONEN
AVDELNINGEN FÖR
OPTIMERINGSLÄRA OCH SYSTEMTEORI
5B1722 TILLÄMPAD OPTIMERINGSLÄRA FÖR MMT,
VT 2005

EXAMINATOR och FÖRELÄSARE: Claes Trygger (trygger@math.kth.se)
rum 3710, Lindstedtsvägen 25
tel 790 7419
ÖVNINGSASSISTENT
och
LABORATIONSANSVARIG:		 Mats Werme (werme@math.kth.se)
rum 3713, Lindstedtsvägen 25
tel 790 8433

KURSMATERIAL: Jan Lundgren, Mikael Rönnqvist och
Peter Värbrand: Optimeringslära,
2a uppl., Studentlitteratur, Lund, 2003.
Pris 385-535 kr

Säljs i bl.a. Teknologbutiken

Exempelsamling i optimeringslära
(röd framsida). Pris 60 kr.

Extentor i optimeringslära 5B1722 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.

Datorlaborationer.
Kommer att finnas tillgängliga från kursens hemsida då tiden är mogen. Allmänna anvisningar finns här.

Eventuellt 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.


DETALJERAD KURSBESKRIVNING:
  • 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.16, 1.18, 2.1-2.2, 2.6 (ganska lätta)
1.14, 1.20, 1.22, 2.4, 2.9 och 2.10
(eventuellt något mer krävande)
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.21a
7.1, 7.5 eller 7.6, 7.10-7.12

Här finns fler nyttigheter.

Och du -
varför inte börja med ett besök bland operationsanalyslänkarna?

DATOR-
LABORATIONER:		 I kursen ingår några 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:

Sista datum för inlämning:
Måndagen den 14 februari 2005

Material till Lab 2:

Sista datum för inlämning: 2 mars 2005

Eventuella frågor ställs till Mats.

Watch this space for more info!
TENTAMINA: Ordinarie tentamenstillfälle är
tisdagen den 8 mars kl 14-19.
Omtentamen i påskperioden äger rum
tisdagen den 29 mars kl 14-19.
Hjälpmedel:
Räknedosor som lånas ut av institutionen.


PRELIMINÄRT SCHEMA FÖR FÖRELÄSNINGARNA:
TID SAL INNEHÅLL AVSNITT
I BOKEN
F1 må 17/1, kl 10-12 E31 Allmänna betraktelser.
Introduktion till linjärprogrammering (LP).		Kap 1-2
Kap 3-4
F2 to 20/1, kl 13-15 V33 Konvexa mängder.
Geometrisk lösning av LP-problem.
Det utvidgade problemet.
Motivering av simplexmetodens teori och praktik. 		Kap 2

Kap 4

F3 fr 21/1, kl 8-10E31 Simplexmetoden i praktiken.
Komplikationer.
Alternativa problemformuleringar.
Kap 4
F4 on 26/1, kl 13-15E36 Artificiella variabler och konsten att komma igång:
Tvåfasmetoden.
Simplexmetoden i sammanfattning. 		Kap 4
F5 fr 28/1, kl 8-10 E31 Dualitet.
Kap 6
F6 on 2/2, kl 13-15V21 Komplementaritet.
Känslighetsanalys. 		Kap 6
Kap 5


PRELIMINÄRT SCHEMA FÖR FÖRELÄSNINGARNA:
TID SAL INNEHÅLL AVSNITT
I BOKEN
F7 to 3/2, kl 13-15 V22 Flöden i nätverk. Kap 8
F8 on 9/2, kl 13-15 E36 Flöden i nätverk. Kap 8
F9 fr 11/2, kl 8-10 E31 Heltalsprogrammering : formulering.
Allmänna betraktelser.
Lösning av binära heltalsproblem
med Branch & Bound. 		Kap 13
Kap 14
&
Kap 15
F10 on 16/2, kl 13-15 Q34 Mer heltalsprogrammering:
rena och blandade heltalsproblem.
Kap 13 &
Kap 15
F11 må 21/2, kl 10-12 E31 Ickelinjär optimering: inledning.
Konvexa funktioner.
Ickelinjär optimering (NLP) för problem
utan bivillkor (teoretiska grunder).
Kvadratiska former.
Konvexitet. 		Kap 9
F12 on 23/2, kl 13-15 V11 NLP utan bivillkor i praktiken.
NLP med likhetsbivillkor:
Lagranges multplikatorregel.
Kap 10

Kap 11

F13 to 24/2, kl 13-15 E36 Problem med olikhetsbivillkor.
Karush-Kuhn-Tucker-villkoren.
NLP i praktiken.		Kap 11

Kap 12

F14 må 28/2, kl 10-12 E32 Avslutande betraktelser över NLP.
Tolkning av multiplikatorerna.
Ev sammanfattning och överblick. 		Kap 11
Kap 12
 


PRELIMINÄRT SCHEMA FÖR ÖVNINGARNA:
TID SAL INNEHÅLL
Ö1 må 24/1, kl 10-12 E35 LP: Formulering. Simplexmetoden.
Ö2 må 31/1, kl 10-12 E31 Reviderade simplexmetoden.
Dualitet.
Ö3 må 7/2, kl 10-12 E31 Mer om dualitet.
Känslighetsanalys.
Flödesproblem.
Ö4 må 14/2, kl 10-12 V32 Flödesproblem.
Heltalsprogrammering.
Ö5 to 17/2, kl 13-15 V22 Heltalsproblem.
Ö6 fr 25/2, kl 8-10E31 Konvexitet.
Icke-linjär optimering utan bivillkor.
Ö7 on 2/3, kl 8-10 E31 Icke-linjär optimering med bivillkor.


/ Claes Trygger