Kursplan för

Simulering
Simulation

ETS061, 7,5 högskolepoäng, A (Avancerad nivå)

Gäller för: Läsåret 2016/17
Beslutad av: Utbildningsnämnd A
Beslutsdatum: 2016-04-05

Allmänna uppgifter

Valfri för: C4-ks, D4-ks, E4-ks, I4, I4-pvs, Pi4
Undervisningsspråk: Kursen ges på begäran på 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 studenten

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

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

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

Kursens examination

Betygsskala: TH
Prestationsbedömning: Godkända hemuppgifter ger betyget tre. För betyg fyra eller fem krävs dessutom godkänd hemtentamen.

Antagningsuppgifter

Förutsatta förkunskaper: Programmering, grundläggande matematisk statistik, statistiska metoder, matematisk analys.
Begränsat antal platser: Nej
Kursen överlappar följande kurser: ETS060, ETS120

Kurslitteratur

• Nyberg, C, Kompendium i simulering.
• Michal Pioro: Network Optimization Techniques, Chapter 18 in E. Serpedin, E., Chen, T., and Rajan, D. (eds.): Signal Processing, Communications, and Networking,. CRC Press, 2012, ISBN: 978-1-4398-5513-3.

Kontaktinfo och övrigt

Kursansvarig: Christian Nyberg, Christian.Nyberg@eit.lth.se
Hemsida: http://www.eit.lth.se/kurs/ets061