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.
• Forstå lineær programmerings sensivitets analyse.
• 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.
• Anvende Lagrange relaxering.

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
- Lagrange 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.

Kursusansvarlig:

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