GU-logo
GÖTEBORGS UNIVERSITET
Matematik och Datavetenskap
KURSPLAN

MAM340 Projektkurs i optimering, 5 poäng

(Project course in optimization)


1. Beslut om inrättande av kursen

Kursplanen är fastställd av styrelsen för matematik och datavetenskap 1999-12-28.

2. Kursens mål

Kursens syfte är att ge studenterna en inblick i några av de viktigaste principerna för effektiv problemlösning av praktiska, storskaliga optimeringsproblem, från modellering till metodkonstruktion. Kursens huvudsakliga verksamhet ägnas åt projektarbeten, vari studenterna utnyttjar dessa principer för att effektivt lösa något relevant optimeringsproblem.

3. Kursens innehåll och organisation

Under föreläsningar tas viktiga begrepp upp inom modellering och lösning av optimeringsproblem, med syfte att ge en insikt i hur den inneboende svårigheten och problemstrukturen hos ett givet optimeringsproblem kan identifieras; med denna kunskap kan studenten formulera en lämplig modell och identifiera en eller ett antal alternativa lösningsprinciper. I kursens andra del tillämpas dessa principer i ett projektarbete, där studenten från en given problembeskrivning skall identifiera lämpliga modelleringar av problemet, problemstrukturer och sunda lösningsansatser, för att avsluta med att numeriskt lösa något praktiskt problem med lämplig programvara.
Kortfattat innehåll:
I Optimeringsproblem: Repetition av linjäprogrammering, unimodularitet och konvexitet, minimalt uppspännande träd, kappsäcksproblem, lokaliseringsproblem, generaliserad tillordning, handelsresandeproblem, nätverkskonstruktion, ruttplanering.
II Algoritmprinciper: Dekomposition/koordination, restriktion, projektion, fixering av variabler, omgivningar, relaxeringar (Lagrange, SDP), linjärisering, linjesökning, koordinerande masterproblem.
III Algoritmer: Plansnittning, Lagrangeheuristiker, kolumngenerering, Dantzig-Wolfe dekomposition, Benders dekomposition, derivatafria metoder, lokal sökning, metaheuristiker, moderna trädsökningsmetoder.

4. Examination

Skriftligt och muntligt redovisad projektuppgift, opposition; muntlig tentamen för överbetyg. Studerande som ej godkänts vid ordinarie prov erbjuds ytterligare provtillfällen. På godkänt prov ges betygsgraderna Godkänd eller Väl godkänd.

5. Förkunskaper

Tillämpad optimeringslära.

6. Övriga anvisningar

Kursen ges i samarbete med Chalmers

7. Kurslitteratur och andra läromedel

Se Matematiska institutionens litteraturlista

Last modified: Wed Dec 29 13:30:24 MET 1999