Linjär och kombinatorisk optimering
Linear and Combinatorial Optimization

FMAP05, 7.5 högskolepoäng, A (Avancerad nivå)

Gäller för: 2024/25
Fakultet: Lunds tekniska högskola
Beslutad av: Programledning F/Pi
Beslutsdatum: 2024-04-15
Ikraftträdande: 2024-05-08

Allmänna uppgifter

Fördjupning: Avancerad nivå, kurs/er som inte kan klassificeras
Valfri för: BME4, C4, D4-pv, E4, F4, F4-pv, F4-bs, Pi4-bs, Pi4-pv
Undervisningsspråk: Kursen ges på begäran på 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 studenterna 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å studenten 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 studenten

• 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 studenten

• 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.

Kursens examination

Betygsskala: TH - (U, 3, 4, 5) - (Underkänd, Tre, Fyra, Fem)
Prestationsbedömning:

Skriftlig tentamen eller hemtentamen plus muntlig tentamen, enligt beslut av examinator.

Om så krävs för att en student med varaktig funktionsnedsättning ska ges ett likvärdigt examinationsalternativ jämfört med en student utan funktionsnedsättning, så kan examinator efter samråd med universitetets avdelning för pedagogiskt stöd fatta beslut om alternativ examinationsform för berörd student.

Moduler
Kod: 0122. Benämning: Linjär och kombinatorisk optimering.
Antal högskolepoäng: 7.5. Betygsskala: TH - (U, 3, 4, 5).

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).
Begränsat antal platser: Nej
Kursen överlappar följande kurser: FMA240 FMAF35

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.

Kontaktinfo

Kursansvarig: Studierektor Anders Holst, Studierektor@math.lth.se
Lärare: Stefan Diehl, Stefan.Diehl@math.lth.se
Hemsida: https://canvas.education.lu.se/courses/20371