Komplexitet och operationsanalytiska metoder

Efter godkänd kurs ska studenten kunna:

1. kritiskt analysera och formulera praktiska problem inom ramen för generella operationsanalytiska problem och kontextualisera dem i ett strukturerat beslutsramverk,
2. utforma och motivera formuleringar av praktiska problem som linjär- eller heltalsprogrammeringsmodeller, med hänsyn till modellens antaganden och begränsningar,
3. utveckla, implementera och utvärdera algoritmer för att lösa linjära- och heltalsprogrammeringsproblem, samt analysera deras beräkningsmässiga effektivitet,
4. kritiskt klassificera beräkningsproblem i komplexitetsklasser baserat på de resurser som krävs för att erhålla en exakt lösning och diskutera implikationerna för tillämpning,
5. utforma, implementera och utvärdera heuristiska och stokastiska approximationsmetoder för att hantera beräkningsmässigt intraktabla problem, samt bedöma deras prestanda i relation till exakta metoder,
6. analysera och kvantifiera komplexiteten hos komplexa dynamiska system, karakterisera deras centrala egenskaper och kritiskt särskilja dem från slumpmässiga och kaotiska system.

Med praktiska problem avses här tillämpade problemställningar av relevans för operationsanalytiska metoder, där modellen baseras på verkliga eller realistiska data.

Kursen behandlar formulering och lösning av linjärprogrammeringsproblem som är beräkningsmässigt hanterbara, samt hur man empiriskt estimerar beräkningsresurser i termer av lagring, minne och tidsåtgång för olika algoritmer. För denna problemklass introduceras Simplex-metoden och dess egenskaper. Vidare behandlas beräkningsmässigt intraktabla problem, såsom heltalsprogrammeringsproblem, med fokus på varför exakta algoritmer fallerar och vilka implikationer detta har för tillämpning. Approximerande metoder, inklusive heuristiska och stokastiska angreppssätt som genetiska algoritmer, introduceras och analyseras som alternativ vid intraktabilitet. Kursen inkluderar även en genomgång av komplexa dynamiska system, där särskild vikt läggs vid att beskriva, kvantifiera och särskilja deras beteende från slumpmässiga och kaotiska system. Dualitet i linjärprogrammering behandlas, liksom hur olika algoritmiska metoder relaterar till klassiska operationsanalytiska tillämpningar såsom stoppregler, nätverksflöden, spelteori, schemaläggning och processplanering. Dessa tillämpningar används för att kontextualisera beslutsproblem och illustrera de modeller och metoder som ingår i kursen

• Skriftlig rapport av individuellt projekt
• Seminarium

Som betygsskala används U–G.

On completion of the course, students will be able to:

1. critically analyse and formulate practical problems within the class of general operations research problems, and situate them in a structured decision framework
2. design and justify formulations of practical problems, such as linear or integer programming models, while taking into account model assumptions and limitations
3. develop, implement, and evaluate algorithms for solving linear and integer programming problems, and analyse their computational efficiency
4. classify computational problems into complexity classes based on the computational resources that are required to obtain exact solutions, and discuss the implications for applications
5. design, implement, and evaluate heuristic and stochastic approximation methods for addressing computationally intractable problems, and assess their performance relative to exact methods
6. analyse and quantify the complexity of complex dynamical systems, characterise their key properties, and distinguish them from random and chaotic systems.