Netværksoptimering
Overordnede kursusmål
At give deltagerne en grundig indføring i problemformulering og løsningsmetodik for netværksoptimeringsproblemer som disse opstår i bl.a. trafik- og transport-optimering samt produktions-planlægning. Deltagerne bliver i stand til at identificere et problem som værende et netværksoptimeringsproblem og til at løse det vha. forskellige dedikerede algoritmer ofte baseret på teknikker fra lineær/heltals programmering, primal-duale algoritmer og dekomposition.
See course description in English
Læringsmål
- Analysere og evaluere egnetheden af lineære/heltalsprogrammeringsteknikker til at formulere og løse netværksoptimeringsproblemer.
- Formulere og udvikle primal-dual-algoritmer til at løse netværksoptimeringsproblemer, der opstår inden for områder som trafik- og transportoptimering og produktionsplanlægning.
- Klassificere og skelne mellem de forskellige centrale algoritmer for klassiske netværksproblemer såsom mindste udspændende træ, korteste vej, projektplanlægning, maksimalt flow, min-cost flow og multicommodity flow.
- Kunne løse netværksoptimeringsproblemer ved hjælp af specialiserede algoritmer, der ofte er baseret på teknikker fra lineær/heltalsprogrammering, primal-dual-algoritmer og dekomponering.
- Evaluere og vælge passende grafer og netværk som modelleringsværktøjer til komplekse problemer.
- Vurdere og fortolke de centrale teoremer indenfor netværksoptimering, herunder køretid og korrekthed af de præsenterede algoritmer.
- Analysere og evaluere worst-case tidskompleksitet af algoritmer, der bruges til netværksoptimeringsproblemer.
- Udvikle og implementere simple datastrukturer til grafalgoritmer.
- Selvstændigt formulere og løse et større netværksoptimeringsproblem ved hjælp af passende algoritmer og teknikker.
- Kommuniker resultaterne af et stillet netværksoptimeringsproblem i en skriftlig rapport.
- Blive i stand ti at anvende grafer og netværk som modellerings-sprog
Kursusindhold
Algoritmer til netværk: Resume af relevant grafteori. Algoritmer til bestemmelse af korteste veje, maksimal strømning i netværk med kapacitetsbegrænsninger og strømning med minimal omkostning. Anvendelse af grafer og netværk til at formulere komplekse problemer.
Undervisningsform
Forelæsninger, øvelser, projektarbejde