Linjär och kombinatorisk optimering
Linear and Combinatorial Optimization

FMAP05F, 7,5 högskolepoäng

Gäller från och med: Höstterminen 2022
Beslutad av: Maria Sandsten
Datum för fastställande: 2022-11-23

Allmänna uppgifter

Avdelning: Matematik (LTH)
Kurstyp: Gemensam kurs, avancerad nivå och forskarnivå
Kursen ges även på avancerad nivå med kurskod: FMAP05
Undervisningsspråk: Engelska

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 doktoranderna skall få kännedom om problem i linjär och kombinatorisk optimering som är viktiga inom tillämpningar, och kunskap om moderna matematiska metoder för deras lösning. Syftet är vidare att få doktoranden att utveckla sin förmåga till problemlösning, både med och utan dator, och sin förmåga att läsa matematisk text.

Mål

Kunskap och förståelse

För godkänd kurs skall doktoranden

• förstå och tydligt kunna förklara teorin bakom simplexmetoden.
• kunna beskriva och förklara den matematiska teorin bakom några moderna algoritmer inom kombinatorisk optimering.

Färdighet och förmåga

För godkänd kurs skall doktoranden

• kunna visa god förmåga att (i) identifiera problem inom området, (ii) göra en matematisk formulering av problemet, (iii) välja lämplig metod för att lösa det, samt (iv) genomföra lösningen, eventuellt med användning av dator.
• 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.

Kursinnehåll

Linjär programmering. Heltalsprogrammering. Transportproblem. Tilldelningsproblem. Maximalt flöde. Några moderna metoder inom kombinatorisk optimering. Algoritmkomplexitet.

Kurslitteratur

Kolman, B. & Beck, R.E.: Elementary Linear Programming with Applications. Academic Press, 1995, ISBN: 0-12-417910. Tillgänglig som e-bok från Matematiska biblioteket. Kompletterande material. B.Korte & J. Vygen: Combinatorial Optimization, Theory and Algorithms. Springer, 2019, ISBN: 9783662585665. Sjätte upplagan. Tidigare upplaga finns tllgänglig som e-bok via matematiska biblioteket.

Kursens undervisningsformer

Undervisningsformer: Föreläsningar, seminarier

Kursens examination

Examinationsform: Inlämningsuppgifter. Inlämningsuppgifter. Godkänt på dessa räcker för godkänt.
Betygsskala: Underkänd, godkänd
Examinator:

Antagningsuppgifter

Förutsatta förkunskaper: FMAB20 Linjär algebra. Programmering i Python eller Matlab. Någon matematikkurs utöver Flerdimensionell analys (för matematisk mognad).

Kurstillfällesinformation

Kontaktinformation och övrigt

Kursansvariga:
Hemsida: http://www.maths.lth.se/course/lincombopt75/