MAI - Matematiska institutionen

TAOP89 Optimering för IT

Undervisningsplan 2024

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.

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.9a, 4.3, 4.2. B: 2.1, 3.6, 3.1, 4.5. C: 2.3, 3.7, 3.9b, 3.10, 4.4, 4.7, 4.8.

Fö 2-3: Linjärprogrammering, simplexmetoden, LP-dualitet. Kap 6.
Le 2: Uppgifter: A: 6.5, 6.12, 6.20, 7.17, 7.18. B: 6.6, 6.4, 6.11, 6.13, 6.8. C: 6.7, 6.14, 7.19, 7.21.

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

Laboration 6: Implementering av simplexmetoden.

Fö 4: Optimering i grafer, billigaste uppspännande träd, handelsresandeproblem, brevbärarproblem. Kap 10.
Le 3: Uppgifter: A: 10.16, 10.8a-e, 10.1, 10.4, 10.21. B: 10.2, 10.3, 10.5a,b, 10.9a. 10.12, 10.17. C: 10.7, 10.10, 10.23.

Fö 5: Billigaste väg, maxflöde, dynamisk programmering. Kap 11, 12.2.
Le 4: Uppgifter: A: 11.1, 11.12, 12.2, 12.1, 11.9, 11.11, B: 11.2, 11.6, 11.3, 11.13, 12.13, 12.20c, 11.8. C: 11.4, 11.5, 12.6, 13.6b, 13.7a,c, 13.14b. 11.10.

Fö 6: Minkostnadsflöde. Kap 12.1, 12.3.
Le 5: Uppgifter: A: 12.5, 12.7, 12.3. B: 12.20a-b, 12.4. C: 12.8, 12.12.

Laboration 3: Minkostnadsflöde.

Fö 7: Grundläggande teori, optimalitetsvillkor, olinjär optimering utan bivillkor.
Kap 5, 8.
Le 6: Uppgifter: A: 5.2, 5.11, 5.16, 5.23, 5.18. B: 5.9, 5.7, 6.3, 5.19, 5.20. C: 5.1, 6.1, 5.15, 5.14.

Fö 8: Metoder för olinjär optimering med bivillkor.
Kap 8, 9, 17.
Le 7: A: 9.1a, 17.7, 9.5b, 9.8, 17.8. B: 9.2a, 9.7, 9.3a, 17.3. C: 9.11.

Fö 9: Heltalsproblem, trädsökning, plansnittning. Kap 13, 14.
Le 8: Uppgifter: A: 13.4a, 13.2, 13.15, 13.7a,b. B: 13.10a, 14.3, 13.16. C: 13.9, 13.1, 14.2, 13.12, 13.13.

Fö 10: Problemkomplexitet, heuristiker. Kap 15, 16.
Le 9: Uppgifter: A: 16.4, 16.12, 16.20, 16.8, 16.17. B: 16.19, 16.10, 16.13a. C: 16.3, 16.7, 16.11.

Laboration 4: Lokaliseringsproblemet, dualgap.

Laboration 5: Heuristik för lokaliseringsproblemet.

Sem: Redovisning om grön optimering i basgrupper. Inbjudan.

* Uppgifter lämpade för 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.

* Repetitionen är ej schemalagda, utan är endast förslag på vilka uppgifter man kan räkna hemma själv.

Lab 1: Simplex i tablå, känslighetsanalys (Vileopt).
Lab 2: Minkostnadsflöde (Vineopt).
Lab 3: Olinjär optimering (Nileopt).
Lab 4: Lokaliseringsproblemet, dualgap (GMPL).
Lab 5: Heuristik för lokaliseringsproblemet (Python/matlab/Octave).
Lab 6: Simplexmetoden, egen implementering (Python/matlab/Octave).

Laborationerna är schemalagda i MAI-pul. Laborationerna kan även göras annan tid, och i viss mån även på annan 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 och 6 är en implementeringar som lämpligtvis görs i Python, matlab eller 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: bjorn.moren@liu.se
Senast uppdaterad: 2024-10-02