M4110 Lineární programování

Přírodovědecká fakulta
jaro 2005
Rozsah
2/1/0. 3 kr. (příf plus uk plus > 4). Ukončení: zk.
Vyučující
doc. RNDr. Jiří Kaďourek, CSc. (přednášející)
Garance
doc. RNDr. Jiří Kaďourek, CSc.
Ústav matematiky a statistiky – Ústavy – Přírodovědecká fakulta
Kontaktní osoba: doc. RNDr. Jiří Kaďourek, CSc.
Rozvrh
St 16:00–17:50 N21
  • Rozvrh seminárních/paralelních skupin:
M4110/01: St 15:00–15:50 N21, J. Kaďourek
Předpoklady
M2110 Lineární algebra II || (( M2500 Algebra II || M1110 Lineární algebra I || M1115 Lineární algebra I ) && M3521 Geometrie 2 )
Je nutno předem absolvovat předmět 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
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.
Osnova
  • Formulace úloh lineárního programování.
  • Teorie lineárních nerovnic - Farkasova věta.
  • Dualita 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.
  • Revidovaná simplexová metoda.
  • Geometrie duální simplexové metody.
  • Tabulkový tvar 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
  • Robert Fourer, Linear Programming Frequently Asked Questions, Optim. Techn. Center of Northwestern Univ. and Argonne Nat. Lab., http://www-unix... (2000).
Metody hodnocení
Předmět je ukončen písemnou zkouškou.
Navazující předměty
Informace učitele
Podmínkou pro přístup ke zkoušce je pravidelná účast ve cvičeních s tím, že tolerovány jsou nanejvýš dvě neomluvené absence za semestr. Požadavkem k úspěšnému vykonání zkoušky je teoretické i praktické zvládnutí látky v rozsahu probraném na přednášce i ve cvičeních.
Další komentáře
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 2006, jaro 2007, jaro 2008, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2012 - akreditace, jaro 2013, jaro 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019.