INTERNAL
Operační
výzkum I
Přednášky
Jan Fábry
12/2/2022
INTERNAL
2
Literatura
Základní
▪ FÁBRY, J. Operační výzkum pro prezenční a kombinovanou formu studia. 1. vyd. ŠAVŠ o.p.s., 2019. 164 s.
ISBN 978-80-87042-84-7.
▪ JABLONSKÝ, J. Operační výzkum.: Kvantitativní modely pro ekonomické rozhodování. 3. vyd. Praha: Professional
Publishing, 2007. 323 s. ISBN 978-80-86946-44-3.
Doporučená
▪ FÁBRY, J. Matematické modelování. Praha: Professional Publishing, 2011. 180 s. ISBN 978-80-7431-066-9.
▪ JABLONSKÝ, J. Programy pro matematické modelování. Praha: Oeconomica, 2011. 258 s. ISBN 978-80-245-1810-7.
▪ EISELT, H. -- SANDBLOM, C. Operations Research.: A Model - Based Approach. 1. vyd. Heidelberg: Springer, 2010.
ISBN 978-3-642-10325-4.
▪ HILLIER, F S. -- LIEBERMAN, G J. Introduction to operations research /: Eleventh edition. McGraw-Hill, 2021. 964 s.
ISBN 9781260575873.
▪ BOUCHERIE, R J. -- BRAAKSMA, A. -- TIJMS, H C. Operations research: introduction to models and methods. World
Scientific, 2022. ISBN 9789811239342.
▪ RARDIN, R L. Optimization in operations research /: Second edition. Pearson, 2018. 1144 s. ISBN 978-93-530-6636-9.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
INTERNAL
3
Obsah kurzu
▪ Úvod do operačního výzkumu
▪ Definice a historie
▪ Rozhodovací problém
▪ Modelový přístup
▪ Klasifikace modelů
▪ Lineární programování
▪ Úvod
▪ Úlohy výrobního plánování
▪ Směšovací problém
▪ Řezná úloha
▪ Optimalizace portfolia
▪ Dopravní problém
▪ Kontejnerový dopravní problém
▪ Přiřazovací problém
▪ Úloha o pokrytí
▪ Úloha obchodního cestujícího
▪ Teorie grafů
▪ Úvod
▪ Hledání nejkratší cesty
▪ Optimální spojení míst
▪ Další optimalizační úlohy
▪ Řízení projektů
▪ Úvod
▪ Metoda kritické cesty CPM
▪ Metoda PERT
▪ Modely řízení zásob
▪ Úvod
▪ Model EOQ – Optimální velikost objednávky
▪ Produkčně – spotřební model
▪ Stochastický model s jednorázově vytvářenou zásobou
▪ Modely hromadné obsluhy
▪ Úvod
▪ Jednoduchý exponenciální model HO
▪ Exponenciální model HO s paralelními zařízenímiOperační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
INTERNAL
Úvod do operačního
výzkumu
1
4
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
INTERNAL
5
Úvod do operačního výzkumu
▪ Operational / Operations Research
▪ Management Science
▪ Operations Analysis
▪ Quantitative Analysis
▪ Quantitative Methods
▪ Systems Analysis
▪ Decision Analysis
▪ Decision Science
▪ Computer Science
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Alternativní názvy v zahraniční literatuře
INTERNAL
6
Úvod do operačního výzkumu
1. OV je aplikací vědeckých metod, technik a nástrojů na problémy zahrnující systémové operace, tak jako poskytnutí
kontroly operacím s optimálním řešením úloh.
2. OV je aplikací vědeckých metod pro studium rozsáhlých úloh, složitých organizací nebo aktivit.
3. OV je aplikací vědeckých metod při analýze a řešení rozhodování manažerských problémů.
▪ Shrnutí
▪ Aplikace VĚDĚCKÝCH METOD.
▪ Studuje ROZSÁHLÉ & SLOŽITÉ SYSTÉMY.
▪ Analyzuje MANAŽERSKÉ PROBLÉMY.
▪ Hledá OPTIMÁLNÍ ŘEŠENÍ.
▪ Používá MATEMATICKÉ MODELY.
▪ Používá SPECIÁLNÍ SOFTWARE.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Definice
INTERNAL
7
Úvod do operačního výzkumu
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Software
▪ MPL for Windows
▪ AMPL
▪ Lingo (LINDO)
▪ XPRESS (FICO)
▪ AIMMS
▪ CPLEX (IBM ILOG)
▪ Gurobi
▪ NEOS
▪ MS Excel (FRONTLINE SOLVERS)
▪ PLANT SIMULATION
▪ SIMPROCESS
▪ SIMUL 8
▪ Matlab
INTERNAL
8
Úvod do operačního výzkumu
▪ Dvě nebo více možností.
▪ Výsledek = rozhodnutí.
▪ Systematický proces.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Rozhodovací problém
▪ Definice
problému
▪ Hledání možných
řešení úlohy
▪ Zvolení jedné
možnosti
▪ Vyhodnocení
možností
Obr. 1 – Schéma procesu rozhodovacího problému
INTERNAL
9
Úvod do operačního výzkumu
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Matematické modelování (Rozhodovací problém)
▪ Reálný
systém
▪ Definice problému
▪ Formulace ekonomického
modelu
▪ Formulace
matematického modelu
▪ Řešení úlohy
▪ Interpretace výsledků
▪ Verifikace modelu
▪ Validace modelu
▪ Analýza citlivosti
▪ Implementace
Obr. 2 – Schéma matematického modelování
INTERNAL
10
Úvod do operačního výzkumu
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Modelový přístup
Realita Model
▪ Nalezení kompromisu mezi zjednodušením modelu a vhodnou
úrovní věrného zachycení reality.
Obr. 3 – Model jako zjednodušení reality
INTERNAL
11
Úvod do operačního výzkumu
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Klasifikace modelů
▪ Deterministické – všechna data jsou s jistotou známa.
▪ Pravděpodobnostní (stochastické) – některé procesy nebo hodnoty se
řídí zákony pravděpodobnostního charakteru.
▪ Statické – všechna data jsou známa předem (před
samotným výpočtem).
▪ Dynamický – data mohou být změněna i po získání řešení.
0
10
20
30
40
50
60
70
80
90
100
0 10 20 30 40 50 60 70 80 90 100
0
10
20
30
40
50
60
70
80
90
100
0 10 20 30 40 50 60 70 80 90 100
Obr. 4 – Statický a dynamický model
INTERNAL
Lineární programování
2
12
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
INTERNAL
13
Lineární programování
▪ Ekonomický model
▪ Procesy.
▪ Činitelé.
▪ Cíl.
▪ Matematický model
▪ Proměnné – spojité, celočíselné, binární.
▪ Omezující podmínky – rovnice, nerovnice.
▪ Účelová funkce – max, min.
▪ Řešení
▪ Přípustné – vyhovuje všem omezujícím podmínkám.
▪ Optimální – přípustné řešení s nejlepší hodnotou účelové funkce.
▪ Nepřípustné – nesplňuje některou z omezujících podmínek.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úvod
INTERNAL
14
Lineární programování
▪ Řešení
▪ Interpretace výsledků – vysvětlení získaných numerických výsledků (např. klientovi).
▪ Verifikace modelu – porovnání matematického modelu s ekonomickým modelem.
▪ Validace modelu – porovnání výsledků s reálnými očekáváními.
▪ Analýza citlivosti – zkoumání důsledků změn vstupů na výstupy.
▪ Implementace
▪ Použití výsledků v reálném systému.
▪ Speciální případy úloh LP
▪ Jediné optimální řešení.
▪ Více optimálních řešení.
▪ Žádné optimální řešení.
▪ Žádné přípustné řešení.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úvod
INTERNAL
15
Lineární programování
▪ Příklad
▪ Firma vyrábí dva typy dřevěných hraček: nákladní autíčka a vláčky.
▪ Cena autíčka je 820 Kč, vláčku 1150 Kč. Náklady na dřevo pro autíčko je 100 Kč, pro vláček 180 Kč.
▪ Na výrobu jednoho autíčka je potřeba 1 hodina řezbářské práce a 1 hodina dokončovacích prací. Na jeden vláček
2 hodiny řezbářské práce a 1 hodina dokončovacích prací.
▪ Cena řezbářské práce je 150 Kč/hod a dokončovacích prací 120 Kč/hod.
▪ Každý měsíc je k dispozici 5000 hod řezbářské práce a 3000 hodin dokončovacích prací.
▪ Výroba vláčků je neomezená, ale autíček je možné vyrobit maximálně 2000 za měsíc.
▪ Cílem je maximalizovat měsíční zisk (rozdíl tržeb a nákladů).
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úlohy výrobního plánování
INTERNAL
16
Lineární programování
▪ Proměnné
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úlohy výrobního plánování
▪ Matematický model
Přídatné proměnné
≤
≥
+ přídatná proměnná
- přídatná proměnná
Ekvivalentní soustava rovnic
(dokončovací práce)
(řezbářská práce)
(poptávka)
x1 = počet autíček vyrobených každý měsíc,
x2 = počet vláčků vyrobených každý měsíc.
50002 321 =++ xxx
3000421 =++ xxx
200051 =+ xx
1 2450 550 max,z x x= + →
1 22 5000,x x+ 
1 2 3000,x x+ 
1 2000,x 
1 2, 0,x x 
1 2, celéx x −
INTERNAL
17
Lineární programování
▪ Optimální řešení
▪ Proměnné
▪ Hodnota účelové funkce
▪ Přídatné proměnné
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úlohy výrobního plánování
𝑥1 = 1000
𝑥2 = 2000
𝑧0 = 1550000
𝑥3 = 0
𝑥4 = 0
𝑥5 = 1000
INTERNAL
18
Lineární programování
▪ Vstupy
▪ chemikálie,
▪ slitiny kovů,
▪ surová ropa,
▪ krmivo pro hospodářská zvířata,
▪ potraviny.
▪ Požadavky na výstupy a/nebo cíl
▪ kvalita,
▪ množství,
▪ náklady.
▪ Proměnné
▪ množství složek použitých v konečné směsi.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Směšovací problém
INTERNAL
19
Lineární programování
▪ Příklad
▪ Stanovte optimální složení krmivové směsi, která bude obsahovat alespoň 100 jednotek bílkovin a alespoň
300 jednotek škrobu a která bude vážit alespoň 200 kg s minimálními pořizovacími náklady.
▪ V následující tabulce jsou dány obsahy bílkovin a škrobu v 1 kg každého krmiva a jeho cena za 1 kg.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Směšovací problém
Krmivo K1 Krmivo K2 Krmivo K3 Krmivo K4
Bílkoviny (jednotky) 0 3 1 2
Škrob (jednotky) 1 2 3 0
Cena (Kč) 20 80 60 30
Tab. 1 – Obsahy bílkovin a škrobu ve směsích, ceny směsí
INTERNAL
20
Lineární programování
▪ Proměnné
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Směšovací problém
▪ Matematický model
𝑥i = množství krmiva Ki v konečné směsi (i = 1,2,3,4)
3𝑥2 + 𝑥3 + 2𝑥4 ≥ 100,
𝑥1 + 2𝑥2 + 3𝑥3 ≥ 300,
𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 ≥ 200,
𝑥𝑖 ≥ 0, 𝑖 = 1,2,3,4.
(bílkoviny)
(škrob)
(hmotnost)
𝑧 = 20𝑥1 + 80𝑥2 + 60𝑥3 + 30𝑥4Minimalizovat
za podmínek
INTERNAL
21
Lineární programování
▪ Optimální řešení
▪ Proměnné
▪ Hodnota účelové funkce
▪ Přídatné proměnné
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Směšovací problém
𝑥1 = 120
𝑥2 = 0
𝑥3 = 60
𝑥4 = 20
𝑧0 = 6600
𝑥5 = 0
𝑥6 = 0
𝑥7 = 0
INTERNAL
22
Lineární programování
▪ Vstupy – originální díly (rozměry)
▪ tyče, trubky (1D),
▪ role papíru nebo textilu (1D or 2D),
▪ dřevěné tyče nebo latě (1D),
▪ prkna (1D nebo 2D),
▪ ocelové pláty (2D),
▪ krabice (3D) – 3D řezná úloha.
▪ Výstupy – dokončené nebo rozpracované výrobky
▪ Cíle
▪ minimalizace odpadu,
▪ minimalizace počtu původních dílů použitých pro získání požadovaného množství nařezaných dílů,
▪ maximalizace tržeb či zisku z prodeje vyrobených výrobků.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Řezná úloha
INTERNAL
23
Lineární programování
▪ Tabulka řezných schémat
▪ Obsahuje všechny možnosti rozřezaní originálních dílů.
▪ Každé schéma odpovídá jedné proměnné představující počet originálních dílů, které byly rozřezány dle schématu.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Řezná úloha
Originální
díl
Finální
výrobky
Řezná schémata
Odpad
Obr. 5 – Řezná schémata
INTERNAL
24
Lineární programování
▪ Příklad
▪ Firma vyrábí ptačí krmítka a budky. Výrobce se rozhodl připravit speciální kolekci pro výstavu (s možností prodeje),
která se uskuteční za 20 dní.
▪ Cena krmítka je 260 Kč, cena budky je 570 Kč.
▪ Spotřeba materiálu a čas nezbytný k výrobě obou výrobků jsou uvedeny níže v tabulce 2.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Řezná úloha
Tab. 2 – Spotřeba materiálu a časové nároky na výrobu
Krmítko Budka
Prkna 30 cm 1 2
Prkna 25 cm 1 4
Vruty 8 16
Čas (v min) 30 60
INTERNAL
25
Lineární programování
▪ Příklad
▪ Firma má k dispozici 500 prken dlouhých 1,1 m a 150 prken o délce 1,4 m. Prkna se musí rozřezat na díly o délce
25 a 30 cm.
▪ K dispozici je 3000 vrutů.
▪ Výrobce pracuje 8 hodin denně. Cílem je naplánovat výrobu tak, aby celkové tržby z prodeje výrobků byly maximální.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Řezná úloha
Tab. 3 – Tabulka řezných schémat
Prkno o délce 1,1 m Prkno o délce 1,4 m
Číslo schématu 1 2 3 4 5 6 7 8 9
Prkno o délce 30 cm 3 2 1 0 4 3 2 1 0
Prkno o délce 25 cm 0 2 3 4 0 2 3 4 5
Odpad (cm) 20 0 5 10 20 0 5 10 15
INTERNAL
26
Lineární programování
▪ Proměnné
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Řezná úloha
▪ Matematický model
xi = počet prken dlouhých 1,1 m rozřezaných podle schématu i (i = 1,…,4),
xi = počet prken dlouhých 1,4 m rozřezaných podle schématu i (i = 5,…,9),
x10 = počet vyrobených krmítek,
x11 = počet vyrobených budek.
1110 570260 xxz +=
5004321 +++ xxxx
15098765 ++++ xxxxx
(prkna 1,1 m)
za podmínek
Maximalizovat
(prkna 1,4 m)
INTERNAL
27
Lineární programování
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Řezná úloha
▪ Matematický model
3000168 1110 + xx
10 110,5 160x x+ 
11108765321 223423 xxxxxxxxx +++++++
11109876432 45432432 xxxxxxxxx +++++++
(vruty)
(čas)
(prkna 30 cm)
(prkna 25 cm)
0...,,, 1121 xxx
1121 ...,,, xxx – celé
INTERNAL
28
Lineární programování
▪ Optimální řešení
▪ Proměnné
▪ Hodnota účelové funkce
▪ Přídatné proměnné
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Řezná úloha
x1 = x3 = x4 = x6 = x7 = x8 = x10 = 0
x2 = 65
x5 = 48
x9 = 102
x11 = 160
𝑧0 = 91200
𝑦1 = 435
𝑦2 = 0
𝑦3 = 440
𝑦4 = 0
𝑦5 = 2
𝑦6 = 0
▪ Tyto hodnoty mohou být odlišné, protože
existuje více optimálních řešení.
INTERNAL
29
Lineární programování
▪ Zadání úlohy
▪ Úloha finančního plánování.
▪ Rozdělení disponibilní částky mezi několik investičních alternativ.
▪ Finanční riziko.
▪ Cílem investování do cenných papírů je získání určité částky peněz (výnos).
▪ Cílem je maximalizovat celkový očekávaný výnos a minimalizovat celkové riziko spojené s investicí.
▪ Alternativní investice
▪ Akcie, obligace atd.
▪ Rozhodovací subjekty
▪ Podílový fond, banka, penzijní fond, pojišťovna, individuální investor.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Optimalizace portfolia
INTERNAL
30
Lineární programování
▪ Příklad
▪ Vedení investiční společnosti zvažuje investici do akcií 4 firem produkujících nápoje.
▪ Aby společnost předešla ztrátám plynoucím z rizika spojeného s investováním do soukromého sektoru, rozhodlo se
vedení společnosti část peněz investovat do vládních obligací.
▪ Celková investovaná částka činí 2 mil. Kč. Z dlouhodobého sledování finančního trhu vyplývají roční procenta
očekávaného výnosu a indexy rizika u sledovaných cenných papírů, uvedené v tabulce 4.
Optimalizace portfolia
Tab. 4 – Investiční soubor
Cenný papír Výnos Riziko
České pivovary a.s. 12 % 0,07
Víno Morava a.s. 9 % 0,09
Moravská švestka a.s. 15 % 0,05
České mlékárny a.s. 7 % 0,03
Vládní obligace 6 % 0,01
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
INTERNAL
31
Lineární programování
▪ Příklad
▪ Na poradě managementu společnosti bylo rozhodnuto o následujících pravidlech:
1) Do akcií Českých mlékáren, a.s. se nesmí investovat více než 200 tis. Kč.
2) Investice do vládních obligací musí činit alespoň 20 % všech investic.
3) Z hlediska diverzifikace portfolia se do akcií žádné z firem vyrábějících alkoholické nápoje nesmí investovat
více než 800 tis. Kč.
4) Celkový index rizika portfolia nesmí přesáhnout hodnotu 0,05.
▪ Cílem společnosti je maximalizovat očekávaný roční výnos portfolia při dodržení všech uvedených podmínek.
Optimalizace portfolia
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
INTERNAL
32
Lineární programování
▪ Proměnné
𝑥𝑖 = finanční částka investovaná do 𝑖– tého titulu cenného papíru (𝑖 = 1, 2, … , 5).
▪ Matematický model
▪ Maximalizovat 𝑧 = 0,12𝑥1 + 0,09𝑥2 + 0,15𝑥3 + 0,07𝑥4 + 0,06𝑥5
za podmínek
𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 + 𝑥5 = 2000, (2 mil. Kč)
𝑥4 ≤ 200, (do akcií Českých mlékáren a.s. se nesmí investovat více než 200 tis. Kč)
𝑥5 ≥ 400, (alespoň 20 % výše všech investic musí být do vládních obligací)
𝑥1 ≤ 800; 𝑥2 ≤ 800; 𝑥3 ≤ 800, (nesmí být investováno více než 800 tis. Kč do firem vyrábějících
alkoholické nápoje)
0,07𝑥1+0,09𝑥2+0,05𝑥3+0,03𝑥4+0,01𝑥5
2 000
≤ 0,05, (celkový index rizika portfolia nesmí přesáhnout 0,05)
0,07𝑥1 + 0,09𝑥2 + 0,05𝑥3 + 0,03𝑥4 + 0,01𝑥5 ≤ 100,
𝑥𝑖 ≥ 0, 𝑖 = 1,2, … , 5. (podmínky nezápornosti)
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Optimalizace portfolia
INTERNAL
33
Lineární programování
▪ Optimální řešení
▪ Proměnné
𝑥1 = 800,
𝑥2 = 0,
𝑥3 = 800,
𝑥4 = 0,
𝑥5 = 400.
▪ Hodnota účelové funkce
𝑧0 = 240.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Optimalizace portfolia
INTERNAL
34
Lineární programování
▪ Zadání úlohy
▪ Přeprava homogenního produktu.
▪ Množina dodavatelů s omezenou kapacitou.
▪ Množina odběratelů s poptávkou (požadavkem).
▪ Jednotkové přepravní náklady pro všechny dvojice dodavatelů a odběratelů.
▪ Cílem je uspokojit požadavky všech odběratelů při minimálních celkových přepravních nákladech, přičemž nesmí být
překročena kapacita žádného z dodavatelů.
▪ Typy dopravních problémů
▪ Vyrovnaný – celková kapacita je rovna celkovému požadavku.
▪ Nevyrovnaný – celková kapacita se liší od celkového požadavku. Existuje možnost převést problém na vyrovnaný:
▪ přidáním fiktivního odběratele,
▪ nalezením dodatečného dodavatele nebo přidáním fiktivního dodavatele (s možností neuspokojení
požadavku).
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Dopravní problém
INTERNAL
35
Lineární programování
▪ Příklad
▪ Firma vyrábějící bramborové lupínky zřizuje tři nové pobočky v Benešově, Jihlavě a Táboře.
▪ Hlavní surovinou jsou brambory, které se budou dovážet ze skladů v Humpolci a Pelhřimově.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Dopravní problém
Benešov
Humpolec
Jihlava
Pelhřimov
Tábor
Obr. 6 – Přeprava ze skladů do poboček
INTERNAL
36
Lineární programování
▪ Příklad
▪ V tabulce 5 jsou uvedeny týdenní kapacity skladů a plánované týdenní požadavky výroben (v tunách). Přeprava
brambor se bude uskutečňovat po železnici (jednou týdně). Tabulka 5 obsahuje jednotkové náklady na přepravu
jedné tuny brambor od dodavatelů k odběratelům.
▪ Cílem je naplánovat přepravu brambor tak, aby celkové přepravní náklady byly minimální. Plán musí splňovat
požadavky každé pobočky a nesmí překročit kapacity žádného ze skladů.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Dopravní problém
Tab. 5 – Dodávky, požadavky a jednotkové náklady na přepravu
Benešov Jihlava Tábor Kapacita
Humpolec 330 250 350 70
Pelhřimov 300 240 250 80
Požadavek 45 60 35
INTERNAL
37
Lineární programování
▪ Přípustné řešení (metoda severozápadního rohu)
1. Do severozápadního rohu (levého horního políčka) tabulky dosadíme maximální možné množství.
2. Upravíme kapacitu a požadavek tak, že vypočtený objem přepravy odečteme od příslušné kapacity a požadavku.
3. Pokud je požadavek pro první buňku uspokojen, přesuneme se horizontálně na další buňku ve druhém sloupci.
4. Pokud je kapacita pro první řádek vyčerpána, posuneme se na první buňku druhého řádku.
5. Pokud je v jakékoli buňce kapacita rovna požadavku, přesuneme se na další možné místo v následujícím řádku
nebo sloupci.
6. Pokračujeme až do vyplnění celé tabulky.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Dopravní problém
Benešov Jihlava Tábor Kapacita
Humpolec 45 25 - 70
Pelhřimov - 35 35 80
Požadavek 45 60 35
Tab. 6 – Přípustné řešení DP získané metodou severozápadního rohu
▪ Hodnota účelové funkce
𝑧 = 38250
INTERNAL
38
Lineární programování
▪ Přípustné řešení (metoda maticového minima)
1. Vybíráme vždy políčko s minimálními náklady ze všech dosud neobsazených políček.
2. V prvním kroku přiřadíme přepravu dvojici s minimálními jednotkovými přepravními náklady. Hodnota přepravy je
rovna minimu zbývající kapacity a zbývajícího požadavku pro tuto dvojici.
3. V dalším kroku snížíme zbývající kapacitu a zbývající požadavek (pro dvojici dodavatele a odběratele)
o vypočítanou hodnotu přepravy.
4. Přípustné řešení je nalezeno, jsou-li uspokojeny všechny požadavky, pokud ne, pokračujeme od prvního kroku.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Dopravní problém
Benešov Jihlava Tábor Kapacita
Humpolec 45 - 15 70
Pelhřimov - 60 20 80
Požadavek 45 60 35
Tab. 7 – Přípustné řešení DP získané metodou maticového minima
𝑧 = 39500
▪ Hodnota účelové funkce
INTERNAL
39
Lineární programování
▪ Proměnné
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Dopravní problém
▪ Matematický model
xij = objem týdenní přepravy brambor (v tunách) od i – tého dodavatele k j – tému odběrateli (i = 1,2; j=1,2,3).
Minimalizovat
(Humpolec)
min250240300350250330 232221131211 →+++++= xxxxxxz
70131211 ++ xxx
80232221 ++ xxx
452111 =+ xx
602212 =+ xx
352313 =+ xx
za podmínek
0ijx i = 1,2; j=1,2,3
(Pelhřimov)
(Benešov)
(Jihlava)
(Tábor)
INTERNAL
40
Lineární programování
▪ Obecný matematický model
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Dopravní problém
1 1
min
m n
ij ij
i j
z c x
= =
= →
1
, 1,2,...,
n
ij i
j
x a i m
=
 =
