DM545: Lineær og heltalsprogrammering (5 ECTS)

STADS: 15012321

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 DM559, Lineær- og heltalsprogrammering

Indgangskrav:
Ingen

Faglige forudsætninger:

• Have kendskab til indholdet af kurset: DM507 "Algoritmer og datastrukturer " eller have opnået kendskab til indholdet af DM507 "Algoritmer og datastrukturer” samtidig med at dette kursus undervises
• Kunne programmere

Formål
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. 

Kurset har til formål at sætte den studerende i stand til at anvende matematisk modellering til at løse praktiske optimeringsproblemer og at arbejde med en matematisk softwaresystem til at finde numeriske løsninger på disse problemer. For at nå disse mål vil kurset give til den studerende viden om de grundlæggende principper for lineær programmering og dualitet teori og om de vigtigste løsning teknikker til lineær og heltalsprogrammering, såsom simplex metoden, branch and bound og cutting planes.

Kurset bygger oven på den viden, der er erhvervet i kurset DM507 "Algoritmer og datastrukturer", og giver et fagligt grundlag for at lave et bachelor/master thesis projekt og andre både teoretiske og praktiske studie-aktiviteter så vel som at studere emnerne for andre valgfri kurser, der kan vælges i MatØk, Anvendt Matematik eller andre uddannelsen.

I forhold til uddannelsens kompetenceprofil har kurset eksplicit fokus på at:

• Give kompetence til at håndtere komplekse og udviklingsorienterede situationer i studie- og arbejdssammenhænge
• Give færdigheder i at beskrive, analysere og løse matematiske problemstillinger ved anvendelsen af metoder og modelleringsformalismer fra områder af matematik og datalogi 
• Give færdigheder i at træffe og begrunde fagligt relaterede beslutninger
• Give færdigheder i at beskrive, formulere og formidle problemstillinger og resultater til enten fagfæller og ikke-specialister eller samarbejdspartnere og brugere
• Give viden om hvordan visse optimeringsproblemer kan løses ved hjælp af lineær- og heltaltsprogrammering
• Give viden om at kunne forstå og reflektere over teorier, metoder og praksis inden for det matematiske fagområde

Målbeskrivelse
For at opnå kursets formål er det læringsmålet for kurset, at den studerende demonstrerer evnen til at:

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

Indhold


Litteratur

Meddeles ved kursets start.

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

Forudsætningsprøver

1. Et antal af hjemmeopgaver i løbet af kurset er en forudsætning for deltagelse i eksamenselement a). Bestået/ikke-bestået, intern censur ved underviser. (15012322).

Eksamen- og censurform:

1. 4 timers skriftlig eksamen. (5 ECTS). Bedømmes med karakter efter 7-trinsskalaen og ekstern censur. Alle hjælpemidler og Alle IT-tools tilladte, dog med begrænset internet adgang. (15012302).

Vejledende timetal
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.
Introfase: 26 timer
Træningsfase: 26 timer, heraf:
 - Eksaminatorie: 22 timer
 - Laboratorieøvelser: 4 timer

Aktiviteter i studiefasen

• Læse den tildelte litteratur
• Løse hjemmeopgaver
• Anvende det tilegnede viden i praktiske projekter

Undervisningsform
I introfasen introduceres og perspektiveres begreber, teorier og modeller. I træningsfasen træner de studerende færdigheder og trænger dybere ned i det stof

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

Bemærkninger
Kurset samlæses med: DM559.

 

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Denne kursusbeskrivelse var gyldig fra 1. februar 2018 til 31. januar 2019.