Operační výzkum

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čebnamí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čebnamí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
Pá

Rozvrh na letní semestr 2023/2024:

Rozvrh není připraven

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

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