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 programmering, heltalsprogrammering 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
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:
Lineær Programmering på grafer: 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.
Litteratur:
Ahuja et al.: Network Flows: Theory, Algorithms, and Applications, Prentice Hall. Kursusnoter
Mulighed for GRØN DYST deltagelse:
Dette kursus giver den studerende en mulighed for at lave eller forberede et projekt som kan deltage i DTUs studenterkonference om bæredygtighed, klimateknologi og miljø (GRØN DYST). Se mere på http://www.groendyst.dtu.dk/kursustilmelding.aspx
