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