DM871: Lineær og heltalsprogrammering

Det Naturvidenskabelige Studienævn

Undervisningssprog: På dansk eller engelsk afhængigt af underviser, men engelsk ved internationale studerende
EKA: N340030102
Censur: Intern prøve, to eller flere bedømmere
Bedømmelse: 7-trinsskala
Udbudssteder: Odense
Udbudsterminer: Efterår
Niveau: Kandidat

STADS ID (UVA): N340030101
ECTS-point: 5

Godkendelsesdato: 07-04-2025


Varighed: 1 semester

Version: Godkendt - aktiv

Kommentar

Kurset udbydes efter behov og udbydes ikke nødvendigvis hvert år. Eksamensforsøg for DM871 udbydes efter følgende plan, når kurset udbydes:  Forår (kursusstart februar): ordinær eksamen (juni), første reeksamen (august) og 2. reeksamen i (januar eller marts).

Kurset samlæses med: DM545: Lineær og heltalsprogrammering (5 ECTS).
Kurset er valgfrit for følgende studieordninger: Datalogi, Anvendt matematik, Matematik og Data science.

Indgangskrav

Kurset kan ikke følges hvis enten DM545: Lineær og heltalsprogrammering (5 ECTS) eller DM559 (arkiveret, udbudt sidste gang F18) er bestået, eller hvis enten DM545 eller DM559 indgår obligatorisk i din studieordning.

Faglige forudsætninger

Studerende, der følger kurset, forventes at:

  • Have kendskab til Lineær 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

Kursets formål er at give deltagerne evnen til at formulere, modellere og udtænke løsningstilgang til problemer der opstår indenfor planlægning, skemalægning og ruteplanlægning. 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: 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 pensumlister og yderligere litteraturhenvisninger.

    Eksamensbestemmelser

    Eksamenselement a)

    Tidsmæssig placering

    Efterår

    Udprøvninger

    Skriftlig opgave

    EKA

    N340030102

    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

    Varighed

    En uge

    Hjælpemidler

    Alle almindelige hjælpemidler tilladt

    ECTS-point

    5

    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ællestimer introduceres og perspektiveres begreber, teorier og modeller. I holdtimer 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

    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.