1
, 1,2,...,
m
ij j
i
x b j n
=
= =
0, 1,2,..., ; 1,2,...,ijx i m j n = =
INTERNAL
41
Lineární programování
▪ Optimální řešení
▪ Proměnné
▪ Hodnota účelové funkce
▪ Přídatné proměnné
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Dopravní problém
Benešov Jihlava Tábor Kapacita
Humpolec - 60 - 70
Pelhřimov 45 - 35 80
Požadavek 45 60 35
Tab. 8 – Optimální řešení
𝑧0 = 37250
𝑦1 = 10
𝑦2 = 0
INTERNAL
42
Lineární programování
▪ Vychází z dopravního problému.
▪ K přepravě jsou využívány kontejnery stejné kapacity.
▪ Přepravní náklady nejsou vztaženy na přepravovanou jednotku, ale na přepravu jednoho kontejneru mezi dodavatelem
a odběratelem.
▪ Cílem je určit objem přepravy mezi dodavatelem a odběratelem a počet kontejnerů použitých k přepravě.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Kontejnerový dopravní problém
INTERNAL
43
Lineární programování
▪ Příklad
▪ Předpokládejme, že si v předešlém příkladu bude přepravní společnost účtovat ceny za přepravu (pronájem)
jednoho vagónu mezi jednotlivými dodavateli a odběrateli.
▪ K přepravě lze použít vagóny o kapacitě 18 tun.
▪ Cílem je jednak určit, kolik tun brambor se bude přepravovat mezi jednotlivými místy, ale také stanovit, kolik vagónů
bude na tuto přepravu použito, aby i v tomto případě byly celkové přepravní náklady minimální.
Kontejnerový dopravní problém
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Tab. 9 – Zadání kontejnerového dopravního problému
Benešov Jihlava Tábor Kapacita
Humpolec 4200 4800 5300 70
Pelhřimov 5100 3400 3700 80
Požadavek 45 60 35
INTERNAL
44
Lineární programování
▪ Matematický model vychází z matematického modelu dopravního problému.
▪ Proměnné
𝑥𝑖𝑗 = objem přepravy (v tunách) od 𝑖 – tého dodavatele k 𝑗 – tému odběrateli.
𝑦𝑖𝑗 = počet kontejnerů, které budou použity k přepravě od 𝑖 – tého dodavatele k 𝑗 – tému odběrateli.
▪ Účelová funkce
▪ Omezující podmínky
▪ K podmínkám v dopravním problému je nutné přidat následující omezující podmínky:
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Kontejnerový dopravní problém
1 1
min
m n
ij ij
i j
z c y
= =
= →
, 1,2,..., ; 1,2,...,ij ijx Ky i m j n = =
0, celé, 1,2,..., ; 1,2,...,ijy i m j n = =
INTERNAL
45
Lineární programování
▪ Optimální řešení
Kontejnerový dopravní problém
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Tab. 10 – Objem přepravy
Benešov Jihlava Tábor
Humpolec 45 18 Pelhřimov
- 42 35
Tab. 11 – Počty vagónů
Benešov Jihlava Tábor
Humpolec 3 1 Pelhřimov
- 3 2
INTERNAL
46
Lineární programování
▪ Zadání úlohy
▪ Dvě množiny prvků.
▪ Každému prvku z první množiny je přiřazen právě jeden prvek z druhé množiny.
▪ Každému prvku z druhé množiny je přiřazen právě jeden prvek z první množiny.
▪ Přiřazení každého páru je ohodnoceno.
▪ Cílem je maximalizovat/minimalizovat celkové ohodnocení přiřazených prvků.
▪ Předpokladem je stejný počet prvků v obou množinách (vyrovnaný problém).
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Přiřazovací problém
INTERNAL
47
Lineární programování
▪ Příklad
▪ Stavební firma má za úkol vyhloubit základy na čtyřech parcelách v pražských čtvrtích (Michle, Prosek, Radlice,
Troja).
▪ Výkopové práce budou provedeny bagry, nacházejícími se ve čtyřech různých garážích. Vzdálenosti (v km) mezi
garážemi a parcelami jsou uvedeny v tabulce 12.
▪ Cílem je minimalizovat celkovou vzdálenost, nutnou pro přepravu bagrů na staveniště. Předpokladem je, že
výkopové práce na všech parcelách budou probíhat současně, tj. na každé parcele bude pracovat právě jeden bagr.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Přiřazovací problém
Tab. 12 – Vzdálenosti mezi garážemi a stavebními parcelami
Michle Prosek Radlice Troja
Garáž 1 5 22 12 18
Garáž 2 15 17 6 10
Garáž 3 8 25 5 20
Garáž 4 10 12 19 12
INTERNAL
48
Lineární programování
▪ Proměnné
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Přiřazovací problém
xij =
1 Jestliže bagr z garáže 𝑖 bude pracovat na staveništi 𝑗,
0 jinak,
𝑖 = 1,2,3,4,
𝑗 = 1,2,3,4.
INTERNAL
49
Lineární programování
▪ Matematický model
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Přiřazovací problém
1
1
1
1
44434241
34333231
24232221
14131211
=+++
=+++
=+++
=+++
xxxx
xxxx
xxxx
xxxx
1
1
1
1
44342414
43332313
42322212
41312111
=+++
=+++
=+++
=+++
xxxx
xxxx
xxxx
xxxx
Minimalizovat 441211 12...225 xxxz +++=
(Garáž 1)
(Garáž 2)
(Garáž 3)
(Garáž 4)
(Michle)
(Prosek)
(Radlice)
(Troja)
za podmínek
INTERNAL
50
Lineární programování
▪ Optimální řešení
▪ Proměnné
▪ Hodnota účelové funkce
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Přiřazovací problém
Tab. 13 – Optimální přiřazení bagrů
Michle Prosek Radlice Troja
Garáž 1 1 0 0 0
Garáž 2 0 0 0 1
Garáž 3 0 0 1 0
Garáž 4 0 1 0 0
𝑧0 = 32
INTERNAL
51
Lineární programování
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Přiřazovací problém
min
1 1
→= 
= =
n
i
n
j
ijij xcz
nix
n
j
ij ,...,2,1,1
1
==
=
njx
n
i
ij ,...,2,1,1
1
==
=
  njnixij ,...,2,1;,...,2,1,1,0 ==
