Netværksoptimering

• 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 samt 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, som 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 inden for 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
• Kommunikere resultaterne af et stillet netværksoptimeringsproblem i en skriftlig rapport
• Blive i stand til at anvende grafer og netværk som modelleringssprog

Algoritmer til netværk: Resumé 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 formulering af komplekse problemer.

• 36 – 49 (fre 8-12)

Forelæsninger, øvelser og projektarbejde