DM515: Introduktion til Lineær og Heltalsprogrammering (5 ECTS)

STADS: 15005901

Niveau
Bachelorkursus

Undervisningsperiode
Kurset er placeret i forårssemesteret.
4. kvartal.

Ansvarlige undervisere
Email: marco@imada.sdu.dk

Skemaoplysninger
Vis hele skemaet
Vis personligt skema for dette kursus.

Kommentar:
Ubegrænset deltagerantal. 4. kvartal.

Indgangskrav:
Ingen

Faglige forudsætninger:
Stoffet fra MM505 Lineær algebra og DM507 Algoritmer og datastrukturer skal være kendt.

Kursusintroduktion
At introducere teorien for lineær programmering og dualitet, metoder til at løse lineære programmer, introducere heltals programmering, samt løsningsmetoder til heltalsprogrammer som f.eks branch and bound og Branch and cut.

Kompetencer
De studerende vil opnå indsigt i teorien for lineær og heltals programmering, samt i anvendelsen af denne på en række praktiske problemer. De skal kunne anvende den opnåede viden i relevante sammenhænge til

• at opstille en matematisk (lineær) model ud fra en problembeskrivelse i ord.
• at opskrive det duale program for et givet lineært program.
• at anvende Simplex algoritmen på simple lineære programmer.
• at anvende relaksationsbegrebet i forbindelse med f.eks. branch and bound.
• at anvende teorien fra kurset til at løse praktiske optimeringsproblemer, som for eksempel strømningsproblemer, transportproblemer, matching problemer, pakningsproblemer, simple skeduleringsproblemer etc.
• at anvende branch and bound teknikker til at løse heltals programmeringsproblemer.
• at anvende et computerværktøj til løsning af lineær og heltals programmeringsproblemer.

Forventet læringsudbytte
Ved kursets afslutning forventes de studerende at kunne:

- opstille en matematisk (lineær) model ud fra en problemskrivelse i ord.
- opskrive det duale program for et givet lineært program.
- anvende Simplex algoritmen på simple lineære programmer.
- anvende relaksationsbegrebet i forbindelse med f. eks. branch and bound.
- anvende teorien fra kurset til at løse praktiske optimeringsproblemer,som for eksempel strømningsproblemer, matching problemer, pakningsproblemer, simple skeduleringsproblemer etc.
- anvende branch and bound teknikker til at løse heltals programmeringsproblemer.
- anvende et computerværktøj til løsning af lineær og heltals programmeringsproblemer.

Emneoversigt
Simplexmetoden, dualitetsætningen, network flows, heltals programmering, løsningsmetoder til heltalsprogrammer, branch and bound, branch and cut, relaksation, lineære modeller. De studerende vil også lære at bruge en programpakke til at løse lineær- og heltals programmeringsproblemer.

Litteratur

• Meddeles ved kursets start..

Pensum
Se pensumbeskrivelse.

Kursets hjemmeside
Dette kursus benytter e-learn (blackboard).

Forudsætningsprøver
Ingen

Eksamen- og censurform:
a) Obligatoriske projektopgaver. Intern censur ved én underviser. bestået/ikke bestået. Projektopgaverne skal være bestået for at man kan deltage i eksamen.

b) 4 timers skriftlig eksamen med alle hjælpemidler (lærebog, noter og lommeregner). Ekstern censur. Karakter efter 7-trinsskalaen.

Reeksamen efter 2. kvartal. Reeksamen er en mundtlig eksamen, der bedømmes med karakter efter 7-trinsskalaen og ekstern censur.

Vejledende timetal
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.

Forelæsninger (22 timer) og eksaminatorier/laboratorier (20 timer).
Aktiviteter i studiefasen

Sprog
Dette kursus undervises på dansk eller engelsk, afhængigt af underviseren. Dog altid på Engelsk ved deltagelse af internationale studerende.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Dette er den nyeste version af en kursusbeskrivelse, som trådte i kraft den 1. feb 2009.