Antal högskolepoäng: 6. Betygsskala: TH. Nivå: G2 (Grundnivå, fördjupad). Huvudområde: Teknik. Undervisningsspråk: Kursen kan komma att ges på engelska. Valfri för: D4, D4pv, E4, E4pv, F4, F4bs, F4fm, F4pv, I4, Pi3, Pi3fm, Pi3pv. Kursansvarig: Studierektor Anders Holst, Anders.Holst@math.lth.se, Matematik. Förutsatta förkunskaper: FMA420 Linjär algebra. Prestationsbedömning: Skriftlig och/eller muntlig tentamen enligt beslut av examinator. Datorlaborationer. Några miniprojekt skall vara fullgjorda före tentamen. Hemsida: http://www.maths.lth.se/matematiklth/vitahyllan/vitahyllan.html.

Syfte
Inom teknik, naturvetenskap och ekonomi uppträder allt oftare linjära och kombinatoriska optimeringsproblem. Det mest kända exemplet är linjär programmering, där den s.k. simplexmetoden varit av ovärderlig betydelse inom industrin sedan dess upptäckt i mitten av 1900-talet. Andra viktiga problem, exempelvis för effektiv databearbetning, innehåller variabler som är diskreta, till exempel heltal. I samband med dessa har kombinatoriska metoder fått en kraftigt ökad betydelse. Kursens syfte är att studenterna skall få kännedom om inom tillämpningarna viktiga problem i linjär och kombinatorisk optimering, och kunskap om matematiska metoder för deras lösning. Syftet är vidare att få studenten att utveckla sin förmåga till problemlösning, både med och utan dator.

Mål

Kunskap och förståelse
För godkänd kurs skall studenten

kunna beskriva och översiktligt förklara den matematiska teorin bakom centrala algoritmer inom kombinatorisk optimering (inkl. lokalsökning, förgrena och begränsa, simulerad stelning, genetisk optimering, neurala nätverk).

med och utan dators hjälp och med lämpliga programpaket kunna visa god förmåga att lösa transport-, tilldelnings-, minsta snitt- och maxflödesproblem.

Färdighet och förmåga
För godkänd kurs skall studenten

kunna skriva dataprogram för att lösa linjära och kombinatoriska optimeringsproblem.

med adekvat terminologi, väl strukturerat och logiskt sammanhängande, kunna redogöra för lösningen av problem inom linjär och kombinatorisk optimering.

Innehåll
Linjär programmering. Transportproblem. Maximalt flöde. Lokal sökning. Simulerad stelning. Genetisk optimering. Neurala nätverk.

Litteratur
Kolman, B.- Beck, R.E.: Elementary Linear Programming with Applications. Acdemic Press 1995. ISBN 0-12-417910.
Kompletterande material från institutionen.
Eventuellt kommer kursboken att bytas ut.