M4110 Lineární programování

Přírodovědecká fakulta
jaro 2010
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í)
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
Rozvrh
Út 16:00–17:50 M1,01017
  • Rozvrh seminárních/paralelních skupin:
M4110/01: Út 15:00–15:50 M1,01017, 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
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
předmět má 7 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 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).
Výukové metody
Klasická forma výuky pozůstávající z přednášek doplněných cvičeními.
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
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 2011, jaro 2012, jaro 2012 - akreditace, jaro 2013, jaro 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019.