42115 Netværksoptimering
2024/2025
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.
Læringsmål
En studerende, der fuldt ud har opfyldt kursets mål, vil kunne:
- 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.
Litteraturhenvisninger
Kursusnoter, artikler
Sidst opdateret
02. maj, 2024