M4110 Lineární programování

Přírodovědecká fakulta
jaro 2014
Rozsah
2/1/0. 3 kr. (příf plus uk k 1 zk 2 plus 1 > 4). Ukončení: zk.
Vyučující
doc. Mgr. Michal Kunc, Ph.D. (přednášející)
Garance
doc. RNDr. Jiří Kaďourek, CSc.
Ústav matematiky a statistiky – Ústavy – Přírodovědecká fakulta
Kontaktní osoba: doc. Mgr. Michal Kunc, Ph.D.
Dodavatelské pracoviště: Ústav matematiky a statistiky – Ústavy – Přírodovědecká fakulta
Rozvrh
Čt 16:00–17:50 M2,01021
  • Rozvrh seminárních/paralelních skupin:
M4110/01: Čt 18:00–18:50 M2,01021, M. Kunc
Předpoklady
M2110 Lineární algebra a geom. II || (( M1110 Lineární algebra a geom. I || M1115 Lineární algebra a geom. 1 ) && M3521 Geometrie 2 ) || PROGRAM(N-MA) || PROGRAM(N-AM) || PROGRAM(N-SS) || ( FI:MA004 Lineární algebra II ) || SOUHLAS
Znalost afinní geometrie v rozsahu předmětu M2110 Lineární algebra a geometrie II.
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
předmět má 9 mateřských oborů, zobrazit
Cíle předmětu
Lineární programování představuje jednu ze základních optimalizačních metod se širokým spektrem aplikací. Obsahem předmětu jsou nejprve teoretické základy této disciplíny pozůstávající ze studia soustav lineárních nerovnic a vedoucí až k pojmu duality v lineárním programování. Dále je probírána základní technika lineárního programování, totiž simplexová metoda a její různé varianty.
Po absolvování tohoto předmětu bude student schopen: aplikovat teoretické výsledky o systémech lineárních nerovnic a úlohách lineárního programování; chápat algebraické odvození simplexové metody a duální simplexové metody opírající se o příslušný geometrický náhled; používat výpočetní techniky založené na simplexové metodě a duální simplexové metodě.
Osnova
  • Formulace úloh lineárního programování.
  • Systémy lineárních nerovnic - Farkasovo lemma.
  • Věta o dualitě v lineárním programování.
  • Konvexní kužely a polyedry.
  • Rozklad polyedrů - Minkowského věta.
  • Struktura polyedrů - stěny polyedrů.
  • Geometrické odvození simplexové metody.
  • Tabulkový zápis simplexové metody.
  • Blandovo pravidlo.
  • Dvoufázová metoda.
  • Geometrické odvození duální simplexové metody.
  • Tabulkový zápis duální simplexové metody.
  • Dopravní problém.
  • Řešení dopravního problému simplexovou metodou.
Literatura
  • PLESNÍK, Ján, Jitka DUPAČOVÁ a Milan VLACH. Lineárne programovanie. 1. vyd. Bratislava: Alfa, vydavateľstvo technickej a ekonomickej literatúry, 1990, 314 s. ISBN 80-05-00679-9. info
  • SCHRIJVER, Alexander. Theory of Linear and Integer Programming. Chichester: John Wiley & Sons, 1986, 471 s. ISBN 0 471 90854 1. info
Výukové metody
přednášky, cvičení
Metody hodnocení
Písemná zkouška: požadováno alespoň 50% bodů.
Navazující předměty
Informace učitele
Podmínkou pro přístup ke zkoušce je pravidelná účast ve cvičeních, přičemž tolerovány jsou nanejvýš tři neomluvené absence.
Další komentáře
Studijní materiály
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích jaro 2008 - akreditace, jaro 2011 - akreditace, jaro 2000, jaro 2001, jaro 2002, jaro 2003, jaro 2004, jaro 2005, jaro 2006, jaro 2007, jaro 2008, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2012 - akreditace, jaro 2013, jaro 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019.