Datalogisk Institut
Københavns Universitet

Introduktion til Optimering og Operationsanalyse, blok 2, 2007-08

[Meddelelser] [Undervisningsplan] [Opgaver] [Litteratur] [SIS]

Meddelelser

Relaterede kurser

Algoritmer og datastrukturer
Videregående algoritmik
Recent research results in combinatorial optimization
Operationsanalyse 1 (IMF)

Forudsætninger

Videregående algoritmik (VA). Videregående algoritmik kan med fordel følges sideløbende med INT-OPT i blok 2.

Formål

Optimering handler om bedst mulig udnyttelse af knappe ressourcer. Teknisk set gøres dette ved at bestemme ekstreme værdier for funktioner af mange variable, hvor disse tillige skal tilfredsstille et antal begrænsninger. Med udgangspunkt i Simplex algoritmen som blev gennemgået på Vidergående Algoritmik gennemgås modelbygning med lineære variable, følsomhedsanalyse og dualitet i flere detaljer. Herefter betragtes løsning af graf- og netværksproblemer ved brug af lineær programmering. I anden del af kurset betragtes kombinatorisk optimering, hvor nogle af de involverede beslutningsvariable kun må antage heltallige værdier. Kravet om heltallige løsninger gør ofte problemer NP-hårde at løse, hvorfor vi gennemgår en række teknikker til at løse og/eller dekomponere problemerne.

Kompetencer

Deltagerne vil blive i stand til at bygge komplekse lineære og heltals-modeller, samt kunne skelne polynomielle formuleringer fra NP-hårde. Endvidere vil deltagerne få erfaring med en lang række teknikker der kan bruges til at løse NP-hårde heltalsproblemer.

Indhold

Modelbygning
Dualitet
Følsomhedsanalyse
Graf og flow problemer
Branch-and-bound for IP problemer
Snitplan metoder
Stærke lovlige uligheder
Grænseværdier
Dantzig Wolfe dekomponering

Forelæsning og øvelser

Undervisere:
David Pisinger (DP) kursusansvarlig

Instruktorer:
Thomas Friis Antonsen
Anja Westh-Liljenbøl

Forlæsninger og øvelser:
Skemagruppe C komplet oversigt
Forelæsning mandag 10-12, Store Auditorium, DIKU
Forelæsning onsdag 10-12, Lille Auditorium, DIKU
Øvelser, mandag 8-10, N018 (Anton), N010 (Anja)
Øvelser, onsdag 13-15, N004 (Anton), N022 (Anja)
Første øvelsesgang onsdag 14/11, sidste øvelsesgang mandag 14/1.

Elektronisk materiale

 Java Applet til simplex
Endnu en Java Applet til simplex
Liste over rettelser til Wolsey findes her
"Snydearket" pdf

Undervisningsplan

 Foreløbig plan for kurset. Forbehold for ændringer.

Dato Lærer Indhold/Emne Projektopgave Litteratur Plancher Opgaver
ma:12/11
on:14/11		 DP OR, Simplex, Revised simplex
ma:Taha 2.1, 2.2, 2.3, 2.4, 3.1, 3.2, 3.3, 3.4
on:Taha 7.1, 7.2, 7.3		 ma:pdf
on:pdf		 on: Opg1 (fase 1 betyder M-method), Eksamenssæt Juni2003: M1-M5, T2 (hint: T2 kan løses ved inspektion).
ma:19/11
on:21/11		 DP Sensitivity analysis, grafproblemer P1 stilles
21/11 (forside)		 ma:Taha 3.6, 4.1, 4.2, 4.3, 4.4, 4.5
on:Taha 5.1, 5.2, 5.3, 5.4, 6.3, 6.4		 ma:pdf
on:pdf		 ma: PastaBasta Q1-Q8, Eksamenssæt Januar2005: S1-S8
on: PastaBasta Q9-Q20, TAHA 4.2C 3 og 4.2D 3+4, TAHA 4.1A 6, TAHA 4.2C 1, Eksamenssæt Juni2003: T1
ma:26/11
on:28/11		 DP ma:Interior Point metoder
on:Gæsteforedrag, MOSEK		 ma: artikel, noter (kapitel 5)
on:
 ma:pdf
on:pdf		 ma:TAHA 4.1A 4, Januar2005: S9-S10, transp.opgave
on:Jan2006 Q1-Q7 + snak om P1
ma:3/12
on:5/12		 DP ma:Modelbygning
on:Branch-bound		 P1 afleveres
5/12		 ma:Williams 9,10
on:Wolsey 7		 ma:pdf
on:pdf		 ma: Skriftlig eksamen 17. december 2003 (i opgave 8 er det rigtige svar ikke blandt de 5 foreslåede muligheder)
on: IP-opgaver: 4, 5, 6, 24. Eksamenssæt 1998: Q17, Q18. Eksamenssæt 2001: Q20.
ma:10/12
on:12/12		 DP ma:Snitplan metoder
on:Snitplan metoder		 P2 stilles
12/12 (forside)		 ma:Wolsey 8
on:Wolsey 8,9		 ma:pdf
on:pdf		 ma: IP-opgaver: 7, 8, 9, 25. Eksamenssæt 2000: Q19. Eksamenssæt 1999; Q11, Q12.
on: IP-opgaver: 11, 14, 15. Eksamenssæt 1998: Q11, Q12, Q13. Eksamenssæt 1999: Q15, Q16, Q17.
ma:17/12
on:2/1		 DP ma:Stærke lovlige uligheder
on:Grænseværdier
ma:Wolsey 9
on:Wolsey 10		 ma:pdf
On:pdf		 ma: IP-opgaver: 10,16,17. Eksamenssæt 2000: Q11, Q20, Q16, Q17, Q18.
on: Eksamenssæt 1999: Q13, Q14. Eksamenssæt 2000: Q13. Eksamenssæt dec2003: Q17, Q18, Q19, Q20.
Projektopgave 2 (diskussion)
ma:7/1
on:9/1		 DP ma:Grænseværdier
on:Dantzig-Wolfe dekomponering		 P2 afleveres
7/1		 ma:Wolsey 10
on:Wolsey 11		 ma:pdf
on:pdf		 ma: IP-opgaver: 21, 22, 23 Eksamenssæt 1999: Q19, Q20. Eksamenssæt 2000: Q14, Q15
on: Eksamenssæt juni2003 (alt), Eksamenssæt juni2004 (alt)

Eksamen

 Eksamen: Skriftlig prøve den 23. januar 2008. Reeksamen: Skriftlig prøve den 16. april 2008.

Opgaver

Løsninger til opgaver gennemgået ved øvelserne

Den bedste gennemgang af opgaverne finder sted ved øvelserne, men skulle du have været syg findes her forslag til besvarelser:

Litteratur
[ Upwards | DIKU Home ]