Enkeltfag Engelsk 5 ECTS

Heltalsprogrammering

Overordnede kursusmål

Matematisk optimering er en essentiel og kompleks del af data science. Som en del af optimering giver heltalsprogrammering mulighed for at få det fulde udbytte ud af ens data. I planlægning af f.eks. transport-, energi eller produktionssystemer kan heltalsprogrammering give afgørende fordele. Dette kursus giver deltagerne en grundig indtroduktion til problemformulering og løsningsmetodik for heltalsprogrammeringsproblemer som disse opstår i en lang række komplekse situationer. Deltagerne bliver i stand til såvel af formulere heltalsprogrammeringer som at anvende det til at etablere optimale løsninger for såvel simple som komplekse planlægnings- og beslutningsproblemer.

See course description in English

Læringsmål

  • define et “mixed integer” program, et heltalsprogram og et binært program i forhold til et lineært program.
  • gennemføre simpel identifikation af løsningsmetoder for et heltalsprogrammerings (IP) problem.
  • opstille en heltalsprogrammering model med målfunktion, begrænsninger og variabeldefinition ud fra en simpel tekst.
  • definere en relaksering og beskrive eksempler på relaksering fra pensum
  • beskrive konstruktionen af en branch-and-bound (B&B) algoritme for et standard IP problem.
  • gengive betydningen af og indholdet af de centrale beviser indenfor heltalsprogrammering som angivet i kurset.
  • definere og beskrive brugen af gyldige uligheder og snit generelt og specifikt i forbindelse med et givet simpelt IP problem.
  • beskrive problemstillingerne ved udvidelsen fra uligheder og snit til en branch-and-cut (B&C) algoritme.
  • overordnet beskrive brugen af B&B, B&C, øvre og nedre grænse ifm. en implementering af effektive løsningsmetoder for simple IP problemer (herunder specielt TSP).
  • opstille en dynamisk programmerings algoritme bestående af “princple of optimality”, “stage” og “state” for et simpelt problem.
  • definere Lagrange relaxering for et heltalsprogram og beskrive brugen af Lagrange relaxering på et simpelt IP problem.

Kursusindhold

Relaxation, duality, Branch & Bound, snitplaner, Branch & Cut, Lagrange relaksering, dynamisk programmering. Eksempler på anvendelser: Projektplanlægning, rutelægning og produktionsplanlægning.

Anbefalede forudsætninger

42101, Et indledende kursus i operationsanalyse er en nødvendig faglig forudsætning.

Undervisningsform

Forelæsninger, øvelser og projektarbejde

Se kurset i kursusbasen

Tilmelding

Sprog

Engelsk

Varighed

13 uger

Institut

Management

Sted

DTU Lyngby Campus

Kursus ID 42114
Kursustype Kandidat
Semesterstart Uge 35
Semester slut Uge 48
Dage tirs 13-17
Pris

7.500,00 kr.

0 pladser tilbage

Tilmelding