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

STADS: 15001501

Niveau
Bachelorkursus

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

Ansvarlige undervisere
Email: jbj@imada.sdu.dk

Skemaoplysninger
Vis hele skemaet
Vis personligt skema for dette kursus.

Kommentar:
Ubegrænset deltagerantal

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.

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

Emneoversigt
Simplexmetoden, dualitetsætningen, primal-dual algoritmen, network flows, heltals programmering, løsningsmetoder til heltalsprogrammer, branch and bound, 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:
4 timers skriftlig eksamen med alle hjælpemidler (lærebog, noter og lommeregner). Ekstern censur. Karakter efter 7-skalaen.
Reeksamen efter 2. kvartal. Reeksamen er en mundtlig eksamen, der bedømmes med karakter efter 7-skalaen 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.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Denne kursusbeskrivelse var gyldig fra 1. februar 2008 til 31. januar 2009.