MAI - Matematiska institutionen

TAOP89 Optimering för IT

Undervisningsplan 2024

Denna information gäller fram till 2024. Information finns numera i Lisam. Vissa saker här är dock fortfarande relevanta. Notera att kurslitteratur inte längre är ett tillåtet hjälpmedel på tentamen. Efter sommaren 2024 har kursen en ny examinator.

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: 2025-08-25