Kombinatorisk optimering gk

Mål

Kursen behandlar matematiska verktyg för att lösa och analysera kombinatoriska optimeringsproblem. Fokus ligger på att modellera problemet, välja och använda den mest effektiva algoritmen för varje specifik problemstruktur samt användaprogramvara för att lösa olika typer av problem. Kursens lärandemål är kategoriserade under följande två huvudrubriker och lärandemålen M1-M6 inom denna struktur specificerar vad studenten ska kunna efter fullgjord kurs.

1. Inom matematisk modellering och användning av programvara för att lösa optimeringsproblem, kunna

• (M1) identifiera optimeringsfrågor, beskriva och formulera viktiga typer av kombinatoriska och heltal optimeringsproblem som matematiska modeller och bedöma problemens svårighetsgrad med hjälp av komplexitetsteori;
• (M2) kombinera kunskaper inom modellering av optimeringsproblem, användning av optimeringsmjukvara och programmering för att lösa ett givet optimeringsproblem, samt genomföra rimlighetsbedömning ochanalys av resultatet;
• (M3) tillämpa optimeringslära på problemställningar hållbar utveckling.

2. Inom lösningsmetoder och teori, kunna

• (M4) använda grundläggande begrepp och satser, samt välja och tillämpa lämpliga metoder för att lösa och analysera linjära programmeringsproblem modellerade med kontinuerliga beslutsvariabler;
• (M5) använda grundläggande begrepp och satser, samt välja och tillämpa lämpliga metoder för att lösa och analysera linjära programmeringsproblem modellerade med diskreta beslutsvariabler eller i form av ett nätverk;
• (M6) utveckla en enkel heuristik för ett strukturerat kombinatoriskt optimeringsprobleminom ramen för vad som beskrivs av kursinnehållet.
• Som en del av (M4), (M5) och (M6) kunna tydligt redovisa beräkningar och resonemang, samt göra enklare rimlighetsbedömningar av resultaten.

Innehåll

Introduktion till optimering, problemformulering, grafisk lösning, beräkningskomplexitet. Simplexmetoden, linjär dualitet och känslighetsanalys. Grundläggande grafteori, modeller och metoder för att finna billigaste uppspännande träd, billigaste handelsresandetur, billigaste brevbärartur, billigaste väg, minkostnadsflöde samt maxflöde. Metoder för heltalsoptimering, bl.a. trädsökningsmetoder. Problemkomplexitet samt heuristiker.