DM545: Lineær og heltalsprogrammering

Kommentar

Kurset samlæses med DM871.
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 AI511, DM561, MM505, MM538 eller DS827.
Kunne programmere, fx ved at have fulgt DM536, DM594, 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.

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

Se itslearning for litteraturhenvisninger.

Eksamensbestemmelser

Eksamenselement a)

Tidsmæssig placering

Efterår

Udprøvninger

Skriftlig eksamen

EKA

N330047102

Censur

Intern prøve, to eller flere bedømmere

Bedømmelse

7-trinsskala

Identifikation

Studiekort - Fulde navn og SDU brugernavn

Sprog

Følger, som udgangspunkt, undervisningssprog

Varighed

3 timer

Hjælpemidler

Alle almindelige hjælpemidler tilladt

ECTS-point

Uddybende information

Eksamensopgaven er frit format.

Vejledende antal undervisningstimer

44 timer per semester

Undervisningsform

Skemalagte undervisningstimer:
Antal undervisningstimer i alt: 44
Heraf:
Fællestimer i klasselokale: 28
Holdtimer i klasselokale: 14

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

Andre planlagte undervisningsaktiviteter:

Læse den tildelte litteratur
Løse hjemmeopgaver
Anvende den tilegnede viden i praktiske opgaver

Ansvarlig underviser

Navn	E-mail	Institut
Marco Chiarandini	marco@imada.sdu.dk	Data Science

Skemaoplysninger

Odense

Vis fuldt skema

Administrationsenhed

Institut for Matematik og Datalogi (datalogi)

Team hos Registratur

NAT

Udbudssteder

Odense

Anbefalede studieforløb

Profil	Uddannelse	Semester	Udbuds periode

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.