M8150 Celočíselné programování

Přírodovědecká fakulta
jaro 2008
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
Předpoklady
M4110 Lineární programování || M5170 Matem. programování
Je nutno předem absolvovat buď předmět M4110 Lineární programování nebo předmět M5170 Matematické programování.
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
Obsahem předmětu jsou obecné algoritmy pro řešení úloh celočíselného lineárního programování. Ty lze rozčlenit do dvou skupin. Jedním typem algoritmů jsou algoritmy řezných rovin. Typickými představiteli této skupiny algoritmů jsou Gomoryho algoritmy. Jiným typem algoritmů jsou metody založené na implicitní enumeraci využívající lineárních relaxací. Oba přístupy mohou být kombinovány k získání účinnějších algoritmů například při řešení úloh binárního programování.
Osnova
  • Úlohy celočíselného lineárního programování
  • Status úlohy celočíselného programování
  • Schéma algoritmů řezných rovin
  • Gomoryho zlomkový algoritmus řezných rovin
  • Gomoryho plně celočíselný algoritmus řezných rovin
  • Schema metod větví a mezí
  • Metoda větví a mezí s užitím lineárních relaxací
  • Dynamické programování a úlohy o batohu
  • Řešení úlohy o binárním batohu metodou větví a mezí
  • Řešení úloh binárního programování kombinací metody řezných rovin s metodou větví a mezí.
Literatura
  • NEMHAUSER, George L. a Laurence A. WOLSEY. Integer and Combinatorial Optimization. New York: John Wiley & Sons, 1988, 763 s. ISBN 0-471-82819-X. info
  • SCHRIJVER, Alexander. Theory of Linear and Integer Programming. Chichester: John Wiley & Sons, 1986, 471 s. ISBN 0 471 90854 1. info
Metody hodnocení
Předmět je ukončen písemnou zkouškou.
Další komentáře
Předmět je vyučován jednou za dva roky.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích jaro 2008 - akreditace, jaro 2000, jaro 2002, jaro 2004, jaro 2006.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.muni.cz/predmet/sci/jaro2008/M8150