Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2020/2021

Operační výzkum

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
U63C5101 Z,ZK 6 2P+2C česky
Přednášející:
Jiří Demel (gar.), Jana Kučerová
Cvičící:
Jiří Demel (gar.), Jana Kučerová
Předmět zajišťuje:
institut ekonomických studií
Anotace:

Operační výzkum je vědní obor se zabývá formulováním, modelováním a řešením rozmanitých rozhodovacích situací, ve kterých vybíráme nejlepší z přípustných řešení.

Požadavky:

kalkulačka, MS Excel

Osnova přednášek:

1. Úvod do předmětu. Lineární programování. Sestavování matematických modelů. Obecná pravidla sestavování matematických modelů. Základní typové úlohy - Výrobní program, řezný plán, směšovací problém, investiční problém. Sestavování modelů v praxi.

2. Základní pojmy lineárního programování. Maticový zápis soustavy rovnic. Bazické řešení soustavy rovnic. Kanonický tvar úlohy lineárního programování. Úprava omezujících podmínek z nerovnic na rovnice a se zápornou pravou stranou. Přípustné bazické řešení úlohy lineárního programování.

3. Grafické řešení úlohy lineárního programování. Základní principy grafického řešení, postup grafického řešení.

4. Simplexova metoda řešení úlohy lineárního programování - řešení pomocí simplexova algoritmu. Maticový zápis simplexové tabulky.

5. Dualita. Sestavování duálních úloh, hledání řešení duální úlohy ze simplexové tabulky primární úlohy. Věta o komplementaritě. Slabá a silná věta o dualitě.

6. Ekonomická interpretace duálně sdružených úloh. Duální simplexův algoritmus.

7. Analýza citlivosti. Analýza citlivosti pravé strany omezujících podmínek. Analýza citlivosti koeficientů účelové funkce.

8. Celočíselné programování. Metoda řezných nadrovin. Gomorihy algorimus I. a II. Požadavek celočíselnosti na všechny strukturních proměnných. Požadavek celočíselnosti jen na vybrané strukturní proměnné.

9. Dopravní úloha. Formulace dopravní úlohy. Nalezení výchozího bazického řešení dopravní úlohy - metoda severozápadního rohu, indexní metoda a metoda VAM (Vogelova aproximační metoda). Dantzigova optimalizační metoda.

10. Přiřazovací problém. Formulace úlohy minimalizační či maximalizační. Maďarská metoda řešení přiřazovacího problému. Hledání optimální permutace.

11. Teorie grafů. Základní pojmy teorie grafů. Reprezentace grafů. Kostry, stromy, cesty v grafech. Izomorfismus grafů.

12. Prohledávání v orientovaných a neorientovaných grafech. Grafové algoritmy. Hledání maximální dráhy. Stanovení maximálního toku - propustnost v dopravní síti. Floydův algoritmus.

13. Síťová analýza I. Metoda CPM - metoda kritické cesty. Metoda PERT. Stanovení časových rezerv.

14. Úvod do teorie zásob.

Osnova cvičení:

1. Sestavování matematických modelů. Procvičování základních typových úloh LP - Výrobní program, řezný plán, směšovací problém, investiční problém.

2. Příklady na převod úloh LP na kanonický tvar úlohy lineárního programování.

3. Grafické řešení úlohy lineárního programování.

4. Simplexova metoda řešení úlohy lineárního programování - řešení pomocí simplexova algoritmu.

5. Simplexova metoda řešení úlohy lineárního programování - řešení pomocí maticového zápisu simplexové tabulky.

6. Sestavování duálních úloh, hledání řešení duální úlohy ze simplexové tabulky primární úlohy. Aplikace věty o komplementaritě na hledání řešení duální úlohy ze zadání primární úlohy.

7. Příklady na duální simplexův algoritmus.

8. Analýza citlivosti I. Analýza citlivosti pravé strany omezujících podmínek.

9. Analýza citlivosti II. Analýza citlivosti koeficientů účelové funkce.

10. Celočíselné programování. Metoda řezných nadrovin. Gomorihy algorimus I. a II. Požadavek celočíselnosti na všechny strukturních proměnných. Požadavek celočíselnosti jen na vybrané strukturní proměnné.

11. Dopravní úloha. Formulace dopravní úlohy. Nalezení výchozího bazického řešení dopravní úlohy - metoda severozápadního rohu, indexní metoda a metoda VAM (Vogelova aproximační metoda). Dantzigova optimalizační metoda.

12. Přiřazovací problém. Formulace úlohy minimalizační či maximalizační. Maďarská metoda řešení přiřazovacího problému. Hledání optimální permutace.

13. Teorie grafů. Reprezentace grafů. Kostry, stromy, cesty v grafech. Izomorfismus grafů.

14. Síťová analýza. Stanovení kritické cesty. Sestavení síťového grafu.

Cíle studia:

Cílem předmětu bude naučit studenty vytvářet a řešit matematické modely reálných (především ekonomických) systémů s důrazem na hledání optimálních rozhodnutí podle zvolených kritérií. Studenti se seznámí s oblastmi lineárního programování a budou řešit obecné či celočíselné úlohy lineárního programování aplikací simplexova algoritmu/duálního simplexova algoritmu. Dále budou seznámeni s problematiku dopravních úloh s cílem minimalizace dopravních nákladů a přiřazovací problém s aplikací maďarské metody k hledání optimálního přiřazení.

Dále bude cílem seznámit studenty se základními pojmy z teorie grafů, zejména reprezentace grafů, hledání koster grafů, cest či propustnost v grafu, grafové algoritmy v orientovaných a neorientovaných grafů. Součástí bude i problematika síťové analýzy, zejména aplikace metody CPM a metody PERT. Závěrem budou studenti seznámeni s úvodem do teorie zásob, resp. modely pro řízení zásob.

Studijní materiály:

JABLONSKÝ, J. Programy pro matematické modelování. Praha: Oeconomica, 2011. 258 s. ISBN 978-80-245-1810-7.

JABLONSKÝ, J. Operační výzkum. 3.vyd. Praha: Professional Publishing, 2007. ISBN 978-80-8694-644-3.

VOLEK, J., LINDA, B. Teorie grafů - aplikace v dopravě a veřejné správě. Pardubice: Univerzita Pardubice, 2012. ISBN 978-80-7395-225-9.

BRÁZDOVÁ, M. Řešené úlohy lineárního programování. Pardubice: Univerzita Pardubice, 2011. ISBN 978-80-7395-361-4.

Poznámka:
Další informace:
http://moodle-vyuka.cvut.cz
Rozvrh na zimní semestr 2020/2021:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
místnost

16:00–17:30
(paralelka 101)
Út
St
místnost DEJ:103

12:30–14:00
(přednášková par. 1)
Dejvice
103
Čt
místnost DEJ:102

12:30–14:00
(paralelka 104)
Dejvice
102

místnost DEJ:402

09:00–10:30
(paralelka 102)
Dejvice
Učebna
místnost DEJ:402

10:45–12:15
(paralelka 103)
Dejvice
Učebna
místnost DEJ:402

12:30–14:00
(paralelka 105)
Dejvice
Učebna
Rozvrh na letní semestr 2020/2021:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 17. 1. 2021
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet5367606.html