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. En studerende, der fuldt ud har opfyldt kursets mål, vil kunne:

• beskrive hvordan teknikker fra lineær/​heltasprogrammering kan bruges til at udvikle og bevise korrekthed af forskellige netværks algoritmer
• forklare 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.
• analysere og beskrive værste-tids tidskompleksitet af en algoritme.
• beskrive simple datastrukturer til grafalgoritmer
• arbejde selvstændigt med et større netværksproblem
• udarbejde en rapport om fundne resultater

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. kapitler fra: Ahuja et al.: Network Flows: Theory, Algorithms, and Applications, Prentice Hall.
Kursusnoter 02. november, 2020