▪ Vyrovnaný problém
njx
n
i
ij ,...,2,1,1
1
==
=
▪ Nevyrovnaný problém (m > n)
min
1 1
→= 
= =
m
i
n
j
ijij xcz
miax i
n
j
ij ,...,2,1,
1
=
=
  njnixij ,...,2,1;,...,2,1,1,0 ==
nebo použitím (m – n) fiktivních prvků
INTERNAL
52
Lineární programování
▪ V úloze o pokrytí je definovaná množina prvků (projekty, práce, procesy, aktivity atd.), které musí být pokryty několika
možnými alternativami (firmy, zaměstnanci, manažeři atd.).
▪ Alternativy jsou většinou vybrány podle nákladů.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úloha o pokrytí
INTERNAL
53
Lineární programování
▪ Příklad
▪ Ve dvou z šesti městských obvodů je nutné zřídit stanice rychlé záchranné služby, které pokryjí všechny obvody.
▪ V tabulce 14 jsou zadány průměrné dojezdové časy (v min) ze stanice, která bude zřízena v daném obvodě (na
předem určeném místě), k případům v jednotlivých obvodech.
▪ V posledním řádku tabulky jsou uvedeny průměrné denní četnosti zásahů v jednotlivých obvodech.
▪ Cílem je navrhnout, kde zřídit stanice a přiřadit k těmto stanicím obvody, které budou obsluhovat, aby průměrná
denní doba zásahů byla minimální.
Úloha o pokrytí
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Tab. 14 – Zadání úlohy o pokrytí
O1 O2 O3 O4 O5 O6
O1 4 12 14 17 11 9
O2 20 7 10 19 24 16
O3 21 13 5 8 11 15
O4 9 12 14 3 8 18
O5 17 25 13 10 6 16
O6 13 8 9 15 10 5
četnosti 30 50 42 36 24 28
INTERNAL
54
Lineární programování
▪ Proměnné
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úloha o pokrytí
INTERNAL
55
Lineární programování
▪ Účelová funkce
▪ Omezující podmínky
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úloha o pokrytí
1 1
min
n n
j ij ij
i j
z f c x
= =
= →
1
( 1) , 1,2,...,
n
ij i
j
x n K y i n
=
 − + =
