![[New]](new.gif)
Datalogisk Institut
Københavns Universitet
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.
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 heltaslproblemer.
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
Undervisere:
David Pisinger (DP) kursusansvarlig,
Kent H. Andersen (KHA), IMF
Forlæsninger:
Skemagruppe
B:
Tirsdag 13-15 auditorium 3, HCØ, fredag 12-14 auditorium 3, HCØ.
Øvelser: Tirsdag 10.15 - 12.00 (N010), Fredag 10.15 - 12.00 (N010).
| Dato | Lærer | Indhold/Emne | Projektopgave | Litteratur | Plancher | Opgaver |
| ti:6/2 fr:9/2 |
KHA | Repetetion af simplex algoritmer samt transportmodeller. | ti:Taha kap 3-4 fr:Taha kap 4-5 |
ti: fr: |
fr: Opg1 (fase 1 betyder initialize_simplex), Eksamenssæt Juni2003: M1-M5, T2 (hint: T2 kan løses ved inspektion). | |
| ti:13/2 fr:16/2 |
KHA | Advanceret linear programering og netværksmodeller/algoritmer | P1 stilles 16/2 |
ti:Taha kap 6-7 fr:Taha kap 7-8 |
ti: fr: |
ti: Opg2, Eksamenssæt Januar2005: S1-S8 fr: TAHA 4.2C 2 og 4.2D 3+4, TAHA 4.1A 6, TAHA 4.2C 6, Eksamenssæt Juni2003: T1 transp.opgave |
| ti:20/2 fr:23/2 |
DP | ti:Interior Point metoder fr:Modelbygning |
ti:
artikel, noter (kapitel 5)
fr:Williams 9,10 link |
ti:pdf fr:pdf |
ti:TAHA 4.1A 4 (scannet),
Januar2005: S9-S10 fr:Jan2006 Q1-Q7 + snak om P1 |
|
| ti:27/2 fr:2/3 |
DP | ti:Branch-and-bound fr:Gæsteforedrag |
P1 afleveres 27/2 |
ti:Wolsey 7 fr:Wolsey 7 |
ti:pdf fr:abstract |
ti:
Skriftlig eksamen 17. december 2003
fr: IP-opgaver: 4, 5, 6, 24. Eksamenssæt 1998: Q17, Q18. Eksamenssæt 2001: Q20. |
| ti:6/3 fr:9/3 |
DP | ti:Snitplan metoder fr:Snitplan metoder |
P2 stilles 9/3 |
ti:Wolsey 8 fr:Wolsey 8,9 |
ti:pdf fr:pdf |
ti:
IP-opgaver: 7, 8, 9, 25.
Eksamenssæt 2000: Q19.
Eksamenssæt 1999; Q11, Q12.
fr: IP-opgaver: 11, 14, 15. Eksamenssæt 1998: Q11, Q12, Q13. Eksamenssæt 1999: Q15, Q16, Q17. |
| ti:13/3 fr:16/3 |
DP | ti:Stærke lovlige uligheder fr:Grænseværdier |
ti:Wolsey 9 fr:Wolsey 10 |
ti:pdf fr:pdf |
ti:
IP-opgaver: 10,16,17.
Eksamenssæt 2000: Q11, Q20,
Q16, Q17, Q18.
fr: Eksamenssæt 1999: Q13, Q14. Eksamenssæt 2000: Q13. Eksamenssæt dec2003: Q17, Q18, Q19, Q20. Projektopgave 2 (diskussion) |
|
| ti:20/3 fr:23/3 |
DP | ti:Grænseværdier fr:Dantzig-Wolfe dekomponering |
P2 afleveres 20/3 |
ti:Wolsey 10 fr:Wolsey 11 |
ti:pdf fr:pdf |
ti:
IP-opgaver: 21, 22, 23
Eksamenssæt 1999: Q19, Q20.
Eksamenssæt 2000: Q14, Q15
fr: Eksamenssæt juni2003 (alt), Eksamenssæt juni2004 (alt) |
| dec 1998 | dec 1999 | dec 2000 | dec 2001 | juni2003 | dec 2003 | juni 2004 | jan 2005 | jan 2006, jan 2006 |