FSF3850 Numerisk linjärprogrammering 7,5 hp

Kursen behandlar teori och algoritmer för linjärprogrammeringsproblem.

Från 1940-talet var simplexmetoden, utvecklad av Dantzig, den enda praktiska metoden för att lösa linjärprogrammeringsproblem. Khachian hade i slutet av 1970-talet presenterat den polynomiella ellipsoidmetoden, men den var inte användbar i praktiken.

När Karmarkar presenterade sin inrepunktsmetod 1984, förändrades allt detta. Denna metod var polynomiell och enligt uppgift bättre än simplexmetoden även i praktiken.

Karmarkar's metod ledde till en "explosion" inom linjärprogrammeringsområdet. Gill et al. visade snart att Karmarkar's metod var ekvivalent med en logaritmisk barriärmetod, och utvecklingen av nya inrepunktsmetoder gick snabbt. Denna "tävlan" mellan simplexmetoden och inrepunktsmetoder har lett till avsevärda förbättringar för båda typerna av metoder. Avsikten med kursen är att spegla denna utveckling. Några mer avancerade aspekter av simplemetoden är inkluderade, till exempel brantaste lutningen, partiell dualuppdatering, och för inrepunktsmetoder exempelvis prediktions-korrektionsmetoder. Speciellt försöker vi förstå hur de olika metoderna fungerar.

Att studenten ska förvärva en djup förståelse för den matematiska teorin och de numeriska metoderna för linjärprogrammering.

Efter avslutad kurs ska studenten kunna

• Härleda fundamentala koncept hörande till polyedrar i linjära optimeringsproblem
• Förklara grundläggande dualitetskoncepts för linjärprogrammering.
• Förklara hur simplexmetoden fungerar, primal simplex, dual simplex, brantaste lutningen.
• Förklara hur inrepunktsmetoder fungerar, speciellt primal-duala metoder

Civilingenjörs- eller Masterexamen med minst 30 hp inom matematik (en- och flervariabelanalys, linjär algebra, differentialekvationer och transformer) samt minst 6 hp inom matematisk statistik, 6 hp inom numerisk analys och 6 hp inom optimeringslära.

Lämpliga förkunskaper är kurserna SF2812 Tillämpad linjär optimering och SF2520 Tillämpad numerisk analys, eller motsvarande förkunskaper.

Lämpliga förkunskaper är kurserna SF2812 Tillämpad linjär optimering och SF2520 Tillämpad numerisk metod eller liknande kunskaper.

Annonseras vid kursstart.

När kurs inte längre ges har student möjlighet att examineras under ytterligare två läsår.

• INL1 - Inlämningsuppgift, 7,5 hp, betygsskala: P, F

Examinator beslutar, baserat på rekommendation från KTH:s handläggare av stöd till studenter med funktionsnedsättning, om eventuell anpassad examination för studenter med dokumenterad, varaktig funktionsnedsättning.

Examinator får medge annan examinationsform vid omexamination av enstaka studenter.

Examination sker genom hemuppgifter och en muntlig sluttentamen

Hemuppgifter, muntlig slutexamen.

Anders Forsgren

• Vid grupparbete har alla i gruppen ansvar för gruppens arbete.
• Vid examination ska varje student ärligt redovisa hjälp som erhållits och källor som använts.
• Vid muntlig examination ska varje student kunna redogöra för hela uppgiften och hela lösningen.