| TAOP86 |
Kombinatorisk optimering med miljötillämpningar, 8 hp
/Combinatorial Optimization with Environmental Applications/
För:
IT
|
OBS! |
Får ej ingå i examen samtidigt som TAOP33.
|
| |
Prel. schemalagd
tid: 68
Rek. självstudietid: 145
|
| |
Utbildningsområde: Naturvetenskap
Huvudområde: Matematik, Tillämpad matematik Nivå (G1,G2,A): G2
|
| |
Mål:
IUAE-matris
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
|
| |
Förkunskaper: (gäller studerande antagna till program som kursen ges inom, se 'För:' ovan)
Linjär algebra, Diskreta strukturer, Datastrukturer och algoritmer.
OBS! Tillträdeskrav för icke programstudenter omfattar vanligen också tillträdeskrav för programmet och ev. tröskelkrav för progression inom programmet, eller motsvarande.
|
| |
Organisation:
Kursen ges i form av storseminarier, laborationer och basgruppsarbete. Storseminarierna kan ses som en blandning av föreläsningar och lektioner, och behandlar teori, metoder och modeller. Tid ägnas även åt övningar i modellformulering och problemlösning. Laborationerna innehåller både implementering av optimeringsalgoritmer och lösning av kombinatoriska optimeringsproblem med hjälp av tillgänglig programvara.
|
| |
Kursinnehå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.
|
| |
Kurslitteratur:
Kaj Holmberg: Optimering (Liber, 2010).
|
| |
Examination: |
TEN1
LAB1
BAS1
|
En skriftlig tentamen (U,3,4,5)
Laborationer (U,G)
Basgruppsarbete (U,G)
|
4 hp
2 hp
2 hp
|
| |
|
|
|