LINJÄR OCH KOMBINATORISK OPTIMERING 2006-2007


Kursledare: Fredrik Kahl

Förkunskaper: Matematik GK. Kunskaper om Matlab är en fördel.

Tid: Lp 3 2007. Se schema F3, I3, E4, D4.

Omfattning: Föreläsningar 28 timmar. Laborationer. Inlämningsuppgifter.

Poäng: 4 poäng i civilingenjörsexamen.

Anmälan: Via KA-systemet.

Hemsida: http://www.maths.lth.se/matematiklth/personal/fredrik/kombopt


Vill du lära dig hur man skriver datorprogram som automatiskt löser Korsordskrypton? Vill du lära dig hur man optimerar sin poker-strategi, sina resurser eller hur man väljer vilken ordning man ska ta orienteringskontrollerna för att anstränga sig så lite som möjligt? Då skall du passa att läsa kursen Linjär- och kombinatorisk optimering nästa vår.

Många praktiska optimeringsproblem i industri och tillämpningar går ut på att maximera eller minimera en linjär funktion i flera variabler under linjära bivillkor, linjär programmering. Det kan då röra sig om flera tusen variabler, och även tusentals bivillkor. Här har man ingen nytta av differentialkalkylen. Sedan början av 1950-talet, då den utvecklades av Dantzig, har den så kallade simplexmetoden i olika varianter använts för att lösa sådana problem. På senare tid har metoden fått konkurrens av andra algoritmer (Karmarkars algoritm).

Vissa optimeringsproblem för nätverk (s.k. transportproblem och maximala flödesproblem) kan formuleras som linjär programmering. För dessa finns dock andra lösningsalgoritmer, direkt anpassade till problemställningen.

Optimering i nätverk är exempel på kombinatorisk optimering. Andra exempel är vilken ordning man ska ta orienteringskontrollerna för att anstränga sig så lite som möjligt. Detta kallas även handelsresandeproblemet. Kombinatorisk optimering har många roliga tillämpningar, t ex inom korsordslösning och spelteori. I kursen kommer vi att behandla några metoder (lokalsökning, heltelsoptimering, simulerad stelning, genetisk optimering och dynamisk optimering) för att lösa kombinatoriska optimeringsproblem.


Lars Vretare