Markovprocesser med diskreta tillståndsrum. Absorption, stationaritet och ergodicitet.
Födelse- dödsprocesser i allmänhet och Poissonprocessen i synnerhet.
Enkla modeller för betjäningssystem, M/M/1 och M/M/c, och köteori.
Exempel på optimeringstillämpningar och formuleringsträning.
Grundläggande begrepp och teori för optimering, speciellt teori för konvexa problem.
Linjär algebra i R^n, speciellt baser till nollrum och bildrum samt LDLT-faktorisering.
Linjär optimering, inklusive dualitetsteori.
Optimering av flöden i nätverk.
Kvadratisk optimering med linjära bivillkor.
Linjära minsta-kvadratproblem, speciellt minsta-normlösningar.
Ickelinjär optimering utan bivillkor, t ex ickelinjära minsta-kvadratproblem.
Optimalitetsvillkor för ickelinjär optimering med bivillkor, speciellt för konvexa problem.
Lagrangerelaxering.
Kursens övergripande mål är att studenten ska bli väl förtrogen med grundläggande teori för och tillämpningar av markovprocesser, samt grundläggande begrepp, teori, modeller och lösningsmetoder för optimering. Vidare att studenten förvärvar basala färdigheter i att modellera och med hjälp av dator lösa tillämpade optimeringsproblem av skiftande slag.
Mätbara mål
För att bli godkänt i kursen ska studenten kunna följande:
- Ställa upp enkla markovkedjemodeller i diskret och kontinuerlig tid och redogöra för deras asymptotiska uppträdande och egenskaper, speciellt Poissonprocessens.
- Använda absorptionsteknik i kontinuerlig och diskret tid för Markovkedjor.
- Modellera enkla kösystem med födelse- dödsprocesser och göra beräkningar i dessa modeller av köteoretiskt intressanta storheter såsom förväntad kölängd och kötid etc.
- Redogöra för grundläggande begrepp och teori inom optimeringsläran, speciellt modelleringskonceptet variabler-målfunktion-bivillkor och egenskaper hos konvexa optimeringsproblem, samt avgöra huruvida ett givet problem är konvext eller ej.
- Med hjälp av papper och penna analysera och lösa givna (relativt små) problem av följande slag: linjär optimering med både likhets- och olikhetsbivillkor, duala problemet till ett linjärt optimeringsproblem, kvadratisk optimering utan bivillkor, kvadratisk optimering med linjära likhetsbivillkor, linjära minsta-kvadratproblem, minsta-normlösningen till linjära minsta-kvadratproblem, optimering av nätverksflöden med linjära eller kvadratiska kostnader, ickelinjär optimering utan bivillkor (med Newtons metod), ickelinjära minsta-kvadratproblem (med Gauss-Newtons metod).
- Ställa upp relevanta optimalitetsvillkor och använda dessa för att avgöra huruvida en given tillåten lösning till ett givet konvext problem med bivillkor (t ex något av problemen under föregående punkt) är en globalt optimal lösning eller ej.
- Bestämma samtliga punkter som uppfyller Karush-Kuhn-Tuckers optimalitetsvillkor för ett givet (typiskt tillrättalagt men eventuellt inte konvext) optimeringsproblem med ickelinjär målfunktion och ickelinjära likhets- och/eller olikhetsbivillkor, samt avgöra om någon av dessa utgör en global optimallösning.
För att uppnå högsta betyg ska studenten dessutom kunna följande:
- Redogöra för begreppet Lagrangerelaxering och använda detta verktyg för att lösa separabla konvexa problem.
- Formulera vissa (relativt renodlade) tillämpningsproblem, exempelvis optimering av länkflödena i olika typer av nätverk eller att bestämma den minsta sfär som omsluter ett mängd givna punkter i R^3, som optimeringsproblem på lämplig form samt med tillgänglig programvara i Matlab lösa dessa problem och tolka resultaten.
- Kombinera samtliga ovannämnda begrepp och metoder för att lösa mer sammansatta problem.
