MV026 Lineární programování

Fakulta informatiky
jaro 2004
Rozsah
2/1. 3 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k, z.
Vyučující
doc. RNDr. Jiří Kaďourek, CSc. (přednášející)
Garance
doc. RNDr. Jiří Kaďourek, CSc.
Ústavy – Přírodovědecká fakulta
Kontaktní osoba: doc. RNDr. Jiří Kaďourek, CSc.
Předpoklady
! M026 Lineární programování && ( M004 Lineární algebra II || MA004 Lineární algebra II || SOUHLAS )
Před zápisem tohoto kursu studenti musí absolvovat 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í. Technika lineárního programování, totiž tzv. simplexová metoda, je jedním z nejvíce využívaných matematických algoritmů na počítačích. 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 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. 314 s. ISBN 80-05-00679-9. 1990. info
  • SCHRIJVER, Alexander. Theory of Linear and Integer Programming. Chichester: John Wiley & Sons. 471 s. ISBN 0 471 90854 1. 1986. info
Metody hodnocení
Předmět je ukončen písemnou zkouškou.
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ě.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích jaro 2003, jaro 2005.