1
1, 1,2,...,
n
ij
i
x j n
=
= =
1
n
i
i
y K
=
=
Každý odvod bude obsluhován právě jednou stanicí.
Zřízení přesně 𝐾 stanic.
Souvislost mezi zřízením stanice v obvodě a obsluhou obvodů touto stanicí.
INTERNAL
56
Lineární programování
▪ Optimální řešení
Úloha o pokrytí
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Tab. 15 – Optimální řešení úlohy o pokrytí
O1 O2 O3 O4 O5 O6
O1 0 0 0 0 0 0
O2 0 0 0 0 0 0
O3 0 0 0 0 0 0
O4 1 0 0 1 1 0
O5 0 0 0 0 0 0
O6 0 1 1 0 0 1
První stanice bude zřízena v obvodě O4 a bude obsluhovat (kromě sebe sama) obvody O1 a O5. Druhá stanice bude
zřízena v obvodu O6 a bude obsluhovat (opět kromě sebe sama) obvody O2 a O3.
INTERNAL
57
Lineární programování
▪ Zadání úlohy
▪ Zadána množina míst.
▪ Každé místo musí být navštíveno právě jednou.
▪ Výsledná trasa tvoří okruh (cyklus) se začátkem a koncem ve výchozím místě (index 1).
▪ Cílem je minimalizovat celkovou délku trasy, celkový čas nebo celkové náklady.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úloha obchodního cestujícího
INTERNAL
58
Lineární programování
▪ Příklad
▪ Obchodní zástupce pivovaru ve Velvarech musí navštívit 7 restaurací v 7 obcích.
▪ V tabulce 16 jsou uvedeny vzdálenosti (v km) odpovídající přímým spojením obcí (silnicemi). Pomlčka odpovídá
situaci, kdy obce nejsou přímo spojeny silnicí.
▪ Cílem je navštívit všechny restaurace a ujet přitom minimální vzdálenost.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úloha obchodního cestujícího
Tab. 16 – Přímá spojení obcí
Obec Velv Kra Lib Sla Zlo Vra Bri Velt
Velvary 0 8 - 13 10 - 12 9
Kralupy 8 0 6 16 - - - 4
Libcice - 6 0 - - - - Slany
13 16 - 0 7 - - Zlonice
10 - - 7 0 7 13 Vrany
- - - - 7 0 15 Briza
12 - - - 13 15 0 13
Veltrusy 9 4 - - - - 13 0
INTERNAL
59
Lineární programování
▪ Příklad
▪ Tabulka 17 obsahuje matici vzdáleností mezi dvojicemi míst.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úloha obchodního cestujícího
Tab. 17 – Matice vzdáleností mezi místy
Obec Velv Kra Lib Sla Zlo Vra Bri Velt
Velvary 0 8 14 13 10 17 12 9
Kralupy 8 0 6 16 18 25 17 4
Libcice 14 6 0 22 24 31 23 10
Slany 13 16 22 0 7 14 20 20
Zlonice 10 18 24 7 0 7 13 19
Vrany 17 25 31 14 7 0 15 26
Briza 12 17 23 20 13 15 0 13
Veltrusy 9 4 10 20 19 26 13 0
INTERNAL
60
Lineární programování
▪ Přípustné řešení (metoda nejbližšího souseda)
1. Vybereme jakékoli místo jako výchozí.
2. Najdeme nejbližší místo (z těch, která nebyla dosud zařazena do okruhu) k poslednímu místu na trase a zařadíme
jej do trasy. Pokud takové místo neexistuje, pak uzavřeme trasu zařazením výchozího místa na její konec
a pokračujeme krokem 4.
3. Pokračujeme krokem 2.
4. Konec.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úloha obchodního cestujícího
Tab. 18 – Přípustné řešení TSP získané metodou nejbližšího souseda
Obec Velv Kra Lib Sla Zlo Vra Bri Velt
Velvary 0 8 14 13 10 17 12 9
Kralupy 8 0 6 16 18 25 17 4
Libcice 14 6 0 22 24 31 23 10
Slany 13 16 22 0 7 14 20 20
Zlonice 10 18 24 7 0 7 13 19
Vrany 17 25 31 14 7 0 15 26
Briza 12 17 23 20 13 15 0 13
Veltrusy 9 4 10 20 19 26 13 0
▪ Hodnota účelové funkce
𝑧 = 85
INTERNAL
61
Lineární programování
▪ Proměnné
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úloha obchodního cestujícího
1 jestliže vozidlo jede přímo z místa
do místa , 1,2,..., ,
1,2,..., ,
0 jinak,
ij
i
j i n
x
j n

 =
= 
=

𝑢𝑖 = umělá proměnná v omezujících podmínkách zabraňujících vytváření parciálních cyklů.
INTERNAL
62
Lineární programování
▪ Matematický model
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úloha obchodního cestujícího
1 1
min
n n
ij ij
i j
z c x
= =
= →
1
1, 1,2,...,
n
ij
j
x i n
=
= =
1
1, 1,2,...,
n
ij
i
x j n
=
= =
1 ( 1)(1 ) , 1,2,..., ; 2,3,...,i ij ju n x u i n j n+ − − −  = =
 0,1 , 1,2,..., ; 1,2,...,ijx i n j n = =
