Komplexitet och operationsanalytiska metoder

Efter avslutad kurs skall studenten kunna:

• 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ässiga utmaningarna för att nå en exakt lösning,
• identifiera och implementera approximationsmetoder, både heuristika och stokastiska, för problem där exakt lösning inte är beräkningsmässigt möjligt.

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

Enskilt projektarbete som rapporteras skriftligt. En förutsättning för att examineras är att studenten deltagit aktivt vid minst två tredjedelar av schemalagda laborationer.

Föreläsningar och obligatoriska laborationer. Vid laborationerna tilldelas studenten uppgifter att lösa och i slutet av laborationen ges återkoppling på lösningarna på uppgifterna.

Som betygsskala används U–VG.