Homepage
TAOP89 Optimering för IT
Undervisningsplan 2023
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.16, 6.20.
B: 6.6, 6.4, 6.11, 6.13, 6.8.
C: 6.7, 6.14,
7.17, 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,
11.7.
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.18, 12.24.
B: 12.3, 12.20a-b, 12.4, 12.8, 12.9, 12.10, 12.26.
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,c, 9.5b, 9.8, 17.2, 9.6.
B: 9.2a, 9.7, 9.3a, 17.3.
C: 9.11, 17.8.
Fö 9: Heltalsproblem, trädsökning, plansnittning.
Kap 13, 14.
Le 8:
Uppgifter:
A: 13.10, 14.3, 13.9, 13.15, 13.7a,b.
B: 13.4, 13.16, 13.12.
C: 13.1, 14.2, 13.13.
Fö 10: Problemkomplexitet, heuristiker.
Kap 15, 16.
Le 9:
Uppgifter:
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.
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.
Laborationer
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: Kaj Holmberg
Senast uppdaterad: 2023-09-27