Kursinformation TAOP86

TAOP86 Kombinatorisk optimering med miljötillämpningar

Undervisningsplan 2011

Under föreläsningarna genomgås bakgrund, teori och metoder. Under lektionerna genomgås övningsexempel. Kursplanen förutsätter även problemlösning i form av hemarbete. Laborationerna och basgruppsarbetet ger fördjupad förståelse för vissa moment i kursen.

Pass 1 - 3: Introduktion, modellformulering, grafisk lösning, komplexitet. Kap 1, 2, 3, 4, 5.4.
Uppgifter: A: 2.2, 3.2, 3.3, 3.10a, 4.3, 4.7. B: 2.1, 3.5, 3.1, 4.5. C: 2.3, 3.7, 3.10b, 3.9, 4.4.

Pass 4 - 5: Grundläggande teori, optimalitetsvillkor. Kap 5.
Uppgifter: A: 5.9, 5.2, 5.12, 8.1, 5.21. B: 5.7, 6.3, 5.1, 5.19. C: 5.11, 6.1, 5.17, 5.15.

Pass 6 - 7: Linjärprogrammering, simplexmetoden. Kap 6.
Uppgifter: A: 6.4, 6.11, 6.15. B: 6.5, 6.10, 6.12, 6.7. C: 6.6, 6.13.

Pass 8 - 9: LP-dualitet och känslighetsanalys. Kap 7.
Uppgifter: A: 7.1, 7.5, 7.10, 7.9. B: 7.14, 7.3. C: 7.2, 7.13, 7.15.

Laboration 1: Simplex i tablå, känslighetsanalys.

Laboration 2: Implementering av simplexmetoden.

Pass 10 - 11: Optimering i grafer, billigaste uppspännande träd, handelsresandeproblem, brevbärarproblem. Kap 10.
Uppgifter: A: 10.1, 10.19, 10.9, 10.3, 10.4. B: 10.2, 10.5a,b, 10.10. 10.15. C: 10.7, 10.11.

Pass 12 - 13: Billigaste väg, maxflöde, dynamisk programmering. Kap 11, 12.2.
Uppgifter: A: 11.1, 11.2, 11.9, 11.12, 12.1, 12.7, 11.10, 13.17b, 13.9b. B: 11.4, 11.5, 12.2, 12.8a, 12.19. 11.11, 13.7b, 13.8a,c. C: 11.7, 11.8, 12.9.

Pass 14 - 15: Minkostnadsflöde. Kap 12.1, 12.3.
Uppgifter: A: 12.6, 12.3, 12.13b, 12.10. B: 12.4, 12.5, 12.11, 12.12, 12.14. C: 12.17.

Laboration 3: Minkostnadsflöde.

Pass 16 - 17: Heltalsproblem, trädsökning, plansnittning. Kap 13, 14.
Uppgifter: A: 13.12, 14.4, 13.11, 13.8a,b. B: 13.4, 13.5, 13.15. C: 13.1, 14.3, 13.16.

Pass 18 - 19: Problemkomplexitet, heuristiker. Kap 15, 16.
Uppgifter: A: 15.6 (valda delar), 15.1, 16.3, 16.1a,c, 16.4, 16.8. B: 15.3, 16.7. C: 16.8.

Laboration 4: Lokaliseringsproblemet, dualgap.

Laboration 5: Heuristik för lokaliseringsproblemet.

Pass 20: Redovisning, repetition.

Uppgifter lämpade för repetition: 7.18, 7.21, 12.20, 12.21.

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.

Laborationer

Lab 1: Simplex i tablå, känslighetsanalys (Vileopt). Schemalagd, 2h, handleding.
Lab 2: Implementering av simplexmetoden (matlab/Octave). Schemalagd, 2+2h, ej handledning.
Lab 3: Minkostnadsflöde (Vineopt). Schemalagd, 2h, handledning.
Lab 4: Lokaliseringsproblemet, dualgap (GMPL). Schemalagd, 2h, handledning.
Lab 5: Heuristik för lokaliseringsproblemet (matlab/Octave). Schemalagd, 2+2h, ej handledning.

Laborationerna är schemalagda i MAI-pul. Under laboration 1, 3 och 4 erbjuds handledning på plats. Laborationerna kan även göras annan tid, och i viss mån även på annan plats. Lab 1, 3 och 4 görs med hjälp av speciell programvara som tillhandahålls via MAI:s datorsystem. Lab 2 och 5 är implementeringar som lämpligtvis görs i matlab (eller Octave), och kräver ingen annan programvara. Alla laborationer redovisas skriftligt, och programkod skickas in via epost.

Kurslitteratur:
Kaj Holmberg: Optimering (2010), Liber. ISBN 978-91-47-09935-1.

Sidansvarig: kaj.holmberg@liu.se
Senast uppdaterad: 2011-01-14