DM85: Netværk og Heltalsprogrammering (10 ECTS)

STADS: 1506542

Niveau


Undervisningsperiode

Forår

Ansvarlige undervisere
Email: jbj@imada.sdu.dk

Skemaoplysninger
Der er ingen skemaoplysninger for den valgte periode.

Indgangskrav:
Ingen

Faglige forudsætninger:
Stoffet fra DM02, MM02 og DM19 skal være kendt.

Kursusintroduktion
At give de studerende et solidt kendskab til et meget vigtigt optimeringsværktøj, som finder anvendelse overalt hvor der optræder optimeringsproblemer af diskret natur. Vi vil fokusere på problemer fra industrielle anvendelser, blandt andet konstruktion af (tele)netværk, transport og skeduleringsproblemer samt produktionsplanlægning. Sammen med kurset DM63 om metaheuristikker udgør kurset en pakke, der vil sætte de studerende i stand til at formulere og løse en lang række optimeringsproblemer af stor interesse for erhvervslivet. Deltagerne bliver i stand til at formulere netværks og heltalsprogrammeringsproblemer, samt anvende en række af de simplere optimeringsmetoder for disse. De bliver også i stand til at anvende et kommercielt værktøj, som f.eks ILOGs CPLEX løser til at løse store optimeringsproblemer som optræder i praktiske anvendelser. Der vil blive gennemgået en del ny teori, men både i projektet og ved den mundtlige eksamen vil hovedvægten blive lagt på, at man demonstrer evne til at anvende teorien og metoderne på praktiske problemstillinger. Kurset er meget relevant for personer, der ønsker at lave et erhvervsrelateret speciale indenfor optimering og effektive algoritmer.

Forventet læringsudbytte


Emneoversigt
Lineær programmering på grafer: resume af lineære programmeringsbegreber, samt kendte emner fra grafteori (minimum udspændende træer, korteste veje etc.), maksimum strømning i netværk, minimum omkostningsstrømme, vægtet pardannelse i grafer. Produktionsplanlægning. Heltalsprogrammering: Resume af Branch and Bound teknikken, snitplaner, Branch and Cut, Lagrange relaksation, kolonne genereringsteknikker. Eksempler på anvendelser: Projektplanlægning, ruteplanlægning, produktionsplanlægning, konstruktion af (tele)netværk med specificerede egenskaber. Desuden vil der blive arbejdet med et optimeringsværktøj, som f.eks kunne være ILOGs CPLEX løser.

Litteratur

Meddeles ved kursets start.

Pensum
Se pensumbeskrivelse.

Kursets hjemmeside
Dette kursus benytter e-learn (blackboard).

Forudsætningsprøver
Ingen

Eksamen- og censurform:
Mundtlig eksamen (30 minutter med forberedelse) og bedømmelse af projektrapport(er). Den mundtlige eksamen og bedømmelse af rapport tæller hver 50% af den samlede karakter. Ekstern censur med bedømmelse efter 13 skala. Projekt(er) bedømmes uden censur af lærer, men censor får adgang til at se rapporterne ved eksamen. Af hensyn til at opnå en rimelig arbejdsbyrde kan projekter laves af op til 3 personer sammen. Der kan spørges i projektemnerne til den mundtlige eksamen. Der er kun eksamen, når faget er kørt. Eksamen i modfase terminer kun efter ansøgning til studienævnet.

Vejledende timetal
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.

Forelæsninger, øvelser og projektarbejde. Der vil være ca. 4 konfrontationstimer per uge. Herudover skal der påregnes en del tid til projektarbejdet.
Aktiviteter i studiefasen

Sprog
Dette kursus undervises på engelsk, hvis der deltager internationale studerende, ellers undervises på dansk.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Denne kursusbeskrivelse var gyldig fra 1. februar 2006 til 31. januar 2011.