Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2023/2024
UPOZORNĚNÍ: Jsou dostupné studijní plány pro následující akademický rok.

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
32BC-P-OPVY-01 Z,ZK 6 2P+2C česky
Vztahy:
Předmět 32BC-P-OPVY-01 nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět U63C5101 (vztah je symetrický)
Předmět 32BC-P-OPVY-01 může při kontrole studijních plánů nahradit předmět U63C5101
Garant předmětu:
Petr Makovský
Přednášející:
Petr Makovský, Jiří Nárožný
Cvičící:
Petr Makovský, Jiří Nárožný
Předmět zajišťuje:
institut ekonomických studií
Anotace:

Operační výzkum je vědní obor, který se zabývá formulováním, modelováním a řešením rozmanitých rozhodovacích problémů zejména optimalizačního charakteru.

Požadavky:

K úspěšnému splnění předmětu je třeba zisk zápočtu a složení písemné zkoušky. Získání zápočtu je podmíněno pravidelnou docházkou na cvičení při maximálním počtu tří řádných absencí za semestr* a napsáním písemné zápočtové prověrky

na alespoň 50% z maximálního počtu bodů. Zápočtová prověrka se píše zhruba v polovině semestru.

Zkoušková písemná práce je považována za úspěšně složenou v případě dosažení alespoň 50% bodů z maxima.

*Do tohoto počtu absencí se nezahrnují mimořádné absence, k nimž student(ka) předloží relevantní důvody. Cvičící si může v takových situacích vyžádat podklady k jejich ověření.

Osnova přednášek:

1.Úvod do předmětu. Lineární programování. Sestavování matematických modelů. Obecná pravidla při 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í metody 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.Simplexová metoda řešení úlohy lineárního programování – řešení simplexovým algoritmem. Maticový zápis simplexové tabulky.

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

6.Úvod do celočíselného programování. Metoda řezných nadrovin. Gomorih algoritmus I. a II. Požadavek celočíselnosti na všechny či jen některé vybrané strukturní proměnné.

7.Dopravní úloha. Formulace dopravní úlohy. Nalezení výchozího bazického řešení dopravní úlohy – metoda „severozápadního rohu“, indexní metoda.

8.Metoda VAM (Vogelova aproximační metoda). Dantzigova optimalizační metoda.

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

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

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

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

13.Úvod do teorie zásob. Vícekriteriální rozhodování.

14.Modely hromadné obsluhy. Markovovy modely.

Osnova cvičení:

1.Sestavování matematických modelů. Procvičování základních typů úloh lineárního programování

a)Výrobní program

b)Řezný plán

c)Směšovací problém

d)Investiční problém

2.Hledání bazického řešení soustavy lineárních rovnic pomocí metod z lineární algebry. Příklady hledání přípustného bazického řešení úlohy lineárního programování.

3.Grafické řešení úlohy lineárního programování. Strojové řešení úlohy lineárního programování (MS Excel, LINGO)

4.Simplexová metoda řešení úlohy lineárního programování. Řešení pomocí maticového zápisu simplexové tabulky.

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

6.Úlohy vedoucí na celočíselné lineární programování.

7.Dopravní úloha. Formulace dopravní úlohy. Nalezení výchozího bazického řešení dopravní úlohy – metoda „severozápadního rohu“. Metoda indexní.

8.Metoda VAM (= Vogelova aproximační metoda). Dantzigova optimalizační metoda.

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

10.Teorie grafů. Reprezentace grafů. Kostry, stromy, cesty v grafech. Izomorfizmus grafů.

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

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

13.Úvod do teorie zásob. Vícekriteriální rozhodování.

14.Modely hromadné obsluhy. Markovovy modely.

Cíle studia:

Obecným cílem předmětu je 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í se základními metodami lineárního programování, na konkrétních příkladech bude vysvětlena aplikace simplexova

algoritmu a duálního simplexova algoritmu. Dále bude představena problematika 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í.

V dalším se studenti seznámí 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 grafech. Součástí bude i problematika síťové analýzy, zejména aplikace metody CPM.

V závěrečné části semestru se studenti seznámí s pokročilejšími partiemi operačního výzkumu, bude jim představena teorie zásob, hromadné obsluhy, vícekriteriálního

rozhodování a Markovovských procesů.

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:
Rozvrh na zimní semestr 2023/2024:
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 DEJ:421

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

12:30–14:00
(paralelka 102)
Dejvice
Učebna
Út
St
místnost DEJ:421

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

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

09:00–10:30
(přednášková par. 1)
Dejvice
103

Rozvrh na letní semestr 2023/2024:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 14. 6. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet1246743918505.html