Operační výzkum

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

Jakub Hanousek, Petr Makovský, Jiří Nárožný, Ladislav Vaniš

Cvičící:

Jakub Hanousek, Petr Makovský, Jiří Nárožný, Ladislav Vaniš

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:

Aktivita v hodinách: 10 bodů; Zápočtový písemný test (nutno 50 %): 30 bodů; Zkouška - písemný test: 60 bodů; Povinná docházka min. 80% cvič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 2024/2025:

	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:104 12:30–14:00 (paralelka 101) Dejvice 104místnost DEJ:104 14:15–15:45 (paralelka 102) Dejvice 104
Út	místnost JP:B-770 12:30–14:00 (paralelka 103) Jugoslávských partyzánů 3místnost JP:B-770 14:15–15:45 (paralelka 104) Jugoslávských partyzánů 3
St	místnost DEJ:103 10:45–12:15 (přednášková par. 1) Dejvice 103místnost DEJ:409 12:30–14:00 (paralelka 105) Dejvice Učebnamístnost DEJ:409 14:15–15:45 (paralelka 106) Dejvice Učebna
Čt	místnost DEJ:103 10:45–12:15 (přednášková par. 2) Dejvice 103místnost DEJ:104 12:30–14:00 (paralelka 107) Dejvice 104místnost DEJ:104 14:15–15:45 (paralelka 108) Dejvice 104
Pá

Rozvrh na letní semestr 2024/2025:

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)
• B-EM-P prezenční studium od 22/23 (povinný předmět)