MAI - Matematiska institutionen

TAOP88 Optimering för ingenjörer

Undervisningsplan 2024

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

Föreläsningar

Fö 1: Introduktion, modellformulering, grafisk lösning.
Kap 1, 2, 3, 4, 5.4.

Fö 2-3: Linjärprogrammering, simplexmetoden, LP-dualitet.
Kap 5, 6, 7.

Fö 4: Optimering i grafer, billigaste uppspännande träd, handelsresandeproblem.
Kap 10.1, 10.2, 10.3, 10.6.

Fö 5: Billigaste väg, maxflöde, dynamisk programmering.
Kap 11, 12.2.

Fö 6: Minkostnadsflöde, simplex i nätverk, tillordningsproblem.
Kap 12.1, 12.3.

Fö 7: Grundläggande teori, optimalitetsvillkor, olinjär optimering utan bivillkor.
Kap 5, 8.

Fö 8: Metoder för olinjär optimering med bivillkor.
Kap 8, 9, 17.

Fö 9: Heltalsproblem, trädsökning, plansnittning.
Kap 3.2, 3.3, 3.4, 13, 14.

Fö 10: Heuristiker.
Kap 16.

Se även detaljerade läsanvisningar till boken.

Lektioner

Le 1: A: 3.2, 2.2, 3.3, 3.9a, 4.3, 4.2. B: 2.1, 3.6, 3.1, 4.5. C: 3.7, 3.9b, 4.4, 4.7, 4.8.

Le 2: A: 6.5, 6.12, 6.20, 7.17, 7.18. B: 6.3, 6.4, 6.6, 6.11, 6.13, 6.8. C: 6.7, 6.14, 7.19, 7.21.

Le 3: A: 10.16, 10.8a-e, 10.1, 10.4, 10.21. B: 10.2, 10.3, 10.5, 10.9a. 10.12, 10.17. C: 10.7, 10.10, 10.14, 10.23.

Le 4: A: 11.1, 11.12, 12.2, 12.1, 11.9, 11.11. B: 11.2, 11.6, 11.3, 11.13, 12.6, 12.20c. C: 11.4, 11.5, 12.13, 11.10.

Le 5: A: 12.5, 12.7, 12.3. B: 12.20a-b, 12.4. C: 12.8, 12.12.

Le 6: A: 5.2, 5.11, 5.16, 5.23, 5.18. B: 5.9, 5.7, 5.14, 5.15, 5.20. C: 5.1, 6.1.

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.

Le 8: 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.

Le 9: 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.

Bra 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.

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).

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 är en implementering som lämpligtvis görs i matlab, octave eller python, 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