Introduktion til Optimering og Operationsanalyse, Efteråret 2002.

Meddelser

Karakterer for vintereksamen 2002/03 er offentliggjort.

Ved vintereksamen blevet der klaget over at "følsomhedsanalyse" ikke var del af pensum i Hamacher-Klamroth. Klagen er taget til efterretning således at karakterskalaen blev justeret for alle eksaminerede.

Reeksamen sommer 2003, finder sted den 10. juni 2003.

Om kurset

Kurset udbydes af Datalogisk Institut og Institut for Matematiske Fag i fællesskab.
Denne side ligger på: www.diku.dk/undervisning/2002e/415/

Form og krav

Undervisningen tilbydes i form af 4 timers forelæsninger og 3 timers øvelser, ugentligt.
I løbet af kurset stilles 3 større opgaver som løses i grupper. Det er en forudsætning for deltagelse i eksamenen at disse projektopgaver er løst tilfredsstillende.

Kurset afsluttes med en skriftlig prøve den 14. januar 2003. Til denne prøve må der medbringes bøger og notater, men ingen computere, lommeregnere eller andre elektroniske hjælpemidler.

Kontaktpersoner

Jakob Krarup, krarup@diku.dk, David Pisinger, pisinger@diku.dk, Erik Christensen, echris@math.ku.dk.

Tid og sted

Forlæsninger: Tirsdage kl. 9 - 11 i Lille UP1 og fredage kl. 11 - 13 i Lille UP1.

Øvelser:

I tilfælde af at hold 3 bliver overtegnet vil matematikstuderende med skemamæssige problemer have førsteret til dette hold.

Undervisningsperioden er fra den 3. september til den 20. december 2002, og der er ikke øvelser i den første uge.

Indhold

Operationsanalysens overordnede formål er, via analyse af matematiske modeller, at finde gode løsninger til realistiske beslutningsproblemer. I erkendelse af _optimeringsmodellers_ betydning som teoretisk grundlag for fagområdet og udbredte anvendelighed i praksis indledes med _lineær programmering_ (LP), hvor såvel målet for en løsnings kvalitet som de begrænsninger som løsninger skal opfylde er lineære funktioner af ofte mange variable. Med _netværk_ som referenceramme fortsættes med en række specielt strukturerede LP-problemer og dertil hørende algoritmer. Endelig følger _heltalsprogrammering_ (eller _kombinatorisk optimering_), hvor tillægskravet er at nogle eller alle variable skal antage heltallige værdier, sædvanligvis blot 0 eller 1. Herunder redegøres tillige for begrebet NP-fuldstændighed.

Lærebøger

Udover de egentlige lærebøger vil der blive uddelt fotokopier, herunder kopier af kapitlerne 9 og 10 fra: og udvalgte kapitler fra I forbindelse med løsning af praktiske opgaver vil det være nødvendigt for eleverne at lære sig at betjene sig af mindst et af systemerne GAMS eller CPLEX.

Undervisningsplan

Undervisningen vil blive delt mellem de 3 lærere efter følgende plan.

Jakob Krarup vil med udgangspunkt i kapitlerne 1 - 4 fra Hamacher og Klamroths bog give en introduktion til operationsanalyse, med særligt henblik på problemer der kan beskrives som lineære optimeringsopgaver. Herunder vil algoritmer til løsning af sådanne problemer samt den teori der knytter sig hertil blive behandlet. Denne del af undervisningen finder sted i perioden fra 3. september til og med 1. oktober. Der vil blive stillet en obligatorisk opgave af 2 ugers varighed den 20. september.

Erik Christensen vil med udgangspunkt i kapitlerne 5 - 8 fra Hamacher og Klamroths bog samt kapitel 5 fra Wolseys bog give en introduktion til problemstillinger af operationsanalytisk natur som kan beskrives ved hjælp af grafteoretiske modeller. En stor del af disse opgaver kan omformes til lineære optimeringsproblemer. Teorien vil blive søgt illustreret ved gennemgang af flere praktiske eksempler. Denne del af undervisningen finder sted i perioden fra 4. oktober til og med 8. november. Der vil blive stillet en obligatorisk opgave af 2 ugers varighed den 29. oktober.

