lu.se

Forskar­utbildnings­kurser

Lunds tekniska högskola | Lunds universitet

Detaljer för kursplan för kurs ETS061F giltig från och med VT 2017

Utskriftsvänlig visning

Allmänt
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.
Innehå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.
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
Undervisningsformer
  • Föreläsningar
  • övningar
Examinationsformer
  • Skriftlig tentamen
  • Inlämningsuppgifter
  • För godkänt resultat krävs godkända inlämningsuppgifter samt godkänd hemtentamen
  • Underkänd, godkänd
Förkunskapskrav
Förutsatta förkunskaper
  • Programmering, grundläggande matematisk statistik, statistiska metoder, matematisk analys.
Urvalskriterier
Litteratur
  • Nyberg, C.: Kompendium i simulering..
Övrig information
  • Kurskoordinator, professor Björn Landfeldt
Kurskod
  • ETS061F
Administrativ information
  •  -05-04
  • Professor Thomas Johansson

Alla publicerade kurstillfällen för kursplanen

Inga matchande kurstillfällen hittades.

0 kurstillfällen.


Utskriftsvänlig visning