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 anvende grafer og netværk som modellerings-sprog
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:
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:
kapitler fra: Ahuja et al.: Network Flows: Theory, Algorithms, and
Applications, Prentice Hall.
Kursusnoter
