FSF3812 Tillämpad linjär optimering 7,5 hp

Teori och metoder:

Simplexmetoden och inrepunktsmetoder för linjärprogrammering. Utnyttjande av problemstruktur, exempelvis dekomposition och kolumngenerering. Stokastisk programmering, metoder samt utnyttjande av problemstruktur. Branch and bound för heltalsprogrammering. Lagrangerelaxering och subgradientmetoder tillämpat på storskaliga heltalsprogrammeringsproblem med speciell struktur.

Projektuppgifter:

Denna del av kursen är uppbyggd kring praktisk optimeringsmodellering och problemlösning. Här ska man formulera optimeringsproblem, tillämpa sina metodkunskaper och lösa problemen med befintlig optimeringsprogramvara. Detta genomförs i form av projekt i mindre grupper. Ett viktigt inslag är samarbete inom gruppen samt muntlig och skriftlig presentation av resultaten.

Kursens övergripande mål är dels att studenten ska behärska modeller, metoder och teori för olika varianter av linjär optimering och heltalsoptimering, dels att studenten ska kunna modellera och ha ett modelleringsspråk lösa realistiska linjära optimeringsproblem, samt presentera resultaten muntligt och skriftligt.

Efter genomgången kurs ska studenten kunna:

• Förklara hur simplexmetoden fungerar.
• Förklara hur primal-duala inrepunktsmetoder för linjärprogrammeringsproblem fungerar.
• Utgående från en tillrättalagd problembeskrivning formulera ett linjärprogrammeringsproblem eller ett linjärt heltalsprogrammeringsproblem och lösa det med hjälp av det modelleringsspråk som används i kursen.
• Tolka svaren i de lösta tillrättalagda verkliga problem med hjälp av fundamentala begrepp som känslighetsanalys.
• Förklara hur trädsökning fungerar för att lösa heltalsprogrammeringsproblem.
• Under lämpliga förutsättningar visa fundamentala resultat om linjärprogrammering såsom stark dualitet och existens av extrempunktslösningar.
• Beskriva vad relaxeringar är.
• Relatera modelleringen till det egna forskningsområdet.

Studenter som tillgodogjort sig kursen väl förväntas dessutom kunna:

• Utnyttja problemstruktur för att lösa speciella klasser av linjärprogrammeringsproblem, exempelvis Dantzig-Wolfedekomposition.

• Förklara hur lagrangerelaxering kan användas för att lösa linjära heltalsprogrammeringsproblem.

• Förklara hur subgradientmetoder fungerar applicerade på duala problem till linjära heltalsprogrammeringsproblem.

• Använda kolumngenerering för att lösa speciella klasser av linjärprogrammeringsproblem.

• Använda stokastisk programmering för att modellera osäkerhet i problemdata.

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

Anges vid kursstart. Preliminär litteratur:

Linear and Nonlinear Programming av S.G.Nash och A.Sofer, McGraw-Hill, samt kompletterande material från institutionen.

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

• PRO1 - Projektarbete, 3,0 hp, betygsskala: P, F
• TEN1 - Skriftlig tentamen, 4,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.

Projektuppgifter.

Skriftlig tentamen.

Jan Kronqvist

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