0, 1,2,...,iu i n =
INTERNAL
63
Lineární programování
▪ Optimální řešení
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úloha obchodního cestujícího
Tab. 19 – Optimální řešení
▪ Hodnota účelové funkce
𝑧0 = 79
Obec Velv Kra Lib Sla Zlo Vra Bri Velt
Velvary 0 8 14 13 10 17 12 9
Kralupy 8 0 6 16 18 25 17 4
Libcice 14 6 0 22 24 31 23 10
Slany 13 16 22 0 7 14 20 20
Zlonice 10 18 24 7 0 7 13 19
Vrany 17 25 31 14 7 0 15 26
Briza 12 17 23 20 13 15 0 13
Veltrusy 9 4 10 20 19 26 13 0
INTERNAL
Teorie grafů
3
64
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
INTERNAL
65
Teorie grafů
▪ Sedm königsbergských mostů
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úvod
Obr. 7 – Reálná situace
B
A
C
D
D
Obr. 8 – Model v podobě grafu
INTERNAL
66
Teorie grafů
▪ Základní pojmy
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úvod
INTERNAL
67
Teorie grafů
▪ Základní pojmy
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úvod
INTERNAL
68
Teorie grafů
▪ Základní pojmy
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úvod
INTERNAL
69
Teorie grafů
▪ Základní pojmy
▪ Souvislý a nesouvislý graf
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úvod
Obr. 9 – Souvislý graf Obr. 10 – Nesouvislý graf
INTERNAL
70
Teorie grafů
▪ Základní pojmy
▪ Cyklus (okruh)
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úvod
Obr. 11 – Cyklus
INTERNAL
71
Teorie grafů
▪ Základní pojmy
▪ Strom a kostra
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úvod
Obr. 12 – Stromy Obr. 13 – Kostra grafu
INTERNAL
72
Teorie grafů
▪ Cílem je najít nejkratší cestu mezi dvojicí uzlů.
▪ Úloha řešená na každodenní bázi při používání navigace v autě či hledání spojení na některém mapovém portálu.
▪ Existuje mnoho algoritmů, s jejichž pomocí lze snadno najít všechny vzdálenosti mezi všemi dvojicemi uzlů v zadaném
grafu.
▪ Dijkstrův algoritmus je určen pro hledání nejkratších cest z jednoho konkrétního uzlu do všech ostatních uzlů v grafu.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Hledání nejkratší cesty
INTERNAL
73
Teorie grafů
▪ Příklad
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Hledání nejkratší cesty
1
3
2
5
7
8
8
7
10
12
9
17
13
11
6
16
4
6
11
4
15
7
14
Obr. 14 – Distribuční síť pro přepravu nadměrného nákladu
INTERNAL
74
Teorie grafů
▪ V prvním kroku algoritmu sestavíme tabulku 20. V prvním řádku je seznam všech uzlů. Druhý řádek je určený pro
vypočítané vzdálenosti odpovídající nejkratším cestám z uzlu 1 k ostatním uzlům. Vzdálenost z uzlu 1 do uzlu
𝑖 označíme 𝑡𝑖. V poslední části tabulky je pro každý uzel 𝑖 uvedený seznam uzlů 𝑗, do kterých z něj vede hrana.
V závorce je uvedena délka této hrany, obecně 𝑦𝑖𝑗.
▪ V dalších krocích se budeme zabývat jen sloupci, v nichž je již hodnota 𝑡𝑖 vypočtena. Hledáme vždy nejkratší cesty
právě z těchto uzlů do uzlů 𝑗, jejichž hodnota 𝑡𝑗 doposud určena není, a to přes hrany uvedené v seznamu.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Hledání nejkratší cesty
i 1 2 3 4 5 6 7 8
ti 0
( )ijj y
2(8) 3(10) 2(10) 6(15) 2(12) 4(15) 2(16) 3(17)
4(7) 7(16) 4(4) 3(9) 8(7) 5(11) 5(13)
5(9) 7(11) 8(6) 6(7)
6(14) 7(6)
8(17)
Tab. 20 – Vstupní data pro výpočet nejkratší cesty
INTERNAL
75
Teorie grafů
▪ Ve druhém kroku se tedy budeme zabývat pouze prvním sloupcem a uzly 2 a 4.
▪ Z uzlu 1 vedou dvě přímé cesty, a to do uzlu 2, která má délku (0+8), a do uzlu 4 o délce (0+7). Vybereme minimum
z těchto dvou hodnot, tedy 7 a tuto hodnotu zapíšeme k příslušnému uzlu, tedy k uzlu 4. Platí tedy 𝑡4 = 7. Orámujeme
vybranou hranu a odstraníme všechny hrany, které vedou do uzlu 4.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Hledání nejkratší cesty
i 1 2 3 4 5 6 7 8
ti 0 7
( )ijj y
2(8) 3(10) 2(10) 6(15) 2(12) 4(15) 2(16) 3(17)
4(7) 7(16) 4(4) 3(9) 8(7) 5(11) 5(13)
5(9) 7(11) 8(6) 6(7)
6(14) 7(6)
8(17)
Tab. 21 – Výpočet nejkratší cesty do uzlu 4
INTERNAL
76
Teorie grafů
▪ Ve třetím kroku, jehož základem je tabulka 21, hledáme minimum ze dvou hodnot (0+8) a (7+15). V dalším kroku
hledáme min(8+10, 8+16, 7+15) = 8+10 = 18.
▪ Pokračujeme do té doby, dokud nejsou známé všechny hodnoty 𝑡𝑖.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Hledání nejkratší cesty
i 1 2 3 4 5 6 7 8
ti 0 8 7
( )ijj y
2(8) 3(10) 2(10) 6(15) 2(12) 4(15) 2(16) 3(17)
4(7) 7(16) 4(4) 3(9) 8(7) 5(11) 5(13)
5(9) 7(11) 8(6) 6(7)
6(14) 7(6)
8(17)
Tab. 22 – Výpočet nejkratší cesty do uzlu 2
INTERNAL
i 1 2 3 4 5 6 7 8
ti 0 8 18 7 27 22 24 29
( )ijj y
2(8) 3(10) 2(10) 6(15) 2(12) 4(15) 2(16) 3(17)
4(7) 7(16) 4(4) 3(9) 8(7) 5(11) 5(13)
5(9) 7(11) 8(6) 6(7)
6(14) 7(6)
8(17)
77
Teorie grafů
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Hledání nejkratší cesty
Tab. 23 – Řešení hledání nejkratší cesty
INTERNAL
78
Teorie grafů
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Hledání nejkratší cesty
1
3
2
5
7
8
8
7
10
9
16
4
6
15
7
Obr. 15 – Nejkratší cesty z uzlu 1 do všech ostatních uzlů
INTERNAL
79
Teorie grafů
▪ Zadání úlohy
▪ Graf s 𝑛 uzly a množinou ohodnocených hran.
▪ Cílem je nalézt kostru grafu s celkovou minimální hodnotou přiřazenou ke zvoleným hranám.
▪ Optimalizační metoda
1. Setřídíme hrany vzestupně podle jejich ohodnocení.
2. Vybereme dvě hrany s minimálním ohodnocením a zařadíme je do množiny 𝐾.
3. Ze seznamu hran vybereme další hranu. Pokud hrana tvoří cyklus s některými hranami z množiny 𝐾,
musíme ji vyloučit ze seznamu hran.
4. Opakujeme krok 3, dokud množina 𝐾 nebude obsahovat 𝑛 − 1 hran.
5. Minimální kostra grafu je určena množinou 𝐾.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Optimální spojení míst
INTERNAL
80
Teorie grafů
▪ Příklad
▪ Manažer zajišťující výstavu softwarových produktů musí zabezpečit dodávku elektrické energie ze zdroje do 9 míst.
▪ Cílem je stanovit minimální celkové náklady na pořízení kabelu a určit, kudy spojovací kabely povedou.
▪ Vzdálenosti (v metrech) mezi místy jsou vyjádřeny v grafu na obr. 16.
▪ Místo 1 je zdrojem elektrické energie.
▪ Cena kabelu za metr je 10 Kč.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Optimální spojení míst
Obr. 16 – Výstaviště
1
3
2
5
7
8
88
60
90
76
40
80
55
63
70
85
4
9
10
6
75
52
71
74
61
68
43
120
35
54
Zdroj
INTERNAL
81
Teorie grafů
▪ Optimální řešení
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Optimální spojení míst
Obr. 17 – Rozmístění kabelů
▪ Minimální hodnota kostry
𝑧0 = 4901
3
2
5
7
8
88
60
90
76
40
80
55
63
70
85
4
9
10
6
75
52
71
74
61
68
43
120
35
54
Zdroj
INTERNAL
82
Teorie grafů
▪ Spojení
▪ Optimální spojení míst.
▪ Minimální Steinerův strom.
▪ Cesty a trasy
▪ Hledání nejkratší cesty.
▪ Úloha obchodního cestujícího.
▪ Rozvozní úloha.
▪ Problém vyzvednutí a doručení.
▪ Úloha čínského listonoše.
▪ Toky
▪ Hledání maximálního toku.
▪ Hledání toku s minimálními náklady.
▪ Transshipment problém.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Další optimalizační úlohy
INTERNAL
Řízení projektů
4
83
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
INTERNAL
84
Řízení projektů
▪ Projekt
▪ Soubor navazujících činností (aktivit).
▪ Činnosti:
▪ doba trvání,
▪ náklady na realizaci činnosti,
▪ požadavky na zdroje
▪ seznam bezprostředně předchozích činností.
▪ Doba trvání
▪ deterministická (předem známá konstanta) – Critical Path Method (CPM), Metra Potential Method (MPM)
▪ stochastická (hodnota náhodné veličiny) – Program Evaluation and Review Technique (PERT)
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úvod
INTERNAL
85
Řízení projektů
▪ Síťový graf
▪ Grafické znázornění projektu.
▪ Činnosti jsou znázorněny
▪ hranami (CPM),
▪ uzly (MPM).
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úvod
Obr. 18 – Činnosti znázorněné hranami Obr. 19 – Činnosti znázorněné uzly
Činnost 2
Činnost 1
Činnost 4
Činnost 3
Činnost 5
Činnost 7
Činnost 6
Činnost 2
INTERNAL
86
Řízení projektů
▪ Fáze projektu
▪ Plánování
▪ definování všech činností, doby trvání a bezprostředně předchozích činností,
▪ konstrukce síťového grafu znázorňujícího projekt.
▪ Analýza
▪ čas dokončení projektu,
▪ začátek a konec každé činnosti,
▪ kritická cesta obsahující úzká místa,
▪ nekritické činnosti a jejich možné zpoždění,
▪ Ganttův diagram.
▪ Realizace a kontrola
▪ porovnání skutečnosti s navrhovaným plánem,
▪ provedení změn v plánu.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Metoda kritické cesty CPM
INTERNAL
87
Řízení projektů
▪ Příklad
▪ Projektový manažer direktmarketingové firmy připravuje pro zákazníky vydání kolekce českých vánočních koled.
▪ Kampaň má být naplánována tak, aby všichni vybraní zákazníci obdrželi nabídku do předem určeného termínu.
▪ Projekt, týkající se hudební kampaně, je tvořen následujícími 11 činnostmi (viz Tabulka 24).
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Metoda kritické cesty CPM
INTERNAL
88
Řízení projektů
▪ Příklad
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Metoda kritické cesty CPM
Tab. 24 – Aktivity direktmarketingového projektu
Činnost Popis činnosti Doba trvání
Bezprostředně
předchozí činnosti
A Výběr skladeb 15 B
Mastering 8 A
C Zpracování promotion materiálů 6 A
D Analýza zákazníků 7 A
E Výroba promotion materiálů 4 C, D
F Doprava promotion materiálů 5 E
G Výběr zákazníků 3 D
H Výroba produktů 12 B, D
I Zpracování dat o zákaznících 3 G
J Kompletace 9 F, I
K Obeslání 8 H, J
INTERNAL
89
Řízení projektů
▪ Konstrukce síťového grafu
▪ Jeden vstupní uzel na a jeden výstupní uzel.
▪ Každá činnost musí být znázorněna právě jednou hranou.
▪ Dva uzly jsou spojeny maximálně jednou hranou.
▪ Uzel, znázorňující dokončenou činnost má vyšší číslo než uzel znázorňující začátek této činnosti – pravidlo
zamezuje mj. tvoření okruhů v síťovém grafu.
▪ Fiktivní činnosti (hrany) zajišťují správné návaznosti mezi reálnými činnostmi. Jejich doba trvání je nulová.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Metoda kritické cesty CPM
INTERNAL
90
Řízení projektů
▪ Sestrojení síťového grafu
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Metoda kritické cesty CPM
Obr. 20 – Síťový graf projektu
▪ X1, X2 – fiktivní hrany
INTERNAL
91
Řízení projektů
▪ Výpočet termínů nejdříve možných začátků činností
▪ Pro každý uzel jsou v jeho levé dolní části vypočítány termíny nejdříve možných začátků činností, které v tomto
uzlu začínají.
▪ Výpočet probíhá vzestupně dle čísel jednotlivých uzlů od začátku do konce projektu.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Metoda kritické cesty CPM
Obr. 21 – Termín nejdříve možného začátku činností
max( )j i ij
i
z z t= + j = 2, 3, …, n
T = zn
▪ Termín nejdříve možného dokončení projektu je
termín nejdříve možného dokončení poslední
činnosti:
j
jz
INTERNAL
92
Řízení projektů
▪ Výpočet termínů nejdříve možných začátků činností
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Metoda kritické cesty CPM
Obr. 22 – Výpočet termínů nejdříve možných začátků činností
T = 48
INTERNAL
93
Řízení projektů
▪ Výpočet termínů nejpozději přípustných konců činností
▪ Termín nejpozději přípustného dokončení činnosti je nejpozději přípustný okamžik, kdy lze činnost dokončit bez
zpoždění termínu dokončení projektu.
▪ Tento termín často vychází z požadavku zákazníka, který pevně stanovil dobu, během níž musí být projekt
dokončen.
▪ Oproti předchozímu výpočtu termínů nejdříve možných začátků činností probíhající ve vzestupném pořadí,
výpočet termínů nejpozději přípustných konců činností probíhá v sestupném pořadí.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Metoda kritické cesty CPM
Obr. 23 – Termín nejpozději přípustných konců činností
▪ Termín nejpozději přípustného dokončení projektu může
být nastaven v plánování procesu nebo může být
zvažován jako termín nejdříve možného dokončení
projektu:
kn = TPL ≥ T
min( )i j ij
j
k k t= − i = n – 1, n – 2, …, 1
i
ik
INTERNAL
94
Řízení projektů
▪ Výpočet termínů nejpozději přípustných konců činností
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Metoda kritické cesty CPM
Obr. 24 – Výpočet termínů nejpozději přípustných konců činností
▪ Deadline TPL = 48
INTERNAL
95
Řízení projektů
▪ Určení kritické cesty
▪ Určení celkové časové rezervy pro všechny činnosti:
▪ Kritické činnosti:
▪ Nekritické činnosti:
▪ Mohou nastat tři základní možnosti povoleného zpoždění činnosti (za předpokladu splnění deadlinu TPL) :
1. Začátek činnosti může být posunut.
2. Doba trvání činnosti může být prodloužena.
3. Kombinace možností 1 a 2.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Metoda kritické cesty CPM
( )ij j i ijCR k z t= − −
ij PLCR T T= −
ij PLCR T T −
INTERNAL
96
Řízení projektů
▪ Určení kritické cesty
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Metoda kritické cesty CPM
Obr. 25 – Kritická cesta
▪ Kritická cesta = A – D – (X1) – E – F – J – K
INTERNAL
97
Řízení projektů
▪ Ganttův diagram
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Metoda kritické cesty CPM
Obr. 26 – Ganttův diagram
INTERNAL
98
Řízení projektů
▪ Předpoklady
▪ Doba trvání každé činnosti je hodnotou náhodné veličiny.
▪ 𝛽-rozdělení:
▪ 𝑎𝑖𝑗 - optimistický odhad jako nejkratší možná doba trvání činnosti,
▪ 𝑏𝑖𝑗 - pesimistický odhad jako nejdelší doba trvání,
▪ 𝑚𝑖𝑗 - modální odhad jako nejpravděpodobnější doba trvání činnosti, která předpokládá nejčastější (obvyklé)
podmínky pro realizaci.
▪ Střední hodnota doby trvání činnosti
▪ Směrodatná odchylka doby trvání činnosti
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Metoda PERT
6
4 ijijij
ij
bma ++
=
6
ijij
ij
ab −
=
Obr. 27 – Hustota pravděpodobnosti β-rozdělení
Optimistický
odhad
Modální
odhad
Střední hodnota
doby trvání
Pesimistický
odhad
INTERNAL
99
Řízení projektů
▪ Příklad
▪ V projektu jsou zadány tři definované odhady doby trvání činností namísto jediné pevně dané hodnoty.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Metoda PERT
Tab. 25 – Direktmarketingový projekt – vstupní data pro metodu PERT
Činnost Popis činnosti 𝑎𝑖𝑗 𝑚𝑖𝑗 𝑏𝑖𝑗
Bezprostředně
předchozí činnosti
A Výběr skladeb 11 15 19 B
Mastering 7 8 9 A
C Zpracování promotion materiálů 5 6 7 A
D Analýza zákazníků 5 7 9 A
E Výroba promotion materiálů 2 3 10 C, D
F Doprava promotion materiálů 3 4 11 E
G Výběr zákazníků 2 3 4 D
H Výroba produktů 8 11 20 B, D
I Zpracování dat o zákaznících 2 3 4 G
J Kompletace 6 8 16 F, I
K Obeslání 6 8 10 H, J
INTERNAL
100
Řízení projektů
▪ Popis metody
▪ Sestavení síťového grafu.
▪ Výpočet středních hodnot a směrodatných odchylek doby trvání všech činností.
▪ Aplikace metody CPM, určení kritické cesty (KC).
▪ Střední hodnota doby trvání projektu
▪ Rozptyl doby trvání projektu
▪ Směrodatná odchylka doby trvání projektu
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Metoda PERT
( , ) KC
ij
i j
M 

