
DM872: Matematisk Optimering i Praksis
Kommentar
Efterår: ordinær eksamen (januar), første reeksamen (marts) og 2. reeksamen i (juni)
Forår: ordinær eksamen (juni), første reeksamen (august) og 2. reeksamen i (januar)
Indgangskrav
Faglige forudsætninger
Studerende, der følger kurset, forventes at:
- Have kendskab til indholdet af kurset: DM545 / DM871: Lineær og heltalsprogrammering
- Kunne programmere
Kurset bygger oven på den viden, der er erhvervet i kurset "Lineær og Heltalsprogrammering", og giver et fagligt grundlag for at lave et master thesis projekt og andre både teoretiske og praktiske studie-aktiviteter så vel som at studere emnerne for andre valgfri kurser, der kan vælges i Datalogi, MatØk, Anvendt Matematik eller andre uddannelsen.
Formål
Kurset fokus er på avancerede løsningsteknikker til matematiske optimeringsproblemer, der opstår fra konkrete anvendelser i skedulering og ruteplanlægning. Eksempler på anvendelser er: flow shop og jobshop skedulering i produktion, ressourcebegrænset aktivitetsplanlægning, bemanding og arbejdshold planlægning, tidsplanlægning og køretøj ruteplanlægning med tidsvinduer. Kurset sigter på at give teorien bag løsningsmetoderne og frem for alt praktisk erfaring med at implementere dem på numeriske instanser af disse optimeringsproblemer.
Anvendelser vil blive præcist formuleret og modelleret med hensyn til blandet heltal og lineær programmering (MILP) problemer. På grund af størrelsen af disse instanser fra disse problemer er grundlæggende løsningsteknikker for MILP-problemer utilstrækkelige, og avancerede løsningsteknikker nødvendige. Vi vil lære om Lagrangian relaxation, Dantzig Wolfe decomposition, søjle generering og Benders decomposition med hovedfokus på implementeringen af disse teknikker på baggrund af et software system til MILP problemer.
Målbeskrivelse
- Genkende og beskrive problemer, der opstår i planlægning og routing, ved brug af formel notation.
- Formulere en matematisk (lineær) model fra en given problembeskrivelse i ord.
- Beskrive avancerede løsninger, baseret på blandet heltal og lineær programmering.
- Implementere avancerede løsninger til MILP-problemer ved brug af computersoftware.
- Analysere løsningsmetoderne med hensyn til beregningstid og løsningskvalitet.
- Tænk innovativt ved at se muligheder for at anvende teoretisk viden i erhverv.
Indhold
- Branch and Cut
- Lagrangian relaxation
- Dantzig-Wolfe decomposition og Søjle generering
- Branch and Price
- Stochastic programmering
- Bemanding og arbejdshold planlægning
- Køretøj ruteplanlægning
- Software systemer til løsning af MILP-problemer
Litteratur
Eksamensbestemmelser
Eksamenselement a)
Tidsmæssig placering
Udprøvninger
Obligatoriske opgaver
EKA
Censur
Bedømmelse
Identifikation
Sprog
Hjælpemidler
ECTS-point
Uddybende information
Vejledende antal undervisningstimer
Undervisningsform
- Læse forskningartikler
- Løse hjemmeopgaver
- Anvende det tilegnede viden i praktiske opgaver
Ansvarlig underviser
Yderligere undervisere
Skemaoplysninger
Administrationsenhed
Team hos Registratur
Udbudssteder
Anbefalede studieforløb
Overgangsordninger
Se overgangsordninger for alle kurser på Det Naturvidenskabelige Fakultet.