Optimering 3, 7,5 hp

Innehåll

I kursen ges fördjupade kunskaper om optimering. Speciell vikt läggs vid heltalsprograms egenskaper och tekniker för att lösa dessa. De metoder för att lösa heltalsprogram som behandlas är främst trädsökning och skärande plan. Olika familjer av skärande plan studeras. De används i kursen både för att lösa, och ge starkare formuleringar av, heltalsproblem. Tekniker för att hitta bra övre och undre gränser för målfunktionen vid trädsökning behandlas, särskilt linjärprograms- och Lagrangerelaxering, dualitet till heltalsprogram samt olika heuristiker. Olika egenskaper för heltalsprogram, som total unimodalitet hos matriser, studeras. Dessutom diskuteras komplexitetsklasser och exempel på olika algoritmer för att lösa heltalsproblem ur dessa klasser ges. Sambandet mellan separation och optimering behandlas. Kolumngenerering och heuristiker för att lösa stora heltalsproblem avslutar kursen.

Förväntade studieresultat

För godkänd kurs ska studenten kunna

• förklara skillnaden mellan linjärprogram, heltalsprogram och mixade heltalsprogram
• redogöra för komplexitetsklasserna P, NP och NPC samt ge exempel på algoritmer
  ur dem
• redogöra för teorin för totalt unimodulära matriser och förklara varför de är viktiga
• tillämpa trädsökning vid lösning av optimeringsproblem
• tillämpa tekniker för att hitta övre och undre gränser för målfunktionen och redovisa
  den bakomliggande teorin
• redogöra för teorin för skärande plan samt några klasser av skärande plan
• redogöra för kolumngenerering och Dantzig-Wolfe dekomposition av heltalsprogram
• redogöra för och tillämpa några heuristiker som används för optimering
• lösa heltalsproblem och mixade heltalsproblem med de tekniker som behandlas på kursen

Behörighetskrav

Operationsanalys 2 (5MA095) alternativt Optimering 2 eller motsvarande kunskaper. Engelska A och svenska för grundläggande behörighet för högskolestudier (om kursen ges på svenska).

Undervisningens upplägg

Undervisningen bedrivs i form av föreläsningar och lektionsundervisning samt i förekommande fall datorlaborationer.

Examination

Kunskapsredovisningen sker i form av skriftliga prov samt eventuella laborationsrapporter och inlämningsuppgifter. På de skriftliga proven ges något av betygen Underkänd (U), Godkänd (3), Icke utan beröm godkänd (4) eller Med beröm godkänd (5). I de fall inlämningsuppgifter och laborationsrappporter förekommer ges endas betygen Underkänd (U) eller Godkänd (G). På hel kurs ges något av betygen Underkänd (U), Godkänd (3), Icke utan beröm godkänd (4) eller Med beröm godkänd (5). För att bli godkänd på kursen krävs att samtliga examinerande delar är godkända. Betyget utgör en sammanfattande bedömning av resultatet vid examinationens olika delar och sätts först när alla delar är godkända. Den som erhållit betyget godkänt på kursen kan ej examineras gör högre betyg. För studerande som inte blivit godkända på ordinarie provtillfälle anordnas ytterligare provtillfälle. En student som utan godkänt resultat har genomgått två prov för en kurs eller en del av en kurs, har rätt att få en annan examinator utsedd, om inte särskilda skäl talar emot det (HF 6 kap. 22 §). Begäran om ny examinator ställs till prefekten för institutionen för matematik och matematisk statistik. Examination baserad på denna kursplan garanteras under minst två år efter studentens förstagångsregistrering på kursen.

Tillgodoräknande
Tillgodoräknande prövas alltid individuellt (se universitetets regelsamling och tillgodoräknandeordning).