Homepage
TAOP33 Kombinatorisk optimering grundkurs
Undervisningsplan 2022
Föreläsningarna behandlar bakgrund, teori och metoder. Övningsexempel genomgås på lektionerna. Kursplanen förutsätter även problemlösning i form av hemarbete. Laborationerna ger fördjupad förståelse för vissa moment i kursen.
Föreläsningar
Fö 1: Introduktion, modellformulering, grafisk lösning, komplexitet.
Kap 1, 2, 3, 5.4.
Fö 2: Linjärprogrammering, simplexmetoden.
Kap 5, 6.
Fö 3: LP-dualitet.
Kap 7.
Fö 4: Optimering i grafer, billigaste uppspännande träd, handelsresandeproblem.
Kap 10.1, 10.2, 10.3, 10.6.
Fö 5: Billigaste väg, maxflöde, dynamisk programmering.
Kap 11, 12.2.
Fö 6: Minkostnadsflöde, simplex i nätverk, tillordningsproblem.
Kap 12.1, 12.3.
Fö 7: Heltalsproblem, trädsökning, plansnittning.
Kap 13, 14.
Fö 8: Problemkomplexitet, heuristiker.
Kap 15, 16.
Lektioner
Le 1: A: 3.2, 2.2, 3.3, 3.9a. B: 2.1, 3.6, 3.1. C: 3.7, 3.9b, 3.10.
Le 2: A: 6.5, 6.12, 6.16, 6.20. B: 5.9ab, 6.3, 6.6, 6.11, 6.13. C: 6.7, 6.8, 6.14.
Le 3: A: 7.1, 7.10, 7.4, 7.18de, 7.17. B: 7.19, 7.20bcd, 7.21, 7.9. C: 7.7, 7.8, 7.3, 7.2.
Le 4: A: 10.16, 10.8a,d,f, 10.1, 10.4, 10.12a-f,h-j, 10.13a-e,g, 10.21, 10.3. B: 10.2, 10.5, 10.9, 10.17, 10.22. C: 10.7, 10.10, 10.14, 10.23.
Le 5: A: 11.1, 11.12, 12.2, 12.1, 11.9, 11.11. B: 11.2, 11.6, 11.3, 11.13, 12.6, 12.20c. C: 11.4, 11.5, 12.13, 11.10.
Le 6: A: 12.5, 12.7, 12.18, 12.24. B: 12.3, 12.20a-b, 12.4, 12.8, 12.9, 12.10, 12.26. C: 12.8, 12.12.
Le 7: A: 13.10, 14.3, 13.9, 13.15, 13.7a,b,d. B: 13.4, 13.16, 13.12. c: 13.1, 14.2, 13.13.
* Le 8: A: 16.1a,c, 16.4, 16.12, 16.13, 16.17. B: 16.19, 16.9, 16.10. C: 16.3, 16.7, 16.1d, 16.11, 16.8.
* Repetition. 7.13, 7.16, 12.14, 12.15.
Uppgifterna är uppdelade i kategori A (nödvändiga uppgifter), B (bra övningsuppgifter) och C (relevanta uppgifter). Uppgifter ur A-gruppen tas upp på lektionstid. Resterande A-uppgifter samt B-uppgifterna räknas självständigt, på lektionstid och/eller hemma. C-uppgifterna är lite mer inriktade på förståelse och överbetyg.
* Lektion 7 och repetitionen är ej schemalagda, utan är endast förslag på vilka uppgifter man kan/bör räkna hemma själv.
Laborationer
Lab 1: Simplex i tablå, känslighetsanalys (Vileopt).
Lab 2: Minkostnadsflöde (Vineopt).
Lab 3: LP-problem, formulering, lösning (GMPL).
Lab 4: Lokaliseringsproblemet, dualgap (GMPL).
Lab 5: Heuristik för lokaliseringsproblemet (python/matlab/Octave).
Laborationerna är schemalagda i MAI-pul. Vissa delar kan dock göras vid valfri tid och i viss mån på valfri plats. Lab 1, 2 och 3 görs med hjälp av speciell programvara som tillhandahålls via MAI:s datorsystem. Lab 4 kan göras med valfri lösare för linjära heltaslproblem (såsom GLPK). Lab 5 görs lämpligtvis i Python/matlab/Octave, och kräver ingen annan programvara. Alla laborationer redovisas skriftligt, och programkod skickas in via epost.
Kurslitteratur:
Kaj Holmberg: Optimering (2018) upplaga 2, Liber. ISBN
978-91-47-12578-4.
Sidansvarig: Kaj Holmberg
Senast uppdaterad: 2022-09-21