FEL3350 Nätverksoptimering 4,0 hp
Innehåll och lärandemål
Kursinnehåll
1. Introduktion till nätverksoptimering (L1)
- baseras på kap 1 i kursboken
- grundläggande terminologi och notation
- diskutera exempel på nätverksoptimering
- grunderna i linjär nätverksoptimering
2. "Shortest path problems" (L2)
- baseras på kap 2 i kursboken
- exempel på tillämpningsområden
- vanliga verktyg för att lösa problemet
- lösningsalgoritmernas prestanda
3. Maximala flödesproblem (L3)
- baseras på kap 3 i kursboken
- exempel på tillämpningsområden
- vanliga verktyg för att lösa problemet
4. Kostnadsminimering av flöden (L4)
-baseras på kap 4 i kursboken
- ekvivalenta varianter
- utveckla resultat inom dualitet i samband med problemet
5. Auktionsalgoritmer för kostnadsminimering av flöden (L5)
- baseras på kap 7 i kursboken
- steg för algoritmdesign
- varianter av auktionsalgoritmer
6. Flödesargument för begränsning av blandningstider för Markovkedjor (mixing time) (L6)
- introduktion av konceptet blandningstider för Markovkedjor
- begränsningar av konduktansen och relationen till egenvärden
- varuflöden och "method of canonical path"
7. "Accelerated dual descent" för flödesoptimering (L7)
- Newtons metod
- Approximativ Newtons metod baserad på nätverkets struktur
Lärandemål
Efter slutförd kurs kommer deltagaren:
- känna till grunderna för linjär, icke-linjär, och diskret optimering
-känna till de viktigaste aspekterna av nätverksoptimering
- analysera på djupet de viktigaste problemen med nätverksoptimering
- kunna tillämpa nätverksoptimering i praktiska ingenjörsproblem
- utveckla ett forskningsprojekt
Kurslitteratur och förberedelser
Särskild behörighet
Rekommenderade förkunskaper
Utrustning
Kurslitteratur
D. P. Bertsekas, Network Optimization Continuous and Discrete Models, Athena Scientific, Belmont, Mass., USA, 1998.
Examination och slutförande
När kurs inte längre ges har student möjlighet att examineras under ytterligare två läsår.
Betygsskala
Examination
Examinator beslutar, baserat på rekommendation från KTH:s handläggare av stöd till studenter med funktionsnedsättning, om eventuell anpassad examination för studenter med dokumenterad, varaktig funktionsnedsättning.
Examinator får medge annan examinationsform vid omexamination av enstaka studenter.
Övriga krav för slutbetyg
För att bli godkänd på kursen måste minst 70% av poängen uppnås enligt följande kategorier:
- Närvaro: godkänd om man har deltagit på minst två av sju föreläsningar
- Hemuppgifter: godkänd om man har klarat två av fem hemuppgifter
- Projekt: godkänt projekt
- Sluttenta: godkänd tentamen
Möjlighet till komplettering
Möjlighet till plussning
Examinator
Etiskt förhållningssätt
- Vid grupparbete har alla i gruppen ansvar för gruppens arbete.
- Vid examination ska varje student ärligt redovisa hjälp som erhållits och källor som använts.
- Vid muntlig examination ska varje student kunna redogöra för hela uppgiften och hela lösningen.