Simulering
Simulation

ETS061F, 7,5 högskolepoäng

Gäller från och med: Vårterminen 2017
Beslutad av: Professor Thomas Johansson
Datum för fastställande: 2017-05-04

Allmänna uppgifter

Avdelning: Inst för elektro- och informationsteknik
Kurstyp: Gemensam kurs, avancerad nivå och forskarnivå
Kursen ges även på avancerad nivå med kurskod: ETS061
Undervisningsspråk: Engelska

Syfte

Kursens syfte är att ge en introduktion till diskret händelsesimulering, grundläggande optimering och heuristiska metoder som simulated annealing, tabu-sökning, evolutionära algoritmer och GRASP.

Mål

Kunskap och förståelse

För godkänd kurs skall doktoranden

• Ha kunskap om olika sorters dynamiska modeller som används inom tekniken
• Kunna beskriva hur simuleringsprogram som använder händelse- eller processimulering är uppbyggda
• Kunna uppskatta noggrannheten hos simuleringsresultat
• Känna till de grundläggande begreppen inom optimeringsläran
• Veta hur man löser linjära optimeringsproblem
• Känna till hur man löser problem inom heltalsoptimering
• Visa kännedom om grundläggande begrepp inom komplexitetsteori
• Känna till de mest grundläggande heuristiska algoritmerna för optimering

Färdighet och förmåga

För godkänd kurs skall doktoranden

• Skriva välstrukturerade simuleringsprogram i ett generellt programspråk
• Uppskatta noggrannheten hos simuleringsresultat
• Kunna verifiera och validera simuleringsprogram
• Veta vad ett generellt, statiskt optimeringsproblem är, vad ett generellt konvext optimeringsproblem och dess dual är, och vad ett kombinatoriskt optimeringsproblem är
• Förstå hur dualitet kan tillämpas på linjära optimeringsproblem och på kolumngenerering i linjär optimering
• Kunna lösa linjära optimeringsproblem med simplexalgoritmen
• Kunna använda linjär approximering vid icke-linjära optimeringsproblem
• Förstå sambandet mellan heltals- och linjär programmering
• Kunna använda branch-and-bound-metoder vid heltalsprogrammering och förstå vad cutting-plane-metoden innebär
• Förstå de grundläggande begreppen i komplexitetsteori som polynomella problem och NP-hardness
• Ha grundläggande kunskaper i heuristiska metoder inom kombinatorisk optimering
• Kunna implementera simulated annealing och evolutionära algoritmer
• Vara bekant med Monte Carlo-tekniker

Värderingsförmåga och förhållningssätt

För godkänd kurs skall doktoranden

• Visa kunskaper om möjligheterna och begränsningarna med simulering
• Självständigt kunna ställa upp modeller för optimeringsproblem och kunna anända GUROBI (eller något annat optimeringsverktyg) för att lösa dem och därvid visa full förståelse för lösningsprocessen och resultaten
• Kunna välja och tillämpa en heuristisk metod för att lösa ett optimeringsproblem

Kursinnehåll

I kursen börjar vi med att studera diskret händelsesimulering. Studenterna lär sig att skriva händelse- och processimuleringsprogram i generella programspråk som Java. Uppskattning av noggrannhet, generering av slumptal, metoder för att studera sällsynta händelser, verifiering och validering studeras också. Sedan fortsätter vi med optimeringslära. Vi studerar konvexa problem och deras dualer. Vi fortsätter med linjär programmering, simplexalgoritmen och kolumngenerering. Vi visar hur icke-linjäritet kan modelleras. Därefter fortsätter vi med heltalsprogrammering, dess relation till linjär optimering och branch-and-bound-metoden för heltalsprogrammering. Vi nämner också cutting plane-metoden för heltalsprogrammering och ger en översikt av komplexitetsteorin som omfattar polynomiell komplexitet och NP-hardness. Slutligen betraktar vi heuristiska metoder för kombinatoriska optimeringsproblem varvid vi betraktar dem som en metod att optimera via simulering. Lokal sökning och hur slumpmässighet spelar in förklaras. Grundläggande meta-heuristiska metoder so simulated annealing, evolutionära algoritmer och GRASP förklaras. Vi illustrerar också Monte Carlo-metoder.

Kurslitteratur

Nyberg, C.: Kompendium i simulering..

Kursens undervisningsformer

Undervisningsformer: Föreläsningar, övningar

Kursens examination

Examinationsformer: Skriftlig tentamen, inlämningsuppgifter. För godkänt resultat krävs godkända inlämningsuppgifter samt godkänd hemtentamen
Betygsskala: Underkänd, godkänd
Examinator:

Antagningsuppgifter

Förutsatta förkunskaper: Programmering, grundläggande matematisk statistik, statistiska metoder, matematisk analys.

Övrig information

Kurskoordinator, professor Björn Landfeldt

Kurstillfällesinformation

Kontaktinformation och övrigt

Kursansvariga:
Hemsida: http://www.eit.lth.se/kurs/ets061