Overordnede kursusmål:

Målet med kurset er at give en grundig indføring i dekompositions algoritmer. Dette skal gøre det muligt for de studerende at anvende dekompositions algoritmer til at løse komplekse optimerings problemer.

Læringsmål:

En studerende, der fuldt ud har opfyldt kursets mål, vil kunne:

• Analysere matematiske optimerings modeller.
• Forstå og anvende lineær programmerings dualitet i metode udvikling.
• Anvendelse af modeleringssoftware til implementere iterative algoritmer
• Forstå og anvende nedregrænse metoder.
• Dekomponere matematisk modeller så disse kan løses iterativt.
• Anvende Benders dekompositions algoritme.
• Anvende Søjle genererings algoritmen/Dantzig-Wolfe dekomposition.
• Forstå korrektheden af Benders dekompositions algoritme og Dantzig-Wolfe dekomposition algoritme

Kursusindhold:

Mange vigtige optimerings problemer kan modelleres vha.blandet heltals programmerings modeller. Når disse ikke kan løses med standard løsere, kan dekompositions metoder anvendes til at løse problemerne iterativt. Metoderne er:
- Benders dekompositions algoritme
- Søjle generering/Dantzig-Wolfe dekomposition

Kurset giver den studerende en grundig indføring i de tre typer af dekomponerings algoritmer og illustrere anvendelsen af dem til diverse problemer.

Litteraturhenvisninger:

Kursusnoter

Bemærkninger:

Kurset er kvantitativt orienteret og en god forståelse af lineær programmering er nødvendig. I øvelserne vil der blive benyttet computer sproget GAMS (som der undervises i i kurset 42112) til at implementere dekompositions algoritmerne. Studerende uden GAMS kendskab skal forberede sig på en betydelig ekstra arbejdsindsats.

Kursusansvarlig:

Thomas Jacob Riis Stidsen , Lyngby Campus, Bygning 426, Tlf. (+45) 4525 4449 , thst@dtu.dk