Operační výzkum

Předmět U63C5101 nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět 32BC-P-OPVY-01 (vztah je symetrický)

Předmět U63C5101 může být splněn v zastoupení předmětem 32BC-P-OPVY-01

Garant předmětu:

Přednášející:

Cvičící:

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

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• B-EK-prez.forma od 15/16 (povinný předmět)
• B-PM-prez.forma od 15/16 (povinně volitelný předmět)
• B-EK-prez.forma od 16/17 (povinný předmět)
• B-EK-prez.forma od 17/18 (povinný předmět)
• B-EM-P prezenční studium od 18/19 (povinný předmět)
• B-EM-P prezenční studium od 19/20 (povinný předmět)
• B-EM-P prezenční studium od 20/21 (povinný předmět)
• B-EM-P prezenční studium od 21/22 (povinný předmět)
• B-EM-P prezenční studium od 22/23 (povinný předmět)