= 
2 2
( , ) KC
ij
i j
 

= 
2
 =
INTERNAL
101
Řízení projektů
▪ Popis metody
▪ Pravděpodobnostní analýza:
▪ Jaká je pravděpodobnost, že projekt bude dokončen do předem stanoveného termínu 𝑻 𝑺?
▪ Transformace se standardním normálním rozdělením 𝑁 0,1 :
▪ V jakém termínu bude projekt dokončen s požadovanou pravděpodobností 𝒑?
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Metoda PERT
S KCpT M z= + 
S
KC
p
T M
z
−
=

INTERNAL
102
Řízení projektů
▪ Sestrojení síťového grafu
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Metoda PERT
Obr. 28 – Síťový graf projektu
▪ X1, X2 – fiktivní hrany
INTERNAL
103
Řízení projektů
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Metoda PERT
Činnost Popis činnosti 𝑎𝑖𝑗 𝑚𝑖𝑗 𝑏𝑖𝑗 𝜇𝑖𝑗
A Výběr skladeb 11 15 19 15
B Mastering 7 8 9 8
C Zpracování promotion materiálů 5 6 7 6
D Analýza zákazníků 5 7 9 7
E Výroba promotion materiálů 2 3 10 4
F Doprava promotion materiálů 3 4 11 5
G Výběr zákazníků 2 3 4 3
H Výroba produktů 8 11 20 12
I Zpracování dat o zákaznících 2 3 4 3
J Kompletace 6 8 16 9
K Obeslání 6 8 10 8
Tab. 26 – Direktmarketingový projekt – střední hodnoty doby trvání činností
▪ Příklad
▪ Výpočet středních hodnot doby trvání činností.
INTERNAL
104
Řízení projektů
▪ Příklad
▪ Určení kritické cesty
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Metoda PERT
Obr. 29 – Příklad – určení kritické cesty
▪ Kritická cesta: A – D – (X1) – E – F – J – K
INTERNAL
105
Řízení projektů
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Metoda PERT
Tab. 27 – Střední hodnoty a směrodatné odchylky doby trvání kritických činností
Činnost 𝑎𝑖𝑗 𝑚𝑖𝑗 𝑏𝑖𝑗 𝜇𝑖𝑗 𝜎𝑖𝑗
A 11 15 19 15 8/6
D 5 7 9 7 4/6
E 2 3 10 4 8/6
F 3 4 11 5 8/6
J 6 8 16 9 10/6
K 6 8 10 8 4/6
▪ Příklad
▪ Výpočet směrodatné odchylky doby trvání činností.
INTERNAL
▪ Příklad
▪ Střední hodnota doby trvání projektu
▪ Rozptyl doby trvání projektu
▪ Směrodatná odchylka doby trvání projektu
106
Řízení projektů
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Metoda PERT
488954715 =+++++=M
2 2 2 2 2 2 2
KC (8 / 6) (4 / 6) (8 / 6) (8 / 6) (10 / 6) (4 / 6) 9,= + + + + + =
KC 3=
INTERNAL
107
Řízení projektů
▪ Příklad – pravděpodobnostní analýza
▪ Jaká je pravděpodobnost, že projekt bude dokončen do předem stanoveného termínu 𝑇𝑆 = 45 dní?
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Metoda PERT
45 48
1
3
z
−
= = − 0,1587p =
čas (dny)
Tabulky N(0,1)
Obr. 30 – Pravděpodobnostní analýza
INTERNAL
108
Řízení projektů
▪ Příklad – pravděpodobnostní analýza
▪ V jakém termínu bude projekt dokončen s 95% pravděpodobností?
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Metoda PERT
0.95 1,64z =
Tabulky N(0,1)
0,95p =
Obr. 31 – Pravděpodobnostní analýza
čas (dny)
S 48 1,64(3) 52,92T + =
INTERNAL
Modely řízení zásob
5
109
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
INTERNAL
110
Modely řízení zásob
▪ Zásoby
▪ Skladovány pro budoucí použití (rychle a flexibilně dostupné, minimalizace nákladů).
▪ Příklady zásob:
▪ suroviny,
▪ materiál,
▪ polotovary,
▪ náhradní díly.
▪ Řízení zásobování
▪ Kolik objednávat?
▪ Kdy objednávat?
▪ Cíl – minimalizace celkových nákladů.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úvod
INTERNAL
111
Modely řízení zásob
▪ Dílčí náklady
▪ Skladovací náklady
▪ pronájem skladovacích prostor,
▪ manipulace,
▪ pojištění zásob,
▪ úrok (investice),
▪ stárnutí & znehodnocení.
▪ Pořizovací náklady
▪ přepravní náklady,
▪ celní poplatky,
▪ náklady na přejímku a kontrolu zboží,
▪ pojištění.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úvod
INTERNAL
112
Modely řízení zásob
▪ Stav zásoby
▪ Dostupné množství zásoby (množství skladované položky, množství skladovaného materiálu atd.)
v určitém časovém okamžiku.
▪ Poptávka
▪ Velikost poptávky – množství položek nebo materiálu požadovaných za určité období.
▪ Čerpání zásob
▪ Intenzita spotřeby – množství skladovaných položek nebo materiálu přesunutého ze skladu. Odvození z velikosti
poptávky.
▪ Snižování stavu zásoby.
▪ Doplňování zásob
▪ Přesun doručených položek nebo materiálu do skladu.
▪ Zvyšování stavu zásoby.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úvod
INTERNAL
113
Modely řízení zásob
▪ Objednávání
▪ Pořizovací lhůta dodávky – časový interval mezi okamžikem vystavení objednávky a okamžikem doručení
dodávky.
▪ Bod znovuobjednávky – stav zásob, při kterém je zapotřebí vystavit novou objednávku.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úvod
Obr. 32 – Proces znovuobjednání
Čas
Pořizovací lhůta dodávky
Vystavení
objednávky
Doručení dodávky
&
doplnění skladu
INTERNAL
114
Modely řízení zásob
▪ Nedostatek zásoby
▪ Prázdný sklad vede ke vzniku neuspokojené poptávky (jestliže nevzniká během intervalu, v němž je sklad
prázdný, žádný požadavek, pak tento stav není považován za nedostatek zásoby).
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úvod
Obr. 33 – Nedostatek zásoby
Pořizovací lhůta
dodávky
Čas
Nedostatek zásoby !!
Doručení
dodávky
Vystavení
objednávky
Optimální okamžik
znovuobjednání
Stav zásoby = 0
INTERNAL
115
Modely řízení zásob
▪ Pojistná zásoba
▪ V případě stochastické poptávky.
▪ Pojistná zásoba je vytvářena za účelem zabránit vzniku nedostatku zásoby. Obecně není možné zcela vyloučit
vznik nedostatku zásoby (záleží na typu pravděpodobnostního rozdělení velikosti poptávky).
▪ Deterministické modely
▪ Všechny parametry jsou předem známé (především velikost poptávky a pořizovací lhůta dodávky).
▪ Stochastické modely
▪ Některé parametry jsou hodnotami náhodné veličiny.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úvod
INTERNAL
116
Modely řízení zásob
▪ Klasifikace poptávky
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úvod
Obr. 34 – Klasifikace poptávky
▪ Statická poptávka
▪ Velikost poptávky se v čase nemění.
▪ Dynamická poptávka
▪ Velikost poptávky je předem známá, ale
mění se v čase.
▪ Stacionární poptávka
▪ Pravděpodobnostní rozdělení se v čase
nemění.
▪ Nestacionární poptávka
▪ Pravděpodobnostní rozdělení se v čase
mění.
Poptávka
Deterministická Stochastická
Statická Dynamická Stacionární Nestacionární
Zvyšování složitosti matematických modelů
INTERNAL
117
Modely řízení zásob
▪ Řízení zásob
▪ Kolik objednávat?
▪ Kdy objednávat?
▪ Jaké jsou celkové náklady?
▪ Jaký je maximální stav zásoby?
▪ Jaká je optimální délka zásobovacího cyklu?
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Model EOQ – Optimální velikost objednávky
INTERNAL
118
Modely řízení zásob
▪ Předpoklady
▪ položka jediného typu,
▪ poptávka je předem známá a v čase konstantní (statická)
▪ pořizovací lhůta dodávky je známá a konstantní,
▪ čerpání zásob ze skladu je rovnoměrné,
▪ velikost objednávek je konstantní,
▪ nákupní cena je nezávislá na velikosti objednávky (žádné množstevní slevy),
▪ doplnění skladu probíhá v určitém časovém okamžiku, a to přesně v okamžiku jeho vyčerpání.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Model EOQ – Optimální velikost objednávky
INTERNAL
119
Modely řízení zásob
▪ Zásobovací cykly
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Model EOQ – Optimální velikost objednávky
Obr. 35 – EOQ model – zásobovací cykly
INTERNAL
120
Modely řízení zásob
▪ Příklad
▪ Soukromý pivovar vyrábí měsíčně 4 000 hl piva.
▪ 25 % produkce se prodává v podobě lahvového piva. Prázdné půllitrové láhve jsou uloženy v pivních přepravkách
po 20 lahvích. Průměrné roční skladovací náklady jsou vyčísleny na 20 Kč za jednu přepravku.
▪ Dodavatel lahví si účtuje 11 000 Kč za jednu dodávku, pivovar navíc musí zaúčtovat dalších 1 000 Kč za každou
objednávku jako vlastní fixní náklady.
▪ Pořizovací lhůta dodávky je 1/2 měsíce. Protože plnění lahví je rovnoměrný proces, čerpání lahví ze skladu je
také rovnoměrné.
▪ Provoz pivovaru je třísměnný (nepřetržitý), nesmí dojít k přerušení zásobovacího procesu.
▪ Management pivovaru se rozhodl analyzovat zásobovací proces tak, aby minimalizoval celkové náklady, spojené
se skladováním a objednáváním prázdných lahví.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Model EOQ – Optimální velikost objednávky
INTERNAL
121
Modely řízení zásob
▪ Vstupní parametry a proměnné
▪ Roční poptávka
▪ Jednotkové skladovací náklady (roční)
▪ Pořizovací náklady
▪ Pořizovací lhůta dodávky
▪ Velikost objednávky
▪ Počet objednávek za rok
▪ Délka dodávkového cyklu
▪ Bod znovuobjednávky
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Model EOQ – Optimální velikost objednávky
Q = 120 000 přepravek
c1 = 20 Kč/přepravka
c2 = 12 000 Kč/objednávka
d = 1/2 měsíce = 1/24 roku
q
n
t
r
INTERNAL
122
Modely řízení zásob
▪ Celkové roční náklady
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Model EOQ – Optimální velikost objednávky
N – celkové roční náklady
NS – celkové roční skladovací náklady
NP – celkové roční skladovací náklady
qmax – maximální stav zásoby
qavg – průměrný stav zásoby
qq =max
2
q
qavg =
1 1
2
S avg
q
N c q c= =
q
Q
n =
S PN N N= +
1 2( )
2
q Q
N q c c
q
= +
2 2P
Q
N c n c
q
= =
INTERNAL
123
Modely řízení zásob
▪ Celkové roční náklady
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Model EOQ – Optimální velikost objednávky
Tab. 28 – Tři různé strategie řízení objednávek
Obr. 36 – EOQ model – nákladové funkce
1 2( )
2
q Q
N q c c
q
= +
INTERNAL
124
Modely řízení zásob
▪ Zásobovací cykly
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Model EOQ – Optimální velikost objednávky
Obr. 37 – Zásobovací cykly při různých strategiích
INTERNAL
125
Modely řízení zásob
▪ Optimální velikost objednávky
▪ Optimální celkové roční náklady
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Model EOQ – Optimální velikost objednávky
1
2* 2
c
Qc
q =
1
2 2
0
2
cdN Q
c
dq q
= − =
→ min1 2( )
2
q Q
N q c c
q
= +
*
1 22N Qc c= Kč*
2(120000)(20)(12000) 240000N = =
přepravek* 2(120000)(12000)
12000
20
q = =
INTERNAL
126
Modely řízení zásob
▪ Optimální velikost objednávky, optimální celkové roční náklady
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Model EOQ – Optimální velikost objednávky
Obr. 38 – Minimální náklady při optimální velikosti objednávky
INTERNAL
127
Modely řízení zásob
▪ Optimální délka zásobovacího cyklu
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Model EOQ – Optimální velikost objednávky
Obr. 39 – Zásobovací cykly při optimální strategii
*
*
*
1 q
t
n Q
= = t* = 1/10 roku
INTERNAL
128
Modely řízení zásob
▪ Optimální bod znovuobjednávky
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Model EOQ – Optimální velikost objednávky
Obr. 40 – Určení bodu znovuobjednávky
Podobnost trojúhelníků:
*
* *
r d
q t
=
dQ
t
dq
r == *
*
*
0005000120
24
1*
==r přepravek
*
* * *
*
mod mod
dq
r q dQ q
t
= =
INTERNAL
129
Modely řízení zásob
▪ Příklad
▪ Firma zabývající se distribucí uhlí realizuje pravidelné týdenní objednávky (předpokládáme 50 týdnů v roce).
▪ Roční nájem skladových prostor činí 20 Kč na jednu tunu uhlí, pořizovací náklady na jednu objednávku jsou
800 Kč.
▪ Zkušební přechod na pravidelné dvoutýdenní objednávky nezpůsobil žádnou změnu celkových ročních
nákladů.
▪ Vypočtěte velikost objednávky a velikost celkových ročních nákladů odpovídající předchozí i současné
strategii.
▪ Optimalizujte zásobovací proces.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Model EOQ – Optimální velikost objednávky
INTERNAL
130
Modely řízení zásob
▪ Vstupní parametry a proměnné
▪ Roční skladovací náklady na jednotku
▪ Pořizovací náklady
▪ Počet objednávek – strategie 1
▪ Počet objednávek – strategie 2
▪ Velikost objednávky – strategie 1
▪ Velikost objednávky – strategie 2
▪ Celkové roční náklady – strategie 1
▪ Celkové roční náklady – strategie 2
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Model EOQ – Optimální velikost objednávky
c1 = 20 Kč/tuna
c2 = 800 Kč/objednávka
n1 = 50/rok
n2 = 25/rok
q
2q
N1
N2
INTERNAL
131
Modely řízení zásob
▪ Velikost objednávky a celkové roční náklady pro obě strategie
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Model EOQ – Optimální velikost objednávky
𝑁1 = 𝑁2
𝑐1
𝑞
2
+ n1 𝑐2 = 𝑐1
2𝑞
2
+ n2 𝑐2
20
𝑞
2
+ 50(800) = 20
2𝑞
2
+ 25(800)
𝑞 = 2000 tun
𝑄 = 50.2000 = 100000 tun
𝑁1 = 𝑁2 = 60000 Kč
2𝑞 = 4000 tun
▪ Optimální velikost objednávky a optimální celkové roční náklady
𝑞∗ =
2(100000)(800)
20
ሶ= 2828 tun
𝑁∗ = 2(100000)(20)(800) ሶ= 56570 Kč
INTERNAL
132
Modely řízení zásob
▪ Řízení zásob
▪ Jaká je optimální velikost výrobní dávky?
▪ Jaký je maximální stav zásoby?
▪ Jaké jsou celkové náklady?
▪ Jak dlouho trvá výroba?
▪ Kdy se má začít s přípravou následující výrobní dávky?
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Produkčně – spotřební model
INTERNAL
133
Modely řízení zásob
▪ Předpoklady
▪ položka jediného typu,
▪ poptávka je předem známá a v čase konstantní (statická)
▪ délka časového intervalu nutného pro přípravu následující výrobní dávky je známá a konstantní hodnota,
▪ čerpání zásob ze skladu je rovnoměrné,
▪ velikost dávky je konstantní,
▪ doplnění probíhá v produkčním cyklu,
▪ žádný nedostatek ani přebytek (produkční cyklus začíná přesně v momentě dokončení spotřebního cyklu).
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Produkčně – spotřební model
INTERNAL
134
Modely řízení zásob
▪ Zásobovací cykly
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Produkčně – spotřební model
Obr. 41 – Zásobovací cykly v produkčně – spotřebním modelu
INTERNAL
135
Modely řízení zásob
▪ Zásobovací cykly
▪ Produkční cyklus
▪ intenzita produkce,
▪ intenzita spotřeby,
▪ doplňování zásob.
▪ Spotřební cyklus
▪ intenzita spotřeby,
▪ čerpání.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Produkčně – spotřební model
intenzita produkce > intenzita spotřeby
INTERNAL
136
Modely řízení zásob
▪ Příklad
▪ Soukromý pivovar vyrábí měsíčně 4 000 hl piva.
▪ 25 % produkce se prodává v podobě lahvového piva. Prázdné půllitrové láhve jsou uloženy v pivních přepravkách
po 20 lahvích. Průměrné roční skladovací náklady jsou vyčísleny na 20 Kč za jednu přepravku.
▪ Linka je schopná vyčistit maximálně 8 000 lahví za den.
▪ Náklady spojené s přípravou jedné čistící dávky jsou 12 000 Kč.
▪ Příprava čistící linky trvá 1/2 měsíce.
▪ Cílem je optimalizovat výrobní a zásobovací proces.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Produkčně – spotřební model
Obr. 42 – Produkční cyklus Obr. 43 – Spotřební cyklus
Čistící
linka
Sklad
Plnění
lahví
Sklad
Plnění
lahvíČistící
linka
INTERNAL
137
Modely řízení zásob
▪ Vstupní parametry a proměnné
▪ Velikost celkové (roční) poptávky
▪ Jednotkové skladovací náklady (roční)
▪ Fixní náklady na přípravu a realizaci jedné výrobní dávky
▪ Délka časového intervalu nutného pro přípravu následující výrobní dávky
▪ Intenzita produkce
▪ Intenzita spotřeby
▪ Velikost výrobní dávky
▪ Celkový počet výrobních dávek (v jednom roce)
▪ Délka zásobovacího cyklu
▪ Délka produkčního cyklu
▪ Délka spotřebního cyklu
▪ Stav zásob, při kterém se začíná připravovat následující výrobní dávka
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Produkčně – spotřební model
Q = 120 000 přepravek
c1 = 20 Kč/přepravek
c2 = 12 000 Kč/dávka
d = 1/2 měsíce= 1/24 roku
p = 146 000 přepravek za rok
h = 120 000 přepravek za rok
q
n
t
t1
t2
r
INTERNAL
138
Modely řízení zásob
▪ Celkové roční náklady
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Produkčně – spotřební model
N – celkové roční náklady
NS – celkové roční skladovací náklady
ND – celkové roční náklady na přípravu a realizaci dávek
qmax – maximální stav zásoby
qavg – průměrný stav zásoby
S DN N N= +
q
Q
n =
1q pt=
max
2 2
avg
q p h q
q
p
−
= =
max 1 1 1( )
p h
q pt ht p h t q
p
−
= − = − =
S 1 avg 1
2
p h q
N c q c
p
−
= =
D 2 2
Q
N c n c
q
= = 1 2( )
2
p h q Q
N q c c
p q
−
= +
INTERNAL
139
Modely řízení zásob
▪ Optimální velikost výrobní dávky
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Produkčně – spotřební model
1 2
2
( )
0
2
c c QdN q p h
dq p q
−
= − =
hp
p
c
Qc
q
−
=
1
2* 2
* 2(120000)(12000) 146000
28 436,16 cases.
20 146000 120000
q = =
−
1 2( )
2
p h q Q
N q c c
p q
−
= + → min
přepravek
INTERNAL
140
Modely řízení zásob
▪ Optimální celkové roční náklady
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Produkčně – spotřební model
* 146000 120000
2(120000)(20)(12000) 101280 CZK.
146000
N
−
= =
*
1 22
p h
N Qc c
p
−
=
INTERNAL
141
Modely řízení zásob
▪ Optimální délka výrobního cyklu
▪ Optimální délka spotřebního cyklu
▪ Optimální délka zásobovacího cyklu
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Produkčně – spotřební model
p
q
t
*
*
1 = *
1 0,1948 roku = 71,1 dnet =
*
*
max*
2 q
ph
hp
h
q
t
−
== *
2 0,0422 roku = 15,4 dnet =
* * *
1 2t t t= + *
0,1948 0,0422 0,237 roku = 86,5 dnet = + =
INTERNAL
142
Modely řízení zásob
▪ Stav zásoby na začátku období pro přípravu následující výrobní dávky
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Produkčně – spotřební model
hdr =* )()( **
dthpr −−=
Obr. 44 – Stav zásoby na začátku období pro přípravu následující výrobní dávky
INTERNAL
143
Modely řízení zásob
▪ Stav zásoby na začátku období pro přípravu následující výrobní dávky
▪ Maximální stav zásoby pro optimální velikost čistící dávky
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Produkčně – spotřební model
*
21/ 24 0,0417 0,0422d t= =  =
* *
max 2q ht= *
max 5064 přepravekq =
,r hd
= * 1
120000 5000
24
r = = přepravek
INTERNAL
144
Modely řízení zásob
▪ Předpoklady
▪ položka jediného typu,
▪ stochastická poptávka,
▪ uskutečněna jediná objednávka (v průběhu nelze doplňovat sklad),
▪ na konci sledovaného období mohou nastat dvě situace:
▪ přebytek,
▪ nedostatek.
▪ Příklady sezónního zboží a zboží podléhajícího rychlé zkáze a znehodnocení
▪ noviny, pečivo, květiny, ovoce, módní oděvy, vánoční stromky.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Stochastický model s jednorázově vytvářenou zásobou
INTERNAL
145
Modely řízení zásob
▪ Příklad
▪ Oddělení potravin v hypermarketu řeší otázku, jak velkou zásobu rohlíků má vytvořit pro daný den.
▪ Rohlíky do hypermarketu dodává pekárna, která si účtuje 1 Kč za kus. Hypermarket svým zákazníkům nabízí 1 kus
za 2 Kč. Pokud na konci dne nějaké rohlíky zbydou, pak se nechají ztvrdnout či usušit a použijí se na výrobu
strouhanky. V sáčku, který se prodává za 12 Kč, je nastrouháno 20 rohlíků.
▪ Experti odhadli, že následující den se velikost poptávky bude řídit normálním pravděpodobnostním rozdělením se
střední hodnotou 10 000 ks a směrodatnou odchylkou 500 ks.
▪ Kolik rohlíků má hypermarket objednat, pokud chce maximalizovat zisk?
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Stochastický model s jednorázově vytvářenou zásobou
INTERNAL
146
Modely řízení zásob
▪ Vstupní parametry a proměnné
▪ střední hodnota velikosti poptávky 𝜇 = 10 000 rohlíků
▪ směrodatná odchylka velikosti poptávky 𝜎 = 500 rohlíků
▪ nákupní cena 1 Kč/rohlík
▪ prodejní cena 2 Kč/rohlík
▪ zůstatková hodnota 12/20 = 0,6 Kč/rohlík
▪ skutečná velikost poptávky 𝑄
▪ velikost objednávky 𝑞
▪ úroveň obsluhy 𝑝
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Stochastický model s jednorázově vytvářenou zásobou
INTERNAL
147
Modely řízení zásob
▪ Mezní ztráta
▪ Velikost objednávky převyšuje skutečnou velikost poptávky nebo se jí rovná ( 𝑞 ≥ 𝑄)
▪ Očekávaná mezní ztráta
▪ Mezní ušlý zisk
▪ Velikost objednávky je nižší než skutečná velikost poptávky ( 𝑞 < 𝑄)
▪ Očekávaný mezní ušlý zisk
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Stochastický model s jednorázově vytvářenou zásobou
ML = nákupní cena – zůstatková hodnota ML = 1 – 0,6 = 0,4 Kč/rohlík
p(ML)
MPL = prodejní cena – nákupní cena MPL = 2 – 1 = 1 Kč/rohlík
(1 – p)(MPL)
INTERNAL
148
Modely řízení zásob
▪ Optimální úroveň obsluhy
▪ Optimální velikost objednávky
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Stochastický model s jednorázově vytvářenou zásobou
MPLML
MPL
p
+
=
1
0,7143
0,4 1
p = =
+
  pqQ P

−
=
Q
zp
 pzq +
 += pzQ→
 pzq +=* *
10 000 0,57(500) 10 285 rollsq = + =
(1 )pML p MPL= −
rohlíků
INTERNAL
149
Modely řízení zásob
▪ Příklad
▪ Předpokládejme nyní, že velikost denní poptávky po rohlících má diskrétní rovnoměrné pravděpodobnostní rozdělení
s minimální hodnotou 8 000 ks a maximální hodnotou 10 000 ks. Opět máme rozhodnout o optimální velikosti
objednávky.
▪ Optimální velikost objednávky
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Stochastický model s jednorázově vytvářenou zásobou
q* = 8 000 + 0,7143 (10 000 – 8 000) ሶ= 9 429 rohlíků
INTERNAL
Modely hromadné obsluhy
6
150
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
INTERNAL
151
Modely hromadné obsluhy
▪ Systém hromadné obsluhy
▪ Dva prvky v systému
▪ požadavky,
▪ obslužná zařízení (obslužné linky).
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úvod
Obr. 45 – Základní schéma systému hromadné obsluhy
Zdroj požadavků
Příchod
požadavků
Odchod
požadavků
Fronta
Obsluha
INTERNAL
152
Modely hromadné obsluhy
▪ Systém hromadné obsluhy
▪ Příklady reálných systémů hromadné obsluhy
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úvod
Tab. 29 – Příklady systémů hromadné obsluhy
Systém hromadné obsluhy Požadavek Obslužné zařízení
lékařská pohotovost pacient lékař
banka klient úředník
křižovatka auto semafor
call centrum hovor operátor
letiště letadlo runway
hasičská stanice požár zásahová jednotka
stanice záchranné služby dopravní nehoda záchranná jednotka
INTERNAL
153
Modely hromadné obsluhy
▪ Zdroj požadavků
▪ Velikost zdroje
▪ nekonečný (turisté),
▪ konečný (vozový park firmy).
▪ Příchody požadavků
▪ Způsob příchodu
▪ individuálně (pacient),
▪ ve skupinách (skupina turistů).
▪ Čas příchodu
▪ plánované (vlaky),
▪ neplánované (pacienti bez objednání, např. na pohotovosti).
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úvod
INTERNAL
154
Modely hromadné obsluhy
▪ Příchody požadavků
▪ Počet požadavků
▪ počet požadavků, které do systému přijdou
za jednotku času (Poissonovo
pravděpodobnostní rozdělení),
▪ λ = intenzita příchodu požadavků –
průměrný počet požadavků, příchozích za
jednotku času.
▪ Okamžik příchodu požadavků
▪ interval mezi příchody – doba mezi příchody
dvou po sobě příchozích požadavků.
(exponenciální rozdělení),
▪ 1/λ = střední doba mezi příchody
požadavků do systému – průměrná doba
mezi příchody dvou požadavků.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úvod
Obr. 46 – Příchod požadavků
Příchod
Příchod
Příchod
Čas
INTERNAL
155
Modely hromadné obsluhy
▪ Obsluha
▪ Počet požadavků
▪ počet požadavků, které zařízení obslouží za jednotku času (Poissonovo pravděpodobnostní rozdělení),
▪ μ = intenzita obsluhy – průměrný počet požadavků obsloužených za časovou jednotku.
▪ Doba obsluhy
▪ doba, za kterou je požadavek obsloužen (exponenciální rozdělení),
▪ 1/μ = střední doba trvání obsluhy – průměrná doba trvání obsluhy požadavků.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úvod
INTERNAL
156
Modely hromadné obsluhy
▪ Síť obslužných zařízení
▪ Typ zařízení – typ nabízené obsluhy.
▪ Počet zařízení – jedno nebo více zařízení.
▪ Uspořádání obslužných zařízení – způsob uspořádání zařízení.
▪ Konfigurace
1. Jednoduchý systém hromadné obsluhy
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úvod
Obr. 47 – Jednoduchý systém hromadné obsluhy
Příchod
Fronta Obsluha
Odchod
INTERNAL
157
Modely hromadné obsluhy
▪ Konfigurace
2. Paralelní uspořádání obslužných linek
3. Sériové uspořádání obslužných linek
4. Kombinované uspořádání obslužných linek
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úvod
Obr. 48 – Identická obsluha, společná fronta Obr. 49 – Identická fronta, samostatné fronty Obr. 50 – Neidentická obsluha
Obr. 51 – Sériové uspořádání obslužných linek
Příchod
Fronta
Obsluha
Odchod
Příchod
Fronty Obsluha
Odchod
Fronty Obsluha
Příchod
Odchod
Příchod
Fronta
Obsluha
Odchod
Fronta Fronta
Obsluha Obsluha
INTERNAL
158
Modely hromadné obsluhy
▪ Režimy front
▪ FCFS (First-Come, First-Served) – FIFO (First-In, First-Out)
▪ LCFS (Last-Come, First-Served) – LIFO (Last-In, First-Out)
▪ PRI (PRIority system) – fronta s prioritou
▪ SIRO (Selection In Random Order) – náhodný výběr
▪ Klasifikace modelů hromadné obsluhy (Kendallova klasifikace)
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Úvod
Obr. 52 – Kendallova klasifikace
Velikost zdroje požadavků
Režim fronty
Počet paralelně uspořádaných obslužných
zařízení
Pravděpodobnostní rozdělení intervalu mezi příchody
Pravděpodobnostní rozdělení doby obsluhy
Maximální počet požadavků
v systému
INTERNAL
159
Modely hromadné obsluhy
▪ Předpoklady
▪ Kendallův kód: M/M/1/FIFO/∞/∞,
▪ jedno obslužné zařízení,
▪ exponenciální pravděpodobnostní rozdělení intervalu mezi příchody (λ = intenzita příchodu požadavků),
▪ exponenciální pravděpodobnostní rozdělení doby obsluhy (μ = intenzita obsluhy),
▪ režim fronty je FIFO,
▪ kapacita systému je neomezená,
▪ zdroj požadavků je nekonečný,
▪ μ>λ stabilizace systému.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Jednoduchý exponenciální model HO
INTERNAL
160
Modely hromadné obsluhy
▪ Příklad
▪ V obchodu se smíšeným zbožím je prodejní pult s jedním prodavačem.
▪ Během otevírací doby od 8:00 do 18:00 přichází do obchodu průměrně 18 zákazníků za hodinu.
▪ Prodavač dokáže obsloužit během hodiny průměrně 25 zákazníků.
▪ Úkolem je provést analýzu tohoto systému hromadné obsluhy.
▪ Vstupní parametry
▪ Intenzita příchodu požadavků
▪ Intenzita obsluhy
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Jednoduchý exponenciální model HO
λ = 18 požadavků za hodinu
μ = 25 požadavků za hodinu
INTERNAL
161
Modely hromadné obsluhy
▪ Pravděpodobnostní charakteristiky
▪ Intenzita provozu
▪ pravděpodobnost, že obslužné zařízení pracuje,
▪ pravděpodobnost, že prodavač právě obsluhuje nějakého zákazníka,
▪ pravděpodobnost, že zákazník bude muset čekat ve frontě.
▪ Pravděpodobnost, že v systému není žádný požadavek
▪ pravděpodobnost, že obslužné zařízení nepracuje,
▪ pravděpodobnost, že zákazník nebude muset čekat ve frontě.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Jednoduchý exponenciální model HO


 = ρ = 0,72
0 1p = − 0 0,28p =
INTERNAL
162
Modely hromadné obsluhy
▪ Pravděpodobnostní charakteristiky
▪ Pravděpodobnost, že se v systému nachází přesně 𝑛 požadavků.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Jednoduchý exponenciální model HO
𝑛 𝑝 𝑛
0 0,280
1 0,202
2 0,145
3 0,105
4 0,075
5 0,054
Tab. 30 – Pravděpodobnost, že v prodejně je přesně 𝒏 zákazníků
0 (1 )n n
np p= = −  
n
np
0 1 2 3 ... 1p p p p+ + + + =
INTERNAL
163
Modely hromadné obsluhy
▪ Časové charakteristiky
▪ Průměrná doba, kterou požadavek stráví v systému
▪ Průměrná doba čekání požadavku ve frontě
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Jednoduchý exponenciální model HO
T ሶ= 0,143 hodin ሶ= 8,6 min
1
fT T

= − Tf ሶ= 0,103 hodin ሶ= 6,2 min
1
T =
− 
INTERNAL
164
Modely hromadné obsluhy
▪ Charakteristiky týkající se počtu požadavků
▪ Průměrný počet požadavků nacházejících se v systému
▪ Průměrný počet požadavků čekajících ve frontě
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Jednoduchý exponenciální model HO
N ሶ= 2,57 požadavkůN T=
Nf ሶ= 1,85 požadavkůf fN T=
INTERNAL
165
Modely hromadné obsluhy
▪ Předpoklady
▪ Kendallův kód: M/M/K/FIFO/∞/∞,
▪ K paralelně uspořádaných identických zařízení,
▪ exponenciální pravděpodobnostní rozdělení intervalu mezi příchody (λ = intenzita příchodu požadavků),
▪ exponenciální pravděpodobnostní rozdělení doby obsluhy (μ = intenzita obsluhy),
▪ režim fronty je FIFO,
▪ kapacita systému je neomezená,
▪ zdroj požadavků je nekonečný,
▪ Kμ>λ stabilizace systému.
Operační výzkum I, ŠAVŠ, Jan Fábry, 9.11.2022
Exponenciální model HO s paralelními zařízeními
INTERNAL
www.savs.cz
Děkuji za pozornost
Jan Fábry
Katedra řízení výroby, logistiky a kvality
fabry@savs.cz www.janfabry.cz