Informace o předmětu

M8150 Celočíselné programování

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

• 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

• 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.

M8150 Celočíselné programování

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

• 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.

M8150 Celočíselné programování

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

• 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.

M8150 Celočíselné programování

Rozsah

2/1/0. 4 kr. 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í || M7100 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

Ú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í

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

Další komentáře

Předmět je vyučován jednou za dva roky.
Výuka probíhá každý týden.

M8150 Celočíselné programování

Rozsah

2/1/0. 4 kr. 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í

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)

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í

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

Další komentáře

Předmět je vyučován jednou za dva roky.
Výuka probíhá každý týden.

M8150 Celočíselné programování

Předmět se v období jaro 2025 nevypisuje.

Rozsah

2/1/0. 3 kr. (příf plus uk k 1 zk 2 plus 1 > 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
Dodavatelské pracoviště: Ú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

• 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í.
Cíle předmětu: Po absolvování tohoto předmětu bude student schopen se orientovat v teoretických základech celočíselného lineárního programování, bude ovládat početní techniky odvozené z Gomoryho algoritmů umožňující řešit v ruce konkrétní malé úlohy celočíselného lineárního programování a bude rovněž schopen aplikovat metody založené na implicitní enumeraci a využívající lineárních relaxací k řešení některých problémů binárního programování, jako je například úloha o binárním batohu.

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í

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.

Informace učitele

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 již není vypisován.
Výuka probíhá každý týden.

M8150 Celočíselné programování

Předmět se v období jaro 2024 nevypisuje.

Rozsah

2/1/0. 3 kr. (příf plus uk k 1 zk 2 plus 1 > 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
Dodavatelské pracoviště: Ú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

• 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í.
Cíle předmětu: Po absolvování tohoto předmětu bude student schopen se orientovat v teoretických základech celočíselného lineárního programování, bude ovládat početní techniky odvozené z Gomoryho algoritmů umožňující řešit v ruce konkrétní malé úlohy celočíselného lineárního programování a bude rovněž schopen aplikovat metody založené na implicitní enumeraci a využívající lineárních relaxací k řešení některých problémů binárního programování, jako je například úloha o binárním batohu.

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í

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.

Informace učitele

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 již není vypisován.
Výuka probíhá každý týden.

M8150 Celočíselné programování

Předmět se v období jaro 2023 nevypisuje.

Rozsah

2/1/0. 3 kr. (příf plus uk k 1 zk 2 plus 1 > 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
Dodavatelské pracoviště: Ú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

• 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í.
Cíle předmětu: Po absolvování tohoto předmětu bude student schopen se orientovat v teoretických základech celočíselného lineárního programování, bude ovládat početní techniky odvozené z Gomoryho algoritmů umožňující řešit v ruce konkrétní malé úlohy celočíselného lineárního programování a bude rovněž schopen aplikovat metody založené na implicitní enumeraci a využívající lineárních relaxací k řešení některých problémů binárního programování, jako je například úloha o binárním batohu.

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í

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.

Informace učitele

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 již není vypisován.
Výuka probíhá každý týden.

M8150 Celočíselné programování

Předmět se v období jaro 2022 nevypisuje.

Rozsah

2/1/0. 3 kr. (příf plus uk k 1 zk 2 plus 1 > 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
Dodavatelské pracoviště: Ú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

• 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í.
Cíle předmětu: Po absolvování tohoto předmětu bude student schopen se orientovat v teoretických základech celočíselného lineárního programování, bude ovládat početní techniky odvozené z Gomoryho algoritmů umožňující řešit v ruce konkrétní malé úlohy celočíselného lineárního programování a bude rovněž schopen aplikovat metody založené na implicitní enumeraci a využívající lineárních relaxací k řešení některých problémů binárního programování, jako je například úloha o binárním batohu.

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í

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.

Informace učitele

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 již není vypisován.
Výuka probíhá každý týden.

M8150 Celočíselné programování

Předmět se v období jaro 2021 nevypisuje.

Rozsah

2/1/0. 3 kr. (příf plus uk k 1 zk 2 plus 1 > 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
Dodavatelské pracoviště: Ú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

• 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í.
Cíle předmětu: Po absolvování tohoto předmětu bude student schopen se orientovat v teoretických základech celočíselného lineárního programování, bude ovládat početní techniky odvozené z Gomoryho algoritmů umožňující řešit v ruce konkrétní malé úlohy celočíselného lineárního programování a bude rovněž schopen aplikovat metody založené na implicitní enumeraci a využívající lineárních relaxací k řešení některých problémů binárního programování, jako je například úloha o binárním batohu.

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í

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.

Informace učitele

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 již není vypisován.
Výuka probíhá každý týden.

M8150 Celočíselné programování

Předmět se v období jaro 2020 nevypisuje.

Rozsah

2/1/0. 3 kr. (příf plus uk k 1 zk 2 plus 1 > 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
Dodavatelské pracoviště: Ú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

• 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í.
Cíle předmětu: Po absolvování tohoto předmětu bude student schopen se orientovat v teoretických základech celočíselného lineárního programování, bude ovládat početní techniky odvozené z Gomoryho algoritmů umožňující řešit v ruce konkrétní malé úlohy celočíselného lineárního programování a bude rovněž schopen aplikovat metody založené na implicitní enumeraci a využívající lineárních relaxací k řešení některých problémů binárního programování, jako je například úloha o binárním batohu.

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í

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.

Informace učitele

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 již není vypisován.
Výuka probíhá každý týden.

M8150 Celočíselné programování

Předmět se v období jaro 2019 nevypisuje.

Rozsah

2/1/0. 3 kr. (příf plus uk k 1 zk 2 plus 1 > 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
Dodavatelské pracoviště: Ú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

• 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í.
Cíle předmětu: Po absolvování tohoto předmětu bude student schopen se orientovat v teoretických základech celočíselného lineárního programování, bude ovládat početní techniky odvozené z Gomoryho algoritmů umožňující řešit v ruce konkrétní malé úlohy celočíselného lineárního programování a bude rovněž schopen aplikovat metody založené na implicitní enumeraci a využívající lineárních relaxací k řešení některých problémů binárního programování, jako je například úloha o binárním batohu.

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í

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.

Informace učitele

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 již není vypisován.
Výuka probíhá každý týden.

M8150 Celočíselné programování

Předmět se v období jaro 2018 nevypisuje.

Rozsah

2/1/0. 3 kr. (příf plus uk k 1 zk 2 plus 1 > 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
Dodavatelské pracoviště: Ú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

• 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í.
Cíle předmětu: Po absolvování tohoto předmětu bude student schopen se orientovat v teoretických základech celočíselného lineárního programování, bude ovládat početní techniky odvozené z Gomoryho algoritmů umožňující řešit v ruce konkrétní malé úlohy celočíselného lineárního programování a bude rovněž schopen aplikovat metody založené na implicitní enumeraci a využívající lineárních relaxací k řešení některých problémů binárního programování, jako je například úloha o binárním batohu.

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í

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.

Informace učitele

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 již není vypisován.
Výuka probíhá každý týden.

M8150 Celočíselné programování

Předmět se v období jaro 2017 nevypisuje.

Rozsah

2/1/0. 3 kr. (příf plus uk k 1 zk 2 plus 1 > 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
Dodavatelské pracoviště: Ú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

• 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í.
Cíle předmětu: Po absolvování tohoto předmětu bude student schopen se orientovat v teoretických základech celočíselného lineárního programování, bude ovládat početní techniky odvozené z Gomoryho algoritmů umožňující řešit v ruce konkrétní malé úlohy celočíselného lineárního programování a bude rovněž schopen aplikovat metody založené na implicitní enumeraci a využívající lineárních relaxací k řešení některých problémů binárního programování, jako je například úloha o binárním batohu.

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í

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.

Informace učitele

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 již není vypisován.
Výuka probíhá každý týden.

M8150 Celočíselné programování

Předmět se v období jaro 2016 nevypisuje.

Rozsah

2/1/0. 3 kr. (příf plus uk k 1 zk 2 plus 1 > 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
Dodavatelské pracoviště: Ú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

• 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í.
Cíle předmětu: Po absolvování tohoto předmětu bude student schopen se orientovat v teoretických základech celočíselného lineárního programování, bude ovládat početní techniky odvozené z Gomoryho algoritmů umožňující řešit v ruce konkrétní malé úlohy celočíselného lineárního programování a bude rovněž schopen aplikovat metody založené na implicitní enumeraci a využívající lineárních relaxací k řešení některých problémů binárního programování, jako je například úloha o binárním batohu.

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í

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.

Informace učitele

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 jednou za dva roky.
Výuka probíhá každý týden.

M8150 Celočíselné programování

Předmět se v období jaro 2015 nevypisuje.

Rozsah

2/1/0. 3 kr. (příf plus uk k 1 zk 2 plus 1 > 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
Dodavatelské pracoviště: Ú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

• 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í.
Cíle předmětu: Po absolvování tohoto předmětu bude student schopen se orientovat v teoretických základech celočíselného lineárního programování, bude ovládat početní techniky odvozené z Gomoryho algoritmů umožňující řešit v ruce konkrétní malé úlohy celočíselného lineárního programování a bude rovněž schopen aplikovat metody založené na implicitní enumeraci a využívající lineárních relaxací k řešení některých problémů binárního programování, jako je například úloha o binárním batohu.

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í

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.

Informace učitele

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 jednou za dva roky.
Výuka probíhá každý týden.

M8150 Celočíselné programování

Předmět se v období jaro 2014 nevypisuje.

Rozsah

2/1/0. 3 kr. (příf plus uk k 1 zk 2 plus 1 > 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
Dodavatelské pracoviště: Ú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

• 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í.
Cíle předmětu: Po absolvování tohoto předmětu bude student schopen se orientovat v teoretických základech celočíselného lineárního programování, bude ovládat početní techniky odvozené z Gomoryho algoritmů umožňující řešit v ruce konkrétní malé úlohy celočíselného lineárního programování a bude rovněž schopen aplikovat metody založené na implicitní enumeraci a využívající lineárních relaxací k řešení některých problémů binárního programování, jako je například úloha o binárním batohu.

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í

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.

Informace učitele

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 jednou za dva roky.
Výuka probíhá každý týden.

M8150 Celočíselné programování

Předmět se v období jaro 2013 nevypisuje.

Rozsah

2/1/0. 3 kr. (příf plus uk k 1 zk 2 plus 1 > 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
Dodavatelské pracoviště: Ú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

• 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í.
Cíle předmětu: Po absolvování tohoto předmětu bude student schopen se orientovat v teoretických základech celočíselného lineárního programování, bude ovládat početní techniky odvozené z Gomoryho algoritmů umožňující řešit v ruce konkrétní malé úlohy celočíselného lineárního programování a bude rovněž schopen aplikovat metody založené na implicitní enumeraci a využívající lineárních relaxací k řešení některých problémů binárního programování, jako je například úloha o binárním batohu.

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í

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.

Informace učitele

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 jednou za dva roky.
Výuka probíhá každý týden.

M8150 Celočíselné programování

Předmět se v období jaro 2012 nevypisuje.

Rozsah

2/1/0. 3 kr. (příf plus uk k 1 zk 2 plus 1 > 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
Dodavatelské pracoviště: Ú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

• 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í.
Cíle předmětu: Po absolvování tohoto předmětu bude student schopen se orientovat v teoretických základech celočíselného lineárního programování, bude ovládat početní techniky odvozené z Gomoryho algoritmů umožňující řešit v ruce konkrétní malé úlohy celočíselného lineárního programování a bude rovněž schopen aplikovat metody založené na implicitní enumeraci a využívající lineárních relaxací k řešení některých problémů binárního programování, jako je například úloha o binárním batohu.

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í

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.

Informace učitele

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 jednou za dva roky.
Výuka probíhá každý týden.

M8150 Celočíselné programování

Předmět se v období jaro 2011 nevypisuje.

Rozsah

2/1/0. 3 kr. (příf plus uk k 1 zk 2 plus 1 > 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

• 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í.
Cíle předmětu: Po absolvování tohoto předmětu bude student schopen se orientovat v teoretických základech celočíselného lineárního programování, bude ovládat početní techniky odvozené z Gomoryho algoritmů umožňující řešit v ruce konkrétní malé úlohy celočíselného lineárního programování a bude rovněž schopen aplikovat metody založené na implicitní enumeraci a využívající lineárních relaxací k řešení některých problémů binárního programování, jako je například úloha o binárním batohu.

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í

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.

Informace učitele

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 jednou za dva roky.
Výuka probíhá každý týden.

M8150 Celočíselné programování

Předmět se v období jaro 2010 nevypisuje.

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

• 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í.
Cíle předmětu: Po absolvování tohoto předmětu bude student schopen se orientovat v teoretických základech celočíselného lineárního programování, bude ovládat početní techniky odvozené z Gomoryho algoritmů umožňující řešit v ruce konkrétní malé úlohy celočíselného lineárního programování a bude rovněž schopen aplikovat metody založené na implicitní enumeraci a využívající lineárních relaxací k řešení některých problémů binárního programování, jako je například úloha o binárním batohu.

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í

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.

Informace učitele

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 jednou za dva roky.
Výuka probíhá každý týden.

M8150 Celočíselné programování

Předmět se v období jaro 2009 nevypisuje.

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

• 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í.
Cíle předmětu: Po absolvování tohoto předmětu bude student schopen se orientovat v teoretických základech celočíselného lineárního programování, bude ovládat početní techniky odvozené z Gomoryho algoritmů umožňující řešit v ruce konkrétní malé úlohy celočíselného lineárního programování a bude rovněž schopen aplikovat metody založené na implicitní enumeraci a využívající lineárních relaxací k řešení některých problémů binárního programování, jako je například úloha o binárním batohu.

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í

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.

Informace učitele

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 jednou za dva roky.
Výuka probíhá každý týden.

M8150 Celočíselné programování

Předmět se v období jaro 2007 nevypisuje.

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

• 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.

M8150 Celočíselné programování

Předmět se v období jaro 2005 nevypisuje.

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

• 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.

M8150 Celočíselné programování

Předmět se v období jaro 2001 nevypisuje.

Rozsah

2/1/0. 4 kr. 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í

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

Ú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í

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

Další komentáře

Předmět je vyučován jednou za dva roky.
Výuka probíhá každý týden.

M8150 Celočíselné programování

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 Analýza v komplexním oboru
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

• 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.

M8150 Celočíselné programování

Předmět se v období jaro 2012 - akreditace nevypisuje.

Údaje z období jaro 2012 - akreditace se nezveřejňují

Rozsah

2/1/0. 3 kr. (příf plus uk k 1 zk 2 plus 1 > 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
Dodavatelské pracoviště: Ú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

• 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í.
Cíle předmětu: Po absolvování tohoto předmětu bude student schopen se orientovat v teoretických základech celočíselného lineárního programování, bude ovládat početní techniky odvozené z Gomoryho algoritmů umožňující řešit v ruce konkrétní malé úlohy celočíselného lineárního programování a bude rovněž schopen aplikovat metody založené na implicitní enumeraci a využívající lineárních relaxací k řešení některých problémů binárního programování, jako je například úloha o binárním batohu.

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í

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.

Informace učitele

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 jednou za dva roky.
Výuka probíhá každý týden.

M8150 Celočíselné programování

Předmět se v období jaro 2011 - akreditace nevypisuje.

Rozsah

2/1/0. 3 kr. (příf plus uk k 1 zk 2 plus 1 > 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 Analýza v komplexním oboru
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í.
Cíle předmětu: Po absolvování tohoto předmětu bude student schopen se orientovat v teoretických základech celočíselného lineárního programování, bude ovládat početní techniky odvozené z Gomoryho algoritmů umožňující řešit v ruce konkrétní malé úlohy celočíselného lineárního programování a bude rovněž schopen aplikovat metody založené na implicitní enumeraci a využívající lineárních relaxací k řešení některých problémů binárního programování, jako je například úloha o binárním batohu.

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í

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.

Informace učitele

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 jednou za dva roky.
Výuka probíhá každý týden.

• Statistika zápisu (nejnovější)