NMAB02 OPTIMERINGSLÄRA 1, 10 poäng
/Optimization/
För: matematik 2 och fristående kurs.

Utbildningsområde: Naturvetenskap    Ämnesgrupp: Matematik
Fördjupningsnivå: B
Mål:
Kursen är en grundkurs i optimeringslära och består av två delar vilka behandlar problem med kontinuerliga respektive diskreta variabler. Såväl teori som metodik för lösning av optimeringsproblem behandlas. Kursen avser att ge de studerande - en exemplifierad orientering av viktiga klasser av optimeringsproblem - färdighet i analys och formulering av verkliga problem från teknisk och ekonomisk verksamhet med hjälp av matematiska modeller - kunskap om uppbyggnad av effektiva metoder för att med hjälp av dator lösa uppkomna matematiska modeller - färdighet i lösning av optimeringsproblem, såväl manuellt som med dator

Förkunskaper:
Genomgångna kurser i årskurs 1 av matematikprogrammet med minst 25 p godkända, varav samtliga laborativa moment godkända.

Organisation:
Undervisningen består av föreläsningar, lektioner, seminarier och laboratio ner. Deltagande i seminarier och laborationer är obligatoriskt.

Kursinnehåll:
Del 1 (5p) är inriktad mot optimeringsproblem i kontinuerliga variabler och innehåller delmomenten Konvexitetsteori: Representationssatsen, extrempunkt, baslösning, linjär programmeringens fundamentalsats, Farkas lemma, separationssatsen, konvexa mängder och funktioner, lokala och globala optima, Sadelpunktsatsen, Karush -Kuhn-Tucker villkoren, Lagrangedualitet. Linjärprogrammering: Linjära optimeringsmodeller, grafisk lösning, simplexmetoden, känslighetsanalys, dualitet. Ickelinjär programmering: Ickelinjära optimeringsmodeller utan respektive med bivillkor, endimensionell sökning, brantaste lutningsmetoden, Newtons modifierade metod, Frank Wolfe algoritmen, kvadratisk programmering. Del 2 (5p) behandlar i huvudsak optimeringsproblem med diskreta variabler och innehåller delmomenten Heltalsoptimering: Problemformulering, lösningsmetoder baserade på plan snittning, trädsökning och implicit uppräkning, algoritmer för speciella heltals problem såsom kappsäcksproblem, övertäcknings- och uppdelningsproblem. Nätverksoptimering: Problemtyper med graf- och nätverksstruktur, linjär programmering med heltalsegenskap, transportproblemet, billigaste väg problem, flöden i nätverk. Dynamisk programmering: Problemområden, problemformulering, optimalitetsprincipen. Gemensamt för kursens båda delar är att ett flertal praktiska övningar/dator laborationer ingår, ett par av större format.

Kurslitteratur:
Jönsson, H.: Linjärprogrammering, LiTH 1988. Jönsson, H., Migdalas, S.: Ickelinjär programmering , LiTH 1989. Holmberg, K.: Flöden i nätverk och kombinatorisk optimering, LiTH 1989. Holmberg, K.: Heltalsprogrammering och dynamisk programmering, LiTH 1989. Kompletterande material.

TEN1Skriftliga tentamina omfattande problemformulering, problemlösning och teorifrågor. 5 p
TEN 2Skriftliga tentamina omfattande problemformulering, problemlösning och teorifrågor. 5 p
LAB1Laboration omfattande lösning av optimeringsproblem med hjälp av dator.
LAB2Laboration omfattande lösning av optimeringsproblem med hjälp av dator.

Engelsk kursplan
Gäller 1997/98, beslut av utbildningsnämnden maj-97