PřF:M8150 Celočíselné programování - Informace o předmětu
M8150 Celočíselné programování
Přírodovědecká fakultajaro 2004
- 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. - Předpoklady
- M4110 Lineární programování || M5170 Matematické 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
- Matematika (program PřF, M-MA)
- Matematika (program PřF, N-MA)
- 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
- 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.
- Statistika zápisu (jaro 2004, nejnovější)
- Permalink: https://is.muni.cz/predmet/sci/jaro2004/M8150