DM545: Lineær og heltalsprogrammering
Kommentar
Kurser afløser 15012321(tidligere UVA) studerende der tidligere har fulgt denne udgave tilbydes en sidste reeksamen juni 2019 på gammel vilkår.
Fælles undervisning med DM559, Lineær- og heltalsprogrammering
Kurset kan ikke følges af studerende, der: har bestået DM559
Kurset er valgfrit for følgende studieordninger / The course is optional in the following curricula: Computer Science, Applied Mathematics, Mathematics
Indgangskrav
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
- Kendskab til Linear Algebra
- 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
- 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
Udprøvninger
Obligatoriske opgaver i form af short-answer tests, der laves i løbet af undervisningen
EKA
Censur
Bedømmelse
Identifikation
Sprog
Hjælpemidler
ECTS-point
Uddybende information
Vejledende antal undervisningstimer
Undervisningsform
- Introfase (forelæsning, holdtimer) - 26 timer
- Træningsfase: 26 timer, heraf 22 timer eksaminatorie og 4 timer laboratorie
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
Profil | Uddannelse | Semester | Udbuds periode |
---|---|---|---|
BSc.scient.oecon | BSc.scient.oecon | Bachelor i matematik-økonomi | Odense | 4 | E20, F21 |
BSc.scient.oecon | BSc.scient.oecon | Bachelor i matematik-økonomi | Odense | 4 | F20 |