Göm meny
Kursinformation TAOP86

TAOP86 Kombinatorisk optimering med miljötillämpningar

Undervisningsplan 2017

Denna sida ska inte användas 2018 och framåt.

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.

Tillägg till och fel i övningsexemplen i boken.

Fö 1: Introduktion, modellformulering, grafisk lösning, komplexitet. Kap 1, 2, 3, 4, 5.4.
Le 1: Uppgifter: A: 3.2, 2.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.

Fö 2: Linjärprogrammering, simplexmetoden. Kap 6.
Le 2: Uppgifter: A: 6.4, 6.11, 6.15. B: 6.5, 6.10, 6.12, 6.7. C: 6.6, 6.13.

Fö 3: Grundläggande teori, optimalitetsvillkor. Kap 5.
Le 3: Uppgifter: A: 5.2, 5.12, 5.19, 5.18. B: 5.9, 5.7, 6.3, 5.21. C: 5.1, 5.11, 6.1, 5.17, 5.15.

Fö 4: LP-dualitet och känslighetsanalys. Kap 7.
Le 4: 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.

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

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

Fö 7: Minkostnadsflöde. Kap 12.1, 12.3.
Le 7: 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.

Fö 8: Heltalsproblem, trädsökning, plansnittning. Kap 13, 14.
Le 8: 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.

Fö 9: Problemkomplexitet, heuristiker. Kap 15, 16.
Le 9: Uppgifter: A: 16.1a,c,d, 16.4, 16.9, 16.3, 16.10. B: 16.7, 16.11. C: 16.8.

Fö 10: Miljötillämpningar. Grön optimering.

Laboration 4: Lokaliseringsproblemet, dualgap.

Laboration 5: Heuristik för lokaliseringsproblemet.

Fö 11: Redovisning i basgrupper. Inbjudan.

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), 2h.
Lab 2: Implementering av simplexmetoden (matlab/Octave/Python), 2+2h.
Lab 3: Minkostnadsflöde (Vineopt), 2h.
Lab 4: Lokaliseringsproblemet, dualgap (GMPL), 2h.
Lab 5: Heuristik för lokaliseringsproblemet (matlab/Octave/Python), 2+2h.

Laborationerna är schemalagda i MAI-pul. 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 inte kräver någon annan programvara. Alla laborationer redovisas skriftligt, och programkod skickas in via epost.


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

Sidansvarig: Kaj Holmberg
Senast uppdaterad: 2019-11-29