In English

SF2812 Tillämpad linjär optimering 7,5 hp

Applied Linear Optimization

  • Utbildningsnivå

    Avancerad nivå

  • Kursnivå (A-D)

    D

  • Huvudområde

    Matematik

  • Betygsskala

    A, B, C, D, E, FX, F

Kurstillfällen/kursomgångar

VT14 för programstuderande

Lärandemål

Kursens övergripande mål är dels att studenten ska behärska modeller, metoder och teori för olika varianter av linjär optimering och heltalsoptimering, dels att studenten ska kunna modellera och mha ett modelleringsspråk lösa realistiska linjära optimeringsproblem, samt presentera resultaten muntligt och skriftligt.

Mätbara mål

Efter genomgången kurs ska studenten kunna:

  • Förklara hur simplexmetoden fungerar.
  • Förklara hur primal-duala inrepunktsmetoder för linjärprogrammeringsproblem fungerar.
  • Utgående från en tillrättalagd problembeskrivning formulera ett linjärprogrammeringsproblem eller ett linjärt heltalsprogrammeringsproblem och lösa det med hjälp av det modelleringsspråk som används i kursen.
  • Tolka svaren i de lösta tillrättalagda verkliga problem med hjälp av fundamentala begrepp som känslighetsanalys.
  • Förklara hur trädsökning fungerar för att lösa heltalsprogrammeringsproblem.
  • Under lämpliga förutsättningar visa fundamentala resultat om linjärprogrammering såsom stark dualitet och existens av extrempunktslösningar.
  • Beskriva vad relaxeringar är.

Studenter som tillgodogjort sig kursen väl förväntas dessutom kunna:

  • Utnyttja problemstruktur för att lösa speciella klasser av linjärprogrammeringsproblem, exempelvis Dantzig-Wolfedekomposition.
  • Förklara hur lagrangerelaxering kan användas för att lösa linjära heltalsprogrammeringsproblem.
  • Förklara hur subgradientmetoder fungerar applicerade på duala problem till linjära heltalsprogrammeringsproblem.
  • Använda kolumngenerering för att lösa speciella klasser av linjärprogrammeringsproblem.
  • Använda stokastisk programmering för att modellera osäkerhet i problemdata.

Kursens huvudsakliga innehåll

Teori och metoder:

Simplexmetoden och inrepunktsmetoder för linjärprogrammering. Utnyttjande av problemstruktur, exempelvis dekomposition och kolumngenerering. Stokastisk programmering, metoder samt utnyttjande av problemstruktur. Branch and bound för heltalsprogrammering. Lagrangerelaxering och subgradientmetoder tillämpat på storskaliga heltalsprogrammeringsproblem med speciell struktur.

Projektuppgifter:

Denna del av kursen är uppbyggd kring praktisk optimeringsmodellering och problemlösning. Här ska man formulera optimeringsproblem, tillämpa sina metodkunskaper och lösa problemen med befintlig optimeringsprogramvara. Detta genomförs i form av projekt i mindre grupper. Ett viktigt inslag är samarbete inom gruppen samt muntlig och skriftlig presentation av resultaten.

Behörighet

Allmänt:

150 hp inklusive 28 hp inom matematik, 6 hp inom matematisk statistik och 6 hp inom optimeringslära. Engelska B.

Mer precist för KTH-studenter:

Avklarade kurser i en- och flervariabelanalys, linjär algebra, differentialekvationer, matematisk statistik, numerisk analys, optimeringslära.

Litteratur

Anges vid kursstart. Preliminär litteratur:

Linear and Nonlinear Programming av S.G.Nash och A.Sofer, McGraw-Hill, samt kompletterande material från institutionen.

Examination

  • PRO1 - Projektuppgift 1, 1,5 hp, betygsskala: A, B, C, D, E, FX, F
  • PRO2 - Projektuppgift 2, 1,5 hp, betygsskala: A, B, C, D, E, FX, F
  • TEN1 - Tentamen, 4,5 hp, betygsskala: A, B, C, D, E, FX, F

Krav för slutbetyg

En skriftlig tentamen (TEN1; 4,5 hp).
Projektuppgifter (PRO1; 3 hp).

Ges av

SCI/Matematik

Examinator

Anders Forsgren

Versionsinformation

Kursplan giltig från och med HT11.
Examinationsinformation giltig från och med HT07.