TIEA382 Lineaarinen ja diskreetti optimointi

kevät 2012

yliassistentti Jussi Hakanen
jussi.hakanen(at)jyu.fi
AgC 426.3

Kurssi Korpissa: https://korppi.jyu.fi/kotka/r.jsp?course=114134

Laajuus: 5 op

Taso: Tietotekniikan kandidaattiopintojen valinnainen kurssi. Vaaditaan esitietoina laskennallisten tieteiden (ent. simuloinnin ja optimoinnin)
suuntautumisvaihtoehdon maisteriopinnoissa. Korvaa vanhan Optimointimenetelmät-kurssin.

Sisältö: lineaarista, kombinatorista ja kokonaislukuoptimointia

Esitiedot: Matematiikan approbatur tai vastaavat tiedot.

Luennot: ke 8.30-10 ja to 14-16 salissa AgC 233 11.1.-8.3.2012. Huom. viikolla 4 ei luentoja eikä demoja!

Harjoitukset: to 12-14 salissa Ag C231 19.1. alkaen.
Laskuharjoitusten tekemisestä saa hyvityspisteitä loppukokeeseen seuraavasti:
20% -> 1p
40% -> 2p
60% -> 3p
80% -> 4p

Kurssin suoritus: loppukoe ja harjoitustyö

Kurssin suorittamiseen kuuluu harjoitustyö, jossa ratkaistaan lineaarinen optimointiongelma. Harjoitustyö sisältää annetun optimointiongelman matemaattisen mallintamisen,
mallin ratkaisemisen lineaarisen optimoinnin ohjelmistolla sekä tulosten tulkinnan. Työstä laaditaan raportti. Harjoitustyön aiheita voi pyytää luennoitsijalta.

Loppukokeet: 15.3., 13.4. ja 25.5.

Kurssista on luentomoniste Lineaarinen ja diskreetti optimointi, jota voi ostaa Ylistön kirjastosta, YlistöK 308, hintaan 7,80 euroa.

Demotehtävät:
1. demot 19.1.
2. demot 2.2.
3. demot 9.2.
4. demot 16.2.
5. demot 23.2.
6. demot 1.3.
7. demot 8.3.

Luentomateriaali:
Aloitusluento
Yleistä optimoinnista
Lineaarisen optimoinnin perusteita
Simplex-menetelmä
Yleinen Simplex-menetelmä
Lineaarisen optimoinnin duaaliteoriaa
Tehtävän jälki- ja herkkyysanalyysiä
Parametrinen optimointi
Monitavoiteoptimointi
Kombinatorista optimointia
Kokonaislukuoptimointia
Kokonaislukuoptimointitehtävän ratkaiseminen
Kuljetus- ja kohdistustehtävien ratkaisemisesta
Optimoinnista verkkoteoriassa
Kertaus
Tuukka Purasen vierailuluento reittien optimoinnista.

Kirjallisuutta:

Taha, Operations Research: An Introduction, 2007 (8th edition)
Vanderbei, Linear Programming: Foundations and Extensions, 2001 (2nd edition), saatavilla sähköisesti
Chinneck, Practical Optimization: a Gentle Introduction, 2001, saatavilla sähköisesti
Bertsimas & Tsitsikis, Introduction to Linear Optimization, 1997
Fletcher, Practical Methods of Optimization vol 2, 1987 (1980)
Luenberger, Linear and Nonlinear Programming, 1984
Juha Haataja, Optimointitehtävien ratkaiseminen, CSC:n oppaat, 2004, saatavilla sähköisesti

Lineaarisen optimoinnin ohjelmistoja voi etsiä mm. seuraavilta WWW-sivuilta:

NEOS (Network Enabled Optimization System) Optimization Software Guide
Decision Tree for Optimization Software

Demoversion Lingo-ohjelmasta (nykyinen versio Lindosta) voi ladata osoitteesta:

Lingo download