David Pisinger vil med udgangspunkt i kapitlerne 6 - 9 fra Wolseys bog samt kapitlerne 9 og 10 fra Williams bog give en introduktion til kombinatorisk optimering, eller heltalsprogrammering. Mange af disse problemstillinger kan modelleres som lineære optimeringsopgaver, men med heltallige variable. Sådanne problemer kan imimdlertid kun løses ved hjælp af specielle algoritmer. Undersøgelser af kompleksiteten af såvel heltalsproblemer som de præsenterede algoritmer vil være et væsentligt aspekt ved undervisningen. Denne del af undervisningen finder sted i perioden fra 12. november til og med 17. december. Der vil blive stillet en obligatorisk opgave af 2 ugers varighed den 3. december.

Jakob Krarup, vil fredag den 20. december afslutte kurset med en "juleforelæsning" hvori han bl. a. vil fortælle om den historiske udvikling af faget operationsanalyse i Danmark.

Uge Lærer Indhold/Emne Plancher Opgaver (gennemgås ved øvelserne) Diverse
36 JK Fundamentals of OR and LP (ORbit + HK 1.1)
Standard form, basic solutions (HK 2.1 + lidt af 2.2)		 Kopier uddeles ved forelæsning ingen øvelser
37 JK The Simplex Method (HK 2.2 + 2.3)
Degeneracy, cycling, Finding a feasible ... (HK 2.4, 2.5) GAMS (T. Stidsen)		 Kopier uddeles ved forelæsning Belgiums Best Beer, opg Q1-Q12
Hamacher-Klamroth opg 1, 2, 3		 Wyndor Glass
GAMS program
38 JK Dual programs, duality thms. (HK 3.1)
Complementary Slackness, Dual Simplex (HK 3.2, 3.3)		 Kopier uddeles ved forelæsning Pasta Basta, opg Q1-Q15
Hamacher-Klamroth opg 6, 7, 10		 Java applet til simplex
39 JK Linear Assignment, Hungarian algorithm (noter udleveres), Gæst: Bjarni Kristjansson
Simplex Method, Phase 1 (HK 2.5) Degeneration, cycling (HK 2.4) 		Kopier uddeles ved forelæsning Pasta Basta II - The rest of the story Q1-Q9.
Danske OR-opgaver opg. 5,6,7. (Se opgaver)
Hamacker-Klamroth opg. 8.
HL 4.4-9 (ps) (pdf)
40 JK
EC		 Dual Simplex (HK 3.3)
Introduktion til grafteori (HK s. 105-110) og (N s. 1-12, 20 23-25) 		Kopier uddeles ved forelæsning Danske OR-opgaver opg. 8, 11 og 12
Hamacker-Klamroth opg. 12 og 14
Opgave 11 mangler en
simplextabel. Tabellen
er her
41 EC Maksimale strømninger i netværk (HK s. 133-138, 149-151) og (N. s. 81-96)
Billigste strømninger i netværk, Mange OR opgaver som f. eks. transportproblemet, tildelingsproblemet og ruteplanlægning kan modelleres vha. strømninger med transportomkostninger. Denne model kan udtrykkes som et lineært program og løses som et sådant. (HK s. 117, 131 - 132, 160 - 165), ( W 3.1 - 3.4), (N s. 27, dual graf).
Opgavesamling til uge 41 (se opgaver)
Danske OR-opgaver opg. 13 		Opgavesamling med
netværkssimplex
opgaver i dueslaget
foran administrationen
på DIKU.
42 EC Efterårsferie.



