DM545: Lineær og heltalsprogrammering
Det Naturvidenskabelige Studienævn
Undervisningssprog: På dansk eller engelsk afhængigt af underviser, men engelsk ved internationale studerende
EKA: N330047102
Censur: Intern prøve, to eller flere bedømmere
Bedømmelse: 7-trinsskala
Udbudssteder: Odense
Udbudsterminer: Efterår
Niveau: Bachelor
STADS ID (UVA): N330047101
ECTS-point: 5
Godkendelsesdato: 10-04-2024
Varighed: 1 semester
Version: Godkendt - aktiv
Kommentar
Kurset samlæses med DM871: Lineær og heltalsprogrammering (5 ECTS).
Kurset er valgfrit for følgende Bacheloruddannelser: Anvendt Mathematics, Datalogi og Matematik.
Data science studerende henvises til kurset DM871.
Indgangskrav
Kurset kan ikke følges hvis DM559 (arkiveret, udbudt sidste gang F18) eller DM871 er bestået, eller hvis DM559 eller DM871 indgår obligatorisk i din studieordning
Faglige forudsætninger
Studerende, der følger kurset, forventes at:
- Kendskab til Linear Algebra, fx ved at have fulgt DM561, MM505, MM538 eller DS827
- Kunne programmere, fx ved at have fulgt DM536, DM550, DM574, DS800 eller DS831
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
Kurset indeholder følgende faglige hovedområder:
- Linær programmering og Simplexmetoden
- Dualitetsætningen
- Heltals programmering og branch and bound og cutting plane algoritmer
- Min cost flow problem og dets anveldenser
- Programpakker til at løse lineær- og heltals programmeringsproblemer.
Litteratur
Eksamensbestemmelser
Eksamenselement a)
Tidsmæssig placering
Efterår
Udprøvninger
Obligatoriske opgaver
EKA
N330047102
Censur
Intern prøve, to eller flere bedømmere
Bedømmelse
7-trinsskala
Identifikation
Fulde navn og SDU brugernavn
Sprog
Følger, som udgangspunkt, undervisningssprog
Hjælpemidler
Tilladt, nærmere beskrivelse af eksamensreglerne vil blive offentliggjort i itslearning.
ECTS-point
5
Uddybende information
Eksamen består af obligatoriske opgaver i form af short-answer tests, der laves i løbet af undervisningen
Der skal deltages i alle test som forgår løbende i undervisningen. Tests i løbet af undervisningen kan eksempelvis være i form af 24 timers hjemmeopgaver eller eksamenstimer i undervisningslokalet. Tidspunkterne bliver aftalt med kursusdeltagerne.
Reeksamen foregår med en enkelt, kortfristet hjemmeopgave i form af short-answer test tilsvarende til de oblikatoriske opgaver for den ordinære eksamen.
Der skal deltages i alle test som forgår løbende i undervisningen. Tests i løbet af undervisningen kan eksempelvis være i form af 24 timers hjemmeopgaver eller eksamenstimer i undervisningslokalet. Tidspunkterne bliver aftalt med kursusdeltagerne.
Reeksamen foregår med en enkelt, kortfristet hjemmeopgave i form af short-answer test tilsvarende til de oblikatoriske opgaver for den ordinære eksamen.
Vejledende antal undervisningstimer
Undervisningsform
Undervisningsaktiviteter udmønter sig i en anslået vejledende fordeling af arbejdsindsatsen hos en gennemsnitsstuderende på følgende måde:
- Introfase (forelæsning) - 32 timer
- Træningsfase: 18 timer
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.
Aktiviteter i studiefasen:
- Læse den tildelte litteratur
- Løse hjemmeopgaver
- Anvende den tilegnede viden i praktiske opgaver
Ansvarlig underviser
Skemaoplysninger
Administrationsenhed
Team hos Uddannelsesjura & Registratur
Udbudssteder
Anbefalede studieforløb
Overgangsordninger
Overgangsordninger beskriver, hvordan et kursus erstatter et andet kursus, når der ændres i et studieforløb.
Hvis der er lavet en overgangsordning for et kursus vil den fremgå af oversigten.
Se overgangsordninger for alle kurser på Det Naturvidenskabelige Fakultet.
Se overgangsordninger for alle kurser på Det Naturvidenskabelige Fakultet.