At give deltagerne en grundig indføring i problemformulering og løsningsmetodik for netværksoptimeringsproblemer, som opstår bl.a. inden for trafik- og transportoptimering samt produktionsplanlægning. Deltagerne bliver i stand til at identificere et problem som et netværksoptimeringsproblem og til at løse det ved hjælp af forskellige dedikerede algoritmer, ofte baseret på teknikker fra lineær/​heltalsprogrammering, primal-duale algoritmer og dekomposition. En studerende, der fuldt ud har opfyldt kursets mål, vil kunne:

• 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. Kursusnoter og artikler 15. oktober, 2025