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 fra uge 12.

Indgangskrav:
Ingen

Faglige forudsætninger:
Studerende, der følger kurset, forventes at:

• Have kendskab til indholdet af kurset: DM507 "Algoritmer og datastrukturer "
• 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 arbejde først med elementer af lineær algebra, som er relevante inden for datalogi og især lineær og heltalsprogrammering, derefter med de grundlæggende principper af lineær programmering og dualitetsteori og til sidst med de vigtigste løsningsteknikker, såsom simplex metoden, branch and bound og cutting plane metoder. Udover at give den studerende færdigheder i matematisk modellering, har kurset også til formål at give til den studerende erfaring med praktiske anvendelser og med et matematisk software system for at finde numeriske løsninger på de praktiske anvendelser. 

Kurset bygger oven på den viden, der er erhvervet i kurserne DM507 "Algoritmer og datastrukturer" og giver et fagligt grundlag for at lave et bachelor thesis projekt og andre både teoretiske og pratiske studie-aktiviteter så vel som at studere emnerne for andre valgfri kurser, der kan vælges i 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 datalogiske problemstillinger ved anvendelsen af metoder og modelleringsformalismer fra fagets kerneområder og dets matematiske støttediscipliner
• 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 datalogiske fagområde

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

• foretage beregninger inden for 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.

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. Bestået/ikke-bestået, intern censur ved underviser. Forudsætningsprøven er en forudsætning for deltagelse i eksamenselement a). (15018012).

Eksamen- og censurform:

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

Vejledende timetal
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.
Introfase: 46 timer
Træningsfase: 50 timer, heraf:
 - Eksaminatorie: 42 timer
 - Laboratorieøvelser: 8 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: DM545 i den anden del af semester.

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