DM559: Lineær og heltalsprogrammering (7.5 ECTS)

STADS: 15018001

Niveau
Bachelorkursus

Undervisningsperiode
Kurset er placeret i forårssemesteret.

Ansvarlige undervisere
Email: marco@imada.sdu.dk

Skemaoplysninger
Vis hele skemaet
Vis personligt skema for dette kursus.

Kommentar:
Ubegrænset deltagerantal. Fælles undervisning med DM545 Lineær- og heltalsprogrammering.

Indgangskrav:
Ingen

Faglige forudsætninger:
Stoffet fra DM507 Algoritmer og datastrukturer forudsættes kendt.

Kursusintroduktion
Lineær og heltalsprogrammering er et felt i skæringspunktet mellem matematik og datalogi, der har set en stor udvikling i de sidste 60 år. Det giver de værktøjer, der er kernen i operationsanalyse, den disciplin, der giver analysemetoder til at hjælpe at træffe bedre beslutninger. Det primære fokus for lineær og heltalsprogrammering er på ressource begrænset optimeringsproblemer, der kan beskrives ved hjælp af lineære uligheder og en lineær objektivfunktion. Disse problemer kan opstå i beslutningsprocessen i flere sammenhænge, såsom produktionsindustri, logistik, sundhedssektor, uddannelse, finans, energiforsyning og med flere. Indholdet af kurset har derfor en høj praktisk relevans. I kurset vil vi først introducere de elementer af lineær algebra, som er relevante for datalogi og især for lineær og heltalsprogrammering. Derefter vil vi fokusere på de grundlæggende principper af lineær programmering og dualitet teori. Endelig vil det præsenteres de vigtigste løsningsteknikker, såsom simplex metoden, branch and bound og cutting plane metoder. Udover at præsentere teorien og give de studerende færdigheder i matematisk modellering, har kurset først og fremmest et praktisk formål. Det beskæftiger sig med algoritmer og anvendelser, og det omfatter erfaring med et matematisk software system til at finde numeriske løsninger på de problemer, der studeres.

Kompetencer

• Evne til at modellere matematisk ressourcebegrænsede optimeringsproblemer samt løse disse ved hjælp af et matematisk software system.

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

• foretage beregninger indenfor matrix algebra.
• løse systemer af lineære ligninger både manuelt og med computeren.
• anvende lineær algebra til at løse praktiske problemer, der ligner dem behandlet i løbet af kurset.
• 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 branch and bound til at løse små problemeksempler.
• udlede Gomory cuts og anvende cutting plane algoritme i små problemeksempler.
• anvende teorien fra kurset til at løse praktiske optimeringsproblemer, som for eksempel strømningsproblemer, matching problemer, pakningsproblemer, simple skeduleringsproblemer etc.
• anvende et computerværktøj til løsning af lineær og heltals programmeringsproblemer.
• tænke nyt med at se muligheder for anvendelsesorienteret brug af teoretisk viden i industriverden.

Emneoversigt
Matrix algebra, systemer af lineære ligninger, rang af matricer, Gauss elimination, matrixinvertering, vektorrum, lineære transformationer, indre produkter, simplexmetoden, dualitetsætningen, network flows, heltals programmering, løsningsmetoder til heltalsprogrammer, branch and bound, branch and cut, relaksation, lineære modeller. Programpakker til at løse lineær- og heltals programmeringsproblemer.

Litteratur

Meddeles ved kursets start.

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

Forudsætningsprøver
Obligatoriske projektopgaver. Bedømmes ved intern censur af underviseren efter bestået/ikke bestået. Opgaverne skal være bestået for at deltage til den skriftlige eksamen. (15018012)

Eksamen- og censurform:

1. 4 timers skriftlig eksamen med alle hjælpemidler. Bedømmes ved ekstern censur efter 7-trinsskalaen. (15018002)

Reeksamen i samme eksamenstermin eller i umiddelbar forlængelse heraf. 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.
Introfase: 44 timer
Træningsfase: 50 timer, heraf:
 - Eksaminatorie: 42 timer
 - Laboratorieøvelser: 8 timer

Aktiviteter i studiefasen Studiefase: 30 timer

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

Bemærkninger
Samlæses i andet kvartal med DM545.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Denne kursusbeskrivelse var gyldig fra 1. februar 2016 til 31. januar 2017.