Kursplan

Komplexitet och operationsanalytiska metoder för forskarstuderande

Kurskod
FMI2223
Poäng
7,5 högskolepoäng
Nivå
Forskarnivå
Akademi
Akademin Industri och samhälle
Ämnestillhörighet
Mikrodataanalys (MIKRODAT)
Fastställd
Fastställd 2017-10-04.
Kursplanen gäller fr.o.m. 2019-10-04.

Lärandemål

Efter avslutad kurs ska doktoranden kunna:

• uttrycka och relatera ett praktiskt problem till klassen av generella operationsanalytiska problem samt till ett beslutsramverk,
• uttrycka praktiska problem som ett linjärprogrammeringsproblem,
• uttrycka praktiska problem som ett heltalsprogrammeringsproblem,
• implementera algoritmer som löser linjära- och heltalsprogrammeringsproblem,
• kategorisera problem i olika former av komplexitet beroende på de beräkningsmäss-iga utmaningarna för att nå en exakt lösning,
• identifiera och implementera approximationsmetoder, både heuristiska och sto-kastiska, för problem där exakt lösning inte är beräkningsmässigt möjligt.

Innehåll

Kursen behandlar linjärprogrammeringsproblem som är beräkningsmässigt möjliga att lösa och hur man empiriskt kan skatta beräkningsresurs avseende lagring, minne och tidsåtgång för en viss algoritm. För denna klass av problem introduceras Simplex-metoden och Big M-metoden. Vidare behandlas beräkningsmässigt olösbara problem såsom heltalsprogrammeringsproblem, samt hur och varför dessa algoritmer fallerar i samband med olösbara problem. Kursen går också igenom avancerade metoder för att lösa beräkningsmässigt olösbara problem av både stokastiskt och heuristiskt slag såsom Tabu Search, Branch and Bound, Relaxation, Genetic Algorithms och Simulated Annealing. Dualitet introduceras och de algoritmiska metoderna relateras till klassiska och generella operationsanalytiska problem såsom stoppregler, nätverksflöden, spelteori, schemaläggning och processplanering.

Examinationsformer

Examination sker i form av enskilt projektarbete och examinerande seminarium

Arbetsformer

Kursen består av föreläsningar, obligatoriska laborationer och självständiga studier.

Betyg

Som betygsskala används U - G

Förkunskapskrav

  • Magisterexamen i Mikrodataanalys eller motsvarande