Kombinatorisk optimering med miljötillämpningar

Mål

Kursen behandlar matematiska verktyg för att formulera, lösa och analysera kombinatoriska optimeringsproblem, till stor del baserade på olika nätverks- och grafstrukturer. Hållbar utveckling och miljöaspekter intar en framträdande roll i de tillämpningar som berörs. En viktig aspekt är att kunna välja och använda den mest effektiva algoritmen för varje specifik problemstruktur. Algoritmerna är avsedda att passa för storskaliga problem och datorimplementering.Efter fullgjord kurs skall studenten kunna:redogöra för viktiga klasser av kombinatoriska optimeringsproblem.formulera kombinatoriska optimeringsproblem som matematiska modeller, i relevanta fall med graftermer, samt bedöma problemens svårighetsgrad med hjälp av komplexitetsteori.förklara uppbyggnaden av och principerna bakom effektiva lösningsmetoder samt välja och använda specifika metoder för att lösa olika typer av kombinatoriska optimeringsproblem.använda tillgänglig programvara för att lösa optimeringsproblem.medverka vid utveckling av ny programvara för optimeringsproblem.utveckla heuristiker för vissa strukturerade kombinatoriska optimeringsproblem.förklara och använda grundläggande begrepp, såsom lokal och global optimalitet, konvexitet, extrempunkt, komplexitet, dualitet, heuristik, trädsökning, plansnittning samt graftermer, speciellt träd och cykler av olika typer.ge exempel på hur kombinatorisk optimering kan användas för att främja hållbar utveckling och förbättra miljön

Innehåll

Introduktion till optimering, modellformulering, grafisk lösning, beräkningskomplexitet, problemkomplexitet. Simplexmetoden, linjär dualitet och känslighetsanalys. Grundläggande grafteori och översikt av olika optimeringsproblem i grafer.Modeller och metoder för att finna billigaste uppspännande träd, billigaste handelsresandetur, billigaste brevbärartur, billigaste väg, billigaste tillordning, minkostnadsflöde samt maxflöde.Metoder för heltalsoptimering, speciellt trädsökning, plansnittning och dynamisk programmering. Heuristiker för svåra kombinatoriska optimeringsproblem.Exempel på tillämpningar som berör olika aspekter inom hållbar utveckling, bland annat vinjetter som rör ett terminsgemensamt scenario.