43 EC Parring i en graf, (HK s. 179, 185 - 188), (N s. 125 - 130, 175 - 184)
Parringer, strømninger og dualitetsteori, (HK s. 191- 198), (W s. 53 - 62).
Danske OR-opgaver opg. 16 og 17.
Opgaver fra Frank Nielsen 1.11, 1.24, 3.1 (Opskriv også det tilsvarende LP) og 3.9.
44 EC (Se nye undervisningsplan)
Hillier og Lieberman: 4.3-4, 4.3-8, 4.5-2, 4.6-4, 5.3-3, 5.3-9.
45 EC
DP		 TIR: (Se nye undervisningsplan)
FRE: Introduktion til heltalsprogrammering, indikatorvariable, Williams kap 9		 FRE: ps, pdf HL: 5.3-3, 6.3-4, 6.3-6, 6.6-1, 6.7-3, 9.6-4
Wyndor Glass
IP version
46 DP TIR: Modelbygning, gode og dårlige formuleringer, Williams kap 10
FRE: Løsning af heltalsproblemer, branch-and-bound, Wolsey kap. 7		 TIR: ps, pdf
FRE: ps, pdf 		HL: 6.7-26, 9.3-6, 9.5-4
Heltalsprogrammering (se her): 4, 5, 6.
rettelser til Wolsey
47 DP TIR: Løsning af heltalsproblemer, branch-and-bound, preprocessing, Wolsey kap. 7
FRE: Snitplan-metoder: Chvatal snit, Chvatal-Gomory snit, Gomory snit, Wolsey kap 8		 TIR: ps, pdf
FRE: ps, pdf		 Heltalsprogrammering: 7, 8, 9.
Eksamenssæt 2000: Q11, Q12, Q19.
Eksamenssæt 1999; Q11, Q12.


48 DP TIR: Stærke lovlige uligheder: Facetter, dimension, cover uligheder. Wolsey kap 9
FRE: Grænseværdi beregning: lagrange relaxering, Wolsey kap. 10		 TIR: ps, pdf
FRE: ps, pdf		 Heltalsprogrammering 10,16,17.
Eksamenssæt 2000: Q16, Q17, Q18.
Eksamenssæt 1998: Q11, Q12, Q13.
 Knapsack problem gams Knapsack problem med to mængder gams
49 DP TIR: Grænseværdi beregning: lp-relaxering, surrogat relaxering, lagrange relaxering, subgradient optimering, Wolsey kap. 10
(godkendelsesopgave stilles)
FRE: NP-fuldstændighed, Wolsey kap 6		 TIR: ps, pdf
FRE: ps, pdf
 Heltalsprogrammering 11, 22, 23. Eksamenssæt 2000: Q13, Q14, Q15
Eksamenssæt 1999: Q15, Q19, Q20.
 Se 1.000.000 dollar opgaven og følgende kompendium
50 DP
JK		 TIR: NP-fuldstændighed, Wolsey kap 6, Forelæsning i store auditorium FRE: Post-optimal analyses (noter udleveres) TIR: ps, pdf Heltalsprogrammering 1, 2.
Wolsey afsnit 6.7 opgaver 1, 6.
Eksamenssæt 2000: Q20.
Eksamenssæt 1999: Q16, Q17.
51 JK
JK		 Gæst: Jørgen Tind, Interior point methods (HK 4)
juleforelæsning
Eksamenssæt 2001 (første 10 opgaver, sidste 10 opgaver). 2OK opgaven fra 90/91, opgave 1 fra sommeren 98. (findes her) [New]

Tilmelding

For studerende fra Datalogisk Institut senest 9. august. For studerende fra Institut for Matematiske Fag, senest den 14. juni 2002 kl 12.00 via den elektroniske tilmelding.
Senere tilmelding kan ske via email til Erik Christensen, echris@math.ku.dk.

Faglige forudsætninger

For studerende fra Datalogisk Institut: Datalogi 0 samt matematiske forudsætninger svarende til kurset Matematik og Beregninger. For studerende fra Institut for Matematiske Fag: Indholdet af Matematik 1 og Datalogi A.

[ Upwards | DIKU Home ]
David Pisinger