M4110 Lineární programování

Přírodovědecká fakulta
jaro 2009
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
Rozvrh
Čt 16:00–17:50 M1,01017
  • Rozvrh seminárních/paralelních skupin:
M4110/01: Čt 15:00–15:50 M1,01017, J. Kaďourek
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
Studenti bakalářských programů Přírodovědecké fakulty musí předem absolvovat buďto předmět M2110 Lineární algebra a geometrie II, anebo některý z předmětů M1110 Lineární algebra a geometrie I či M1115 Lineární algebra a geometrie I a navíc předmět M3521 Geometrie 2.
Studenti Fakulty informatiky musí předem absolvovat předmět M2110 Lineární algebra a geometrie II nebo předmět MA004 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.
Cíle předmětu: Po absolvování tohoto předmětu bude student schopen se orientovat v teoretických základech lineárního programování, bude obeznámen s algebraickým odvozením simplexové metody a duální simplexové metody opírajícím se o příslušný geometrický náhled a bude ovládat početní techniky založené na těchto metodách umožňující řešit v ruce konkrétní malé úlohy lineárního programování.
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í
Výuka předmětu pozůstává z přednášek doplněných cvičeními. 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 2005, jaro 2006, jaro 2007, jaro 2008, jaro 2010, jaro 2011, jaro 2012, jaro 2012 - akreditace, jaro 2013, jaro 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019.