Fra og med efteråret 2012 opdeles 42113 Netværks
og Heltalsprogrammering i to kurser hver på 5 ECTS; et for
heltalsprogrammering og et for netværksoptimering. 42113 udgår
herefter.
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:
forstå hvordan teknikker fra lineær/heltasprogrammering kan
bruges til at udvikle og bevise korrekthed af forskellige netværks
algoritmer
kende til primal-duale algoritmer og deres anvendelse
beskrive og bruge de centrale algoritmer indenfor de klassiske
netværksproblemstillinger: mindst udspændende træ, korteste vej,
projektplanlægning, maximum flow, minimum cost flow og
multicommodity flow.
kunne opskrive en heltalsmodel for de studerede problemer
gengive betydningen af og indholdet af de centrale beviser
indenfor netværksoptimering.
have en forståelse for værste-tids tidskompleksitet af en
algoritme.
forstå simple datastrukturer til grafalgoritmer
kunne arbejde selvstændigt med et større netværksproblem
udarbejde en rapport om fundne resultater
Kursusindhold:
Primal-duale 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.
Litteraturhenvisninger:
Ahuja et al.: Network Flows: Theory, Algorithms, and Applications,
Prentice Hall. Kursusnoter
