Technická univerzita v Liberci Fakulta mechatroniky, informatiky a mezioborových studií. Petr Rálek, Josef Novák, Josef Chudoba

Technická univerzita v Liberci Fakulta mechatroniky, informatiky a mezioborov´ ych studi´ı

Metody uˇ z´ıvan´ e v logistice

Petr R´ alek, Josef Novák, Josef Chudoba

Materi´ al byl vytvoˇ ren´ y s podporou ESF v r´ amci projektu: ”Inovace a realizace bakal´ aˇ rsk´ eho oboru Informatika a logistika v souladu s poˇ zadavky pr˚ umyslu a veˇ rejn´ e spr´ avy”, ˇ c´ıslo projektu CZ.04.1.03/3.2.15.3/0442

1

Obsah 1 Teorie z´ asob - u ´vod Charakteristika parametr˚ u v modelech zásob . . . . . . . . . . . . . . . . . . . . . . . Modely z´ asob Deterministické modely zásob . . . . . . . . . . . . . . . . Model 1 . . . . . . . . . . . . . . . . . . . . . . . . . Model 2 . . . . . . . . . . . . . . . . . . . . . . . . . Model 3 . . . . . . . . . . . . . . . . . . . . . . . . . Model 4 . . . . . . . . . . . . . . . . . . . . . . . . . Stochastické modely zásob . . . . . . . . . . . . . . . . . . Model 1 . . . . . . . . . . . . . . . . . . . . . . . . . Model 2 - optimalizace jednorázovˇe vytváˇrené zásoby

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

4 5 7 7 7 14 17 20 21 21 23

Cviˇ cen´ı a pˇ r´ıklady

26

2 S´ıt’ov´ a anal´ yza - u ´vod

28

Z´ akladn´ı pojmy teorie graf˚ u 30 Neorientovaný graf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Orientovaný graf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 S´ıt’ov´ y graf

32

Metoda kritick´ e cesty Výpoˇcet kritické cesty . . . . Výpoˇcet v s´ıt’ovém grafu Výpoˇcet v tabulce . . . . Analýza z´ıskaných výsledk˚ u .

36 37 40 41 42

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

Metoda PERT

44


47

3 Teorie front a syst´ emy hromadn´ e obsluhy - u ´vod Základn´ı pojmy SHO . . . . . . . . . . . . . . . . . . . . Klasifikace SHO . . . . . . . . . . . . . . . . . . . . . . . Obecná klasifikace . . . . . . . . . . . . . . . . . . Klasifikace podle ˇcást´ı SHO . . . . . . . . . . . . . Kendallova klasifikace SHO . . . . . . . . . . . . .

50 51 52 52 53 54

2

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

Typy SHO a jejich Markovské SHO . M/M/1/0 . M/M/n/0 . M/M/n/m . M/M/1/∞ . M/M/n/∞

modely . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

56 56 56 59 61 62 66


69

4 Teorie obnovy ´ Uvod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Charakteristiky proces˚ u obnovy . . . . . . . . . . . . . . Rovnice procesu obnovy . . . . . . . . . . . . . . . . . . Procesy obnovy a jejich modely . . . . . . . . . . . . . . Obnova zaˇr´ızen´ı z hlediska náklad˚ u pˇri jeho selhán´ı Obnova zaˇr´ızen´ı z d˚ uvodu jeho opotˇreben´ı . . . . .

72 72 72 74 77 77 79

Literatura

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

81

3

Kapitola 1 Teorie z´ asob - u ´vod Zásoby tvoˇr´ı poloˇzku, ve které má podnik vázanou urˇcitou (významnou) ˇcást aktiv. Proto patˇr´ı teorie zásob k tradiˇcn´ım oblastem logistiky a operaˇcn´ıho výzkumu. Jej´ım c´ılem je minimalizace náklad˚ u, které jsou se zásobami spojené (jejich poˇrizován´ı a skladován´ı), a optimalizace ˇr´ızen´ı zásob (stanoven´ı interval˚ u nákupu surovin ˇci skladován´ı výrobk˚ u). Na obr. 1.1 je jednoduché schéma výrobn´ıho procesu.

dodavatelé zdrojù

sklad zdrojù

spotøebitelé

výroba

sklad výrobkù

Obrázek 1.1: Schéma funkce zásob je ve výrobn´ım procesu Zásoby vystupuj´ı na dvou m´ıstech procesu: • sklad zdroj˚ u - materiál a suroviny potˇrebné pro výrobu, • sklad výrobk˚ u - fináln´ı výrobky ˇci dodávky pro dalˇs´ı výrobu V teorii zásob se oba pˇr´ıpady nerozliˇsuj´ı, vˇzdy se jedná o proces typu VSTUP - SKLAD ´ VYSTUP, liˇs´ı se pouze charakter vstupu. Následuj´ıc´ı pˇr´ıklady pˇredstavuj´ı obˇe typické u ´ lohy: Pˇ r´ıklad 1. Pˇredpokládejme, ˇze pr˚ umˇerný roˇcn´ı stav zásoby polotovar˚ u pro výrobu je 500 ks s t´ım, ˇze nákupn´ı cena 1 ks je 2000 Kˇc. Celkem je tedy v zásobách u této jednotky v penˇeˇzn´ım vyjádˇren´ı 1 mil. Kˇc. Pokud by tyto prostˇredky byly volné , potom by mohly být investovány a pˇrinesly by roˇcnˇe ˇreknˇeme 8 %, tj. 80000 Kˇc. Tuto cenu volných penˇez je rozumné zahrnout do skladovac´ıch náklad˚ u - na 1 ks skladovaného polotovaru tak roˇcnˇe pˇripadá 160 Kˇc. Pokud by byly ostatn´ı sloˇzky skladovac´ıch náklad˚ u vyˇciˇstˇeny na 80 Kˇc na 1 ks za rok, potom jsou celkové skladovac´ı náklady jedné jednotky za 1 rok 240 Kˇc. tj. 12 % z poˇrizovac´ı ceny polotovaru. Pˇ r´ıklad 2. Fruta a.s. produkuje v jedné ze svých poboˇcek limonády ve dvoulitrových plastikových lahv´ıch. Výroba a distribuce tˇechto výrobk˚ u je, vzhledem k poptávce v pr˚ ubˇehu roku, rovnomˇerná. Plastikové lahve jsou od dodavatele odeb´ırány v kartonech (kaˇzdý z nich obsahuje 24 ks lahv´ı) - potˇreba tˇechto karton˚ u za celý rok je plánovaná ve výˇsi 36000 ks. Nákupn´ı cena jednoho kartonu je 120 Kˇc. Lahve jsou objednávány pravidelnˇe v urˇcitých kvantech s t´ım, ˇze 4

s kaˇzdou objednávkou souvisej´ı fixn´ı náklady ve výˇsi 12000 Kˇc. Poˇrizovac´ı lh˚ uta dodávek je fixn´ı a ˇcin´ı 1/2 mˇes´ıce. Skladovac´ı náklady jednoho kartonu za 1 rok ˇcin´ı 20% z jeho nákupn´ı ceny. V pˇr´ıpadˇe nedostatku zásoby na skladu vznikaj´ı spoleˇcnosti nadnáklady a ztráty, které byly vykalkulovány ve výˇsi 50 Kˇc na 1 karton za 1 rok. Fruta, a.s. se rozhodla analyzovat systém svého skladového hospodáˇrstv´ı tak, aby minimalizovala náklady, které souvisej´ı s doplˇ nován´ım zásob a s jejich skladován´ım. Modely ˇr´ızen´ı zásob ˇreˇs´ı 2 hlavn´ı otázky: 1. V jakém okamˇziku objednat novou dodávku daného objemu zásob? 2. Jak velká by mˇela být objednávka? Ilustrujme situaci na dvou extrémn´ıch pˇr´ıpadech stavu zásob ve skladu: • Velmi vysok´ y stav zásob ve skladu.

Výhody - plynulá výroba , doplˇ nován´ı skladu v delˇs´ıch ˇcasových intervalech. Nevýhody - náklady na skladován´ı (skladovac´ı prostor, manipulace se zásobami), vázaná aktiva v zásobách, moˇzné znehodnocen´ı zásob stárnut´ım.

• Velmi n´ızk´ y stav zásob ve skladu. Výhody, resp. nevýhody tohoto pˇr´ıpadu jsou opakem nevýhod, resp. výhod prvn´ıho pˇr´ıpadu. ˇ ızen´ı zásob je tedy podm´ınˇeno ˇreˇsen´ım optimalizaˇcn´ı u R´ ´ lohy: stanovit takovou výˇsi zásob, která minimalizuje celkové náklady za dané obdob´ı. V u ´ loze vystupuje celá ˇrada r˚ uzných parametr˚ u. Lze je rozdˇelit do tˇr´ı skupin - parametry popt´ avky, objedn´ avky a skladovac´ıch n´ aklad˚ u (viz obr. 1.2).

poptávka stav skladu

vstup

odbyt ze skladu

objednávka Obrázek 1.2: Zásobovac´ı proces

Charakteristika parametr˚ u v modelech z´ asob Prvn´ı skupinou parametr˚ u v modelech ˇr´ızen´ı zásob je charakter popt´ avky po sledované jednotce zásoby. • Poptávka m˚ uˇze být rozliˇsena na deterministickou (DP) a stochastickou (SP). Velikost ˇci intenzita DP je v rámci daného ˇcasového intervalu pevnˇe daná. To je tˇreba pˇr´ıpad poptávky po souˇcástce montované do výrobku, v´ıme-li, ˇze za smˇenu se vyrob´ı daný poˇcet výrobk˚ u. SP je neurˇcitá a jako veliˇcinu ji lze odhadnout pouze s urˇcitou pravdˇepodobnost´ı (rozdˇelen´ı pravdˇepodobnosti je tˇreba urˇcit pomoc´ı statistických metod). Pˇr´ıkladem SP je poptávka po novˇe uvádˇeném zboˇz´ı na trhu. V oblasti objedn´ avek sledujeme: 5

• Rytmus objedn´ avky - ˇcasový interval mezi pravidelnˇe se opakuj´ıc´ımi se objednávkami. • Rytmus dod´ avky - ˇcasový interval mezi pravidelnˇe se opakuj´ıc´ımi se dodávkami. • Poˇ rizovac´ı lh˚ uta dod´ avky (PLD) - ˇcasový interval, který uplyne od okamˇziku objednávky (kdy odeˇsleme objednávku) do okamˇziku dodávky (kdy máme zboˇz´ı na skladˇe). PLD m˚ uˇze být deterministická nebo stochastická. V nejjednoduˇsˇs´ıch modelech se PLD zanedbává a vol´ı se okamˇzik objednávky = okamˇzik dodávky. Objednávky se ˇr´ıd´ı podle dvou základn´ıch strategi´ı: 1. Objednávka je vystavena v okamˇziku, kdy zásoba klesne na pˇredem stanovenou mez, která oznaˇcuje jeho bod znovuobjedn´ avky. Je tedy tˇreba plynule sledovat stav zásob a pˇri poklesu na stanovenou mez objednat dodávku. Pˇri tomto procesu provád´ıme spojité sledován´ı zásoby. Vˇsechny objednávky maj´ı stejnou velikost, ale délka ˇcasového intervalu mezi nimi se m˚ uˇze liˇsit. Poˇcet objednávek dodávek (dodávek) za jednotku ˇcasu oznaˇcujeme jeho intenzitu objedn´ avek (dod´ avek). ˇ 2. Casov´ e intervaly mezi objednávkami jsou konstantn´ı. V tˇechto intervalech se sleduje velikost zásoby a dle n´ı se obbjedná pˇr´ısluˇsné mnoˇzstv´ı. V tomto systému jsou zásoby sledovány periodicky. Intenzita objednávek je konstantn´ı, liˇs´ı se jejich velikosti. Náklady tvoˇr´ı nejˇcastˇejˇs´ı optimalizaˇcn´ı kritérium v modelech zásob - vˇetˇsinou chceme náklady minimalizovat. Rozliˇsujeme tˇri druhy náklad˚ u: 1. Skladovac´ı n´ aklady se vztahuj´ı ke kaˇzdé jednotce zásoby ve skladu za urˇcité ˇcasové obdob´ı. Zahrnuj´ı hlavnˇe manipulaci ve skladu, pronájem prostor, spotˇrebu energi´ı, mzdové náklady a pojiˇstˇen´ı, popˇr. znehodnocen´ı zásob a ohodnocen´ı vázanosti penˇez v zásobách. Tyto náklady závisej´ı na objemu skladovan´ ych zásob - jsou to náklady variabiln´ı. Skladovac´ı náklady vztaˇzené k jednotce z´ asob (hmotnost, poˇcet kus˚ u) a ˇcasu znaˇc´ıme c1 . Skladovac´ı náklady mohou být zadány dvˇema zp˚ usoby - pevnou ˇcástkou vztaˇzenou k jednotce zásob za ˇcasové obdob´ı nebo jako procento z nákupn´ı ceny zásob (viz pˇr. 1). 2. Poˇ rizovac´ı n´ aklady zahrnuj´ı náklady na pˇrepravu (náklady dodavatele) a mzdy personálu zajiˇst’uj´ıc´ıho objednávku. Týkaj´ı se kaˇzdého doplnˇen´ı skladu a kaˇzdé objednávky. Tyto náklady nezávisej´ı na velikosti objednávky - jedná se o fixn´ı náklady. Znaˇc´ıme je c2 . 3. N´ aklady spojen´ e s nedostatkem z´ asob vznikaj´ı tehdy, kdyˇz v d˚ usledku nedostaku zásob nem˚ uˇze být uspokojena poptávka. Je to napˇr. penále za pozdˇe dodané zboˇz´ı odbˇerateli, uˇslý zisk za nerealizovaný obchod, náklady za mimoˇrádnou objednávku (expresn´ı poplatky), náklady vzniklé omezen´ım ˇci zastaven´ım v´ yroby ˇci zmˇenou výrobn´ıho programu, ale i vyˇc´ıslen´ı ztráty dobrého jména spoleˇcnosti. Tyto náklady znaˇc´ıme c3 .

6

Modely z´ asob Základn´ı modely ˇr´ızen´ı zásob se dˇel´ı na dva typy: • Modely deterministick´ e - s pevnˇe danou poptávkou i poˇrizovac´ı lh˚ utu dodávek. • Modely stochastick´ e - velikost poptávky a poˇrizovac´ı lh˚ uta jsou dány s urˇcitou pravdˇepodobnost´ı. V zásadˇe ˇreˇs´ıme dvˇe otázky - kdy se má zásoba doplnit a o kolik, s podm´ınkou, ˇze chceme minimalizovat náklady.

Deterministick´ e modely z´ asob Model 1 Nejjednoduˇsˇs´ı model byl formulován jiˇz roku 1915. V ˇradˇe modifikac´ı se pouˇz´ıvá dodnes. Vycház´ı se v nˇem z tˇechto zidealizovaných pˇredpoklad˚ u: • poptávka je známá a konstantn´ı - oznaˇc´ıme ji symbolem Q, • ˇcerpán´ı zásob ze skladu je rovnomˇerné, • poˇrizovac´ı lh˚ uta je konstantn´ı, • velikost vˇsech dodávek je známá a konstantn´ı, • nákupn´ı cena je nezávislá na velikosti objednávky (neuvaˇzuj´ı se mnoˇzstevn´ı slevy), • nen´ı pˇripuˇstˇen vznik nedostatku zásoby - k doplnˇen´ı skladu docház´ı v okamˇziku jeho vyˇcerpán´ı), • k doplnˇen´ı skladu docház´ı v jednom ˇcasovém okamˇziku. Pr˚ ubˇeh dodávkových cykl˚ u je znázornˇen na obr. 1.3. V tomto modelu se pravidelnˇe opakuj´ı dodávkové cykly. Délku cyklu znaˇc´ıme t [rok], velikost dodávky q [kus]. Kaˇzdý cyklus se skládá z ˇcerpán´ı zásoby a doplnˇen´ı skladu. Sledované obdob´ı oznaˇcme T [rok]. C´ılem je nalézt optimáln´ı velikost dodávky q ⋆ [kus], která bude minimalizovat celkové náklady za dobu T Q q (1.1) N(q) = c1 T + c2 [Kˇc], 2 q kde prvn´ı sˇc´ıtanec jsou skladovac´ı náklady (jak v´ıme, variabiln´ı), druhý tvoˇr´ı fixn´ı poˇrizovac´ı náklady. V pˇredpokladech modelu neuvaˇzujeme náklady z nedostatku zásob c3 .

7

stav zásoby velikost dodávky

q

doplnìní zásoby èerpání zásoby

... t

3t

2t

dodávkový cyklus

T

èas

Obrázek 1.3: Pr˚ ubˇeh stavu zásoby v závislosti na ˇcase pro Model 1. V rovnici (1.1) jsou: T sledované obdob´ı [rok], c1 jednotkové skladovac´ı náklady za jednotkovou dobu [Kˇc/ks rok], c2 poˇrizovac´ı náklady jedné dodávky [Kˇc/dodávka], q velikost jedné dodávky [ks], Q velikost poptávky za dobu T [ks], q 2

pr˚ umˇerná velikost zásob,

n=

Q q

poˇcet dodávkových cykl˚ u [1 dodávka],

t interval mezi dodávkami [rok], N skladovac´ı a poˇrizovac´ı náklady za dobu T [Kˇc], d dodac´ı lh˚ uta [rok], r bod znovuobjednávky [ks]. Uvedené pojmy budeme charakterizovat na pˇr´ıkladu, jehoˇz parametry jsou zˇrejmé z tabulky 1.1. Urˇc´ıme dvˇe dvˇe odliˇsné zásobovac´ı strategie, liˇs´ıc´ı se poˇctem zásobovac´ıch cykl˚ u a velikost´ı dodávky. Pˇ r´ıklad 3. Prvn´ı strategie spoˇc´ıvá v malém poˇctu objednávek (dodávek) - uskuteˇcn ˇ uj´ı se pouze dvakrát roˇcnˇe a kaˇzdá z nich je o velikosti Q=18000 ks kartón˚ u. Tato strategie je charakterizována vysokým pr˚ umˇerných stavem zásob - polovina mezi maximáln´ım a minimáln´ım stavem, tj 9000 ks. Budou v n´ı tedy vysoké skladovac´ı náklady, ale vzhledem k malému poˇctu dodávkových cykl˚ u, n´ızké fixn´ı náklady. Naopak, druhá strategie poˇc´ıtá s dodávkami kaˇzdý mˇes´ıc - kaˇzdá z nich bude m´ıt tedy velikost 3000 ks. Pr˚ umˇerný stav zásoby je pouze 1500 ks. Ve srovnán´ı s prvn´ı strategi´ı bude charakterizován tento systém n´ızkými skladovac´ımi náklady, ale vysokými fixn´ımi náklady (12 cykl˚ u roˇcnˇe). Budeme-li uvaˇzovat výˇse definované nákladové poloˇzky, tj. náklady na poˇr´ızen´ı jedné dodávky 12000 Kˇc/dodávka (c2 ) a jednotkové skladovac´ı 8

poptávka Q [ks] velikost poptávky q [ks] poˇcet zásobovac´ıch cykl˚ u náklady na poˇr´ızen´ı jedné dodávky c2 [Kˇc/dodávka] poˇrizovac´ı náklady za dobu T [Kˇc] pr˚ umˇerná výˇse zásob [ks] jednotkové skladovac´ı náklady c1 [Kˇc/(ks rok)] celkové skladovac´ı náklady za dobu T [Kˇc] celkové náklady za dobu T

strategie I 36000 18000 2 12000,24000,9000 24,216000,240000,-

strategie II 36000 3000 12 12000,144000,1500 24,36000,180000,-

Tabulka 1.1: Parametry dvou strategi´ı.

náklady 24 Kˇc/(ks rok) (c1 ), potom dostáváme pro celkové náklady N obou strategi´ı u ´ daje obsaˇzené v tabulce 1.1. Z u ´ daj˚ u v tabulce plyne, ˇze strategie II je z hlediska celkových náklad˚ u výhodnˇejˇs´ı. Uvedené porovnán´ı vˇsak zat´ım nevypov´ıdá nic o tom, jaká vypadá optimáln´ı strategie (jaká strategie je charakterizována nejniˇzˇs´ımi celkovými náklady). Celkové náklady (1.1) jsou funkc´ı promˇenné q. Optimalizovat velikost dodávky q a t´ım minimalizovat funkci N(q) je pak prostým výpoˇctem extrému funkce N(q). Prvn´ı derivaci N(q) poloˇz´ıme rovnou 0 a nalezneme stacionárn´ı bod q ⋆ . Obr. 1.4 ilustruje situaci. Souˇctem náklad˚ u

náklady

c1+c2 N* c2 q*

0

c1

velikost dodávky

Obrázek 1.4: Nalezen´ı minima nákladové funkce. N1 (q) = c1 2q · T [Kc/rok], coˇz je pˇr´ımka, a náklad˚ u N2 (q) = c2 Qq [Kc/rok], coˇz je hyperbola, dostáváme graf celkových náklad˚ u N(q). Poloˇzme prvn´ı derivaci N(q) podle q rovnu 0, dN c1 c2 Q = · T − 2 = 0. dq 2 q

(1.2)

ˇ sen´ım (stacionárn´ım bodem) je Reˇ ∗

q =

r

2Qc2 [ks]. c1 T 9

(1.3)

Vzhledem k faktu, ˇze

d2 N 2c2 Q = 3 > 0, 2 dq q

je N ∗ = N(q ∗ ) minimum funkce N(q) a q ∗ je optimáln´ı velikost dodávky. Rovnice (1.2) se nazývá Wilson˚ uv vzorec. Potom plat´ı, ˇze (ponecháno jako cviˇcen´ı): 1. Pro q ∗ je N1 (q ∗ ) = N2 (q ∗ ) a bod [q ∗ , N1 (q ∗ )], je pr˚ useˇc´ıkem graf˚ u N1 a N2 . 2. Pro minimáln´ı hodnotu náklad˚ u plat´ı (dosazen´ım q ∗ ze vztahu 1.3 do vztahu 1.1) p (1.4) N ∗ = 2Qc1 c2 T [Kˇc].

3. Pro optimáln´ı délku cyklu t∗ plat´ı (vzhledem ke t∗ =

Q q

= Tt ), ˇze

q∗ T [rok]. Q

(1.5)

Bod znovuobjedn´ avkyi (signáln´ı u ´ roveˇ n zásoby) r ∗ udává, pˇri jakém poˇctu jednotek na skladu mus´ıme vystavit objednávku, aby k doplnˇen´ı skladu doˇslo v okamˇziku vyˇcerpán´ı skladové zásoby. Bod znovuobjednávky lze vyjádˇrit jako r∗ = Q · d − m · q∗,

(1.6)

kde souˇcin Q · d je poptávka za dobu dodac´ı lh˚ uty d a m je celoˇc´ıselná ˇcást pod´ılu td∗ . Souˇcin m · q ∗ odeˇc´ıtáme proto, ˇze dodac´ı lh˚ uta m˚ uˇze být obecnˇe delˇs´ı neˇz je délka cyklu t∗ . Vrat’me se k pˇr´ıkladu a uved’me jeho optimáln´ı parametry. Pˇ r´ıklad 3b. Pokraˇcován´ı Pˇr´ıkladu 3 se shodnými parametry. Urˇc´ıme optimáln´ı parametry modelu. q q 2Qc2 ∗ q = = 2·36000·12000) = 6000 ks, c1 T √24·1 √ ∗ N = 2Qc1 c2 T = 2.36000.12000.24.1 = 144000 Kˇc. Optimáln´ı velikost dodávky je tedy 6000 ks a s n´ı souvisej´ıc´ı celkové náklady jsou 144000 Kˇc. Vzhledem k tomu, ˇze roˇcn´ı poptávka je 36000 ks, bude interval mezi dodávkami t∗ =

q∗ 6000 ·T = = 1/6 roku = 2 mˇes´ıce. Q 36000

Poˇrizovac´ı lh˚ uta dodávky d byla v zadán´ı u ´ lohy stanovena na 1/2 mˇes´ıce (= 1/24 roku). Oˇcekávaná poptávka v tomto obdob´ı je Qd = 36000/24 = 1500 ks. Protoˇze je zbytek po dˇelen´ı hodnoty 1500 (Qd) hodnotou 6000 (q ∗ ) roven 1500, je tˇreba vystavit objednávku vˇzdy v okamˇziku, kdy klesne stav skladu na u ´ roveˇ n 1500 ks (bod znovuobjednávky r ∗ = 1500 ks). Optimáln´ı poˇcet dodávkových cykl˚ u vztahuj´ıc´ı se k optimáln´ı velikosti dodávky lze spoˇc´ıtat jako T Q n∗ = ∗ = ∗ [dodávka]. t q

10

Pozn´ amka. Parametry q ∗ , t∗ , n∗ mohou být obecnˇe reálná ˇc´ısla. V nˇekterých pˇr´ıpadech mohou vzniknout poˇzadavky na jejich celoˇc´ıselnost - nejˇcastˇeji u poˇctu cykl˚ u. V tomto pˇr´ıpadˇe vezmeme obˇe sousedn´ı celoˇc´ıselné hodnoty n1 = ⌈n∗ ⌉, n2 = ⌈n∗ ⌉ + 1. a jako optimáln´ı vybereme hodnotu, pro kterou budou celkové náklady (1.1) niˇzˇs´ı. Dodateˇcné zásoby na celoˇc´ıselnost q ∗ a t∗ mohou vést na v praxi nerealizovatelné ˇreˇsen´ı (neceloˇc´ıselná ˇ velikost zásob ˇci neceloˇc´ıselné intervaly dodávek). Casto je výhodnˇejˇs´ı volit q a t celoˇc´ıselné a n neceloˇc´ıselné s t´ım, ˇze nebudou po uplynut´ı periody T zcela vyˇcerpané zásoby (viz následuj´ıc´ı pˇr´ıklady [6]). Pˇ r´ıklad 4. Bˇehem doby T = 1 rok = 240 pracovn´ıch dn˚ u ˇcin´ı poptávka po urˇcitém druhu zboˇz´ı Q = 720 kus˚ u. Intenzita poptávky je rovnomˇerná. Jednotkové náklady na skladován´ı necht’ Kˇc , tj. pˇribliˇznˇe 0, 0083 Kˇc , jednotkové nab´ıhaj´ı pouze v pracovn´ıch dny, a jsou c1 = 2 ks·rok ks·den náklady na objednávku jsou c2 = 20 Kˇc/dodávka. Vypoˇctˇete d˚ uleˇzité charakteristiky modelu. ˇ sen´ı: Optimáln´ı výˇse dodávky je Reˇ r r 2c Q 2 · 20 · 720 √ 2 q∗ = = = 14400 = 120 ks. c1 T 2·1 Optimáln´ı náklady vypoˇcteme dosazen´ım do (1), p √ √ N(q ∗ ) = 2c1 c2 T Q = 2 · 2 · 20 · 1 · 720 = 57600 = 240 Kˇc.

Proved’te u výˇse uvedených vztah˚ u rozmˇerovou analýzu. Optimáln´ı poˇcet cykl˚ u je n∗ = qQ∗ = ∗ 720 = 6 dodávek. Optimáln´ı délka cyklu dle (1.5) je t∗ = qQT · T = nT∗ = 240 = 40 pracovn´ıch 120 6 dn˚ u. Pozn´ amka. Výsledky pˇr´ıkladu 4 jsou celoˇc´ıselné ve vˇsech promˇenných n∗ , q ∗ , t∗ . V následuj´ıc´ım pˇr´ıkladˇe ukáˇzeme jak postupovat, jestliˇze nˇekterá z uvedených veliˇcin bude neceloˇc´ıselná a pˇritom bude kladen poˇzadavek na jej´ı celoˇc´ıselnost. Pˇ r´ıklad 5. Bˇehem doby T = 1 ˇctvrtlet´ı = 90 pracovn´ıch dn˚ u ˇcin´ı poptávka po urˇcitém druhu zboˇz´ı Q = 90000 ksM. Poptávka po výrobku je rovnomˇerná. Jednotlivé náklady na skladován´ı Kˇc . Jednotkové náklady na objednávku jsou c = 20 Kˇc/dodávka. Vypoˇctˇete jsou c1 = 0, 005 denks 2 d˚ uleˇzité charakteristiky modelu. Budeme poˇzadovat celoˇc´ıselný poˇcet dodávek za ˇctvrtlet´ı. ˇ sen´ı: Optimáln´ı výˇse dodávky je Reˇ r r 2c2 Q 2 · 20 · 90000 ∗ q = = = 2828 ks. c1 T 0, 005 · 90 Minimálná skladovac´ı a poˇrizovac´ı náklady p p N ∗ = 2Qc1 c2 T = 2 · 90000 · 0, 005 · 20 · 90 = 1272, 79 Kˇc.

Poptávka po výrobku za den je

90000 ks Q = = 1000 . T 90 den 11

Optimáln´ı poˇcet cykl˚ u za rok je n∗ =

Q 90000 T = 1 = 31, 82. ∗ q 2828, 43

Poˇcet dodávek je neceloˇc´ıselný. Optimáln´ı poˇcet cykl˚ u leˇz´ı mezi dvˇema pˇr´ıpustnými celoˇc´ıselnými 1 = 2903 ks, resp. hodnotami, tj. n1 = 31, resp. n2 = 32. Dostáváme q1 = nQ1 T = 90000 31 Q 90000 q2 = n2 T = 32 1 = 2813 ks. N(q1 ), resp. N(q2 ) mus´ıme ovˇsem poˇc´ıtat dle základn´ıho vzorce (1.1), nikoliv dle (), protoˇze vztah () je urˇcen pro výpoˇcet optimáln´ıch náklad˚ u: N(q1 ) = 0, 005 N(q2 ) = 0, 005

2903 90000 90 + 20 = 1273, 23 Kˇc. 2 2903

2813 90000 90 + 20 = 632, 81 + 640, 00 = 1272, 81 Kˇc. 2 2812, 50

Protoˇze N(q2 ) < N(q1 ), je optimáln´ı celoˇc´ıselný poˇcet cykl˚ u n∗ = n2 = 32. Intervaly dodávek 90 T 90 T jsou t1 = n1 = 31 = 2.90 dne, t2 = n2 = 32 = 2.81 dne. Z teoretického hlediska neceloˇc´ıselnost hodnot q ∗ , t∗ nebo n∗ nevad´ı. Z praktického hlediska vˇsak m˚ uˇzeme vyˇzadovat celoˇc´ıselnost poˇctu dodávek, dodávky s definovanou ˇcasovou periodou (napˇr. dodávky pouze kaˇzdé pondˇel´ı), nebo dodávky v definovaných kvantech (napˇr. v celoˇc´ıselných násobc´ıch 50-ti kus˚ u). Vˇenujme se nyn´ı citlivosti nákladové funkce. Srovnáme-li optimáln´ı náklady N ∗ (q) s náklady N(q) plynouc´ımi z pouˇzit´ı jiné neˇz optimáln´ı strategie, z´ıskáme c1 2q T + c2 Qq N(q) 1 = = √ ∗ N (q) 2 2Qc1 c2 T

q∗ q + ∗ q q

.

Vztah odvod’te. Je zˇrejmé, ˇze pomˇer NN∗(q) nen´ı závislý na velikostech fixn´ıch ani variabiln´ıch (q) náklad˚ u, ani na poptávce. Ze vztahu plyne, ˇze velikost dodávky vyˇsˇs´ı o urˇcité procento neˇz dodávka optimáln´ı vede k niˇzˇs´ım náklad˚ um neˇz dodávka o shodné procento niˇzˇs´ı neˇz dodávka optimáln´ı. Jinak ˇreˇceno, náklady strategie zásobován´ı, pˇri n´ıˇz sn´ıˇz´ıme velikost dodávky o x procent oproti velikosti optimáln´ı dodávky se rovnaj´ı náklad˚ um strategie zásobován´ı pˇri n´ıˇz zvýˇs´ıme velikost dodávky o y procent oproti velikosti optimáln´ı dodávky, pˇriˇcemˇz vˇzdy plat´ı, ˇze x < y. Pˇ r´ıpad v´ıce poloˇ zek Výˇse uvedený model uvaˇzuje jediný druh zásoby. V praxi se ˇcasto praktikuje dovoz v´ıce druh˚ u materiálu ˇci zboˇz´ı, z nichˇz kaˇzdý má jiný optimáln´ı interval (napˇr. r˚ uzné velikosti obálek v kanceláˇri). Uvaˇzujme m skladových poloˇzek, které mohou být objednány a dodány spoleˇcnˇe, tedy poˇcet cykl˚ u je pro vˇsechny druhy spoleˇcný, n=

Q1 Qm = ... = [dodávek], q1 qm

kde Qi oznaˇcuje poptávku [ks/rok], qi oznaˇcuj´ı velikost jedné dodávky pro i-tou poloˇzku [ks]. Náklady na objednávku c2 [Kˇc/dodávka] jsou spoleˇcné pro vˇsech m poloˇzek. Jednotkové skladovac´ı náklady c1i [Kˇc/ks rok] jsou souˇctem náklad˚ u i-té poloˇzky. Je výhodné volit objednávky a dodávky tak, aby zásoby kaˇzdé poloˇzky byly vyˇcerpány spoleˇcnˇe. Na obr. 1.5 je znázornˇen pr˚ ubˇeh stavu zásoby pro dvˇe poloˇzky. Celkové náklady je tˇreba opˇet vyjádˇrit jako funkci jedné promˇenné. Jako rozhodovac´ı promˇennou je výhodnˇejˇs´ı volit délku periody t (ˇci poˇcet cykl˚ u) neˇzli velikosti dodávek qi . 12

stav zásoby

q1

q2

... t

3t

2t

T

èas

Obrázek 1.5: Pr˚ ubˇeh stavu zásob jednotlivých poloˇzek v závislosti na ˇcase. Skladovac´ı náklady pro m poloˇzek za dobu T jsou N1 (q) =

m X

c1i qi

i=1

T [Kˇc]. 2

Pro vyjádˇren´ı náklad˚ u jako funkce ˇcasu vyuˇzijme vztahu Qi T = = poˇcet cykl˚ u n. qi t Dostáváme N1 (t) =

m X

c1i

i=1

Náklady na objednávku jsou

N2 (t) = c2

Qi t [Kˇc]. 2

T [Kˇc]. t

Celkové náklady jsou souˇctem náklad˚ u N1 a N2 , N(t) = N1 (t) + N2 (t) =

m X i=1

c1i

Qi t T + c2 . 2 t

(1.7)

Poloˇzme opˇet prvn´ı derivaci funkce (1.7) podle ˇcasu t rovnou 0, dN = 0, dt a z´ıskáme stacionárn´ı bod (ovˇeˇrte) t∗ =

s

2c T Pm 2 [rok]. i=1 c1i Qi

Pomoc´ı druhé derivace N(t) ovˇeˇr´ıme, ˇze se jedná o minimum (proved’te). Pro optimáln´ı velikost objednávky i-té poloˇzky pak plat´ı: Qi [ks] qi∗ = t∗ T a optimáln´ı poˇcet cykl˚ u je T n∗ = ∗ [dodávek]. t 13

Pozn´ amka. Plat´ı analogické u ´ vahy o celoˇc´ıselnosti ˇreˇsen´ı (viz minulou poznámku).

Model 2 Na rozd´ıl od modelu 1 pˇripouˇst´ıme moˇznost nesplnˇen´ı dodávek (a neuspokojen´ı poptávky) z d˚ uvodu pˇrechodného nedostatku zásob na skladˇe. To s sebou pˇrináˇs´ı dodateˇcné náklady (bud’ se poptávka uspokojuje nestandardn´ım zp˚ usobem – zboˇz´ı si napˇr. p˚ ujˇc´ıme od jiného dodavatele a zase jej mus´ıme vrátit – nebo se poptávka a jej´ı uspokojen´ı odloˇz´ı). Na obr. 1.6 je tato situace znázornˇena. Dodávkový cyklus se rozpadá na dva intervaly t1 a t2 . V prvn´ım z nich docház´ı k stav zásoby

q-s èerpání zásoby

...

t2 s

èas

t1 neuspokojená poptávka

Obrázek 1.6: Pr˚ ubˇeh stavu zásob jednotlivých poloˇzek v závislosti na ˇcase pro Model 2. normáln´ımu ˇcerpán´ı zásob ze skladu. V druhém intervalu zásoba na skladˇe nen´ı a poptávka po zásobách nen´ı uspokojena. Velikost nerealizovaného ˇcerpán´ı zásob (neuspokojené poptávky) v ˇcasovém intervalu t2 oznaˇcme jako s [ks]. Pˇredpokládáme, ˇze tato nerealizovaná poptávka bude uspokojena ihned pˇri pˇr´ıˇst´ı dodávce na sklad. Z objemu dodávky q bude okamˇzitˇe vyrovnán deficit s jednotek a stav zásob tedy vzroste na q − s. Ostatn´ı pˇredpoklady jsou stejné jako u modelu 1. C´ılem je nalézt optimáln´ı velikost dodávky q ∗ a optimáln´ı výˇsi neuspokojené poptávky s∗ , které budou minimalizovat celkové náklady. Náklady se skládaj´ı ze tˇr´ı poloˇzek, N(q, s) = N1 (q, s) + N2 (q, s) + N3 (q, s) [Kˇc], kde jsou: • N1 (q, s) skladovac´ı náklady (variabiln´ı) N1 (q, s) = c1

q−s Q t1 [Kˇc], 2 q

• N2 (q, s) poˇrizovac´ı náklady (fixn´ı) na dodávky N2 (q, s) = c2 14

Q [Kˇc], q

(1.8)

• N3 (q, s) náklady z nedostatku zásoby s Q N3 (q, s) = c3 t2 [Kˇc], 2 q kde c3 jsou jednotkové náklady z nedostatku zásob za jednotkovou dobu [Kˇc/ks.rok]. u (ostatn´ı ˇcinitelé tedy vyjadˇruj´ı dané náklady na jeden Ve vˇsech vzorc´ıch je Qq = n poˇcet cykl˚ cyklus). Celkové náklady (1.8) jsou souˇctem tˇechto tˇr´ı poloˇzek, N(q, s) = (c1

q−s s Q t1 + c2 + c3 t2 ) . 2 2 q

(1.9)

Promˇenné t1 a t2 ve vzorci (1.9) lze vyjádˇrit pomoc´ı promˇenných q, s, Q na základˇe známých vztah˚ u q t1 + t2 = t = T Q a podobnosti troj´ uheln´ık˚ u na obr. 1.6 (ovˇeˇrte!): N(q, s) = c1

(q − s)2 Q s2 T + c2 + c3 T. 2q q 2q

(1.10)

Pro nalezen´ı stacionárn´ıho bodu (q ∗ , s∗ ) funkce N(q, s) je tˇreba poloˇzit prvn´ı parciáln´ı derivace rovny nule, ∂N ∂N = = 0. ∂q ∂s Pˇr´ıklad je ponechán jako cviˇcen´ı (je tˇreba rovnˇeˇz ukázat, ˇze Hessián funkce N(q, s) je v bodˇe (q ∗ , s∗ ) pozitivnˇe definitn´ı, pak je N ∗ = N(q ∗ , s∗ ) minimem funkce N(q, s)). Výpoˇctem dostáváme optimáln´ı výˇsi dodávky a neuspokojené poptávky, q q c1 +c3 2 [ks], q ∗ = 2Qc c1 T c3 (1.11) 1 s∗ = q ∗ c1c+c [ks]. 3 Optimáln´ı výˇse dodávky q ∗ je vlastnˇe souˇcinem optimáln´ı dodávky u modelu 1 a konstanty, která závis´ı na parametrech c1 a c3 . Dosazen´ım optimáln´ıho ˇreˇsen´ı (1.11) do vzorce (1.10) dostáváme minimáln´ı hodnotu nákladové funkce, r p c3 ∗ N = 2Qc1 c2 T [Kˇc]. (1.12) c1 + c3 Snadno nahlédneme, ˇze optimáln´ı náklady N ∗ jsou souˇcinem optimáln´ıch náklad˚ u z modelu 1 √ a α, kde c3 [1]. (1.13) α= c1 + c3 √ Konstanta α je menˇs´ı neˇz 1, tud´ıˇz i α je menˇs´ı neˇz 1, a proto jsou optimáln´ı náklady u modelu 2 vˇzdy menˇs´ı neˇz u modelu 1. Ze vztahu t = Qq T z´ıskáme optimáln´ı délku dodávkového cyklu, q∗ t∗ = T = Q

s

2c2 T √ α [rok]. Qc1

15

(1.14)

Bod znovuobjednávky r ∗ se vypoˇcte stejnˇe jako v modelu 1 jako zbytek po dˇelen´ı Qd (kde Qd q∗ je oˇcekávaná poptávka). Je vˇsak tˇreba tento výsledek sn´ıˇzit o optimáln´ı objem neuspokojené poptávky s∗ . Vrat’me se k definici konstanty α. Plat´ı α=

t1 , t

a koeficient α vlastnˇe vyjadˇruje hodnotu pravdˇepodobnosti uspokojen´ı poptávky. Podobnˇe m˚ uˇzeme definovat pravdˇepodobnost, ˇze poˇzadavek bude muset ˇcekat na uspokojen´ı aˇz do dalˇs´ı objednávky, jako t2 s∗ c1 β= = = ∗. (1.15) t c1 + c3 q Zˇrejmˇe plat´ı α + β = 1, a jsou li pevnˇe dané skladovac´ı náklady, pravdˇepodobnosti α, β pak závisej´ı na nákladech z d˚ uvodu neuspokojené poptávky c3 . Bude-li hodnota c3 ≫ c1 , α bude bl´ızká 1 a β se bude bl´ıˇzit 0, t´ım pádem i výˇse neuspokojené poptávky s∗ bude bl´ızko 0 (je jasné, ˇze vzhledem k vysokým náklad˚ um c3 chceme v tomto pˇr´ıpadˇe co nejv´ıce omezit dobu neuspokojené poptávky). Pozn´ amka. Pˇri analýze skladovac´ıho systému m˚ uˇzeme ˇreˇsit u ´ lohu stanoven´ı velikosti c3 tak, aby byla pravdˇepodobnost vyˇcerpán´ı skladu β menˇs´ı neˇz stanovená mez β ∗ , c1 ≤ β∗ c1 + c3

⇒

c3 ≥

c1 (1 − β ∗ ) . β∗

Pozn´ amka. Jako cviˇcen´ı je ponechán výpoˇcet charakteristik systému z pˇr´ıkladu 5. Porovnejte výsledky s modelem 1. Pˇ r´ıklad 6. Výpoˇcet základn´ıch charakteristik modelu 2 budeme ilustrovat na naˇsem pˇr´ıkladu. Hodnota nákladových parametr˚ u je v tomto pˇr´ıkladu c1 = 24 Kˇc/ks rok, c2 = 12000 Kˇc/dod´ avka a c3 = 50 Kˇc/ks rok. Dosazen´ım do vztah˚ u (1.13) a (1.15) z´ıskáme pravdˇepodobnosti uspokojen´ı resp. neuspokojen´ı poptávky: 50 3 = 50+24 = 0, 6757 [1] α = c1c+c 3 . β = 1 − α = 0, 3243 [1].

Optimáln´ı výˇse dodávky q ∗ , optimáln´ı výˇse neuspokojené poptávky s∗ a maximáln´ı výˇse zásoby na skladu q ∗ − s∗ je po dosazen´ı do (1.11): q q √ 2(36000)(12000) 24+50 ∗ = 6000 1, 48 = 7299 ks q = 24·1 50 s∗ = q ∗ β = 7299 · 0, 3243 = 2367 ks q ∗ − s∗ = 7299 − 2367 = 4932 ks. Pro spoleˇcnost Fruta, a.s. by podle tohoto výsledku bylo rozumné, kdyby k doplnˇen´ı skladu doˇslo v okamˇziku, kdy poˇcet neuspokojených poˇzadavk˚ u bude roven 2367 ks kartón˚ u plastikových lahv´ı. Protoˇze je oˇcekávaná poptávka v pr˚ ubˇehu poˇrizovac´ı lh˚ uty zásob Qd rovna 1500 ks (viz. pˇredcházej´ıc´ı model), bude bod znovuobjednávky r ∗ = 1500 − s∗ = 1500 − 2367 = −867 ks (1500 je zbytek po dˇelen´ı hodnoty Qd hodnotou q ∗ ). Objednávku je tedy tˇreba vystavit vˇzdy v okamˇziku, kdy poˇcet neuspokojených poˇzadavk˚ u dosáhne u ´ rovnˇe 867 ks.

16

Náklady souvisej´ıc´ıch s uvedenou optimáln´ı strategi´ı jsou p p √ N ∗ = 2Qc1 c2 T α = 144000 0, 6757 = 118369 Kˇc.

a jsou o 25631 Kˇc niˇzˇs´ı neˇz v modelu 1. ∗ 7299 Optimáln´ı délka dodávkového cyklu je t∗ = qQ T = 36000 = 0.20276 roku. Kdybychom uvaˇzovali v roce 240 pracovn´ıch dn´ı, potom je délka dodávkového cyklu pˇribliˇznˇe 49 pracovn´ıch dn´ı.

Model 3 Model 1 pˇredpokládal poˇr´ızen´ı série výrobk˚ u ˇci doplnˇen´ı sklad˚ u v zanedbatelnˇe krátkém ˇcase. To je vˇetˇsinou pravda pˇri dovozu na sklad zvenˇc´ı, ne vˇsak napˇr. pˇri výrobˇe na sklad. Model 3, tzv. produkˇ cn´ı, má stejné pˇredpoklady jako model 1, ovˇsem doplnˇen´ı skladu nen´ı jednorázové – dodávka pˇricház´ı na sklad po urˇcitý ˇcas. Dodávkový cyklus se rozpadá na dva intervaly - v´ yrobn´ı a spotˇ rebn´ı cyklus. Pˇrirozený je

Obrázek 1.7: Pr˚ ubˇeh stavu zásob v produkˇcn´ım modelu. poˇzadavek, aby byla výroba rychlejˇs´ı neˇz spotˇreba. Ve výrobn´ım cyklu o délce t1 se rovnomˇernˇe doplˇ nuje sklad a zárovˇen ˇ ˇcerpaj´ı zásoby. Ve spotˇrebn´ım cyklu délky t2 se pouze dodává zásoba ze skladu. Nepˇredpokládáme moˇznost vzniku nedostatku zásoby. Chceme minimalizovat náklady potˇrebné k výrobˇe k výrobˇe série (realizace v´ yrobn´ı d´ avky) a skladován´ı za dobu T . Náklady tvoˇr´ı dvˇe poloˇzky – skladovac´ı (variabiln´ı), resp. výrobn´ı (fixn´ı) náklady jedné výrobn´ı dávky. Jednotkové výˇse uvedené náklad˚ u za rok oznaˇcme c1 [Kˇc/ks rok] , resp. c2 [Kˇc/dodávka]. Mus´ıme tedy urˇcit hodnoty objemu výrobn´ı dávky q a ˇcasové intervaly t1 , t2 tak, aby se pokryla poptávka Q a minimalizovaly náklady. [ks/rok]. Pˇri poptávce Q Oznaˇcme K [ks] kapacitu výroby za ˇcas T . Rychlost výroby je pak K T Q je rychlost spotˇreby T [ks/rok]. Obrázek 1.8 znázorˇ nuje podrobnˇeji jeden výrobnˇe – spotˇrebn´ı cyklus. Parametry uˇz´ıvané v tomto modelu jsou: T sledované obdob´ı [rok], c1 jednotkové skladovac´ı náklady za jednotkovou dobu [Kˇc/ks rok], c2 poˇrizovac´ı náklady jedné výrobn´ı dávky [Kˇc/dodávka], 17

stav zásoby

q s

t1

t2

èas

Obrázek 1.8: Závislost stavu zásoby na ˇcase pro Model 3. q velikost jedné výrobn´ı dávky [ks], s velikost skladových zásob po ukonˇcen´ı výrobn´ıho cyklu [ks], Q velikost poptávky za dobu T [ks], K kapacita výroby za dobu T [ks], s 2

pr˚ umˇerná velikost zásob,

n=

Q q

poˇcet cykl˚ u [1 dodávka],

t délka cyklu [rok], t1 délka výrobn´ıho cyklu [rok], t2 délka spotˇrebn´ıho cyklu [rok], N skladovac´ı a poˇrizovac´ı náklady za dobu T [Kˇc], d poˇrizovac´ı lh˚ uta výrobn´ı dávky [rok], Snadno nahlédneme, ˇze na konci výrobn´ıho cyklu je na skladˇe zásoba s (mnoˇzstv´ı q se vyrobilo, q −s se dodalo na trh). Protoˇze rychlost výroby, rychlost plnˇen´ı skladu a rychlost vyskladˇ nován´ı je stejné bˇehem jednoho cyklu jako za celé obdob´ı T , plat´ı q K s K−Q s Q = , = , = . t1 T t1 T t2 T

(1.16)

Celkové náklady lze zapsat jako N(q) = c1 .(pr˚ umˇerná výˇse zásoby) · T + c2 .(poˇcet cykl˚ u za ˇcas T ) [Kc]. Z vzorc˚ u (1.16) z´ıskáme vztah mezi s a q, s=

K−Q Tq K − Q Q t1 = = q(1 − ). T K T K

Pr˚ umˇerná výˇse zásoby je polovina souˇctu maximáln´ı a minimáln´ı zásoby. Minimáln´ı zásoba je 0, proto je pr˚ umˇerná výˇse zásoby rovna (1 −

Q q )T . K 2 18

Poˇcet cykl˚ u je roven

q . Q

Nákladová funkce má tedy tvar N(q) = c1 (1 −

Q Q q )T + c2 . K 2 q

(1.17)

Obvyklým postupem nalezneme optimáln´ı hodnotu výrobn´ı dávky, s r 2Qc2 K q∗ = . c1 · T K − Q Výpoˇcet je ponechán jeho cviˇcen´ı. Optimáln´ı délka cyklu je t∗ =

q∗ · T, Q

minimáln´ı náklady jsou r

K−Q . K V modelu 3 lze zavést poˇrizovac´ı lh˚ utu potˇrebnou k pˇr´ıpravˇe nové výrobn´ı dávky d (podobnˇe jako jsme zavedli poˇrizovac´ı lh˚ utu dodávky u modelu 1). Dle hodnoty d m˚ uˇzeme urˇcit bod r ∗ , obdobu bodu znovuobjednávky z modelu 1. Zavedeme-li jeˇstˇe veliˇciny intenzitu v´ yroby p (maximáln´ı poˇcet vyrobených jednotek zboˇz´ı za ˇcas, napˇr. kapacita výrobn´ı linky) a intenzitu spotˇ reby h (dle odbytu poˇzadovaný poˇcet vyrobených jednotek zboˇz´ı za ˇcas), mohou nastat dva pˇr´ıpady (pˇrirozenˇe pˇredpokládáme d < t): p N ∗ = 2Qc2 c1 T

1. d ≤ t2 ⇒ bod, ve kterém je tˇreba zaˇc´ıt s pˇr´ıpravou nové dávky, spadá do spotˇrebn´ıho cyklu a je roven pˇr´ımo poptávce za dobu d, tzn. r ∗ = hd. 2. d > t2 ⇒ bod, ve kterém je tˇreba zaˇc´ıt s pˇr´ıpravou nové dávky, spadá do výrobn´ıho cyklu; hodnotu r ∗ lze potom vyjádˇrit jako (p − h)(t − d). Pˇ r´ıklad 7. Upravme zadán´ı pˇr´ıkladu 6. Pˇredpokládejme, ˇze spoleˇcnost Fruta, a.s. má k dispozici vlastn´ı recyklaˇcn´ı linku na produkci plastových lahv´ı s kapacitou 5400 ks kartón˚ u lahv´ı mˇes´ıˇcnˇe (pokud by linka pracovala nepˇretrˇzitˇe). Mˇes´ıˇcn´ı potˇreba je vˇsak pouze 3000 ks kartón˚ u (36000 ks roˇcnˇe). Intenzita výroby je tedy p = 5400 ks/mˇes´ıc, intenzita spotˇreby h = 3000 ks/mˇes´ıc. Nákladové poloˇzky z˚ ustávaj´ı definované ve stejné výˇsi jako v p˚ uvodn´ım pˇr´ıkladu – skladovac´ı náklady na 1 rok a kartón jsou c1 = 24 Kˇc/(ks rok) a fixn´ı náklady souvisej´ıc´ı s pˇr´ıpravou jedné výrobn´ı dávky jsou c2 = 12000 Kˇc/dodávka. Doba, kterou si vˇzdy vyˇzádá pˇr´ıprava dalˇs´ı výrobn´ı dávky, je d = 1/2 mˇes´ıce. Urˇc´ıme optimáln´ı velikost výrobn´ı dávky, celkové roˇcn´ı náklady, dobu cyklu, dobu výrobn´ıho a spotˇrebn´ıho cyklu a mnoˇzstv´ı na skladˇe, pˇri kterém je nutné objednat novou výrobn´ı dávku. Pro urˇcen´ı optimáln´ıch charakteristik takto definovaného systému staˇc´ı dosadit jeho parametry do vztah˚ u, které jsme odvodili výˇse. Optimáln´ı objem výrobn´ı dávky a s t´ım souvisej´ıc´ı náklady jsou q q √ 5400·12 q ∗ = 2(36000)(12000) = 6000 2.25 = 9000 ks, 24 5400·12−3000·12 q . = 96000 Kˇ c . N ∗ = 14400 5400−3000 5400

Optimáln´ı délka intervalu mezi dvˇema dodávkami je t∗ =

q∗ 9000 1 T = 1 = roku = 3 mˇes´ıce. Q 36000 4 19

Z toho výrobn´ı cyklus trvá t1 = qp = 9000 = 35 mˇes´ıce, spotˇrebn´ı cyklus pak bude t2 = 3 − 53 = 43 5400 mˇes´ıce. Protoˇze d = 12 < t2 , staˇc´ı zaˇc´ıt s pˇr´ıpravou nové dávky tehdy, pokud zásoba v rámci spotˇrebn´ıho cyklu klesne na u ´ roveˇ n r ∗ = hd = 3000 = 1500 ks kartón˚ u. 2 ∗

Model 4 Tento model popisuje situaci, ve které je moˇznost nákupu zboˇz´ı na sklad s mnoˇzstevn´ı slevou. Cena za jednotku zboˇz´ı se sniˇzuje v závislosti na nakoupeném mnoˇzstv´ı, hovoˇr´ıme o tzv. cenové degresi. Budeme uvaˇzovat pˇr´ıpad, kdy pˇri objednán´ı mnoˇzstv´ı, které pˇresáhne jistou velikost, z´ıskáme celé za výhodnˇejˇs´ı cenu. S výjimkou ceny mˇen´ıc´ı se s mnoˇzstv´ım objednaného zboˇz´ı uvaˇzujeme stejné pˇredpoklady jako u Modelu 1, tj. rovnomˇernou a konstantn´ı poptávku, pravidelné konstantn´ı dodávky ve stejných intervalech a doplnˇen´ı skladu v jednom ˇcasovém okamˇziku. Skladovac´ı náklady c1 budeme v tomto pˇr´ıpadˇe vyjadˇrovat pomˇernou ˇcást´ı z celkové hodnoty zásob za jednotku ˇcasu [1/rok]. Tuto veliˇcinu lze samozˇrejmˇe pˇrevést na procentn´ı sazbu z celkové hodnoty za jednotku ˇcasu [%/rok]. Takto lze ohodnotit i kapitál vázaný v zásobách. Abychom mohli vyjádˇrit skladovac´ı náklady, je nutné zavést dalˇs´ı veliˇcinu, a to cenu za jednotku objednaného zboˇz´ı. Oznaˇcme ki cenu jednotky zboˇz´ı [Kˇc/ks], pokud objednané mnoˇzstv´ı q ∈ hqi , qi+1 ). Pro ceny ki plat´ı, ˇze ki > ki+1 , resp. ki−1 > ki , ˇ ıkáme tedy to, ˇze se vzr˚ R´ ustaj´ıc´ım objednaným mnoˇzstv´ım klesá v pˇredem definovaných intervalech hqi , qi+1 ) jednotková cena zboˇz´ı. Vyjádˇreme nyn´ı náklady spojené se zvolenou strategi´ı zásobován´ı. Je zˇrejmé, ˇze velikost náklad˚ u bude závislá na objemu objednávaného zboˇz´ı (mnoˇzstevn´ı sleva), tedy Q q · ki · T + c2 pro q ∈ hqi , qi+1 ) . (1.18) Ni (q) = c1 2 q Prvn´ı ˇclen udává skladovac´ı náklady. Pod´ıl 2q vyjadˇruje pr˚ umˇernou velikost skladové zásoby (jako u Modelu 1), souˇcin ki 2q jej´ı poˇrizovac´ı hodnotu a koneˇcnˇe c1 ki 2q skladovac´ı náklady, kdyˇz c1 jsou skladovac´ı náklady dané ˇcást´ı jejich poˇrizovac´ı hodnoty. Stejnˇe jako v pˇredchoz´ıch modelech zásob hledáme takovou velikost dodávky, pro kterou jsou náklady strategie zásobován´ı minimáln´ı. Hledáme tedy extrémy nákladových funkc´ı Ni (q). Známým postupem zjist´ıme, ˇze optimáln´ı velikost dodávek je r 2Qc2 ∗ (1.19) qi = c1 k i T a náklady s nimi souvisej´ıc´ı o velikosti Ni∗ =

p

2Qc1 c2 ki T

(1.20)

∗ ∗ Ze vztah˚ u 1.19, 1.20 vyplývá, ˇze pro ki+1 < ki je qi+1 > qi∗ a Ni+1 < Ni∗ . Z uvedené u ´ vahy vyplývá i následuj´ıc´ı postup, kterým se budeme ˇr´ıdit pˇri urˇcen´ı optimáln´ı velikosti dodávky q ∗ .

1. Uvaˇzujme, ˇze i = 1, 2, ..., n. Potom jednotková cena kn < kn−1 < ... < k2 < k1 . Jednotkové ceny ki jsou definovány v intervalech q ∈ hqi , qi+1 ). 2. Nejprve vypoˇcteme qn∗ . Tedy optimáln´ı velikost dodávky v pˇr´ıpadˇe, ˇze uvaˇzujeme nejvýhodnˇejˇs´ı cenovou relaci kn , která je definována na intervalu hqn , ∞). 20

3. Pokud qn∗ > qn , potom qn∗ = q ∗ a tedy i Nn∗ = N ∗ . 4. Pokud qn∗ < qn , potom opakujeme body 1. a 2. pro kn−1 , kn−2 , ..., ki, dokud nenajdeme takové qi∗ , pro které plat´ı, ˇze qi∗ ∈ hqi , qi+1 ). 5. Pokud Ni∗ < N(qi+1 ), potom je pro qi∗ dosaˇzeno globáln´ıho minima nákladové funkce, qi∗ je optimáln´ı velikost´ı dodávky, tedy q ∗ = qi∗ . 6. Pokud Ni∗ > N(qi+1 ), potom je globáln´ıho minima nákladové funkce dosaˇzeno pro qi+1 , optimáln´ı velikost´ı dodávky je qi+1 , tedy q ∗ = qi+1 .

Stochastick´ e modely z´ asob V deterministických modelech jsme pˇredpokládali pevnˇe danou (deterministickou) a rovnomˇernˇe rozloˇzenou poptávku. To je vˇsak v praxi ˇr´ıdkým jevem. Zde uvedeme modely uvaˇzuj´ıc´ı stochastickou poptávku.

Model 1 Model 1 uvaˇzuje stejné pˇredpoklady jako deterministický model 1, kromˇe poptávky – ta je stochastická. To znamená, ˇze výˇse poptávky v daném obdob´ı je náhodná veliˇcina s jistým pravdˇepodobnostn´ım rozdˇelen´ım. Z´ıskat toto pravdˇepodobnostn´ı rozdˇelen´ı (druh a jeho parametry) je v praxi obecnˇe velmi sloˇzité. Stochastický model 1 aproximuje situaci pomoc´ı deterministického modelu 1 tak, ˇze se celková poptávka Q (která je nyn´ı náhodná), nahrad´ı svou stˇredn´ı hodnotou µQ . Takto spoˇcteme optimáln´ı výˇsi objednávky q ∗ a optimáln´ı délku cyklu t∗ ˇci bod znovuobjednávky r ∗ . Pr˚ ubˇeh stavu zásob je zobrazen na obr. 1.9. Kdyby byla dodávka okamˇzitá (d = 0), lze se spokojit se stav zásoby

1. cyklus

2. cyklus

vystavení objednávky

q r èas

d

d vznik nedostatku

Obrázek 1.9: Pr˚ ubˇeh stavu zásoby v závislost na ˇcase. z´ıskaným výsledkem. Ovˇsem vzhledem k nenulové dodac´ı lh˚ utˇe d je tˇreba objednat dodávku v pˇredstihu (pˇri dosaˇzen´ı bodu znovuobjednávky) – pˇri rovnomˇerné poptávce pˇrijde dodávka na sklad v okamˇziku nulových zásob. Pˇri stochastické poptávce mohou ovˇsem bˇehem dodac´ı lh˚ uty snadno nastat dvˇe r˚ uzné situace – poptávka bude niˇzˇs´ı, resp. vyˇsˇs´ı neˇz pr˚ umˇerný stav. ’ Pak nastává situace 1., resp. 2 z obrázku 1.9 – bud 21

1. zbydou zásoby na skladˇe a po dodávce bude celkový stav zásob vyˇsˇs´ı neˇz q nebo 2. docház´ı k ˇcásteˇcnému neuspokojen´ı poˇzadavk˚ u - pˇri dodávce jsou nejprve tyto poˇzadavky uspokojeny a zbytek dodávky je um´ıstˇen na sklad, kde bude nyn´ı stav zásob menˇs´ı neˇz q. Nav´ıc, pokud objednáváme dodávku po dosaˇzen´ı bodu znovuobjednávky, nejsou intervaly mezi objednávkami (dodávkami) stejné. Pravdˇepodobnost, ˇze bˇehem jednoho cyklu nedojde k neuspokojen´ı poˇzadavk˚ u, se nazývá u ´roveˇ n obsluhy. Znaˇc´ıme ji γ. Obvykle poˇzadujeme, aby u ´ roveˇ n obsluhy byla dostateˇcnˇe vysoká (tj. aby pravdˇepodobnost vzniku nedostatku byla dostateˇcnˇe malá, napˇr. 0,05 – pak γ = 0, 95). Splnˇen´ı poˇzadavku na u ´ roveˇ n obsluhy lze zajistit pomoc´ı tzv. pojistn´ e z´ asoby w na skladˇe. Ta slouˇz´ı v pˇr´ıpadˇe pˇrevisu poptávky k jej´ımu pokryt´ı. ˇ s´ıme tedy u Reˇ ´ lohu: stanovit pojistnou zásobu tak, aby pravdˇepodobnost vzniku nedostatku (pravdˇepodobnost toho, ˇze poptávka nebude vyˇsˇs´ı neˇz bod znovuobjednávky plus pojistná zásoba) byla dostateˇcnˇe malá, P {Qd ≤ r ∗ + w} ≥ γ,

kde Qd je poptávka bˇehem poˇrizovac´ı lh˚ uty. Pˇredpokládejme, ˇze skuteˇcná poptávka má normáln´ı Gaussovo rozdˇelen´ı (d˚ usledek centráln´ı limitn´ı vˇety z teorie pravdˇepodobnosti) N (µ, σ) se stˇredn´ı hodnotou µ a smˇerodatnou odchylkou σ. Poptávka bˇehem poˇrizovac´ı lh˚ uty se ˇr´ıd´ı rozdˇelen´ım N (r ∗, σQd ) (parametry Q, d je potˇreba zmˇeˇrit), nebot’ stˇredn´ı hodnota veliˇciny Qd je rovna optimáln´ımu bodu znovuobjednávky r ∗ . Pro praktický výpoˇcet transformujeme veliˇcinu Q· d na veliˇcinu z, která bude popsána normovaným normáln´ım rozdˇelen´ım, Q · d ∼ N(r ∗ , σQd ) −→ z ∼ N(0, 1).

Hodnoty N (0, 1) lze totiˇz nalézt v tabulkách. Lehce lze ukázat, ˇze veliˇcina z definovaná vztahem z=

Q · d − r∗ σQd

se ˇr´ıd´ı normáln´ım normovaným rozdˇelen´ım N (0, 1). Z tabulek normáln´ıho normovaného rozdˇelen´ı urˇc´ıme, pro jaké z ∗ hodnota distribuˇcn´ı funkce N (0, 1) odpov´ıdá γ. Napˇr´ıklad γ = 0, 95 odpov´ıdá z ∗ = 1, 645. Zpˇetnou transformac´ı z´ıskáme objem poptávky bˇehem poˇrizovac´ı lh˚ uty, Q · d∗ = z ∗ σQ·d + r ∗ . Bude-li v okamˇziku objednávky zásoba na skladu Qd∗ , nenastane s pravdˇepodobnost´ı γ nedostatek zásoby. Pojistná zásoba w mus´ı splˇ novat vztah r ∗ + w ≥ Qd∗ .

Udrˇzován´ı pojistných zásob s sebou nese i zvýˇsen´ı celkových náklad˚ u (skladovac´ıch a poˇrizovac´ıch). Stˇredn´ı hodnotu tˇechto náklad˚ u lze vyjádˇrit jako p µN = 2µQ c1 c2 T + c1 w. Náklady jsou tedy souˇctem náklad˚ u vypoˇctených deterministickým modelem 1 a skladovac´ıch náklad˚ u pojistné zásoby. % 22

Pˇ r´ıklad 8. Mˇejme obdobnou jako v deterministických modelech (Fruta, a.s.). Necht’ je µQ = 36000 ks karton˚ u. Skladovac´ı náklady jsou c1 = 24 Kˇc/(ks rok), poˇrizovac´ı náklady c2 = 12000 Kˇc/dodávka. Necht’ poˇrizovac´ı lh˚ uta dodávky je d = 1/2 mˇes´ıce. Pˇredpokládejte, ˇze smˇerodatná odchylka v rámci doby d je σQd = 200 ks. Urˇcete optimáln´ı velikost dodávky, souvisej´ıc´ı náklady, bod znovuobjednávky a velikost pojistné zásoby za pˇredpokladu, ˇze u ´ roveˇ n obsluhy je poˇzadována 95 %. Jak se zmˇen´ı velikost pojistné zásoby, pokud u ´ roveˇ n obsluhy budeme poˇzadovat 99 %? Jak se zvýˇs´ı stˇredn´ı hodnota náklad˚ u, zp˚ usobená zvýˇsen´ım pojistné zásoby? q q 2µQ c2 2·36000·12000) q∗ = = = 6000 ks, c1 T 24·1 √ p N ∗ = 2µQ c1 c2 T = 2.36000.12000.24.1 = 144000 Kˇc. Optimáln´ı velikost dodávky je tedy 6000 ks a s n´ı souvisej´ıc´ı celkové náklady jsou 144000 Kˇc. Poˇrizovac´ı lh˚ uta dodávky d byla v zadán´ı u ´ lohy stanovena na 1/2 mˇes´ıce (= 1/24 roku). Oˇcekávaná poptávka v tomto obdob´ı je µQd = 1500 ks. Z tabulek normovaného normáln´ıho rozdˇelen´ı zjist´ıme, ˇze pro u ´ roveˇ n obsluhy γ = 0, 95 je hodnota 1,645. Obdobnˇe pro hodnotu γ = 0, 99 z´ıskáme hodnotu 2,327. Chceme-li udrˇzet u ´ roveˇ n obsluhy alespoˇ n na u ´ rovni 95%, mus´ıme vytvoˇrit pojistnou zásobu w ve výˇsi w ≥ z ∗ σQd = 1, 645.200 = 329 ks. Zvedneme-li u ´ roveˇ n obsluhy na hodnotu 99%, pojistná zásoba by se musela zvýˇsit na w ≥ z ∗ σQd = 2, 327.200 = 466 ks. V prvn´ım pˇr´ıpadˇe je bod znovuobjednávky r ∗ + w = 1500 + 329 = 1829 ks. Ve druhém pˇr´ıpadˇe je tˇreba vystavit objednávku v okamˇziku, kdy klesne velikost skladových zásob na 1966 ks. Stˇredn´ı hodnota náklad˚ u ve stochastickém modelu stoupne oproti deterministickému modelu o 329c1 = 7896 Kˇc pˇri u ´ rovni obsluhy 95%. Pˇri u ´ rovni obsluhy 99% stoupnou náklady o 466c1 = 11184 Kˇc.

Model 2 - optimalizace jednor´ azovˇ e vytv´ aˇ ren´ e z´ asoby V praxi m˚ uˇze nastat situace, ˇze na poˇcátku sledovaného obdob´ı vytvoˇr´ıme zásobu, kterou dále jiˇz nem˚ uˇzeme doplˇ novat (v jistém smyslu je to jeden cyklus procesu s opakuj´ıc´ımi se dodávkami). Poptávka v daném obdob´ı je popsána nˇejakým pravdˇepodobnostn´ım rozdˇelen´ım se stˇredn´ı hodnotou µ a smˇerodatnou odchylkou σ. Obvykle se pˇri popisu poptávky vycház´ı ze zkuˇsenost´ı z minulých obdob´ı ˇci z marketingových studi´ı. Je to typická situace napˇr´ıklad pro nákup sezónn´ıho zboˇz´ı na sklad (zimn´ı obleˇcen´ı, sportovn´ı potˇreby) ˇci nákup zboˇz´ı, které podléhá rychlé zkáze (ovoce, peˇcivo). Pˇredpokládejme, ˇze na poˇcátku obdob´ı vytvoˇr´ıme zásobu q. Na konci obdob´ı mohou nastat tˇri situace: 1. skuteˇ cn´ a popt´ avka Q v dan´ em obdob´ı byla menˇ s´ı neˇ zq Zásoba ve výˇsi q − Q zbyde na skladˇe. Pˇredpokládáme, ˇze zboˇz´ı má i poté nˇejakou z˚ ustatkovou hodnotu, niˇzˇs´ı neˇz nákupn´ı cena. Z˚ ustatková hodnota m˚ uˇze být i nulová, pˇr´ıpadnˇe záporná, napˇr. pokud máme náklady souvisej´ıc´ı s likvidac´ı zboˇz´ı. 23

Jednotkové náklady z nadbyteˇcné zásoby m˚ uˇzeme vyjádˇrit jako c1 = nákupn´ı cena - z˚ ustatková cena [Kc/ks]. 2. skuteˇ cn´ a popt´ avka Q v dan´ em obdob´ı byla vyˇ sˇ s´ı neˇ zq Posledn´ıch Q − q poˇzadavk˚ u z˚ ustane neuspokojených. Jednotkové náklady z nedostatku zásoby (uˇslý zisk) lze vyjádˇrit jako c2 = prodejn´ı cena - nákupn´ı cena [Kc/ks]. 3. skuteˇ cn´ a popt´ avka Q v dan´ em obdob´ı byla rovna q ˇ adné náklady ani ztráty nevznikaj´ı. Tato situace je vˇsak sp´ıˇse hypotetická. Z´ Minimáln´ı náklady (stˇredn´ı hodnota náklad˚ u) jsou dosaˇzeny, jestliˇze pro u ´ roveˇ n obsluhy γ plat´ı γ=

c2 , γ ∈ h0, 1i . c1 + c2

Optimáln´ı velikost poˇcáteˇcn´ı zásoby q ∗ je taková, pro kterou plat´ı P {Q ≤ q ∗ } ≥ γ. Poptávka m˚ uˇze být popsána spojitým ˇci diskrétn´ım pravdˇepodobnostn´ım rozdˇelen´ım. Pokud je poptávka popsána spojitým pravdˇepodobnostn´ım rozdˇelen´ım, je hodnota q ∗ t´ımto vztahem jednoznaˇcnˇe urˇcena a v tabulkách normovaného normáln´ıho rozdˇelen´ı nalezneme hodnotu z odpov´ıdaj´ıc´ı pˇr´ısluˇsné u ´ rovni obsluhyγ. Z hodnoty z zpˇetnou transformac´ı z normovaného normáln´ıho rozdˇelen´ı urˇc´ıme optimáln´ı velikost poˇcáteˇcn´ı zásoby q ∗ , q ∗ = µ + z · σ. Pokud je vˇsak rozdˇelen´ı diskrétn´ı (definováno v jednotlivých bodech – napˇr. 10 ks, 20 ks, ...), hodnotu q ∗ urˇc´ıme jako nejbliˇzˇs´ı bod z hodnot distribuˇcn´ı funkce, která splˇ nuje vztah P (q ∗ ≤ Qi−1 ) ≤ γ ≤ P (q ∗ ≤ Qi ). K intervalu hQi−1 , Qi ) jsou v tabulce pˇriˇrazeny pravdˇepodobnosti prodeje. Pˇ r´ıklad 9. Typickou u ´ lohou modelu 2 je tzv. newsboy problem, problém distributora novin [1]. Majitel stánku s novinami má na základˇe vlastn´ıch zkuˇsenost´ı zjiˇstˇeno, ˇze prodej Mladé fronty DNES ve vˇsedn´ı dny je spojitá náhodná veliˇcina s normáln´ım rozdˇelen´ım se stˇredn´ı hodnotou µ = 320 ks a smˇerodatnou odchylkou σ = 20 ks. Pokud je skuteˇcná poptávka niˇzˇs´ı neˇz poˇcet výtisk˚ u objednaných u dodavatele, ztrác´ı prodavaˇc na kaˇzdém výtisku c1 = 1 Kˇc/ks. Naopak, v pˇr´ıpadˇe vyˇsˇs´ı poptávky ztrác´ı na uˇslém zisku na kaˇzdém kusu c2 = 0, 4 Kˇc/ks. Optimáln´ı u ´ roveˇ n obsluhy je c2 γ= = 0.2857. c1 + c2 Touto hodnotou je urˇcena optimáln´ı strategie. Z tabulek normáln´ıho rozdˇelen´ı nalezneme hodnotu z odpov´ıdaj´ıc´ı pravdˇepodobnosti γ, z = −0.566. 24

poptávka pravdˇ epodobnost Qi P (q = Q) 250 0.01 260 0.02 270 0.04 280 0.05 290 0.08 300 0.09 310 0.11 320 0.13 330 0.12 340 0.10 350 0.08 360 0.07 370 0.05 380 0.03 390 0.01 400 0.01

kumulovaná pravdˇepodobnost P (Q ≤ q) 0.01 0.03 0.07 0.12 0.20 0.29 0.40 0.53 0.65 0.75 0.83 0.90 0.95 0.98 0.99 1.00

Tabulka 1.2: Pravdˇepodobnost poptávky Optimáln´ı u ´ roveˇ n objednávky je pak . q ∗ = 320 − 0.566 · 20 = 308.68 = 309 ks. Uvaˇzujme nyn´ı stejný pˇr´ıklad, ale mˇejme k dispozici pouze pravdˇepodobnosti toho, ˇze poptávka nabude diskrétn´ıch hodnot 250 − 400. Pravdˇepodobnosti jsou uvedeny v tabulce 1.2. Ve tˇret´ım sloupci jsou uvedeny kumulované pravdˇepodobnosti (hodnota distribuˇcn´ı funkce), ˇze poptávka bude niˇzˇs´ı nebo rovna dané hodnotˇe. Spojitˇe vypoˇctená optimáln´ı u ´ roveˇ n obsluhy leˇz´ı mezi hodnotami 290 ks a 300 ks, takˇze optimáln´ı poˇcáteˇcn´ı zásoba je (viz tabulka 1.2) q ∗ = 300 ks.

25

Cviˇ cen´ı a pˇ r´ıklady Cviˇ cen´ı. 1. Naleznˇete stacionárn´ı bod funkce N(q, s) popsané vzorcem (1.7) a ukaˇzte, ˇze v nˇem funkce n nabývá svého minima. 2. Vypoˇctˇete limity výraz˚ u (1.12) a (1.13) pro c3 → +∞ a c3 → 0. Co dané pˇr´ıpady popisuj´ı? Jak lze interpretovat výsledky? 3. Vypoˇctˇete charakteristiky systému z pˇr´ıkladu 5 pomoc´ı modelu 2 (α, β, q ∗, s∗ , r ∗ , N ∗ ). 4. Naleznˇete stacionárn´ı bod funkce N(q) popsané vzorcem (1.10) a ukaˇzte, ˇze v nˇem daná funkce nabývá minima. 5. Jaké základn´ı nákladové poloˇzky se vyskytuj´ı v nákladových funkc´ıch v modelech zásob? 6. Jaký je rozd´ıl mezi deterministickými a stochastick´ ymi modely zásob? 7. Co je u ´ roveˇ n obsluhy a pojistná zásoba? Jak spolu navzájem tyto dva pojmy souvisej´ı? 8. Co je c´ılem pˇri optimalizaci objemu jednorázovˇe vytváˇrené zásoby? 9. Co je to bod znovuobjednávky a poˇrizovac´ı lh˚ uta dodávky? Jaký je vzájemný vztah tˇechto dvou pojm˚ u? 10. Jak se zmˇen´ı optimáln´ı velikost dodávky ve výˇse popsaných deterministických modelech, kdyˇz celková poptávka, pˇri jinak nezmˇenˇených podm´ınkách, vzroste dvakrát? 11. Ovlivˇ nuje zmˇena ceny skladovaných jednotek u modelu 1 ˇci 2 optimáln´ı velikost dodávky a pokud ano, tak jakým zp˚ usobem? 12. Ovlivˇ nuje zmˇena poˇrizovac´ı lh˚ uty dodávky v deterministických modelech optimáln´ı velikost dodávky a pokud ano, tak jakým zp˚ usobem? Pˇ r´ıklady. 13. Obchod se stavebninami prodá roˇcnˇe 12000 padesátikilových pytl˚ u cementu. Souˇcasná strategie doplˇ nován´ı skladu je taková, ˇze se kaˇzdých 14 dn´ı objedná dodávka o objemu 500 pytl˚ u. Poˇrizovac´ı cena jednoho pytle je 80 Kˇc. Pˇredpokládejme, ˇze poptávka je rovnomˇerná v pr˚ ubˇehu celého rokua ˇze roˇcn´ı skladovac´ı náklady jednoho pytle jsou 20% z jeho poˇrizovac´ı ceny. Náklady souvisej´ıc´ı s doplnˇen´ım skladu dodávkou jakékoliv velikosti jsou fixn´ı a jsou rovny 1000 Kˇc. Vypoˇctˇete celkové skladovac´ı náklady souˇcasné strategie doplˇ nován´ı skladu.

26

Vypoˇctˇete optimáln´ı velikost dodávky, skladovac´ı náklady a délku dodávkového cyklu a porovnejte výsledky se souˇcasnými hodnotami. Jaký je v souˇcasné i v optimáln´ı strategii bod znovuobjednávky, jestliˇze je poˇrizovac´ı lh˚ uta dodávky 1 týden? Uvaˇzujte, ˇze rok má 52 týdn˚ u. 14. Jak se zmˇen´ı strategie doplˇ nován´ı skladu v pˇredcházej´ıc´ı u ´ loze, budeme-li uvaˇzovat moˇznost vzniku pˇrechodného nedostatku zásoby? V´ıme, ˇze s jednotkou nedostatku zásoby souvisej´ı ztráty ve výˇsi 30 Kˇc. 15. Pˇri analýze optimáln´ıho nastaven´ı výrobn´ıch dávek bylo zjiˇstˇeno, ˇze intenzita produkce je 8000 ks roˇcnˇe. Poptávka po produkovaných jednotkách je vˇsak pouze 2000 ks roˇcnˇe. Fixn´ı náklady, které souvisej´ı se zahájen´ım výroby v jedné výrobn´ı dávce, jsou 30000 Kˇc. Skladovac´ı náklady jedné jednotky po dobu jednoho roku jsou 160 Kˇc. Souˇcasná strategie je charakterizována t´ım, ˇze je kaˇzdé 3 mˇes´ıce spuˇstˇena nová výrobn´ı dávka v objemu 500 ks. Vypoˇctˇete celkové skladovac´ı náklady souˇcasné strategie. Vypoˇctˇete optimáln´ı velikost výrobn´ı dávky, náklady, které s optimáln´ı strategi´ı souvisej´ı, a délku výrobn´ıho a spotˇrebn´ıho cyklu. Porovnejte výsledky se souˇcasnými hodnotami. 16. Nákupn´ı stˇredisko prodává sezónn´ı výrobek za 500 Kˇc za kus. Poˇrizovac´ı cena tohoto výrobku je 350 Kˇc. Výrobky, které nebudou prodány v rámci sezony, budou nab´ızeny s 50% slevou, tj. za 250 Kˇc. Pˇredpokládejme, ˇze poptávka po uvedeném produktu za celou sezonu je rovnomˇernˇe rozdˇelená na intervalu od 300 do 800 ks. Kolik kus˚ u výrobku byste doporuˇcili objednat na zaˇcátku sezony? Jaká je pravdˇepodobnost, ˇze se vyskytne poˇzadavek na koupi tohoto výrobku po vyˇcerpán´ı skladu? Jak by se musela zmˇenit výˇse poˇcáteˇcn´ı objednávky tak, aby pravdˇepodobnost neuspokojen´ı zákazn´ık˚ u klesla pod 20%? 17. Jak by se zmˇenily odpovˇedi na otázky v pˇredcházej´ıc´ı u ´ loze, pokud by mˇela poptávka po daném produktu normáln´ı rozdˇelen´ı se stˇredn´ı hodnotou 500 ks a smˇerodatnou odchylkou 100 ks? 18. Poptávka po jistém produktu je v ˇcase rovnomˇernˇe rozdˇelena a je rovna 12000 ks roˇcnˇe. Pˇredpokládejme, ˇze poˇrizovac´ı lh˚ uta dodávky je náhodná veliˇcina s normáln´ım rozdˇelen´ım se stˇredn´ı hodnotou 12 dn˚ u a smˇerodatnou odchylkou 4 dny (bˇehem roku je 240 pracovn´ıch dn˚ u). Urˇcete bod znovuobjednávky a pojistnou zásobu tak, aby u ´ roveˇ n obsluhy byla alespoˇ n 95%.

27

Kapitola 2 S´ıt’ov´ a anal´ yza - u ´vod S´ıt’ov´ a anal´ yza je logistický obor, který se zabývá ˇr´ızen´ım projekt˚ u a popisem tˇechto sloˇzitých optimalizaˇcn´ıch a rozhodovac´ıch problém˚ u pomoc´ı teorie graf˚ u a teorie pravdˇepodobnosti. Projekt je rozsáhlá a dlouhodobá akce, která se skládá ze souboru r˚ uzných vzájemnˇe na sebe navazuj´ıc´ıch ˇ cinnost´ı. Typickými pˇr´ıklady projekt˚ u jsou: • stavebn´ı práce - stavba nového objektu (továrna, silnice, d˚ um, ...), • rekonstrukce objekt˚ u (silnice, domy, ...), • vývoj nového výrobku a jeho uveden´ı na trh, • sezónn´ı obchodn´ı ˇci reklamn´ı kampaˇ n. Obecnˇe lze projekt charakterizovat jako: • Soubor (velkého) poˇctu d´ılˇc´ıch ˇcinnost´ı, které jsou vzájemnˇe podm´ınˇené a realizovatelné v pˇresnˇe vymezeném poˇrádku a smˇeˇruj´ı k celkovému ˇreˇsen´ı stanoveného u ´ kolu. • Poˇcet celkových výstup˚ u je malý, zpravidla jeden - výstavba objektu, oprava objektu ˇci zaˇr´ızen´ı apod. • Realizace kaˇzdé d´ılˇc´ı ˇcinnosti i celého projektu je spojena s vyˇsˇs´ım stupnˇem nejistoty (ˇcasové, výˇse náklad˚ u), neˇz je tomu ve výrobn´ım procesu. Stupeˇ n nejistoty závis´ı na zkuˇsenostech z minula ˇci pˇresnosti odhad˚ u. • D´ılˇc´ı u ´ koly provádˇej´ı zpravidla r˚ uzné subjekty, proto je nutno klást d˚ uraz na jejich koordinaci. ˇ • Casov´ y plán projektu lze v jeho pr˚ ubˇehu mˇenit dle nastalé situace a pˇrizp˚ usobovat ho novým podm´ınkám (tak, aby byly náklady a ˇcas co nejkratˇs´ı). Projekty mohou m´ıt r˚ uzný rozsah - od nˇekolika týdn˚ u po nˇekolik let. Realizace projektu se skládá z postupné realizace vˇsech d´ılˇc´ıch ˇcinnost´ı, které projekt tvoˇr´ı. Kaˇzdá z tˇechto ˇcinnost´ı je pak charakterizována mnoˇzstv´ım u ´ daj˚ u: • dobou trván´ı (známou nebo odhadnutou), • náklady na realizaci (známé nebo odhadnuté), • poˇzadavky na technické, materiálové a personáln´ı zabezpeˇcen´ı, 28

• seznam ˇcinnost´ı, které musej´ı být provedeny pˇred touto ˇcinnost´ı. Je tˇreba stanovit takovou posloupnost ˇcinnost´ı, která urˇc´ı dobu trván´ı celé akce, ˇcasové rezervy jednotlivých ˇcinnost´ı, poˇrad´ı jednotlivých ˇcinnost´ı, atd. Zˇrejmé je to tˇreba u staveb, kde nelze stavˇet zed’, nejsou-li hotové základy. Obˇcas jsme bohuˇzel svˇedky toho, ˇze napˇr´ıklad pˇri opravˇe rozvod˚ u se zaˇcne do jiˇz opravené vozovky ˇci chodn´ıku znovu kopat? Je zˇrejmé, ˇze ˇcinnosti nelze provádˇet v libovolném poˇrad´ı a intenzitˇe. Je tˇreba respektovat dostupné kapacity k realizaci jednotlivých ˇcinnost´ı, poˇc´ıtat s návaznostmi ˇcinnost´ı. Sloˇzitˇejˇs´ı projekty jiˇz proto nelze ˇr´ıdit intuitivnˇe, nýbrˇz je tˇreba plánován´ı a podrobný rozvrh projektu (absence plánován´ı ˇcasto celý projekt prodraˇz´ı a zpomal´ı - viz jiˇz zm´ınˇenou znovu rozkopanou ulici). ˇ Rada optimalizaˇcn´ıch a rozhodovac´ıch problém˚ u m˚ uˇze být popsána s pouˇzit´ım grafické reprezentace dané u ´ lohy. K rozvrhován´ı projekt˚ u je potom moˇzno s u ´ spˇechem pouˇz´ıt rozsáhlých nástroj˚ u teorie graf˚ u. Teorii graf˚ u vyvinul Leonard Euler pˇri ˇreˇsen´ı známého problému - lze proj´ıt vˇsech sedm most˚ u v Kaliningradu tak, abychom kaˇzdý pˇreˇsli pouze jednou? Euler dokázal, ˇze to nelze, a k ˇreˇsen´ı vytvoˇril nav´ıc novou teorii, teorii graf˚ u. Ta je dnes ˇsiroce vyuˇz´ıvána v mnoha vˇedn´ıch a technických oborech. Jej´ı vyuˇzit´ı pˇri ˇr´ızen´ı projekt˚ u bylo vynuceno poˇzadavky z praxe. Základn´ı a dodnes pouˇz´ıvané metody vznikly pˇri potˇrebˇe ˇreˇsen´ı konkrétn´ıch problém˚ u. Prvn´ı z nich, tzv. Metoda kritick´ e cesty, Critical Path Method (CPM), vznikla roku 1957 pˇri ˇreˇsen´ı výstavby komplexu petrochemické spoleˇcnosti duPont. Pravdˇepodobnostn´ı rozˇs´ıˇren´ı metody CPM, metoda Program Evaluation and Review Technique (PERT), byla vyvinuta roku 1958 pro ˇr´ızen´ı projektu atomových stˇrel pro ponorky Polaris a u ´ dajnˇe zkrátila realizaci projektu o 18 mˇes´ıc˚ u.

29

Z´ akladn´ı pojmy teorie graf˚ u Struˇcnˇe pˇripomeneme základn´ı pojmy z teorie graf˚ u, které budeme pouˇz´ıvat. Podrobný výklad byl obsahem pˇredmˇetu Teorie graf˚ u a her.

Neorientovan´ y graf Graf G = {U, H} se skládá z mnoˇziny uzl˚ u U = {u1 , ..., un } a mnoˇziny hran H = {hij }ni,j=1 (hrana hij = [ui , uj ] je spojnice uzl˚ u i a j). Hrana se stejnými koncovými uzly se nazývá smyˇ cka. Na obr. 2.1 je znázornˇen jednoduchý graf se ˇctyˇrmi uzly a pˇeti hranami. Graf obsahuje

h14

u1 h12 h13

u2 u3

h24

u4

h33

Obrázek 2.1: mnoˇzinu uzl˚ u U = {u1 , u2 , u3, u4 } a mnoˇzinu hran H = {h12 , h13 , h14 , h24 , h33 }. Neorientovan´ a hrana hij umoˇzn ˇ uje pohyb jak z uzlu ui do uzlu uj , tak opaˇcným smˇerem. Neorientovan´ y graf obsahuje pouze neorientované hrany. Zopakujme si pojmy teorie graf˚ u a jejich významy: • sled – posloupnost na sebe navazuj´ıc´ıch hran, • cesta v grafu – sled z jednoho uzlu do druhého, který neprocház´ı ˇzádným uzlem v´ıce neˇz jednou, • d´ elka cesty – poˇcet hran v cestˇe, • kruˇ znice – uzavˇrená cesta (zaˇc´ıná a konˇc´ı ve stejném uzlu), ˜ = {U, ˜ H} ˜ - vznikne vynechán´ım nˇekterých uzl˚ • podgraf grafu G u a hran p˚ uvodn´ıho ˜ ˜ grafu, U ⊂ U, H ⊂ H, • souvisl´ y graf – existuje cesta mezi dvˇema libovolnými uzly grafu, 30

• komponenta grafu – nejvˇetˇs´ı souvislý podgraf, • nesouvisl´ y graf – je sloˇzen alespoˇ n ze dvou komponent, • ohodnocen´ y graf – kaˇzdé hranˇe je pˇriˇrazena váha (skalár ˇci vektor), • kostra souvisl´ eho grafu - souvislý podgraf, který obsahuje vˇsechny uzly grafu a neobsahuje kruˇznici. Pˇ r´ıklad 1. Praktickým pˇr´ıkladem pouˇzit´ı neorientovaného grafu v praxi je u ´ loha propojit nˇekolik mˇest elektrickým veden´ım, které bude nejkratˇs´ı moˇzné. Jde o to, nalézt minimáln´ı kostru grafu, který vznikne spojen´ım vˇsech mˇest hranami. ´ Pˇ r´ıklad 2. Ulohu z pˇr´ıkladu 1 lze modifikovat, pokud napˇr´ıklad náklady na postaven´ı veden´ı mezi r˚ uznými mˇesty se liˇs´ı – jednotlivé hrany se oznaˇc´ı váhami (zde je to cena) a bude se jednat o ohodnocený graf. Pak je naˇs´ım u ´ kolem naj´ıt nejlehˇc´ı kostru grafu, tj. takovou kostru, která bude m´ıt nejmenˇs´ı souˇcet vah svých hran.

Orientovan´ y graf Hrany, ve kterých je významné poˇrad´ı uzl˚ u, se nazývaj´ı orientovan´ e. Znázorˇ nujeme je ˇsipkou. U orientované hrany hij = [ui , uj ] je ui poˇcáteˇcn´ı a uj koncový uzel. Graf s orientovanými hranami se nazývá orientovan´ y. Na obr. 2.2 je znázornˇen orientovaný graf s uzly jako naobr. 2.1 a s orientovanými hranami H = {h12 , h24 , h14 , h31 , h33 }. Nˇekteré pojmy orientovaných graf˚ u

u1 u2 u3

Obrázek 2.2: a jejich významy: • orientovan´ e spojen´ı - sled v orientovaném grafu, • dr´ aha - orientovaná cesta, • cyklus - uzavˇrená orientovaná cesta, • acyklick´ y graf - orientovaný graf bez cykl˚ u.

31

u4

S´ıt’ov´ y graf Technicky vzato je s´ıt’ov´ y graf (SG) zobrazen´ı projektu ve formˇe grafu, vyjadˇruj´ıc´ıho technologické vazby mezi d´ılˇc´ımi ˇcinnostmi. Matematicky je to koneˇcný souvislý orientovaný acyklický ohodnocený graf. Obvykle poˇzadujeme, aby mˇel jeden vstupn´ı uzel = poˇcátek projektu a jeden výstupn´ı uzel = konec projektu, ale nen´ı to nutné. K sestaven´ı SG jsou tˇreba podrobné poˇcáteˇcn´ı informace k projektu obsahuj´ıc´ı soupis jednotlivých ˇcinnost´ı, jejich návaznost a dobu trván´ı. ´ Ukolem s´ıt’ové analýzy je naj´ıt takovou posloupnost ˇcinnost´ı, která urˇcuje celkovou dobu trván´ı projektu – je to hledán´ı takové orientované cesty v SG, která vede z poˇcáteˇcn´ıho do koncového uzlu a bude m´ıt nejmenˇs´ı souˇcet vah. Tato cesta se nazývá kritick´ a. Pˇ r´ıklad 3. Princip sestaven´ı a práce se s´ıt’ovým grafem ukáˇzeme na tzv. turistickém problému [2]. V m´ıstˇe A se nacház´ı 8 turist˚ u, kteˇr´ı chtˇej´ı proj´ıt ve skupinách po 2 turistech m´ısty B, C, D, E a F s c´ılem setkat se v m´ıstˇe G. Rozdˇelen´ı tras a skupin popisuje obr. 2.4. Z A do B

Obrázek 2.3: Turistický problém. jdou 2 skupiny spoleˇcnˇe, z B do F pak jde prvn´ı skupina, zat´ımco druhá pokraˇcuje z B do E. Tˇret´ı skupina jde po trase A, C, E, G a ˇctvrtá po trase A, D, G. Po trase z E do G jdou druhá a tˇret´ı skupina spoleˇcnˇe, skupiny na sebe v daném bodˇe musej´ı poˇckat. Pˇredpokládané ˇcasy, nutné pro pˇrejit´ı jednotlivých u ´ sek˚ u, jsou uvedeny v tabulce 2.1. Jednotlivé ˇcasy tvoˇr´ı ohodnocen´ı pˇr´ısluˇsných hran v grafu. Turisté chtˇej´ı vˇedˇet, kdy se mohou vˇsichni nejdˇr´ıve sej´ıt v c´ıli cesty v bodˇe G. Nyn´ı znázorn´ıme u ´ lohu pomoc´ı s´ıt’ového grafu. M´ısta urˇcená k projit´ı jsou znázornˇena pomoc´ı uzl˚ u (oˇc´ıslovaných), cesty mezi jednotlivými m´ısty (uzly) jsou popsány pomoc´ı orientovaných ohodnocených hran. Graf znázorˇ nuje u ´ lohu (projekt), kterou má skupina splnit a ˇcasy, které jsou potˇreba ke splnˇen´ı jednotlivých d´ılˇc´ıch u ´ kol˚ u. Vˇsimnˇeme si, ˇze ˇcinnost (5-7) závis´ı na splnˇen´ı dvou bezprostˇrednˇe pˇredcházej´ıc´ıch ˇcinnost´ı (2-5) a (3-5). Je snadno vidˇet, ˇze jednotlivé skupiny 32

trasa ˇcas A-B A-C A-D B-F B-E C-E D-G E-G F-G

(hod.) 3 2 1 2 5 4 6 1 1

Tabulka 2.1:

3 1

2

2

6

5 2 3

4

1

1

1

5

7

6

4

Obrázek 2.4: Zobrazen´ı turistického problému v s´ıt’ovém grafu. jdou celkem po 4 cestách: • C1 : 1,2,6,7, resp. A-B-F-G, • C2 : 1,2,5,7, resp. A-B-E-G, • C3 : 1,3,5,7, resp. A-C-E-G, • C4 : 1,4,7, resp. A-D-G. Délka trván´ı pochodu jednotlivých skupin je dána souˇctem ohodnocen´ı hran v jednotlivých cestách: • C1 : 6 hod, • C2 : 9 hod, • C3 : 7 hod, • C4 : 7 hod. Celková doba trván´ı projektu je dána cestou s nejvyˇsˇs´ım ohodnocen´ım. Zde je to cesta C2 , která trvá 9 hodin (pˇrirozenˇe projekt povaˇzujeme za ukonˇcený aˇz ve chv´ıli, kdy doraz´ı do c´ıle vˇsechny 4 skupiny). Pokud je doba 9 hodin stanovena jako závazný u ´ kol, skupina jdouc´ı po cestˇe C2 nesm´ı v˚ ubec odpoˇc´ıvat a mus´ı stále j´ıt, ledaˇze by zvýˇsila svoje tempo. Naopak napˇr´ıklad 33

Trasa 1-2 1-3 1-4 2-5 2-6 3-5 4-7 5-7 6-7

Doba trván´ı 3 2 1 5 2 4 6 1 1

Term´ın zahájen´ı

Term´ın ukonˇcen´ı

nejdˇ r´ıve moˇ zn´ y / nejpozdˇ eji pˇ r´ıpustn´ y

nejdˇ r. moˇ zn´ y / nejp. pˇ r´ıpustn´ y

0 0 0 3 3 2 1 8 5

/ / / / / / / / /

0 2 2 3 6 4 3 8 8

3 2 1 8 5 6 7 9 6

/ / / / / / / / /

3 4 3 8 8 8 9 9 9

Rezerva 0 2 2 0 3 2 2 0 3

Tabulka 2.2:

skupina jdouc´ı po cestˇe C1 m˚ uˇze po cestˇe 3 hodiny odpoˇc´ıvat nebo zvolnit svoje tempo a i tak doraz´ı do c´ıle vˇcas. Jednotlivá stanoviˇstˇe lze chápat jako kontroln´ı body plnˇen´ı celé akce. S jednotlivými body (uzly grafu) jsou spojeny term´ıny, kdy m˚ uˇzeme (mus´ıme) zahájit pochod. Napˇr´ıklad skupina jdouc´ı po cestˇe C4 m˚ uˇze dorazit do m´ısta D uˇz za hodinu. Nebo m˚ uˇze zvolnit tempo ˇci zvolit pˇrestávku tak, aby dorazila do D nejpozdˇeji po 3 hodinách od zaˇcátku akce (tak, aby splnila u ´ kol vˇcas, tj. dostala se do G nejpozdˇeji po 9 hodinách). Pokud nevyuˇzije rezervu na prvn´ım u ´ seku, m˚ uˇze (ˇci nemus´ı) ji vyuˇz´ıt na druhém. Pro vˇsechny cesty tak lze stanovit nejdˇr´ıve moˇzné a nejpozdˇeji pˇr´ıpustné term´ıny zahájen´ı a ukonˇcen´ı pochodu (viz tab. 2.2). Rozpis u ´ kol˚ u v tabulce dává moˇznost jednotlivým skupinám naplánovat si své d´ılˇc´ı u ´ koly tak, aby neohrozily celou akci. Nav´ıc vedouc´ı výpravy m˚ uˇze kontrolovat pr˚ ubˇeh celé akce a dˇelat opatˇren´ı ke zdárnému ukonˇcen´ı projektu (sledovat napˇr. zpoˇzdˇen´ı jednotlivých skupin, která mohou nebo nemusej´ı ohrozit splnˇen´ı projektu). Pˇri zahájen´ı akce záviselo jej´ı u ´ spˇeˇsné ukonˇcen´ı na skupinˇe 2, která ˇsla po cestˇe s nejvyˇsˇs´ım ohodnocen´ım ? tato cesta se nazývá kritick´ a. Zdrˇzen´ı druhé skupiny by znamenalo zdrˇzen´ı celé akce a jej´ı d´ılˇc´ı ˇcinnosti nemaj´ı ˇzádnou ˇcasovou rezervu. V pr˚ ubˇehu projektu se vˇsak m˚ uˇze kritická cesta zmˇenit. Pokud napˇr. nabere skupina jdouc´ı po cestˇe C4 (maj´ıc´ı nejdelˇs´ı posledn´ı u ´ sek) na prvn´ım u ´ seku dvouhodinové zpoˇzdˇen´ı, je reálné nebezpeˇc´ı, ˇze se zpozd´ı celý projekt, a nová kritická cesta bude nyn´ı 1-4-7. Na turistickém projektu je názornˇe popsán princip sestaven´ı s´ıt’ového diagramu a plánován´ı doby trván´ı projektu. Shrnut´ı: Obecný projekt je nejprve nutné popsat: rozˇclenit problém na d´ılˇc´ı ˇcinnosti, odhadnout dobu trván´ı a náklady na jednotlivé ˇcinnosti, urˇcit ˇcasovou návaznost jednotlivých ˇcinnost´ı (tj. které ˇcinnosti musej´ı být ukonˇceny pˇred zahájen´ım ostatn´ıch). Podle popisu projektu se sestav´ı s´ıt’ový graf a tabulka s popisem ˇcinnost´ı. Trván´ım projektu je minimáln´ı ˇcas, nutný k proveden´ı vˇsech d´ılˇc´ıch u ´kol˚ u. Cesta z poˇcáteˇcn´ıho bodu projektu do koncového, jej´ıˇz doba je rovna dobˇe trván´ı projektu, se nazývá cesta kritick´ a. Kritická cesta je maximáln´ı (ˇcasovˇe nejdelˇs´ı) ze vˇsech cest v s´ıt’ovém grafu z poˇcáteˇcn´ıho uzlu do koncového. Základn´ı u ´ lohou s´ıt’ové analýzy je hledán´ı kritické cesty v s´ıt’ovém grafu pomoc´ı metody CPM. Jej´ı pravdˇepodobnostn´ı varianta PERT uvaˇzuje doby trván´ı d´ılˇc´ıch ˇcinnost´ı jako náhodné promˇenné popsané pravdˇepodobnostn´ım rozdˇelen´ım. Pak se ˇreˇs´ı otázka, s jakou pravdˇepodobnost´ı bude splnˇen celý projekt nebo jeho ˇcásti. S tˇemito metodami se seznám´ıme v následuj´ıc´ıch kapitolách. 34

Navazuj´ıc´ı u ´ lohou v s´ıt’ové analýze je tzv. problém vyrovnán´ı kapacit. Podnik má omezené pracovn´ı a materiáln´ı kapacity. Kaˇzdá z d´ılˇc´ıch ˇcinnost´ı má urˇcité poˇzadavky na tyto kapacity (poˇcty stroj˚ u, poˇcty pracovn´ık˚ u apod.). C´ılem je stanovit zaˇcátky ˇcinnost´ı tak, aby v ˇzádném okamˇziku nebyla pˇrekroˇcena kapacita ˇzádného zdroje a pracovn´ıci byli co nejrovnomˇernˇeji vyt´ıˇzeni. Tato u ´ loha je mnohem obt´ıˇznˇejˇs´ı a dostupné algoritmy hledaj´ı pouze pˇribliˇzné ˇreˇsen´ı.

35

Metoda kritick´ e cesty Metoda kritické cesty je deterministická metoda, pˇredpokládá pevnˇe dané doby trván´ı d´ılˇc´ıch ˇcinnost´ı a neuvaˇzuje jejich zmˇeny. Jej´ı základn´ı filozofi´ı je odvozen´ı 4 ˇcasových charakteristik pro kaˇzdou d´ılˇc´ı ˇcinnost projektu: • Nejdˇ r´ıve moˇ zn´ y zaˇ c´ atek ˇ cinnosti, ˇcinnost nem˚ uˇze zaˇc´ıt dˇr´ıve, neˇz skonˇc´ı vˇsechny ˇcinnosti, které j´ı pˇredcházej´ı. Vˇsechny ˇcinnosti, vycházej´ıc´ı z uzlu ui, maj´ı stejný nejdˇr´ıve moˇzný zaˇcátek t0i . • Nejdˇ r´ıve moˇ zn´ y konec prov´ adˇ en´ı ˇ cinnosti, souˇcet nejdˇr´ıve moˇzného zaˇcátku a doby trván´ı ˇcinnosti. Pro ˇcinnost reprezentovanou hranou hij je jej´ı nejdˇr´ıve moˇzný konec dán jako t0i + yij , kde yij je doba trván´ı ˇcinnosti. • Nejpozdˇ eji pˇ r´ıpustn´ y konec prov´ adˇ en´ı ˇ cinnosti, udává okamˇzik, ve kterém mus´ı nejpozdˇeji ˇcinnost skonˇcit, aby se nezpozdilo provádˇen´ı navazuj´ıc´ıch ˇcinnost´ı. Vˇsechny ˇcinnosti, konˇc´ıc´ı v uzlu uj , maj´ı nejpozdˇeji pˇr´ıpustný konec t1j . • Nejpozdˇ eji pˇ r´ıpustn´ y zaˇ c´ atek prov´ adˇ en´ı ˇ cinnosti, rozd´ıl mezi nejpozdˇeji pˇr´ıpustným koncem a dobou trván´ı ˇcinnosti. Pro ˇcinnost vyjádˇrenou hranou hij je to t1j − yij . Dle definice kritické cesty je zˇrejmé, ˇze pro kaˇzdý jej´ı vnitˇrn´ı uzel bude nejdˇr´ıve moˇzný zaˇcátek ˇcinnost´ı z uzlu vystupuj´ıc´ıch rovný nejdˇr´ıve moˇznému konci provádˇen´ı ˇcinnost´ı do uzlu vstupuj´ıc´ıch. Vlastn´ı algoritmus CPM je zaloˇzen na výpoˇctu výˇse popsaných ˇcasových charakteristik pro vˇsechny ˇcinnosti. Postup lze rozdˇelit na ˇctyˇri fáze: 1. f´ aze - v´ ypoˇ cet nejdˇ r´ıve moˇ zn´ ych zaˇ c´ atk˚ u a konc˚ u prov´ adˇ en´ı ˇ cinnost´ı dle pravidla: nejdˇ r´ıve moˇ zn´ y zaˇ c´ atek ˇ cinnost´ı zaˇ c´ınaj´ıc´ıch v uzlu uj se rovn´ a maximu z nejdˇ r´ıve moˇ zn´ ych konc˚ uˇ cinnost´ı do uzlu uj vstupuj´ıc´ıch, tedy t0j = max[t0i + yij ], i∈Ij

(2.1)

kde Ij = {i|∃ hij } oznaˇcme mnoˇzinu index˚ u uzl˚ u, z nichˇz vede orientovaná hrana do uzlu uj . Výpoˇcet prob´ıhá postupnˇe od vstupn´ıho aˇz po výstupn´ı uzel s´ıt’ového grafu t´ımto zp˚ usobem: 1. Nejdˇr´ıve moˇzný zaˇcátek t01 ˇcinnost´ı zaˇc´ınaj´ıc´ıch ve vstupn´ım uzlu u1 se poloˇz´ı roven 0. 2. Postupnˇe je podle pravidla (2.1) vypoˇcten nejdˇr´ıve moˇzný zaˇcátek ˇcinnost´ı zaˇc´ınaj´ıc´ıch v uzlech u1 , ..., uN , kde uN je výstupn´ı uzel s´ıtˇe. 3. Oznaˇc´ıme T = t0N nejdˇr´ıve moˇzný zaˇcátek provádˇen´ı ˇcinnost´ı ve výstupn´ım uzlu. Hodnota T je rovna nejkratˇs´ı moˇzné dobˇe, ve které je moˇzné proces realizovat. Zároveˇ n je to ˇ ohodnocen´ı nejdelˇs´ı cesty v s´ıt’ovém grafu. Cinnosti na této cestˇe na sebe bezprostˇrednˇe navazuj´ı a jakékoliv zpoˇzdˇen´ı má za následek zpoˇzdˇen´ı celého projektu (viz turistický problém). Tyto 36

ˇcinnosti se nazývaj´ı kritické a uvedená cesta je kritická cesta. Zat´ım vˇsak neznáme ˇcinnosti, jejichˇz hrany tvoˇr´ı kritickou cestu. Jejich urˇcen´ı bude výsledkem druhé fáze výpoˇctu. 2. f´ aze - v´ ypoˇ cet nejpozdˇ eji pˇ r´ıpustn´ ych zaˇ c´ atk˚ u a konc˚ u prov´ adˇ en´ı ˇ cinnost´ı dle pravidla: nejpozdˇ eji pˇ r´ıpustn´ y konec ˇ cinnost´ı konˇ c´ıc´ıch v uzlu ui se rovn´ a minimu z nejpozdˇ eji pˇ r´ıpustn´ ych zaˇ c´ atk˚ uˇ cinnost´ı z uzlu ui vystupuj´ıc´ıch, tedy t1i = min[t1j − yij ], j∈Ji

(2.2)

kde Ji = {i|∃ hji } je mnoˇzina index˚ u uzl˚ u, ke kterým vede orientovaná hrana z uzlu uj . Výpoˇcet prob´ıhá sestupnˇe od výstupn´ıho aˇz po vstupn´ı uzel s´ıt’ového grafu (opaˇcnˇe neˇz v prvn´ı fázi) t´ımto zp˚ usobem: 1. Za nejpozdˇeji pˇr´ıpustný konec t1n provádˇen´ı ˇcinnost´ı, které konˇc´ı ve výstupn´ım uzlu s´ıtˇe un , je dosazena hodnota Tp1 . Nejpozdˇeji pˇr´ıpustný konec provádˇen´ı ˇcinnost´ı ve výstupn´ım uzlu je souˇcasnˇe nejpozdˇeji pˇr´ıpustným koncem realizace celého projektu. Proto mus´ı být hodnota Tp1 (pˇredstavuj´ıc´ı plánovanou dobu pro ukonˇcen´ı projektu) vˇetˇs´ı nebo rovna délce kritické cesty T (pˇredstavuj´ıc´ı nejkratˇs´ı moˇznou dobu realizace projektu), Tp1 ≥ T . 2. V jednotlivých iterac´ıch je postupnˇe vypoˇcten (podle výˇse uvedeného pravidla) nejpozdˇeji pˇr´ıpustný konec provádˇen´ı ˇcinnost´ı, které konˇc´ı v uzlech un−1 , un−2, ..., u1 . 3. Lze provést ˇcásteˇcnou kontrolu správnosti výpoˇctu: hodnota t11 vypoˇctená v posledn´ı iteraci pˇredcházej´ıc´ıho kroku mus´ı vyj´ıt rovna Tp1 − T . 3. f´ aze - v´ ypoˇ cet celkov´ ych ˇ casov´ ych rezerv Po realizaci prvn´ıch dvou fáz´ı je kaˇzdá ˇcinnost (reprezentovaná hranou hij ) charakterizována okamˇzikem, kdy m˚ uˇze nejdˇr´ıve zaˇc´ıt (nejdˇr´ıve moˇzný zaˇcátek t0i ) a okamˇzikem, kdy mus´ı nejpozdˇeji skonˇcit (nejpozdˇeji pˇr´ıpustný konec t1j ). Tyto dvˇe ˇcasové charakteristiky definuj´ı ˇcasové rozpˇet´ı pro realizaci dané ˇcinnosti. Uváˇz´ıme-li, ˇze doba trván´ı ˇcinnosti je yij , m˚ uˇzeme vypoˇc´ıtat tzv. celkovou ˇ casovou rezervu, která je k dispozici pro proveden´ı této ˇcinnosti, jako CRij = t1j − t0i − yij .

(2.3)

Podle hodnoty celkové ˇcasové rezervy je moˇzné urˇcit kritické ˇcinnosti celého projektu. Pro kritické ˇcinnosti plat´ı CRij = Tp1 − T,

tedy jejich celková ˇcasová rezerva je rovna rozd´ılu mezi plánovanou dobou ukonˇcen´ı projektu a délkou kritické cesty. Pˇri volbˇe Tp1 = T jsou tedy kritické ty ˇcinnosti, jejichˇz celková ˇcasová rezerva je nulová. Tˇret´ı fázi tedy m˚ uˇzeme popsat pravidlem: Celkov´ aˇ casov´ a rezerva je rozd´ılem nejpozdˇ eji pˇ r´ıpustn´ eho konce, nejdˇ r´ıve moˇ zn´ eho zaˇ c´ atku a doby trv´ an´ı ˇ cinnosti (2.3). Kritick´ eˇ cinnosti jsou ˇ cinnosti s minim´ aln´ı hodnotou celkov´ eˇ casov´ e rezervy.

V´ ypoˇ cet kritick´ e cesty Postup výpoˇctu kritické cesty metodou CPM lze pomˇernˇe snadno realizovat (i pro u ´ lohy s des´ıtkami ˇcinnost´ı), máme-li k dispozici s´ıt’ový graf projektu. Výpoˇcet se provád´ı bud’ pˇr´ımo v s´ıt’ovém grafu nebo ve speciáln´ı tabulce. Postup si ukáˇzeme na dalˇs´ım pˇr´ıkladu [1]. 37

ˇcinnost A B C D E F G H I J

popis ˇcinnost výbˇer a nákup vhodného objektu zpracován´ı projektu obsazen´ı pozice manaˇzera výbˇer personálu rekonstrukce a vybaven´ı objektu ˇskolen´ı personálu výbˇer sortimentu zboˇz´ı uzavˇren´ı smluv s dodavateli nákup zboˇz´ı reklama

doba trván´ı (týdny) 6 4 3 3 8 2 2 5 3 2

pˇredchoz´ı ˇcinnosti ˇzádná A A B, C B D B, C G E, F, H H

Tabulka 2.3: Rozpis projektu.

Pˇ r´ıklad Obchodn´ı spoleˇcnost Q-Mark se rozhodla otevˇr´ıt nové obchodn´ı centrum v Liberci. V rámci uvedného projektu definoval jej´ı projektový manaˇzer jednotlivé ˇcinnosti a souˇcasnˇe odhadl, na základˇe zkuˇsenosti z obdobných akc´ı, jejich dobu trván´ı v týdnech. Podrobnˇejˇs´ı analýzou vˇsech ˇcinnost´ı bylo urˇceno, ˇze zpracov´ an´ı projektu a obsazen´ı pozice manaˇ zera lze provést aˇz po v´ ybˇ eru a n´ akupu vhodn´ eho objektu. V´ ybˇ er person´ alu nelze provést dˇr´ıve, neˇz bude zpracov´ an projekt a obsazena pozice manaˇ zera, který se na ˇ v´ ybˇ eru person´ alu bude pod´ılet. Skolen´ ı person´ alu nelze samozˇrejmˇe realizovat dˇr´ıve, neˇz budou definitivnˇe obsazeny vˇsechny pozice. Rekonstrukce a vybaven´ı objektu závis´ı pouze na zpracov´ an´ı projektu. V´ ybˇ er sortimentu a zboˇ z´ı je podm´ınˇen zpracov´ an´ım projektu a obsazen´ım pozice manaˇ zera a naopak podmiˇ nuje uzavˇ ren´ı smluv s dodavateli. N´ akup zboˇ z´ı lze potom realizovat v závislosti na ukonˇ cen´ı rekonstrukce a vybaven´ı objektu, vyˇ skolen´ı person´ alu a uzavˇ ren´ı smluv s dodavateli. Reklamn´ı kampaˇ n k otevˇren´ı nového obchodn´ıho stˇrediska m˚ uˇze zaˇc´ıt aˇz po uzavˇ ren´ı smluv s dodavateli. Výˇse popsané informace (popis ˇcinnost´ı, odhad jejich doby trván´ı a seznam ˇcinnost´ı jim pˇredcházej´ıc´ıch) jsou uvedené v tabulce 2.3. Podle tabulky sestav´ıme s´ıt’ový graf. Ten mus´ı respektovat pˇredevˇs´ım vˇsechny definované návaznosti pro provádˇen´ı jednotlivých ˇcinnost´ı. Vstupn´ım uzlem s´ıtˇe je uzel u1 . Dále je rozumné s´ıt’ konstruovat sekvenˇcnˇe - pˇridávat k n´ı postupnˇe vˇzdy novou hranu reprezentuj´ıc´ı dalˇs´ı ˇcinnost, tak, aby byla respektována definovaná návaznost, ukonˇcit tuto ˇcinnost uzlem a urˇcit dalˇs´ı ˇcinnost, která bude v daném uzlu zaˇc´ınat. V naˇsem pˇr´ıkladu lze velmi jednoduˇse znázornit ˇcást s´ıtˇe obsahuj´ıc´ı ˇcinnosti A, B, C (viz obr. 2.5). Z grafu je

ˇ ast s´ıt’ového grafu. Obrázek 2.5: C´ vidˇet, ˇze zahájen´ı ˇcinnost´ı B a C (reprezentované uzlem u2 ) závis´ı na ukonˇcen´ı ˇcinnosti A ˇ (reprezentované stejným uzlem). Cinnost A nezávis´ı na ˇzádné dalˇs´ı ˇcinnosti, zaˇc´ıná tedy pˇr´ımo ve vstupn´ım uzlu s´ıtˇe u1 . 38

Pokud budeme cht´ıt dále rozˇs´ıˇrit náˇs s´ıt’ový graf o ˇcinnosti D a E, setkáváme se jiˇz s jistými ˇ problémy. Cinnost D závis´ı totiˇz na ukonˇcen´ı obou ˇcinnost´ı B a C, kdeˇzto ˇcinnost E pouze na ˇcinnosti B. Dvˇe moˇznosti, uvedené na obr 2.6, ukazuj´ı nesprávné znázornˇen´ı definovných návaznost´ı. V prvn´ım pˇr´ıpadˇe závis´ı ˇcinnost D skuteˇcnˇe na ukonˇcen´ı ˇcinnost´ı B i C, ale stejná závislost plat´ı i pro ˇcinnost E, coˇz poruˇsuje vstupn´ı podm´ınky (ˇcinnost E má záviset pouze na B). Ve druhém pˇr´ıpadˇe sice závis´ı ˇcinnost E správnˇe pouze na B, ale ˇcinnost D závis´ı pouze na C (chyb´ı závislost na B). Uvedený problém v návaznosti ˇcinnost´ı lze vyˇreˇsit pouze tak, ˇze do

Obrázek 2.6: Nesprávné znázornˇen´ı návaznost´ı ˇcinnost´ı. s´ıt’ového grafu, který je v druhé ˇcásti obr. 2.6, dopln´ıme umˇele mezi uzly u3 a u4 dalˇs´ı hranu, která bude zabezpeˇcovat vytvoˇren´ı návaznosti mezi ˇcinnostmi D a B. Tato novˇe doplnˇená hrana se oznaˇcuje jako fiktivn´ı hrana a ˇcinnost, kterou reprezentuje, se oznaˇcuje fiktivn´ı ˇ cinnost. Fiktivn´ı ˇcinnosti pouze zprostˇredkovávaj´ı návaznosti mezi reálnými ˇcinnostmi, které nelze zabezpeˇcit jiným zp˚ usobem. Samozˇrejmˇe nesmˇej´ı m´ıt vliv na náklady nebo dobu realizace celého projektu. Doba trván´ı fiktivn´ıch ˇcinnost´ı je proto vˇzdy nulová. Výsledný graf po doplnˇen´ı fiktivn´ı hrany (oznaˇcena symbolem X1) je znázornˇen na obrázku2.7. Hrana X1 zprostˇredkovává

Obrázek 2.7: Doplnˇen´ı fiktivn´ı hrany. návaznost mezi D a B. V grafu na obr. 2.7 je znázornˇeno 5 z celkového poˇctu 10 ˇcinnost´ı naˇseho pˇr´ıkladu. Zbývaj´ıc´ı ˇcinnosti lze doplnit analogicky. Kompletn´ı s´ıt’ový graf projektu je znázornˇen na obr. 2.8. V závorce u kaˇzdé ˇcinnsoti je uvedena doba trván´ı této ˇcinnosti. Pozn´ amka. Pˇri sestavován´ı s´ıt’ového grafu je uˇziteˇcné dodrˇzovat podm´ınku (nikoliv nutnou), ˇze v s´ıti by mˇelo pro vˇsechny hrany platit, ˇze index uzlu, ze kterého hrana vycház´ı, je vˇzdy niˇzˇs´ı neˇz index uzlu, ve kterém hrana konˇc´ı. V s´ıti na obr. 2.8 je tato podm´ınka splnˇena. Tato podm´ınka zebezpeˇc´ı, ˇze v grafu nevzniknou ˇzádné orientované cykly. Existence takového cyklu by byla nesmyslná, vzhledem k ˇcasové posloupnosti provádˇen´ı ˇcinnost´ı - pokud bychom napˇr. zaˇcali provádˇet nˇejakou ˇcinnost v ˇcase 0, potom bychom se po proveden´ı nˇekolika ˇcinnost´ı (hrany v cyklu) vrátili zase do ˇcasu 0. Nyn´ı uˇz m˚ uˇzeme projekt analyzovat podle metody kritické cesty. 39

Obrázek 2.8: S´ıt’ový graf pro Q-Mark projekt.

V´ ypoˇ cet v s´ıt’ov´ em grafu Uzel v grafu si rozdˇel´ıme na tˇri ˇcásti (viz obr. 2.9). Horn´ı ˇcást udává index uzlu. Vlevo jsou

Obrázek 2.9: Uzel pˇri výpoˇctu metodou CPM v s´ıti. nejdˇr´ıve moˇzné zaˇcátky ˇcinnost´ı vycházej´ıc´ıch z daného uzlu, vpravo jsou nejpozdˇeji pˇr´ıpustné konce ˇcinnost´ı, které konˇc´ı v daném uzlu. 1. fáze (výpoˇcet nejdˇr´ıve moˇzných zaˇcátk˚ u ˇcinnost´ı) je znázornˇena na obr. 2.10. • Za hodnotu t01 je nejprve dosazena 0. • Do uzlu u2 vstupuje pouze jedna hrana h12 . Proto t02 = t01 + y12 = 0 + 6 = 6. • Do uzlu u3 vstupuje jen jedna hrana h23 . Proto t03 = t02 + y23 = 6 + 4 = 10. • Do uzlu u4 vstupuj´ı dvˇe hrany h23 a h34 . Nejdˇr´ıve moˇzný zaˇcátek ˇcinnost´ı vycházej´ıc´ıch z daného uzlu je proto roven maximu z nejdˇr´ıve moˇzných konc˚ u ˇcinnost´ı na uvedených dvou hranách, tj. t04 = max(t02 + y24 , t03 + y34 ) = max(6 + 3, 10 + 0) = 10. Výpoˇcet prvn´ı fáze pokraˇcuje analogicky aˇz do urˇcen´ı hodnoty t09 = 21. Ohodnocen´ı kritické cesty je tedy v naˇsem pˇr´ıpadˇe T = 21 týdn˚ u. Tato hodnota souˇcasnˇe pˇredstavuje nejkratˇs´ı moˇznou dobu realizace celého projektu. Pˇri výpoˇctu 2. fáze postupujeme opaˇcným smˇerem, od výstupu ke vstupu. V naˇsem pˇr´ıkladu jsme zvolili plánovanou dobu trván´ı celého projektu 21 týdn˚ u - tedy nejkratˇs´ı moˇznou dobu (viz hodnotu v pravé ˇcásti uzlu na obr. 2.10). Výpoˇcet 2. fáze dokumentuje obr. 2.11. 40

Obrázek 2.10: Výpoˇcet nejdˇr´ıve moˇzných zaˇcátk˚ u ˇcinnost´ı.

Obrázek 2.11: Výpoˇcet nejpozdˇeji pˇr´ıpustných konc˚ u ˇcinnost´ı a celkových ˇcasových rezerv. • Z uzlu u8 vycház´ı jen jedna hrana h89 . Nejpozdˇeji pˇr´ıpustný konec ˇcinnost´ı vstupuj´ıc´ıch do uzlu u8 je tedy t18 = t19 − y89 = 21 − 3 = 18. • Z uzlu u7 vycházej´ı dvˇe hrany h78 a h79 . Nejpozdˇeji pˇr´ıpustný konec ˇcinnost´ı vstupuj´ıc´ıch do tohoto uzlu se proto vypoˇcte jako minimum z nejpozdˇeji pˇr´ıpustných zaˇcátk˚ u ˇcinnost´ı reprezentovaných tˇemito hranami, tj. t17 = min(t18 −y78 , t19 −y79 ) = min(18−0, 21−2) = 18. Dalˇs´ı výpoˇcet 2. fáze prob´ıha analogicky aˇz ke vstupn´ımu uzlu s´ıtˇe, kde je t11 = 0. Na obr. 2.11 jsou uvedeny souˇcasnˇe s ohodnocen´ım kaˇzdé hrany v závorce celkové ˇcasové rezervy. Napˇr. rezerva pro ˇcinnost na hranˇe h67 se rovná CR67 = t17 − t06 − y67 = 18 − 12 − 5 = 1. Kritická cesta je v naˇsem pˇr´ıkladˇe tvoˇrena ˇcinnostmi s nulovými celkovými ˇcasovými rezervami. Je tedy tvoˇrena posloupnost´ı hran h12 → h23 → h38 → h89 (viz obr. 2.11), tj. ˇcinnostmi A–B– E–I.

V´ ypoˇ cet v tabulce Tabulkové zpracován´ı metodou CPM je podobné výpoˇctu v s´ıt’ovém grafu, liˇs´ı se jen po formáln´ı stránce. Tabulka obsahuje pro kaˇzdou ˇcinnost jeden ˇrádek, který obsahuje index poˇcáteˇcn´ıho a 41

ˇcinnost hij h12 h23 h24 h34 h38 h45 h46 h58 h67 h78 h79 h89

doba trván´ı n.m. zaˇcátek n.m. konec yij t0i t0i + yij 6 0 6 4 6 10 3 6 9 0 10 10 8 10 18 3 10 13 2 10 12 2 13 15 5 12 17 0 17 17 2 17 19 3 18 21

n.p. konec t1j 6 10 11 11 18 16 13 18 18 18 21 21

n.p. zaˇcátek t1j − yij 0 6 8 11 10 13 11 16 13 18 19 18

CR CRij 0 0 2 1 0 3 1 3 1 1 2 0

Tabulka 2.4: Tabulkový výpoˇcet metody CPM.

koncového uzlu hrany reprezentuj´ıc´ı tuto ˇcinnost, dobu trván´ı, vˇsechny ˇctyˇri ˇcasové charakteristiky, které se odvozuj´ı postupnˇe v pr˚ ubˇehu výpoˇctu, a celkovou ˇcasovou rezervu. Tabulkové zpracován´ı pˇr´ıkladu je znázornˇeno v tabulce 2.4. Zv´ yraznˇeny jsou kritické ˇcinnosti s nulovými ˇcasovými rezervami.

Anal´ yza z´ıskan´ ych v´ ysledk˚ u Posledn´ı, ale velmi d˚ uleˇzitou fáz´ı pˇri ˇr´ızen´ı projekt˚ u metodou CPM je rozbor z´ıskaných výsledk˚ u. Jde o to urˇcit, které ˇcinnosti mohou prob´ıhat paralelnˇe a naopak, které na sebe musej´ı navazovat. V rámci konkrétn´ıho ˇcasového rozvrˇzen´ı provádˇen´ı ˇcinnost´ı lze potom i rozvrhovat zdroje, které jednotlivé ˇcinnosti vyˇzaduj´ı. Principy tohoto rozvrhován´ı jsou znázornˇeny pro náˇs pˇr´ıklad na obr. 2.12. V diagramu je provádˇen´ı kaˇzdé ˇcinnosti rozvrˇzeno na ˇcasové ose.

ˇ Obrázek 2.12: Casov´ y diagram provádˇen´ı ˇcinnost´ı. Vymezen´ı doby pro realizaci ˇcinnosti je vyznaˇceno rámeˇckem – levá hranice pˇredstavuje nejdˇr´ıve moˇzný zaˇcátek, pravá hranice nejpozdˇeji pˇr´ıpustný konec. Doba trván´ı ˇcinnosti je v rámeˇcku 42

vyst´ınovaná, zbytek pˇredstavuje ˇcasovou rezervu. Na prvn´ıch 4 ˇrádc´ıch jsou v diagramu uvedeny ˇcinnosti, u nichˇz jsou celkové ˇcasové rezervy nulové. Je patrné, ˇze tyto ˇcinnosti na sebe musej´ı ˇ bezprostˇrednˇe navazovat, abychom zajistili ukonˇcen´ı projektu v poˇzadovaném ˇcase. Cinnosti ˇ C, D a F musej´ı být realizovány v uvedené posloupnosti. Cinnost C vsak m˚ uˇze zaˇc´ıt jiˇz po 6 týdnech a ˇcinnost F m˚ uˇze skonˇcit aˇz v 18. týdnu. K dispozici pro jejich realizaci máme 12 týdn˚ u, vˇsechny tˇri ˇcinnosti dohromady vˇsak trvaj´ı jen 8 týdn˚ u – je zde tedy prostor pro jisté rozvrhován´ı. Staˇc´ı napˇr´ıklad, kdyˇz C zaˇcne aˇz po 8. týdnu, po jej´ım skonˇcen´ı zaˇcnou bezprostˇrednˇe ˇcinnost D a navazuj´ıc´ı ˇcinnost F a skonˇc´ıme v 16. týdnu, 2 týdny pˇred limitem. Kdybychom chtˇeli napˇr´ıklad minimalizovat poˇcet paralelnˇe prob´ıhaj´ıc´ıch ˇcinnost´ı v projektu, mohl by rozvrh vypadat napˇr takto (obr. 2.13). Za této podm´ınky je vˇsak vidˇet, ˇze skuteˇcné

Obrázek 2.13: Rozvrh posloupnost´ı provádˇen´ı ˇcinnost´ı. ˇcasové rezervy pro provádˇen´ı posloupnost´ı ˇcinnost´ı jsou velmi malé, pro posloupnost ˇcinnost´ı C - G - D - F i pro ˇcinnost H je rezerva pouze 1 týden.

43

Metoda PERT Metoda PERT byla navrˇzena rok po metodˇe CPM jako jej´ı pravdˇepodobnostn´ı rozˇs´ıˇren´ı. Metoda CPM pˇredpokládá, ˇze pracovn´ık odpovˇedný za projekt je uˇz pˇri jeho pˇr´ıpravˇe schopen stanovit pevnˇe doby trván´ı jednotlivých ˇcinnost´ı. Tento pˇredpoklad vˇsak v praxi ˇcasto nen´ı moˇzné splnit. V metodˇe PERT se proto pˇredpokládá, ˇze doba trván´ı kaˇzdé ˇcinnosti, reprezentovaná hranou hij , je náhodnou veliˇcinou, která je definovaná na nˇejakém intervalu haij , bij i, kde aij je pˇredpokládaná nejkratˇs´ı moˇzná doba realizace této ˇcinnosti a bij je uvaˇzovaná nejdelˇs´ı doba proveden´ı této ˇcinnosti. Skuteˇcná délka proveden´ı této ˇcinnosti bude nˇekde uvnitˇr uvedeného intervalu s t´ım, ˇze metoda PERT dále pˇredpokládá, ˇze lze pro ˇcinnosti urˇcit jejich nejpravdˇepodobnˇejˇs´ı dobu trván´ı mij . Pˇri pˇr´ıpravˇe projektu pro zpracován´ı metodou PERT tedy definuje projektový manaˇzer pro kaˇzdou ˇcinnost tˇri ˇcasové charakteristiky: • aij - nejkratˇs´ı pˇredpokládanou dobu trván´ı ˇcinnosti, tzv. optimistick´ y odhad, • bij - nejdelˇs´ı pˇredpokládanou dobu trván´ı ˇcinnosti, tzv. pesimistick´ y odhad, • mij - nejpravdˇepodobnˇejˇs´ı dobu trván´ı ˇcinnosti, tzv. mod´ aln´ı odhad.

Doba trván´ı ˇcinnosti je spojitá náhodná veliˇcina. Jej´ı pravdˇepodobnostn´ı rozdˇelen´ı nen´ı pˇredem známé. Ukazuje se vˇsak, ˇze toto neznámé rozdˇelen´ı lze aproximovat β-rozdˇelen´ım, které má ve srovnán´ı napˇr. s normáln´ım rozdˇelen´ım nˇekteré v´ yhodné vlastnosti: • koneˇcné rozpˇet´ı - definiˇcn´ı obor je koneˇcný interval haij , bij i, • nen´ı obecnˇe symetrické - stˇredn´ı hodnota nemus´ı leˇzet uprostˇred definiˇcn´ıho oboru.

Obr. 2.14 ukazuje graf hustoty pravdˇepodobnosti pro β-rozdˇelen´ı. Stˇredn´ı hodnota, resp. smˇero-

Obrázek 2.14: Hustota pravdˇepodobnosti β-rozdˇelen´ı. datná odchylka β-rozdˇelen´ı (tedy stˇredn´ı doba trván´ı ˇcinnosti a jej´ı smˇerodatná odchylka), maj´ı tvar aij + 4mij + bij , µij = 6 44

ˇcinnost hij h12 h23 h24 h34 h38 h45 h46 h58 h67 h78 h79 h89

opt. odhad mod. odhad pes. odhad stˇr. doba aij [týdny] mij [týdny] bij [týdny] µij [týdny] 3 6 8 35/6 3 4 5 4 1 3 4 17/6 0 0 0 0 6 8 12 50/6 2 3 4 3 2 2 3 11/6 2 2 2 2 2 3 5 19/6 0 0 0 0 2 2 2 2 2 3 4 3

smˇer. odch. σij [týdny] 5/6 2/6 3/6 0 6/6 2/6 1/6 0 3/6 0 0 2/6

σij2

rozptyl [týdny 2 ] 25/36 4/36 9/36 1 36/36 4/36 1/36 0 9/36 0 0 4/36

Tabulka 2.5: Vstupn´ı data pro metodu PERT.

resp.

bij − aij . 6 Vlastn´ı výpoˇcet kritické cesty metodou PERT se neliˇs´ı od metody CPM. M´ısto pevnˇe daných hodnot yij zde pracujeme se stˇredn´ımi hodnotami dob trván´ı ˇcinnost´ı µij . Výsledkem je kritická cesta, jej´ıˇz ohodnocen´ı oznaˇc´ıme M (souˇcet stˇredn´ıch dob trván´ı kritických ˇcinnost´ı). Hodnota M tedy vlastnˇe udává stˇ redn´ı dobu trv´ an´ı cel´ eho projektu. Skuteˇcná doba trván´ı celého projektu T je spojitá náhodná veliˇcina, jej´ıˇz stˇredn´ı hodnota je M a rozptyl σ 2 lze spoˇc´ıtat jako souˇcet rozptyl˚ u vˇsech kritických ˇcinnost´ı. Lze ukázat, ˇze za urˇcitých pˇredpoklad˚ u má ona 2 spojitá náhodná veliˇcina normáln´ı rozdˇelen´ı se stˇredn´ı hodnotou M a rozptylem σ . σij =

Pˇ r´ıklad. Uvaˇzujme projekt popsaný s´ıt´ı 2.8. V tabulce 2.5 jsou pro jednotlivé ˇcinnosti uvedeny optimistické, modáln´ı a pesimistické odhady dob trván´ı ˇcinnost´ı, jejich stˇredn´ı doby a smˇerodatné odchylky. Kritická cesta vypoˇctená na základˇe stˇredn´ıch hodnot µij je v naˇsem pˇr´ıkladˇe tvoˇrena stejnými hranami (ˇcinnostmi) jako kritická cesta v tab. 2.4 vypoˇctená metodou CPM s pevnými dobami trván´ı yij . Kritické ˇcinnosti jsou opˇet zvýraznˇeny. Stˇredn´ı doba trván´ı projektu je M = 35/6 + 4 + 50/6 + 3 = 21.167 týdne, rozptyl doby trván´ı projektu je σ 2 = (5/6)2 + (2/6)2 + (6/6)2 + (2/6)2 = 69/36 = 1.9167 týdne a smˇerodatná odchylka σ=

√

2

1.9167 = 1.3844týdne.

Doba trván´ı celého projektu je pak náhodná veliˇcina s normáln´ım rozdˇelen´ım se stˇredn´ı hodnotou M a smˇerodatnou odchylkou σ. Pak lze zodpovˇedˇet následuj´ıc´ı otázky. 1. Jak´ a je pravdˇ epodobnost, ˇ ze projekt bude ukonˇ cen ve stanoven´ em ˇ case T ? Hledaná pravdˇepodobnost se rovná hodnotˇe distribuˇcn´ı funkce normáln´ıho rozdˇelen´ı N(M, σ) v bodˇe t = T . V praxi najdeme v tabulkách hodnotu N(0, 1) v transformovaném 45

bodˇe z=

TS − M . σ

2. V jak´ em ˇ case TS bude projekt ukonˇ cen se stanovenou pravdˇ epodobnost´ı p? Nalezneme z tabulek N(0, 1) hodnotu z odpov´ıdaj´ıc´ı pravdˇepodobnosti p a zpˇetnou transformac´ı dostaneme hledaný ˇcas jako TS = zσ + M. Cviˇ cen´ı. Naleznˇete pravdˇepodobnosti, s jakou skonˇc´ı náˇs projekt v ˇcasech t1 = 18, t2 = 20 a ˇ sen´ı: 0.011, 0.2, 0.726) t3 = 22 týdn˚ u. (Reˇ

46

Cviˇ cen´ı a pˇ r´ıklady Cviˇ cen´ı. 1. Ukaˇzte, ˇze podm´ınka souvislosti neorientovaného grafu je ekvivalentn´ı tomu, ˇze v grafu existuje uzel, z kterého jsou dosaˇzitelné vˇsechny ostatn´ı. 2. Ukaˇzte, ˇze kostra grafu s n uzly má n − 1 hran. 3. Ukaˇzte, ˇze v kostˇre grafu existuje mezi dvˇema libovolnými uzly vˇzdy právˇe jedna cesta. 4. Najdˇete vˇsechny cesty z uzlu 1 do uzlu 5 u orientovaného grafu na obrázku 2.2. 5. Co je to s´ıt’ový graf? 6. Jaká jsou základn´ı pravidla pro konstrukci s´ıt’ového grafu pˇri analýze projekt˚ u? 7. K ˇcemu slouˇz´ı fiktivn´ı hrany (fiktivn´ı ˇcinnosti) pˇri konstrukci s´ıt’ového grafu? 8. Jaký je základn´ı rozd´ıl mezi metodami CPM a PERT? 9. Co je to kritická ˇcinnost a kritická cesta? 10. Jakým zp˚ usobem je moˇzné interpretovat délku kritické cesty? Proˇc je kritická cesta souˇcasnˇe nejdelˇs´ı cestou v s´ıti mezi vstupn´ım a výstupn´ım uzlem? 11. Co je to celková ˇcasová rezerva a jaký je jej´ı význam pˇri urˇcen´ı kritické cesty? ˇcinnost A B C D E F G H I J

doba trván´ı pˇredchoz´ı ˇcinnosti 3 ˇzádná 4 A 2 A 3 B 3 D 4 B, C 2 B, C 5 F 3 F, G 3 H, I Tabulka 2.6:

47

ˇcinnost A B C D E F G H I J

optimistický odhad modáln´ı odhad pesimistický odhad 2 3 4 2 4 6 1 2 3 1 3 5 2 3 5 1 4 6 2 2 2 2 5 7 1 3 5 2 3 5 Tabulka 2.7:

12. V rámci jistého projektu bylo vyˇclenˇeno 10 ˇcinnost´ı, jejichˇz doba trván´ı v týdnech a ˇcinnosti, které jim musej´ı pˇredcházet, jsou uvedeny v tabulce 2.6. a. Sestavte s´ıt’ový graf odpov´ıdaj´ıc´ı uvedenému projektu. b. Vypoˇctˇete metodou CMP kritickou cestu a navrhnˇete rozvrˇzen´ı provádˇen´ı jednotlivých ˇcinnost´ı. 13. Pˇredpokládejme, ˇze v pˇredcházej´ıc´ı u ´ loze nebudou urˇceny doby trván´ı deterministicky, ale kromˇe nejpravdˇepodobnˇejˇs´ı doby trván´ı bude definován i pesimistický a optimistický odhad (viz tabulku 2.7). a. Vypoˇctˇete kritickou cestu metodou PERT a urˇcete stˇredn´ı hodnotu a smˇerodatnou odchylku doby trván´ı celého projektu. b. Urˇcete pravdˇepodobnost, ˇze celý projekt bude dokonˇcen v ˇcase kratˇs´ım neˇz 20 týdn˚ u. c. V jakých ˇcasech bude projekt dokonˇcen s pravdˇepodobnost´ı 0,90, 0,95 resp. 0,99? 14. Projekt je tvoˇren sedmi ˇcinnostmi, jejichˇz odhady dob trván´ı v mˇes´ıc´ıch a ˇcinnosti, které jim musej´ı pˇredcházet, jsou uvedeny v tabulce 2.8. ˇcinnost A B C D E F G

optimistický odhad modáln´ı odhad pesimistický odhad 2 4 5 4 6 8 1 2 3 5 6 8 2 3 4 1 3 5 3 5 9

pˇredchoz´ı ˇcinnosti ˇzádná ˇzádná A A B, C B, C D, E

Tabulka 2.8:

a. Sestavte s´ıt’ový graf odpov´ıdaj´ıc´ı uvedenému projektu. b. Vypoˇctˇete metodou CPM kritickou cestu a navrhnˇete rozvrˇzen´ı provádˇen´ı jednotlivých ˇcinnost´ı (jako dobu trván´ı uvaˇzujte modáln´ı odhad). 48

c. Vypoˇctˇete kritickou cestu metodou PERT a urˇcete stˇredn´ı hodnotu a smˇerodatnou odchylku doby trván´ı celého projektu.. d. Investor stanovil, ˇze projekt mus´ı být dokonˇcen nejpozdˇeji za 18 mˇes´ıc˚ u. Urˇcete, zda mohou nastat problémy s dodrˇzován´ım tohoto term´ınu.

49

Kapitola 3 Teorie front a syst´ emy hromadn´ e obsluhy - u ´vod Zaˇcnˇeme dvˇema názornými pˇr´ıklady. Myt´ı eˇ sus˚ u za 2. svˇ etov´ e v´ alky [5]. Po obˇedˇe u poln´ı kuchynˇe si vojáci myli j´ıdeln´ı misky u dvou vodovodn´ıch kohoutk˚ u s teplou vodou a potom je oplachovali u dalˇs´ıch dvou kohoutk˚ u se studenou vodou. Pˇri myt´ı se tvoˇrily velmi dlouhé fronty. Operaˇcn´ı d˚ ustojn´ık, který k jednotce pˇriˇsel, si vˇsiml, ˇze myt´ı misky trvá voják˚ um pr˚ umˇernˇe tˇrikrát déle neˇzli jej´ı oplachován´ı. Zaˇr´ıdil tedy, aby teplá voda na myt´ı tekla ze tˇri kohoutk˚ u a studená voda na oplachován´ı jenom z jednoho. Fronty pak skoro u ´ plnˇe zmizely. Druhý z nich, sp´ıˇse pro zasmán´ı, je z New Scientist. Teorie front pˇ red p´ ansk´ ymi a d´ amsk´ ymi z´ achody. ”Robert Matthews, spolupracuj´ıc´ı s Astonskou universitou v Británii, uchopil vˇec zcela serióznˇe, byt’ humornˇe. Matthewse zaujalo, ˇze kdyˇz ˇceká na svou lepˇs´ı poloviˇcku, neˇz vykoná svou potˇrebu, je ˇcas jako kdyby ne´ umˇerný délce fronty pˇred dámskými toaletami. Ze statistik zjistil, ˇze doba, kterou stráv´ı dámy v kabince, je dvakrát delˇs´ı, neˇz to zabere pán˚ um. Ale on ˇcekal na svou poloviˇcku vˇzdy nepomˇernˇe déle, pokud se pˇred toaletou vytvoˇrila fronta dam. Zahloubal se nad vˇec´ı v knihovnˇe a mj. zjistil, ˇze teorie front je hodnˇe velká vˇeda, do které silnˇe zasahuje teorie pravdˇepodobnosti. Po prostudován´ı vˇsech matematických formul´ı se mu vyjevilo, ˇze i kdyˇz jsou dámy v kabince jen dvakrát déle neˇz muˇzi, odbavován´ı dámské fronty trvá 2-krát-2,32- krát déle, ve výsledku tedy pˇetkrát déle.” Výˇse uvedené dva pˇr´ıklady popisuj´ı dvˇe z mnoha situac´ı, se kterými se setkáváme v bˇeˇzném ˇzivotˇe. Existuje mnoho dalˇs´ıch reálných situac´ı tohoto typu: • obsluha v bance, • vydáván´ı j´ıdel v menze, • odbavován´ı letadel na letiˇsti, • telefonn´ı u ´ stˇredna, • studenti ˇcekaj´ıc´ı na chodbˇe na zkouˇsku, ...

50

Základn´ımi charakteristikami systém˚ u hromadné obsluhy, které budeme cht´ıt znát jsou zpravidla: • stˇredn´ı poˇcet jednotek v systému, • stˇredn´ı poˇcet jednotek ve frontˇe, • stˇredn´ı doba, kterou jednotka stráv´ı v systému, • stˇredn´ı doba, kterou stráv´ı jednotka ve frontˇe, • pravdˇepodobnost, ˇze se v systému nacház´ı právˇe n jednotek. V nˇekterých pˇr´ıpadech m˚ uˇzeme uvedené charakteristiky urˇcit i bez znalosti sloˇzitého matematického aparátu. Ve sloˇzitˇejˇs´ıch pˇr´ıpadech uˇz si se selským rozumem nevystaˇc´ıme a je tˇreba vyuˇz´ıt aparátu zaloˇzeného na matematické teorii – tzv. teorii front, zvané také teorie (systém˚ u) hromadn´ e obsluhy. Pozn´ amka [5]. Zaloˇzen´ı oboru se datuje na poˇcátek 20. stolet´ı do Dánska. Matematik A. K. Erlang se pˇri svém p˚ usoben´ı v matematické spoleˇcnosti se setkal s ˇreditelem Copenhagen Telephone Company. Tento muˇz jej seznámil s problematikou ˇcekac´ıch dob pˇri telefonován´ı. Erlang se zaˇcal vˇenovat tomuto problému a v roce 1908 zaˇcal pro Copenhagen Telephone Company pracovat. Výsledkem jeho aplikace teorie pravdˇepodobnosti do kontextu telefonn´ı komunikace je práce The theory of probability and telephone conversations vydaná v roce 1909. V roce 1917 sestavil vztahy pro výpoˇcet ztrát a ˇcekac´ıch dob v telefonii. Tyto vztahy se brzo zaˇcaly pouˇz´ıvat v mnoha dalˇs´ıch telefonn´ıch spoleˇcnostech v r˚ uzných zem´ıch vˇcetnˇe British Post Office. Tato teorie umoˇznila navrhovat optimáln´ı dimenzován´ı telefonn´ıch u ´ stˇreden vzhledem k hustotˇe telefonn´ıho provozu. Prudký rozvoj teorie SHO nastal po druhé svˇetové válce spoleˇcnˇe s rozvojem celé operaˇcn´ı analýzy. Dnes se teorie SHO pouˇz´ıvá v mnoha vˇedn´ıch i pr˚ umyslových oblastech, d˚ uleˇzitá je jej´ı role pˇri provozu mobiln´ıch ˇci poˇc´ıtaˇcových s´ıt´ı.

Z´ akladn´ı pojmy SHO Teorie systém˚ u hromadné obsluhy se zabývá popisem, analýzou a návrhem (obsluˇ zn´ ych) syst´ em˚ u, jejichˇz nápln´ı je opakovaná ˇcinnost spoˇc´ıvaj´ıc´ı v uspokojován´ı urˇcitých potˇreb dané mnoˇziny objekt˚ u. Takovým systémem je napˇr´ıklad • telefonn´ı u ´ stˇredna, • výrobn´ı linka, • pokladna v obchodn´ım domˇe, ... Systém hromadné obsluhy tedy pˇredstavuje systém (fyzický, spoleˇcenský) slouˇz´ıc´ı k uspokojován´ı urˇcitých potˇreb jedinc˚ u, zákazn´ık˚ u, poˇzadavk˚ u vstupuj´ıc´ıch do systému za u ´ˇcelem jejich uspokojen´ı. K tomuto u ´ˇcelu obsahuje systém hromadné obsluhy vstupn´ı linku, kterou zákazn´ıci do systému vstupuj´ı, a obsluˇ zn´ y kan´ al jako zaˇr´ızen´ı provádˇej´ıc´ı obsluhu (uspokojován´ı) poˇzadavk˚ u zákazn´ık˚ u. V nˇekterých pˇr´ıpadech m˚ uˇze systém nav´ıc obsahovat zaˇr´ızen´ı ke shromaˇzd’ován´ı zákazn´ık˚ u ˇcekaj´ıc´ıch na obsluhu (frontu), protoˇze v pˇr´ıpadˇe jejich vstupu byl obsluˇzný kanál zaneprázdnˇen obsluhou pˇredcházej´ıc´ıho poˇzadavku. Schéma syst´ emu hromadn´ e obsluhy je znázornˇeno na obr. 3.1. Na obrázku vystupuj´ı tyto ˇcásti systému: 51

Obrázek 3.1: Systém hromadné obsluhy. z´ akazn´ık letadlo nemocný kupuj´ıc´ı telefonn´ı u ´ˇcastn´ık stroj cestuj´ıc´ı chodec vagon

linka pˇristávac´ı dráha lékaˇr pokladn´ı v samoobsluze centrála seˇrizovaˇc taxi signáln´ı svˇetla nádraˇz´ı

obsluha pˇristán´ı vyˇsetˇren´ı placen´ı nákupu spojen´ı seˇr´ızen´ı j´ızda volný pˇrechod ˇrazen´ı vlak˚ u

Tabulka 3.1:

• zákazn´ıci, poˇzadavky, jednotky - objekty vyˇzaduj´ıc´ı obsluhu, • zdroj jednotek (poˇzadavk˚ u) - uspoˇrádaná mnoˇzina jednotek pˇricházej´ıc´ıch v u ´ vahu pro obsluhu, • vstupn´ı tok - ˇcasová posloupnost vstup˚ u jednotek do systému hromadné obsluhy, • fronta - uspoˇrádaná mnoˇzina jednotek ˇcekaj´ıc´ıch na obsluhu, • kanál obsluhy - objekt (ˇci ˇclovˇek) realizuj´ıc´ı obsluhu, • výstupn´ı tok - ˇcasová posloupnost jednotek vystupuj´ıc´ıch ze systému hromadné obsluhy. Pˇr´ıklady SHO (tab. 3.1):

Klasifikace SHO Obecn´ a klasifikace Na nejvyˇsˇs´ı u ´ rovni lze SHO dˇelit na otevˇ ren´ e a uzavˇ ren´ e. Otevˇrený SHO je takový systém, kde se obsluhované poˇzadavky po jejich obslouˇzen´ı nevracej´ı do zdroje jednotek jako dalˇs´ı 52

potenciáln´ı zákazn´ıci. Naopak v uzavˇreném systému se jednotky po pr˚ uchodu systémem opˇet vracej´ı do zdroje jednotek (napˇr. do restaurace chod´ıme jednou týdnˇe, k holiˇci jednou za mˇes´ıc apod.). V tomto pˇr´ıpadˇe si lze klást otázku, zda se stávaj´ı potencionáln´ımi poˇzadavky okamˇzitˇe nebo vyˇckávaj´ı urˇcitou dobu, obecnˇe závislou na typu jednotky, dobˇe pˇredchoz´ı obsluhy, atd. Dále lze dˇelit SHO na systém se ztr´ atami nebo beze ztr´ at. V systému se ztrátami m˚ uˇze nastat situace, kdy je novˇe pˇr´ıchoz´ı poˇzadavek systémem odm´ıtnut nebo pˇr´ıpadnˇe poˇzadavek nacházej´ıc´ı se v systému tento opust´ı, aniˇz by byl obslouˇzen – docház´ı ke ztrátám. Systém beze ztrát je pak takový systém, ve kterém výˇse zm´ınˇený stav nastat nem˚ uˇze, tj. kaˇzdý pˇr´ıchoz´ı poˇzadavek je systémem obslouˇzen.

Klasifikace podle ˇ c´ ast´ı SHO SHO budeme dále klasifikovat dle specifických vlastnost´ı jednotlivých jeho ˇcást´ı, tedy podle: • Zdroje jednotek – ten m˚ uˇze být koneˇcný (mnoˇzina potencionáln´ıch zákazn´ık˚ u ohraniˇcena) nebo nekoneˇcný (mnoˇzina ohraniˇcena nen´ı). Toto dˇelen´ı je u ´ zce svázáno s dˇelen´ım SHO na otevˇrené a uzavˇrené, nebot’ nen´ı efektivn´ı uvaˇzovat SHO s nekoneˇcnou mnoˇzinou poˇzadavk˚ u jako uzavˇrený SHO (dostateˇcnˇe velkou mnoˇzinu lze povaˇzovat za nekoneˇcnou napˇr. nakupuj´ıc´ı v hypermarketu). Dále lze mnoˇzinu jednotek lze chápat jako homogenn´ı (mnoˇzinu jednotek s shodnými vlastnostmi) nebo jako mnoˇzinu nˇekolika tˇr´ıd jednotek, liˇs´ıc´ıch se urˇcitými vlastnostmi. • charakteru vstupn´ıho toku – ten m˚ uˇze být deterministický (intervaly mezi jednotlivými vstupy jsou pravidelné a známé), náhodný (je známo pouze rozdˇelen´ı pravdˇepodobnosti doby mezi vznikem jednotlivých poˇzadavk˚ u) a nebo kombinac´ı obou charakter˚ u, pˇr´ıpadnˇe závislý na typu poˇzadavku apod. Vstupn´ı tok dále dˇel´ıme podle toho, zda je realizován jednotlivými poˇzadavky ˇci po skupinách. V pˇr´ıpadˇe skupinových vstup˚ u m˚ uˇzeme specifikovat, zda velikost skupiny je pevnˇe daná, ˇci zda je závislá na typu poˇzadavku, dobˇe vzniku skupiny poˇzadavk˚ u ˇci zda je zcela náhodná. • Frontov´ eho reˇ zimu – nutno pˇripomenout, ˇze systém lze dˇelit jiˇz podle toho, zda frontu obsahuje ˇci nikoliv. V pˇr´ıpadˇe, ˇze systém obsahuje frontu, rozdˇelujeme systém podle jej´ıho reˇzimu v zásadˇe na systém s frontou FIFO, LIFO, náhodnˇe uspoˇrádanou a frontu s prioritami. Fronta FIFO pˇredstavuje základn´ı uspoˇrádán´ı poˇzadavk˚ u v poˇrad´ı jejich pˇr´ıchod˚ u. V tomtéˇz poˇrad´ı jsou pak z fronty vyb´ırány do obsluˇzného kanálu. Fronta LIFO je fronta se shodným ˇrazen´ım poˇzadavk˚ u do fronty, ale s opaˇcným výbˇerem z n´ı. V pˇr´ıpadˇe náhodného uspoˇrádán´ı frontového reˇzimu jsou poˇzadavky do fronty ˇrazeny nebo z n´ı vyb´ırány zcela náhodnˇe, pˇr´ıpadnˇe podle daného rozloˇzen´ı pravdˇepodobnosti. Frontový reˇzim s prioritami je jakýmsi zobecnˇen´ım fronty se systémem FIFO, kdy jsou poˇzadavky dále uspoˇrádány podle své priority, tzn. poˇzadavky s vyˇsˇs´ı prioritou jsou ˇrazeny pˇred poˇzadavky s niˇzˇs´ı prioritou. Tento systém priorit je oznaˇcován jako relativn´ı, tj. poˇzadavek s niˇzˇs´ı prioritou v obsluˇzném kanále je obslouˇzen bez pˇreruˇsen´ı. Situaci, kdy pˇr´ıchod poˇzadavku s vyˇsˇs´ı prioritou pˇreruˇs´ı obsluhu poˇzadavku s niˇzˇs´ı prioritou, nazýváme SHO s absolutn´ım systémem priorit. • Obsluˇ zn´ eho kan´ alu – ten nemus´ı být v systému pouze jeden. V pˇr´ıpadˇe v´ıce obsluˇzných kanál˚ u nás zaj´ımá jej´ıch uspoˇrádán´ı, m˚ uˇze být paraleln´ı nebo sériové. Ve vˇetˇsinˇe pˇr´ıpad˚ u ’ ’ je uvaˇzováno pouze paraleln´ı uspoˇrádán´ı, nebot sériové je ˇreˇseno sp´ıˇse jako s´ıt systém˚ u hromadné obsluhy (aˇz na výjimky dané vˇernost´ı modelované reálné situaci). SHO lze dále klasifkovat dle reˇ zimu provozu obsluˇzného kanálu - podle doby obsluhy a podle poˇctu 53

souˇcasnˇe obsluhovaných poˇzadavk˚ u. Dle doby obsluhy rozliˇsujeme obsluˇzné kanály s pevnou dobou obsluhy, s náhodnou dobou obsluhy popsanou rozdˇelen´ım pravdˇepodobnosti a dobou obsluhy závislou na typu obsluhovaného poˇzadavku. Podle poˇ ctu souˇ casnˇ e obsluhovan´ ych poˇ zadavk˚ u rozliˇsujeme obsluˇzný kanál provádˇej´ıc´ı obsluhu jednotlivˇe a obsluˇzný kanál provádˇej´ıc´ı obsluhu po skupinách ˇci fázovou obsluhu. Situaci lze dále komplikovat pˇredpokladem existence pˇrestávek v práci obsluˇzného kanálu, tj. interval˚ u pozasˇ taven´ı ˇcinnosti obsluhy. Cetnost tˇechto pˇrestávek m˚ uˇze být bud’ pravidelná nebo náhodná. Taktéˇz doba pˇreruˇsen´ı m˚ uˇze být pevnˇe dána nebo náhodná. Výˇse uvedené ˇclenˇen´ı lze shrnout tak, ˇze pro popis SHO mus´ıme nutnˇe znát tyto jeho charakteristiky: 1. vstupn´ı tok – popis vzniku a pˇr´ıchodu poˇzadavk˚ u do systému, 2. frontov´ y reˇ zim – jaký je osud poˇzadavk˚ u vstupuj´ıc´ıch do systému v pˇr´ıpadˇe, je-li obsluˇzný kanál obsazen v okamˇziku jejich pˇr´ıchodu, 3. organizace obsluhy – poˇcet obsluˇzných kanál˚ u a popis pr˚ ubˇehu vlastn´ı obsluhy poˇzadavk˚ u.

Kendallova klasifikace SHO Zavést symbolický popis, který by postihoval vˇsechny moˇznosti klasifikace SHO, je prakticky nemoˇzné. Na základˇe ˇctyˇr základn´ıch charakteristik, uvedených výˇse, zavedl Kendal klasifikaci SHO podle schématu X/Y /n/m kde X a Y jsou symboly z mnoˇziny uvedené n´ıˇze a n, m jsou celá ˇc´ıslo. Symboly X a Y popisuj´ı statistické rozdˇelen´ı vstupn´ıho toku, resp. charakter obsluˇzného kanálu, ˇc´ıslo n udává poˇcet obsluˇzných kanál˚ u v systému a ˇc´ıslo m oznaˇcuje maximáln´ı délku fronty. Kendal definoval 6 symbol˚ u pro bˇeˇznˇe pouˇz´ıvané typy vstupn´ıho toku a doby obsluhy: • M – Markovský-Poissonovský vstupn´ı tok, exponenciáln´ı rozdˇelen´ı vzájemnˇe nezávislých interval˚ u pˇr´ıchod˚ u jednotek ˇci doby obsluhy, • EK – Erlangovo rozdˇelen´ı interval˚ u pˇr´ıchod˚ u ˇci dob obsluhy s k ∈ N stupni volnosti, • Kn – χ2 rozdˇelen´ı s n stupni volnosti, • D – deterministické, pravidelné vstupy a doby obsluhy, • N – normáln´ı rozdˇelen´ı vstup˚ u ˇci doby obsluhy, • G – obecný pˇr´ıpad. Oznaˇcen´ı M/M/1/4 tak napˇr. znaˇc´ı systém hromadné obsluhy s poissonovským vstupn´ım tokem a jedn´ım kanálem obsluhy, jehoˇz doba obsluhy má exponenciáln´ı rozdˇelen´ı pravdˇepodobnosti a maximáln´ı délka fronty je 4. Kendalova klasifikace nen´ı u ´ plná, tj. nepostihuje vˇsechny SHO. Kendal p˚ uvodnˇe katalogizoval pouze základn´ı u ´ daje SHO, tj. vstupn´ı tok, reˇzim obsluˇzného kanálu a poˇcet paralelnˇe ˇrazených kanál˚ u s t´ım, ˇze je pˇredpokládán otevˇrený SHO beze ztrát s frontou typu FIFO. Pro speciáln´ı pˇr´ıpady je tedy nutné doplnit Kendalovu klasifikaci slovn´ım popisem odliˇsných parametr˚ u, jako 54

je napˇr´ıklad u ´ daj o omezen´ı mnoˇziny vstupn´ıch jednotek, o tom, ˇze systém je uzavˇrený atd. V literatuˇre lze také naj´ıt r˚ uzná rozˇs´ıˇren´ı standardn´ı Kendalovy klasifikace, zahrnuj´ıc´ı napˇr´ıklad omezen´ı poˇctu poˇzadavk˚ u v SHO apod.

55

Typy SHO a jejich modely C´ıle teorie SHO C´ılem teorie systém˚ u hromadné obsluhy je analýza SHO, jej´ıˇz výsledky pak slouˇz´ı k návrhu nových SHO a (nebo) optimalizaci zkoumaného systému. Obrovská variabilita SHO vˇsak neumoˇzn ˇ uje specifikovat jednotný postup takové analýzy. Teorie SHO vyuˇz´ıvá pˇri analýze matematického aparátu teorie pravdˇepodobnosti.

Markovsk´ e SHO Speciáln´ı tˇr´ıdu SHO, která má bohaté zastoupen´ı v praxi (telefonn´ı komunikace, poˇc´ıtaˇcové s´ıtˇe), tvoˇr´ı Markovské modely SHO. Tato tˇr´ıda má, d´ıky vlastnostem Poissonovského vstupn´ıho toku a exponenciáln´ıho rozdˇelen´ı pravdˇepodobnosti doby obsluhy, tu pˇr´ıjemnou vlastnost, ˇze je jednoduˇse a pˇrehlednˇe analyticky zpracovatelná. Nav´ıc pouˇzité postupy lze uplatnit pro ostatn´ı tˇr´ıdy. Jak jiˇz bylo zm´ınˇeno, markovským modelem SHO rozum´ıme takový SHO, jehoˇz vstupn´ı tok je modelován poissonovským procesem a doba obsluhy v obsluˇzném kanále(ch) má exponenciáln´ı rozdˇelen´ı pravdˇepodobnosti. V Kendalovˇe klasifikaci maj´ı takovéto systémy oznaˇcen´ı M/M/ ∗ .

M/M/1/0 Zaˇcnˇeme popisem markovského systému hromadné obsluhy s intenzitou vstupn´ıho toku λ [n−1 ] a jedn´ım kanálem obsluhy se stˇredn´ı dobou obsluhy µ1 [h] bez fronty, to znamená, ˇze v pˇr´ıpadˇe obsazeného obsluˇzného kanálu je novˇe pˇr´ıchoz´ı poˇzadavek odm´ıtnut. Pozn´ amka. Pˇri popisu markovských SHO se s u ´ spˇechem pouˇz´ıvá tzv. graf pˇ rechod˚ u (viz n´ıˇze) mezi stavy systému. U markovských SHO povaˇzujeme za stav poˇcet poˇzadavk˚ u nacházej´ıc´ıch se v daném okamˇziku v SHO. Pˇr´ıchod nového poˇzadavku zvýˇs´ı poˇcet poˇzadavk˚ u v systému a realizuje pˇrechod systému do vyˇsˇs´ıho stavu. Naopak, ukonˇcen´ı obsluhy poˇzadavku nacházej´ıc´ıho se v obsluˇzném kanále sn´ıˇz´ı poˇcet poˇzadavk˚ u v SHO a pˇredstavuje pˇrechod SHO o stav n´ıˇze. Jinak SHO setrvává ve svém aktuáln´ım stavu. Pro kaˇzdý ˇcasový okamˇzik t lze urˇcit pravdˇepodobnost, ˇze se v SHO nacház´ı právˇe k poˇzadavk˚ u (poˇcet poˇzadavk˚ u ˇcekaj´ıc´ıch ve frontˇe plus poˇzadavek v obsluˇzném kanále). Oznaˇc´ıme-li tuto pravdˇepodobnost symbolem pk (t) (p0 (t) pravdˇepodobnost, ˇze v systému je 0 jednotek, p1 (t) pravdˇepodobnost ˇze v systému je právˇe jedna jednotka atd.), pˇredstavuje vektor p(t) rozloˇzen´ı pravdˇepodobnost´ı poˇctu poˇzadavk˚ u v SHO, který zcela popisuje chován´ı SHO. V systému M/M/1/0 se nevytváˇr´ı fronta, vyskytuje se v nˇem tedy maximálnˇe jeden poˇzadavek, a to v obsluˇzném kanále. Graf pˇrechod˚ u obsahuje pouze dva stavy: prázdný systém (oznaˇc´ıme jako stav 0) a obsazený obsluˇzný kanál (stav 1). Pˇri hledán´ı pˇredpisu pro urˇcen´ı p(t) budeme nejprve specifikovat události, které lze na SHO na intervalu délky ∆t pozorovat. Moˇzné události spolu s jejich pravdˇepodobnostmi jsou pro 56

ud´ alost pˇr´ıchod nového poˇzadavku do systému v intervalu (∆t) ukonˇcen´ı obsluhy poˇzadavku nacházej´ıc´ıho se v obsluˇzném kanále za interval (∆t) nedojde k ˇzádné události v intervalu (∆t)

pravdˇ epodobnost P (∆t) λ∆t µ∆t 1 − (λ + µ)∆t

Tabulka 3.2: Pravdˇepodobnosti vzniku moˇzných událost´ı SHO M/M/1/0.

dostateˇcnˇe malý interval ∆t shrnuty v tabulce 3.2. Systém lze pak popsat pomoc´ı grafu pˇrechod˚ u na obr. 3.2, kde jsou znázornˇeny stavy systému a pravdˇepodobnosti pˇrechod˚ u mezi jednotlivými stavy. Graf pˇrechod˚ u je charakterizován matic´ı pˇrechodu P(t, t + (∆t),

Obrázek 3.2: Graf pˇrechod˚ u SHO M/M/1/0

P(t, t + (∆t) =

1 − λ∆t λ∆t µ∆t 1 − µ∆t

.

Pˇredpokládejme, ˇze známe rozloˇzen´ı pravdˇepodobnosti stav˚ u SHO v ˇcase t, které je dáno vektorem p(t) = [p0 (t), p1 (t)]. Pak lze s vyuˇzit´ım matice pˇrechod˚ u naj´ıt rozloˇzen´ı pravdˇepodobnosti stav˚ u v ˇcase (t + ∆t) pomoc´ı vztahu p(t + ∆t) = p(t) · P(t, t + (∆t).

(3.1)

Ze vztahu (3.1) spolu s matic´ı pˇrechod˚ u lze z´ıskat rozloˇzen´ı pravdˇepodobnosti stav˚ u SHO pro libovolný ˇcas tk = t0 + k∆t, známe-li výchoz´ı rozloˇzen´ı p(t0 ), p(tk ) = p(t0 ) · Pk (t, t + (∆t). Vztah (3.1) lze zapsat jako p(t + ∆t) = p(t)I + p(t)A∆t, kde A=

−λ λ µ −µ

je matice intezity pˇ rechod˚ u. Následnˇe pak lze vztah (3.1) upravit, p(t + ∆t) − p(t) = p(t)A, ∆t a pro ∆t → 0 dostáváme soustavu obyˇcejných diferenciáln´ıch rovnic p˙0 (t) = −λp0 (t) + µp1 (t), p˙1 (t) = λp0 (t) − µp1 (t) 57

(3.2)

ˇ sen´ı soustavy je ponecháno jako cviˇcen´ı, s poˇcáteˇcn´ı podm´ınkou p(0). Reˇ p0 (t) = p0 (0)e−(λ+µ)t +

µ 1 − e−(λ+µ)t . λ+µ

Pro poˇcáteˇcn´ı podm´ınku prázdného stavu SHO, p0 (0) = 1, dostáváme vývoj pravdˇepodobnosti výskytu systému ve stavu ”0”, p0 (t) =

µ λ −(λ+µ)t + e , λ+µ λ+µ

zat´ımco pro zpoˇcátku obsazený SHO, p0 (0) = 0, je p0 (t) =

µ µ −(λ+µ)t − e . λ+µ λ+µ

Vývoj pravdˇepodobnosti p0 (t) výskytu systému ve stavu ”0” pro obˇe poˇcáteˇcn´ı podm´ınky zachycuje graf na obr. 3.3. Vztah pro vývoj pravdˇepodobnosti p1 (t) výskytu ve stavu ”1”

Obrázek 3.3: Pr˚ ubˇeh rozloˇzen´ı pravdˇepodobnosti stavu ”0” SHO pro otevˇrený systém MM/1/0 se urˇc´ı analogicky. Vˇetˇsinou nen´ı nutné znát popis chován´ı SHO v kaˇzdém okaˇziku (napˇr. v okamˇzic´ıch pˇrechodu), ale z hlediska analýzy SHO nás zaj´ımá chován´ı v delˇs´ım horizontu, v ustáleném ”stacionárn´ım” stavu. Pravdˇepodobnost p0 (t) se nezávisle na poˇcáteˇcn´ı podm´ınce bl´ıˇz´ı limitn´ı hodnotˇe pro t → +∞, lim p0 (t) =

µ ∀p0 (0), λ+µ

lim p1 (t) =

λ ∀p1 (0). λ+µ

t→+∞

t→+∞

Pokud nás jiˇz od zaˇcátku nezaj´ımá chován´ı SHO v kaˇzdém okamˇziku a chceme pouze nalézt popis ustáleného SHO, nen´ı efektivn´ı postupovat výˇse uvedeným zp˚ usobem (ˇreˇsen´ım systému ODE). Pro ustálený reˇzim SHO plat´ı dpi (t) = 0, dt pravdˇepodobnosti jsou konstantn´ı a soustava (3.2) pˇrejde na soustavu lineárn´ıch rovnic, 0 = −λp0 + µp1 0 = λp0 − µp1 58

(3.3)

doplnˇenou o normovac´ı podm´ınku (viz cviˇcen´ı) p0 + p1 = 1 ˇ sen´ım soustavy (3.3) dostáváme opˇet (jinak je ˇreˇsen´ı ∞ mnoho). Reˇ p0 =

µ λ , p1 = 1 − p0 = . λ+µ λ+µ

Na základˇe z´ıskaných rozloˇzen´ı pravdˇepodobnost´ı stav˚ u systému m˚ uˇzeme nyn´ı urˇcit potˇrebné charakteristiky SHO. Tyto charakteristiky jsou závislé jednak na typu SHO, hlavnˇe pak na u ´ˇcelu analýzy daného SHO (nˇekteré charakteristiky nás zaj´ımaj´ı, jiné ne). Prvn´ı charakteristikou je tzv. pravdˇ epodobnost odm´ıtnut´ı, definovaná jako pravdˇepodobnost, ˇze nový poˇzadavek nebude pˇrijat do systému k obsluze (= pravdˇepodobnost, ˇze se systém nacház´ı ve stavu ”1”). V naˇsem pˇr´ıpadˇe je pravdˇepodobnost odm´ıtnut´ı rovna podm = p1 =

λ . λ+µ

Pravdˇepodobnost pˇrijet´ı nového poˇzadavku k obsluze (pravdˇepodobnost, ˇze se systém nacház´ı ve stavu ”0”) je také oznaˇcována jako relativn´ı kapacita systému, Kr = p0 = 1 − podm =

µ . λ+µ

Absloutn´ı kapacita systému pak pˇredstavuje pr˚ umˇern´ y poˇcet obslouˇzených poˇzadavk˚ u za jednotku ˇcasu, Ka = λKr . Postup anal´ yzy markovsk´ eho SHO. Podobným zp˚ usobem jako výˇse postupujeme pˇri analýze jakéhokoliv markovského SHO: 1. Sestav´ıme graf pˇrechod˚ u. 2. Nalezneme rozloˇzen´ı pravdˇepodobnosti stav˚ u systému: • na základˇe grafu pˇrechod˚ u sestav´ıme a vyˇreˇs´ıme soustavu diferenciáln´ıch rovnic,

• na základˇe grafu pˇrechod˚ u nalezneme rozloˇzen´ı pravdˇepodobnosti stav˚ u v ustáleném stavu (pokud ten existuje).

3. Provedeme výpoˇcet charakteristik systému.

M/M/n/0 Rozˇs´ıˇr´ıme uvaˇzovaný SHO tak, ˇze budeme uvaˇzovat SHO bez ˇcekán´ı s n obsluˇznými kanály. Dle uvedeného postupu sestav´ıme graf pˇrechod˚ u. Systém má n + 1 stav˚ u (prázdný systém plus obsazené kanály obsluhy). T´ım pádem se zmˇen´ı oproti minulému pˇr´ıpadu pravdˇepodobnost ukonˇcen´ı obsluhy v nˇekterém z pracuj´ıc´ıch kanál˚ u. Pracuje-li k paraleln´ıch kanál˚ u, pak pravdˇepodobnost dokonˇcen´ı obsluhy v nˇekterém z tˇechto kanál˚ u je dána souˇctem pravdˇepodobnost´ı dokonˇcen´ı obsluhy ve vˇsech k pracuj´ıc´ıch kanálech. Je-li intenzita obsluhy pro vˇsechny kanály shodná = µ, pak pravdˇepodobnost dokonˇcen´ı obsluhy v nˇekterém z k pracuj´ıc´ıch kanál˚ u je na ˇcasovém intervalu ∆t rovna pkonec = kµ∆t. 59

Obrázek 3.4: Graf pˇrechod˚ u SHO M/M/n/0 bez ˇcekán´ı. Analogicky odvod´ıme pravdˇepodobnosti pˇrechod˚ u mezi dalˇs´ımi stavy. Graf pˇrechod˚ u je znázornˇen na obr. 3.4 a matice pravdˇepodobnosti pˇrechod˚ u bude m´ıt tvar   1 − λ∆t λ∆t 0 0   ..  µ∆t  1 − (λ + µ)∆t λ∆t 0 .   P=  0 2µ∆t 1 − (λ + 2µ)∆t λ∆t     λ∆t 0 0 ... 1 − nµ∆t ´ Uloha tak vede na soustavu n + 1 diferenciáln´ıch rovnic prvn´ıho ˇrádu, p˙0 (t) p˙1 (t) .. . p˙k (t) .. . p˙n (t)

= −λp0 (t) + µp1 (t), = λp0 (t) − (λ + µ)p1 (t) + 2µp2(t), = λpk−1 (t) − (λ + kµ)pk (t) + (k + 1)µpk+1 (t), = λpn−1 (t) − nµpn (t).

Tato soustava rovnic se nazývá Erlangova. Lze nalézt stacionárn´ı ˇreˇsen´ı (stacionárn´ı ˇreˇsen´ı pro ˇ s´ıme tedy opˇet soustavu lineárn´ıch rovnic vzniklých z diferSHO bez ˇcekán´ı vˇzdy existuje). Reˇ enciáln´ıch rovnic poloˇzen´ım levé strany nule, doplnˇenou podm´ınkou (vˇeta o u ´ plné pravdˇepodobnosti) n X

pi = 1.

(3.4)

i=0

Indukc´ı lze dokázat, ˇze rozloˇzen´ı pravdˇepodobnosti k-tého stavu systému je dáno jako pk =

ρk λ p0 , ρ = . k! µ

(3.5)

Rovnice (3.5) se nazývá Erlang˚ uv vzorec. D˚ ukaz je ponechán jako cviˇcen´ı. Z normovac´ı podm´ınky (3.4) pak dostáváme !−1 n X ψk . p0 = k! k=0

60

Pravdˇepodobnost, ˇze v systému se nacház´ı právˇe k jednotek lze tedy urˇcit ze vztahu pk =

ψk Pnk! ψi i=0 i!

.

Pˇristupme nyn´ı k analýze dalˇs´ıch vlastnost´ı SHO:

1. Pravdˇepodobnost odm´ıtnut´ı novˇe pˇr´ıchoz´ıho poˇzadavku podm = pn (n je poˇcet obsluˇzných kanál˚ u). 2. Pravdˇepodobnost pˇrijet´ı novˇe pˇr´ıchoz´ıho poˇzadavku (relativn´ı kapacita) Kr =

n−1 X i=0

pi = 1 − pn .

3. Absolutn´ı kapacita systému, pˇredstavuje pr˚ umˇern´ y poˇcet obslouˇzených poˇzadavk˚ u za jednotku ˇcasu, Ka = λ(1 − pn ). 4. Stˇredn´ı poˇcet obsazených kanál˚ u nz nz =

n X

kpk .

k=0

5. Koeficient vyuˇzit´ı kanál˚ u obsluhy Kz Kz =

E{nz } . n

6. Stˇredn´ı poˇcet volných kanál˚ u obsluhy n0 n X n0 = (n − k)pk . k=0

7. Koeficient prostoje K0 K0 =

n0 . n

Mus´ı platit n0 + nz = n, K0 + Kz = 1.

M/M/n/m Dalˇs´ım zobecnˇen´ım dostáváme uzavˇrený SHO s n obsluˇznými kanály a maximáln´ı délkou fronty m. Pravdˇepodobnost vzniku nového poˇzadavku je závislá na poˇctu poˇzadavk˚ u v mnoˇzinˇe pˇr´ıpustných poˇzadavk˚ u v dobˇe vzniku nového poˇzadavku. Pravdˇepodobnost vzniku nového poˇzadavku na intervalu délky ∆t v pˇr´ıpadˇe, ˇze v mnoˇzinˇe potenciáln´ıch poˇzadavk˚ u je k poˇzadavk˚ u, je pvznik = kλ∆t. Analýzou moˇzných událost´ı na SHO sestav´ıme graf pˇrechod˚ u (obr. 3.5). Ten umoˇzn ˇ uje publikovaným zp˚ usobem naj´ıt jak u ´ plný popis dynamického chován´ı systému, tak rozloˇzen´ı pravdˇepodobnost´ı stav˚ u systému ve stacionárn´ım reˇzimu, který vzhledem ke koneˇcné mnoˇzinˇe zdroje poˇzadavk˚ u existuje vˇzdy. K proveden´ı analýzy uvaˇzovaného systému lze opˇet pouˇz´ıt navrˇzený postup (graf pˇrechod˚ u, stacionárn´ı ˇreˇsen´ı, analýza vlastnost´ı). Jestliˇze pravdˇepodobnost dosaˇzen´ı stavu m + n se bl´ıˇz´ı nule, potom se vlastnosti systému M/M/n/m bl´ıˇz´ı vlastnostem systému M/M/n/∞. 61

Obrázek 3.5: Graf pˇrechod˚ u SHO M/M/n/m.

M/M/1/∞ Pˇredchoz´ı (uzavˇrené) systémy m˚ uˇzeme zobecnit na systémy s neomezenou délkou fronty (otevˇrené). Pˇredpokládáme frontu typu FIFO. Modely tohoto typu maj´ı nekoneˇcnˇe mnoho stav˚ u, coˇz pˇrináˇs´ı komplikace pˇri ˇreˇsen´ı uvedeným postupem. Jako prvn´ı budeme uvaˇzovat SHO s jedn´ım kanálem obsluhy. Výˇrez grafu pˇrechod˚ u je znázornˇen na obr. 3.6 Matice pravdˇepodobnost´ı pˇrechod˚ u má nekoneˇcný rozmˇer,

Obrázek 3.6: Graf pˇrechod˚ u otevˇreného SHO M/M/1/∞. 

  P(t, t + (∆t) =   

1 − λ∆t λ∆t 0 0 µ∆t 1 − (λ + µ)∆t λ∆t 0 0 µ∆t 1 − (λ + µ)∆t λ∆t 0 0 µ∆t 1 − (λ + µ)∆t ... ... ... ...

62

... ... ... ... ...



  .  

Zavedeme-li matici intenzity pˇrechod˚ u obvyklým zp˚ usobem,  −λ λ 0 0  µ −(λ + µ) λ 0  µ −(λ + µ) λ A=  0  0 0 µ −(λ + µ) ... ... ... ...

ˇreˇs´ıme pak nekoneˇcnˇe velkou soustavu diferenciáln´ıch rovnic,

... ... ... ... ...



  ,  

˙ p(t) = Ap(t) s poˇcáteˇcn´ı podm´ınkou a normovac´ı podm´ınkou X pi = 1. ∀i

Tuto soustavu lze ˇreˇsit, ovˇsem komplikovanˇe. Proto se zde budeme vˇenovat hledán´ı ustáleného reˇzimu. Je nutné urˇcit, zda a za jakých podm´ınek stacionárn´ı reˇzim pro daný SHO existuje. Pro uvaˇzovaný pˇr´ıpad SHO lze urˇcit podm´ınku existence stacionárn´ıho reˇzimu logickou u ´ vahou. V systému se nebudou hromadit poˇzadavky pouze v pˇr´ıpadˇe, ˇze obsluˇzný kanál je schopen za jednotku ˇcasu odbavit v´ıce poˇzadavk˚ u, neˇz kolik jich m˚ uˇze za danou dobu pˇrij´ıt, tj. mus´ı platit λ < µ. Z následuj´ıc´ıho postupu vyplyne, ˇze je to postaˇcuj´ıc´ı podm´ınka pro existenci stacionárn´ıho ˇreˇsen´ı. Pˇredpokládejme nyn´ı, ˇze stacionárn´ı ˇreˇsen´ı existuje. Hledáme ˇreˇsen´ı soustavy lineárn´ıch rovnic Ap = 0, X pi = 1. ∀i

Pokud si uvedenou soustavu rovnic vyjádˇr´ıme, dostáváme: −λp0 + µp1 = 0 λp0 − (λ + µ)p1 + µp2 = 0 λp1 − (λ + µ)p2 + µp3 = 0 ... λpk−1 − (λ + µ)pk + µpk+1 = 0 ... (3.6) Pokusme se nalézt ˇreˇsen´ı rekurentn´ım postupem. Definujme ̺ = µλ . Z prvn´ı rovnice dostáváme p1 = ̺p0 , dosazen´ım do druhé je po u ´ pravˇe (proved’te) p2 = ̺2 p0 . Opakován´ım tohoto postupu dostáváme pro k-tý stav pk = ̺k p0 . 63

Dosazen´ım tohoto vztahu do normovac´ı podm´ınky pak lze z´ıskat vztah pro p0 , X p0 ̺k = 1. ∀i

Jak známo, nekoneˇcná geometrická ˇrada konverguje, pokud ̺ < 1. Potom je souˇcet roven X

1 . 1−̺

̺k =

∀i

Rozloˇzen´ı pravdˇepodobnosti stavu 0 je tedy p0 = 1 − ̺, pro ostatn´ı stavy pak plat´ı pk = ̺k (1 − ̺), k = 0, 1, 2, ... Rozdˇelen´ı pravdˇepodobnost´ı má geometrické rozdˇelen´ı. Z definice ̺ pak plyne, ˇze podm´ınka konvergence ˇrady ̺ < 1 je ekvivalentn´ı podm´ınce λ < µ. Podm´ınku konvergence ˇrady ̺ < 1 téˇz nazýváme podm´ınkou stability systému. Odvozen´ı základn´ıch charakteristik analyzovaného SHO: • stˇredn´ı hodnota poˇctu poˇzadavk˚ u v SHO - ns ns =

∞ X k=0

= (1 − ̺)̺

d d̺

∞ X k=0

k · pk = (1 − ̺)

̺k = (1 − ̺)̺

d d̺

1 1−̺

∞ X k=0

k

k.̺ = (1 − ̺)̺

= (1 − ̺)̺

∞ X

̺k−1 =

k=0

1 ̺ = , (1 − ̺)2 1−̺

• stˇredn´ı hodnota délky fronty nf nf =

∞ X k=0

k.pk+1 = ̺

∞ X k=0

k.pk = ̺E{ds } =

̺2 , 1−̺

• doba strávená v systému hromadné obsluhy ts

Uvaˇzujme, ˇze v okamˇziku t je v SHO k poˇzadavk˚ u a právˇe pˇricház´ı nový (k + 1). Jaká je hustota rozloˇzen´ı doby strávené v SHO právˇe pˇr´ıchoz´ıho poˇzadavku? Tento problém je nutné ˇreˇsit s ohledem na poˇcet poˇzadavk˚ u i, které se jiˇz v SHO nacház´ı.

a) i = 0: Doba strávená v SHO je v tomto pˇr´ıpadˇe rovna dobˇe obsluhy poˇzadavku, tj. f (ts , 0) = µ.e−µts . Hustotu pravdˇepodobnosti lze popsat exponenciáln´ım rozdˇelen´ım s intenzitou náhodného jevu µ.

64

b) i = 1: Jeden poˇzadavek v obsluze a fronta je prázdná. Doba, kterou poˇzadavek stráv´ı v SHO, je rovna ts = τ1 + τ2 , kde • τ1 je doba dokonˇcen´ı obsluhy poˇzadavku v obsluˇzném kanále. Jiˇz v´ıme, ˇze tato doba má exponenciáln´ı rozdˇelen´ı s intenzitou µ. • τ2 je doba obsluhy poˇzadavku, která má opˇet exponenciáln´ı rozdˇelen´ı s intenzitou µ. Doba ts bude m´ıt tud´ıˇz Erlangovo rozdˇelen´ı E2 , µts f (ts , 1) = µ.e−µts 1! c) i = k Doba kterou poˇzadavek stráv´ı v SHO je ts = τ1 + τ2 + ... + τk+1 , kde jsou • τ1 doba dokonˇcen´ı obsluhy poˇzadavku v obsluˇzném kanále, • τ2 , ..., τk doba obsluhy poˇzadavk˚ u nacházej´ıc´ıch se ve frontˇe, • τk+1 obsluha pˇr´ıchoz´ıho poˇzadavku. Doba ts má v tomto pˇr´ıpadˇe Erlangovo rozdˇelen´ı s parametrem k, (µts )k . k! Na základˇe výˇse uvedených skuteˇcnost´ı a poznatk˚ u teorie pravdˇepodobnosti je rozdˇelen´ı pravdˇepodobnosti doby obsluhy dáno vztahem f (ts , k) = µ.e−µts

ts =

∞ X

f (t, k)pk =

k=0

∞ X

µ.e−µts

k=0

= (1 − ̺)µe−µts

∞ X (̺µts )k

k=0 −(µ−λ)ts

= (µ − λ)e

k!

(µts )k (1 − ̺)̺k = k!

= (µ − λ)e−µts eλts =

.

Z pˇredchoz´ıho odvozen´ı je vidˇet, ˇze ts má exponenciáln´ı rozdˇelen´ı pravdˇepodobnosti. Plat´ı tud´ıˇz 1 ts = , µ−λ

4. doba strávená ve frontˇe tf

Lze ji odvodit analogicky k dobˇe strávené v SHO. M˚ uˇzeme vˇsak vyuˇz´ıt vztahu, který plat´ı mezi dobou strávenou ve frontˇe a v SHO, ts = tf + τ, kde τ je doba strávená poˇzadavkem v obsluˇzném kanále. Protoˇze jsou tyto veliˇciny navzájem nezávislé, plat´ı tento vztah i pro stˇredn´ı hodnoty, lze tedy psát tf = ts −

1 1 = ... = ̺ = ̺ts , µ µ−λ 65

Zrekapitulujme nyn´ı vztahy pro výpoˇcet nejd˚ uleˇzitˇejˇs´ıch charakteristik systému: • stˇredn´ı hodnota poˇctu poˇzadavk˚ u v SHO - ns ns =

̺ , 1−̺

• stˇredn´ı hodnota délky fronty nf nf =

̺2 , 1−̺

• doba strávená v systému hromadné obsluhy ts ts = • doba strávená ve frontˇe tf

1 , µ−λ

tf = ̺ts ,

• doba obsluhy tob

Doba obsluhy má exponenciáln´ı rozdˇelen´ı s parametrem µ, tud´ıˇz plat´ı tob =

1 , µ

• doba souvislého prostoje tp

Doba souvislého prostoje nezávis´ı na rychlosti obsluhy. Kdyˇz se ˇcinnost kanálu obsluhy zastav´ı, ˇceká dokud nepˇrijde dalˇs´ı poˇzadavek. V d˚ usledku toho, ˇze intenzita vstupn´ıho toku je λ, potom doba souvislého prostoje má exponenciáln´ı rozdˇelen´ı pravdˇepodobnosti s parametrem λ. M˚ uˇzeme tedy psát 1 tp = , λ

• doba souvislé práce pracoviˇstˇe tz

tz =

1 , µ−λ

M/M/n/∞ Jako posledn´ı budeme analyzovat SHO s n obsluˇznými kanály a neomezenou délkou fronty typu FIFO. Pro jednoduchost pˇredpokládejme, ˇze vˇsechny paraleln´ı kanály maj´ı stejnou intenzitu obsluhy µ. Graf pˇrechod˚ u je na obr. 3.7. Nebudeme zde analyzovat ˇreˇsen´ı soustavy diferenciáln´ıch rovnic a opˇet se zamˇeˇr´ıme na stacionárn´ı ˇreˇsen´ı. Je nutno formulovat podm´ınku existence stacionárn´ıho ˇreˇsen´ı, kterou lze odvodit analogickým zp˚ usobem jako v pˇr´ıpadˇe systému M/M/1/1. Podm´ınku existence stacionárn´ıho reˇzimu lze také naj´ıt cestou zobecnˇené podm´ınky pro systém M/M/1/1. Uvaˇzovaný model SHO s n paraleln´ımi kanály s intenzitami µ lze nahradit systémem s jedn´ım kanálem obsluhy s intenzitou nµ. Intenzita provozu takového systému je urˇcena vztahem ̺¯ =

λ ̺ = , n nµ 66

Obrázek 3.7: Graf pˇrechod˚ u systému M/M/n/∞. pˇriˇcemˇz zobecnˇen´ı pro kanály s r˚ uznými intenzitami µi, i ∈ n ˆ je λ ̺¯ = Pn

k=1 µi

Stacionárn´ı ˇreˇsen´ı (jak tohoto jednokanálového, tak p˚ uvodn´ıho systému) existuje tehdy a jen tehdy, pokud plat´ı ̺¯ < 1. Hledán´ı ˇreˇsen´ı odpov´ıdaj´ıc´ı soustavy algebraických rovnic pom˚ uˇze zjednoduˇsit podrobnˇejˇs´ı analýza grafu pˇrechod˚ u. Ten je moˇzné rozdˇelit na dvˇe ˇcásti, na ˇcást pro k ≤ n, analogickou se systémem M/M/n/n, a na ˇcást pro k > n, analogickou se systémem M/M/1/∞, ve kterém nahrad´ıme n paraleln´ıch kanál˚ u jedn´ım kanálem s intenzitou obsluhy µ ¯ = nµ. Rozdˇelen´ı pravdˇepodobnosti stav˚ u je ̺k p0 , k = 0, 1, ..., n − 1, k! ̺k nn p0 , k ≥ n. = nk n!

pk =

Výˇse uvedené vztahy opˇet dosad´ıme do normovac´ı podm´ınky ∞ X

pk = 1

k=0

a po u ´ pravˇe dostaneme vztah pro rozloˇzen´ı pravdˇepodobnost´ı prázdného systému, " n−1 #−1 X ̺k ̺n n p0 = . + k! (n − ̺)n! k=0

67

Analýza charakteristik SHO se provede analogicky jako v pˇr´ıpadˇe M/M/1/∞. Uvedeme nyn´ı vztahy pro výpoˇcet nejd˚ uleˇzitˇejˇs´ıch charakteristik systému: • pravdˇepodobnosti poˇctu jednotek v systému: p0 =

1 ̺n ̺ n!(1− n )

+

̺i i=0 i!

Pn−1

pi =

̺i · p0 pro i = 1, 2, ..., n i!

pi =

̺i · p0 pro i > n n! · ni−n

• stˇredn´ı hodnota délky fronty nf : nf =

̺n+1 n · n! 1 −

• stˇredn´ı hodnota poˇctu poˇzadavk˚ u v SHO ns :

̺ 2 n

ns = nf + ̺ • doba strávená v SHO ts : ts = tf +

68

1 µ

· p0

Cviˇ cen´ı a pˇ r´ıklady Cviˇ cen´ı. 1. Vyˇreˇste soustavu diferenciáln´ıch rovnic (3.2). ˇ sen´ı: * Reˇ Z vˇety o u ´ plné pravdˇepodobnosti vyplývá, ˇze p0 (t) + p1 (t) = 1. Provedeme substituci za druhou neznámou a dostaneme

ˇ sen´ım rovnice je Reˇ p0 (t) = p0 (0)e−(λ+µ).t + µ

p0˙(t) = −(λ + µ)p0 (t) + µ. Rt 0

e−(λ+µ).τ dτ == p0 (0)e−(λ+µ).t +

µ λ+µ

ˇ sen´ı p1 (t) se nalezne analogicky. Reˇ

1 − e−(λ+µ).t .

Pˇ r´ıklady. 2. Uvaˇzujme informaˇcn´ı stˇredisko, kam pˇricház´ı v pr˚ umˇeru kaˇzdé 2 minuty hovor. Pr˚ umˇerná doba trván´ı hovoru je 0,8 min. Pˇredpokládáme, ˇze vstupn´ı tok je poissonovský a doba obsluhy má exponenciáln´ı rozloˇzen´ı pravdˇepodobnosti. Urˇcete: – jaké procento poˇzadavk˚ u bude obslouˇzeno, tj. relativn´ı kapacitu, – kolik hovor˚ u bud obslouˇzeno za minutu, tj. absolutn´ı kapacitu, – pravdˇepodobnost odm´ıtnut´ı novˇe pˇr´ıchoz´ıho poˇzadavku, – nomináln´ı kapacitu (absolutn´ı), tj. kolik hovor˚ u za jednotku ˇcasu by se mohlo uskuteˇcnit pˇri deterministickém ˇrazen´ı hovor˚ u. 3. V ˇcekárnˇe u lékaˇre je 6 stoliˇcek, ostatn´ı pacienti musej´ı ˇcekat ve stoje. V pr˚ umˇeru jsou ˇ to 3 pacienti. Pˇr´ıchod pacient˚ u je náhodná promˇenná s Poissonovským rozdˇelen´ım. Cas ´ prohl´ıdky má exponenciáln´ı rozdˇelen´ı s pr˚ umˇernou dobou 15 minut. Ukolem je urˇcit: – pravdˇepodobnost, ˇze pˇr´ıchoz´ı pacient najde lékaˇre obsazeného, – ˇcas, který pacient stráv´ı u lékaˇre, – pravdˇepodobnost, ˇze pacient bude muset ze zaˇcátku ˇcekat ve stoje. 4. Pˇredpokládejte vstupn´ı kontrolu pˇri vstupu do zábavn´ıho parku. Ta je provádˇena tˇremi stejnˇe zdatnými pracovn´ıky ochranky. Návˇstˇevn´ık je kontrolován v pˇr´ıpadˇe, ˇze nˇekterý z pracovnik˚ u ochranky je volný, jinak procház´ı bez kontroly. Pˇredpokládejme, ˇze pracovn´ıci dohromady zvládnou zkontrolovat bˇehem hodiny 9 návˇstˇevn´ık˚ u. Dále pˇredpokládáme, ˇze návˇstˇevnic´ı chod´ı jednotlivˇe a bˇehem hodiny pˇrijdou pˇribliˇznˇe 4. Urˇcete: 69

– pr˚ umˇerný poˇcet zákazn´ık˚ u, kteˇri do zábavn´ıho parku vstoup´ı bez kontroly, – pravdˇepodobnost, ˇze se vám podaˇr´ı proj´ıt bez kontroly. 5. Uvaˇzujme sluˇzbu vyhledáván´ı telefonn´ıch ˇc´ısel se 2 linkami. V pˇr´ıpadˇe alespoˇ n jedné volné linky je novˇe pˇr´ıchoz´ı hovor na tuto linku pˇresmˇerován. V pˇr´ıpadˇe obou volných linek je u ´ˇcastn´ık pˇrepojen na prvn´ı linku. V opaˇcném pˇr´ıpadˇe se u ´ stˇredna hlás´ı obsazovacim tónem. Pˇredpokládejme intenzitu pˇr´ıchod˚ u hovor˚ u 10 za hodinu. Operátorka u prvn´ı linky je zdatnˇejˇs´ı a zvládne za hodinu odbavit 20 hovor˚ u. Opérátorka u druhé linky pak pouze 15 hovor˚ u za hodinu. Urˇcete vyuˇzit´ı centrály a dále pak jednotlivých operátorek. 6. Stanice technické kontroly je vybavená dvˇema zkuˇsebn´ımi rampami. V hale je dále vyhrazeno jedno m´ısto pro parkován´ı vozidla ˇcekaj´ıc´ıho na kontrolu. Ostatn´ı vozidla jsou odmitnuta. Zkuˇsebn´ı rampy jsou obsazovány zcela náhodnˇe, pˇr´ıˇcemˇz na prvn´ı modernˇejˇs´ı je moˇzné zkontrolovat 5 vozidel za den, na druhé zastaralejˇs´ı jen 4. Na stanici technické kontroly se v pr˚ umˇeru objev´ı 6 vozidel dennˇe. Urˇcete: – pravdˇepodobnost u ´ spˇeˇsného vyˇr´ızen´ı poˇzadavku na technickou kontrolu, – pr˚ umˇerný poˇcet aut v STK, – vyuˇzit´ı modernˇejˇs´ı zkuˇsebn´ı rampy. 7. Chirurg na poliklinice je schopen vyˇsetˇrit v pr˚ umˇeru 25 pacient˚ u dennˇe. Ordinace je vybavena velice malou ˇcekárnou, která pojme jednoho sed´ıciho a dva stojic´ı pacienty. Ti, co se do ˇcekárny nevejdou, odcházej´ı k jinému lékaˇri. V pr˚ umˇeru se dennˇe vyskytne 20 pacient˚ u poˇzaduj´ıc´ıch oˇsetˇren´ı. Urˇcete: – pr˚ umˇerný poˇcet pacient˚ u ˇcekaj´ıc´ıch v ˇcekárnˇe, – pravdˇepodobnost, ˇze novˇe pˇr´ıchoz´ı pacient najde ˇcekárnu zcela prázdnou, – pravdˇepodobnost, ˇze ˇcekárna bude zaplnˇena. 8. Uvaˇzujme malou výrobn´ı firmu. Ta vyuˇz´ıvá k produkci vlastnich výrobk˚ u ˇctyˇr horizontálnich frézek. Jejich u ´ drˇzbou je povˇeˇren jeden pracovnik, který dokáˇze bˇeˇznou závadu odstranit bˇehem 1 hodiny. Pr˚ umˇerná doba bezporuchového provozu jedne frézky je pˇribliˇznˇe 3,5 hodiny. Urˇcete: – kolik frezék je pˇribliˇznˇe v provozu a kolik jich je kv˚ uli poruˇse odstaveno, – pravdˇepodobnost toho, ˇze pˇri náhodné kontrole najdeme odpoˇc´ıvaj´ıc´ıho pracovn´ıka u ´ drˇzby. 9. Uvaˇzujme poˇc´ıtaˇcový systém objednávek a vydáván´ı poloˇzek ze skladu. Systém je tvoˇren jedn´ım serverem zpracovávaj´ıc´ım poˇzadavky, doplnˇeným bufferem na 1 poˇzadavek, a 3 stanicemi. Zpracován´ı jednoho poˇzadavku trvá serveru pˇribliˇznˇe 1 sekundu, pˇr´ıˇcemˇz za hodinu vznikne na stanic´ıch pˇribliˇznˇe 50 dotaz˚ u. V pˇr´ıpadˇe zaneprázdnˇen´ı serveru je novˇe pˇr´ıchoz´ı dotaz doˇcasnˇe uloˇzen v bufferu. Dalˇs´ı je pak odm´ıtnut jako nezpracovatelný v daném okamˇziku. Urˇcete pravdˇepodobnost, ˇze vzniklý poˇzadavek bude skuteˇcnˇe zpracován. 10. Nápojový automat, um´ıstˇený spolu s nˇekolika dalˇs´ımi v nádraˇzn´ı budovˇe, obslouˇz´ı za den pˇribliˇznˇe 50 zákazn´ık˚ u, pˇriˇcemˇz výdej nápoje trvá pˇribliˇznˇe 5 minut. Automat vˇsak potˇrebuje v pr˚ umˇeru dvakrát dennˇe (pro zjednoduˇsen´ı nezávisle na poˇctu obslouˇzených

70

zákazn´ık˚ u) doplnit výchoz´ı suroviny. Tato procedura zabere technikovi zhruba 1 hodinu. Vzhledem k tomu, ˇze toto nen´ı jediný automat, vyuˇz´ıvaj´ı potenciáln´ı zákazn´ıci v pˇr´ıpadˇe obsazen´ı automatu (jiným zákazn´ıkem nebo u ´drˇzbou) nˇekterý dalˇs´ı automat. Urˇcete pravdˇepodobnost pˇr´ıchodu zákazn´ıka v dobˇe u ´drˇzby. 11. Uvaˇzujme kadeˇrnický salón zahrnuj´ıc´ı dámské i pánské kadeˇrnictv´ı. Do salónu pˇr´ıcházej´ı páni a dámy jak samostatnˇe, tak v párech. Zákazn´ıci pˇr´ıcházej´ı pˇribliˇznˇe kaˇzdou hodinu, 1 pˇriˇcemˇz pravdˇepodobnost pˇr´ıchodu muˇze je 14 , ˇzeny 23 a páru 12 . Uvaˇzujeme, ˇze v pˇr´ıpadˇe obsazen´ı odpov´ıdaj´ıc´ıho oddˇelen´ı zákazn´ık salón opouˇst´ı a v pˇr´ıpadˇe páru opouˇst´ı salón celý pár. Obsluha v dámské ˇcásti trvá pˇribliˇznˇe 43 hodiny a v pánské ˇcásti 14 hodiny. Urˇcete: – pravdˇepodobnost, ˇze pˇr´ıchoz´ı zákazn´ık(ci) nebude obslouˇzen, – pravdˇepodobnost, ˇze pracuje dámská ˇcást, pánská a obˇe spoleˇcnˇe.

71

Kapitola 4 Teorie obnovy ´ Uvod Procesy obnovy zahrnuj´ıc´ı procesy u ´ drˇzby a nahrazován´ı jednotek (zaˇr´ızen´ı, vˇec´ı, výrobk˚ u) jsou studovány pomoc´ı matematických model˚ u v rámci teorie obnovy s c´ılem jejich optimalizace, tj.nalezen´ı optimáln´ı strategie obnovy. Pˇri ˇreˇsen´ı model˚ u obnovy se uplatˇ nuje matematická analýza, teorie pravdˇepodobnosti, matematické programován´ı, dynamické programován´ı a simulaˇcn´ı metody. Obnovou jednotky rozum´ınme jej´ı u ´ drˇzbu a nahrazován´ı. Rozeznáváme jednotky (prvky) • selh´ avaj´ıc´ı - jejich vlastnosti jsou prakticky nemˇenné, ale po urˇcité dobˇe dojde k selhán´ı jednotky a k jej´ımu nahrazen´ı, • zastar´ avaj´ıc´ı - jejich vlastnosti se postupnˇe zhorˇsuj´ı a v d˚ usledku toho rostou náklady na ´ zbou se snaˇz´ıme udrˇzet významné jejich u ´ drˇzbu a sniˇzuj´ı se výnosy z jejich provozu. Udrˇ vlastnosti jednotky v pˇr´ıpustných mez´ıch, coˇz m˚ uˇze být po urˇcitém ˇcase jiˇz nemoˇzné ˇci ekonomicky nevýhodné a potom téˇz docház´ı k nahrazen´ı jednotky. Tomuto dˇelen´ı odpov´ıdá v podstatˇe dˇelen´ı na • jednotky neopraviteln´ e - takové, které nemohou být opraveny, ˇci se neopravuj´ı (ˇzárovky, procesor poˇc´ıtaˇce), • jednotky opraviteln´ e - takové, které mohou být v pˇr´ıpadˇe porucy opraveny (soustruh, automobil).

Charakteristiky proces˚ u obnovy Mˇejme soubor prvk˚ u stejného typu (napˇr. ˇzárovek, loˇzisek), ve kterém jsou v d˚ usledku selhán´ı jednotlivé prvky nahrazovány novými. Tento proces lze popsat na základˇe statistického pozorován´ı vývoje základn´ıho souboru prvk˚ u. Zaved’me následuj´ıc´ı veliˇciny: • t - vˇ ek prvku. M˚ uˇze být vyjádˇren v ˇcasových jednotkách nebo poˇctem odpracovaných cykl˚ u (smˇen), jednotkami odpracovaného výkonu atd. • T -ˇ zivotnost (doba fungován´ı) prvku. • N(t) - poˇ cet prvk˚ u, které funguj´ı v ˇ case t. 72

Pomoc´ı tˇechto zavedených veliˇcin lze definovat základn´ı pravdˇepodobnostn´ı charakteristiky souboru prvk˚ u. • Pravdˇepodobnost selh´ an´ı prvku ve vˇeku t: p(t) =

N(t) − N(t + 1) , N(0)

(4.1)

pravdˇepodobnost, ˇze náhodnˇe vybraný prvek ze základn´ıho souboru prvk˚ u (z N(0) prvk˚ u) selˇze v ˇcasovém intervalu ht, t + 1), tj. pˇred dosaˇzen´ım vˇeku t + 1. • Pravdˇepodobnost pˇ reˇ zit´ı vˇ eku t: p(T > t) =

N(t) , N(0)

(4.2)

pravdˇepodobnost, ˇze náhodnˇe vybraný prvek pˇreˇzije vˇek t. • Podm´ınˇ en´ a pravdˇepodobnost selhán´ı: pc (t) =

N(t) − N(t + 1) , N(t)

(4.3)

pravdˇepodobnost, ˇze náhodnˇe vybraný prvek, ze souboru prvk˚ u, který se doˇzily vˇeku t (z N(t) prvk˚ u), selˇze v ˇcasovém intervalu ht, t + 1). Protoˇze plat´ı N(t) N(t + 1) N(t) − N(t + 1) = − , N(0) N(0) N(0) m˚ uˇzeme vzhledem ke vztah˚ um (4.1), (4.2) psát, ˇze p(t) = p(T > t) − p(T > t + 1). Zcela jasnˇe mezi pravdˇepodobnost´ı pˇreˇzit´ı a pravdˇepodobnostmi selhán´ı plat´ı vztah p(T > t) =

∞ X

p(k),

(4.4)

k=t

který ˇr´ıká, ˇze vˇsechny prvky, které pˇreˇzij´ı ˇcas t, selˇzou v nˇekterém z následuj´ıc´ıch ˇcasových krok˚ u. Na základˇe rovnic (4.1), (4.2), (4.3) odvod´ıme vztah mezi jednotlivými pravdˇepodobnostmi jako N (t)−N (t+1) p(t) N(t) − N(t + 1) N (0) = pc (t) = = . N (t) N(t) p(T > t) N (0)

Znalost rozdˇelen´ı pravdˇepodobnosti selhán´ı p(t) umoˇzn ˇ uje stanovit stˇredn´ı dobu ˇzivotnosti prvku souboru t¯, tj. stˇredn´ı dobu, která uplyne od poˇcátku fungován´ı prvku do jeho selhán´ı. Pro stˇredn´ı dobu ˇzivotnosti t¯ plat´ı vztah t¯ =

∞ X

(t + 1)p(t).

t=0

73

(4.5)

Uvedený vztah vyplývá z u ´ vahy: z N(0) prvk˚ u v ˇcase t = 0 fungovalo jen jedno obdob´ı N(0)p(0) prvk˚ u, jen dvˇe obdob´ı N(0)p(1) prvk˚ u, obecnˇe jen t obdob´ı fungovalo N(0)p(t − 1) prvk˚ u. Celkem tedy tyto prvky fungovaly N(0)p(0) + 2N(0)p(1) + 3N(0)p(2) + ...(t + 1)N(0)p(t) + ...(∞)N(0)p(∞) obdob´ı. Na jeden prvek tedy pˇripadá stˇredn´ı ˇzivotnost (tj. stˇredn´ı poˇcet odpracovaných obdob´ı) 1 (N(0)p(0) + 2N(0)p(1) + 3N(0)p(2) + ...(t + 1)N(0)p(t) + ...(∞)N(0)p(∞)) . N(0) Po u ´ pravˇe posledn´ıho výrazu dostáváme vztah (4.5). Vzhledem k platnosti vztahu (4.4) m˚ uˇzeme psát také ∞ X ¯ t= p(T > t). (4.6) t=0

V pˇr´ıpadˇe, ˇze je udána maximáln´ı ˇzivotnost prvku, tzv. demont´ aˇ zn´ı vˇ ek d, docház´ı k obnovˇe prvku, jakmile prvek tohoto vˇeku dosáhne, bez ohledu na jeho skuteˇcný stav. Potom pˇri výpoˇctu stˇredn´ı doby ˇzivotnosti pouˇz´ıváme modifikované vztahy (4.5), (4.6), které m˚ uˇzeme zapsat jako t¯d =

d−1 X

(t + 1)p(t) +

t=0

t¯d =

d−1 X

∞ X

p(t),

(4.7)

t=d

p(T > t).

(4.8)

t=0

Rovnice procesu obnovy Pro odvozen´ı tzv. rovnice procesu obnovy uvaˇzujme následuj´ıc´ı pˇredpoklady: • prvky daného souboru prvk˚ u jsou obnovovány na konci obdob´ı, v nˇemˇz dojde k jejich selhán´ı, • známe pravdˇepodobnostn´ı rozdˇelen´ı selhán´ı prvk˚ u p(t) v ˇcase, • je stanoven demontáˇzn´ı vˇek d. Oznaˇcme N0 (t−1) poˇcet prvk˚ u, které jsou obnovovány v (t−1)tém obdob´ı, obecnˇe je N0 (t−n) poˇcet prvk˚ u obnovovaných v (t − n)tém obdob´ı. Ponˇevadˇz p(0) udává relativn´ı poˇcet prvk˚ u, které selhávaj´ı bˇehem prvn´ıho obdob´ı fungován´ı, pak souˇcin N0 (t − 1)p(0) udává poˇcet prvk˚ u, které byly vymˇenˇeny v (t − 1)tém obdob´ı a musej´ı být znova vymˇenˇeny v t-tém obdob´ı. Podobnˇe p(1) udává relativn´ı poˇcet prvk˚ u, které selhávaj´ı bˇehem druhého obdob´ı fungován´ı, a potom N0 (t − 2)p(1)

udává poˇcet prvk˚ u, které byly vymˇenˇeny v (t − 2)tém obdob´ı a musej´ı být znova vymˇenˇeny v t-tém obdob´ı. Na základˇe uvedeného m˚ uˇzeme celkový poˇcet prvk˚ u N0 (t), který je nutno obnovit v t-tém obdob´ı, vyjádˇrit jako N0 (t) = N0 (t − 1)p(0) + N0 (t − 2)p(1) + ... + N0 (t − d)p(d − 1). 74

(4.9)

Rovnici (4.9) nazýváme základn´ı rovnic´ı teorie obnovy a vyjadˇruje podm´ınku prosté reprodukce soubor˚ u s obnovovanými prvky. Rovnici jsme odvodili za pˇredpokladu, ˇze obnova prob´ıhá v plném vˇekovém strukturn´ım sloˇzen´ı základn´ıho souboru, tj. ˇze soubor obsahuje prvky s vˇekem v celém intervalu, t ∈ h0, di. Kdybychom chtˇeli popsat proces obnovy v souboru právˇe vytvoˇreném, tj. kdyˇz v okamˇziku t = 0 maj´ı vˇsechny prvky vˇek 0, v ˇcase t = 1 maj´ı nejstarˇs´ı prvky vˇek 1, v ˇcase t = 2 maj´ı nejstarˇs´ı prvky vˇek 2 atd., pak pro t < d dostáváme rovnice obnovy v tzv. ”useknuté” formˇe. M˚ uˇzeme je psát ve tvaru N0 (1) = N0 (0)p(0), N0 (2) = N0 (1)p(0) + N0 (0)p(1), .. . N0 (d − 1) = N0 (d − 2)p(0) + N0 (d − 3)p(1) + ... + N0 (0)p(d − 2).

(4.10)

Rovnice (4.9), (4.13) tvoˇr´ı soustavu rekurentn´ıch vztah˚ u pro postupný výpoˇcet poˇctu prvk˚ u nutných k obnovˇe v libovolném obdob´ı ˇcinnosti systému. V d˚ usledku nestejné ˇzivotnosti jednotlivých prvk˚ u souboru docház´ı v procesu obnovy k u ´ tlumu cykliˇcnosti. Po urˇcité dobˇe docház´ı k ustálen´ı vˇekové struktury sloˇzen´ı souboru a t´ım i k ustálen´ı poˇctu pravidelnˇe obnovovaných prvk˚ u. Tomuto stavu ˇr´ıkáme stabilizovan´ y (rovnomˇerný) proces obnovy. Pˇredpokládejme, ˇze základn´ı soubor v ˇcase t obsahuje N funguj´ıc´ıch prvk˚ u r˚ uzného vˇeku. Plat´ı rovnice N = N0 (t − 1)p(T > 0) + N0 (t − 2)p(T > 1) + ... + N0 (t − d)p(T > d − 1).

(4.11)

Ta nám ˇr´ıká, ˇze poˇcet prvk˚ u, které pˇreˇzily jedno obdob´ı, je dán vztahem N0 (t − 1)p(T > 0), obecnˇe, ˇze prvk˚ u, které pˇreˇzily n obdob´ı, je N0 (t − n)p(T > n). Ve stabilizovaném procesu obnovy je poˇcet obnovovaných prvk˚ u v kaˇzdém obdob´ı stejný, takˇze plat´ı N0 (t) = N0 (t − 1) = N0 (t − 2) = ... = N0 (t − d). Potom lze rovnici (4.11) zapsat ve tvaru N0 (t) [p(T > 0) + p(T > 1) + ... + p(T > d − 1)] = N. S ohledem na platnost (4.8) dostáváme výraz N0 (t)t¯ = N, který m˚ uˇzeme upravit na tvar

¯0 (t) = N . N t¯

(4.12)

¯0 (t) nazýváme limitn´ı hodnotou obnovy a vyjadˇruje poˇcet prvk˚ Hodnotu N u, které je nutné vymˇenit v kaˇzdém ˇcasovém obdob´ı ve stabilizovaném procesu obnovy. Pˇ r´ıklad. Pˇrevzato z [7]. Komunáln´ı podnik mˇesta má na starost u ´drˇzbu veˇrejného osvˇetlen´ı. Veden´ı mˇesta se rozhodlo pro modernizaci a stávaj´ıc´ı výbojky byly naráz vymˇenˇeny za nový typ. Veˇrejné osvˇetlen´ı se skládá celkem z 3000 výbojek. Poˇcet výbojek funguj´ıc´ıch na konci ´ kaˇzdého roku udává tab. 4.1. Ukolem je zjistit, kolik výbojek mus´ı komunáln´ı podnik kaˇzdý rok objednat, aby byla zachována funkˇcnost veˇrejného osvˇetlen´ı. Demontáˇzn´ı vˇek nebudeme zat´ım uvaˇzovat.

75

t [rok] 0 1 2 3 4 5 6

N(t) [ks] 3000 2700 2300 1600 800 300 0

N(t) − N(t + 1)[ks] 300 400 700 800 500 300 0

p(t) p(T > t 0,1000 1,0000 0,1333 0,9000 0,2333 0,7667 0,2667 0,5333 0,1667 0,2667 0,1000 0,1000 0,0000 0,0000

pc (t) 0,1000 0,1481 0,3043 0,5000 0,6250 1,0000 -

Tabulka 4.1: Pravdˇepodobnostn´ı charakteristiky výbojek. t [rok] 1 2 3 4 5

N0 (t) [ks] 300 430 783 1006 885

t [rok] 6 7 8 9 10

N0 (t) [ks] 870 751 840 869 855

Tabulka 4.2: Poˇcty obnovovaných výbojek v jednotlivých letech. ˇ sen´ı: Reˇ Dosazen´ım do vzorc˚ u (4.1), (4.2), (4.3) vypoˇc´ıtáme pravdˇepodobnost selhán´ı, pravdˇepodobnost pˇreˇzit´ı a podm´ınˇené pravdˇepodobnosti selhán´ı - viz tab. 4.1. Stˇredn´ı doba ˇzivotnosti výbojky je t¯ =

6 X

p(T > t) = 1 + 0, 90 + ... + 0, 10 = 3, 57 roku.

t=0

Poˇcty výbojek, které je nutno kaˇzdý rok vymˇenit, z´ıskáme pomoc´ı rekurentn´ıch vztah˚ u (4.13), ’ nebot pˇri modernizaci byly vˇsechny výbojky vymˇenˇeny. Tedy N0 (0) = 3000 ks, N0 (1) = N0 (0)p(0) = 3000 · 0, 10 = 300 ks, N0 (2) = N0 (1)p(0) + N0 (0)p(1) = 300 · 0, 10 + 3000 · 0, 1333 = 433 ks, ... Poˇcty obnovovaných výbojek jsou uvedeny v tab. 4.2. Z n´ı je patrné, ˇze v prvn´ıch letech má proces obnovy výraznˇe cyklický charakter. Ke konci sledovaného obdob´ı se vˇsak poˇcty obnovovaných výbojek ustaluj´ı. Pokud bychom ve výpoˇctu pokraˇcovali i pro delˇs´ı ˇcasový horizont, stále v´ıce bychom se bl´ıˇzili limitn´ı hodnotˇe dané vztahem (4.12), která udává poˇcet prvk˚ u pˇri stabilizovaném procesu obnovy, v naˇsem pˇr´ıpadˇe je N 3000 N¯0 (t) = = 841 ks/rok. = 3, 57 t¯

76

Nyn´ı pozmˇen´ıme zadán´ı pˇr´ıkladu tak, ˇze budeme uvaˇzovat demontáˇzn´ı vˇek výbojek o délce 4 roky. Uváˇzen´ı demontáˇzn´ıho vˇeku se projev´ı na délce stˇredn´ı doby ˇzivotnosti, t¯d =

d−1 X

p(T > t) = 1 + 0, 90 + 0, 7667 + 0, 5333 = 3, 2 roku.

t=0

Stejnˇe tak se zaveden´ı demontáˇzn´ıho vˇeku projev´ı na poˇctech obnovovaných výbojek. V souladu se vztahem 4.13 budou poˇcty obnovovaných výbojek s p˚ uvodn´ım zadán´ım shodné v prvn´ıch tˇrech letech, v následuj´ıc´ıch letech se ve výpoˇctu ale jiˇz projev´ı demontáˇzn´ı vˇek, NO (4) = NO (3)p(0) + NO (2)p(1) + NO (1)p(2) + NO (0)p(3) + NO (0)p(T > 4) = 1806 ks NO (5) = NO (4)p(0) + NO (3)p(1) + NO (2)p(2) + NO (1)p(3) + NO (1)p(T > 4) = 546 ks NO (6) = NO (5)p(0) + NO (4)p(1) + NO (3)p(2) + NO (2)p(3) + NO (2)p(T > 4) = 708 ks .. . Limitn´ı hodnota obnovy se s uváˇzen´ım demontáˇzn´ıho vˇeku vyjádˇr´ı jako N 3000 N¯0 (t) = = 938 ks/rok. = ¯ 3, 2 td K této hodnotˇe bude konvergovat posloupnost poˇctu obnovovaných prvk˚ u v jednotlivých letech.

Procesy obnovy a jejich modely Obnova zaˇ r´ızen´ı z hlediska n´ aklad˚ u pˇ ri jeho selh´ an´ı Jednou ze základn´ıch u ´ loh teorie obnovy je stanoven´ı optimáln´ı doby provozu zaˇr´ızen´ı, pˇri jej´ımˇz dosaˇzen´ı je u ´ˇcelné prvek vymˇenit za u ´ˇcelem minimalizace náklad˚ u na provoz zaˇr´ızen´ı. Princip ˇreˇsen´ı spoˇc´ıvá ve formulaci jednotkových náklad˚ u na provoz a obnovu zaˇr´ızen´ı v závislosti na promˇenné hodnotˇe technického stavu zaˇr´ızen´ı a v nalezen´ı minimáln´ı hodnoty tˇechto náklad˚ u. Pˇredpokládejme, ˇze pro urˇcité zaˇr´ızen´ı (prvek) je známo pravdˇepodobnostn´ı rozdˇelen´ı jeho dob selhán´ı p(t) a známe následuj´ıc´ı náklady: • c1 - náklady na obnovu zaˇr´ızen´ı, je-li uskuteˇcnˇena v dobˇe mimo provoz zaˇr´ızen´ı (náklady na plánovanou obnovu), • c2 - náklady a ztráty vzniklé v d˚ usledku selhán´ı zaˇr´ızen´ı (náklady na neplánovanou – poruchovou obnovu). Stanov´ıme optimáln´ı cyklus obnovy (optimáln´ı dobu provozu zaˇr´ızen´ı) D za dostateˇcnˇe dlouhou dobu H (tzv. plánovac´ı horizont). Doba plánovac´ıho horizontu je výraznˇe delˇs´ı neˇz optimáln´ı cyklus obnovy (H >> D). Oznaˇc´ıme-li stˇredn´ı ˇzivotnost zaˇr´ızen´ı pˇri stanoven´ı doby D symbolem t¯D , pak lze vyjádˇrit celkový poˇcet obnov zaˇr´ızen´ı bˇehem doby H pod´ılem t¯HD . Z toho poˇcet plánovaných obnov je dán výrazem H p(T > D), t¯D

77

kde p(T > D) je pravdˇepodobnost, ˇze se zaˇr´ızen´ı doˇzije alespoˇ n vˇeku D. Poˇcet neplánovaných obnov zaˇr´ızen´ı je dán výrazem H H p(T ≤ D) = (1 − p(T > D)) . ¯ ¯ tD tD Celkové náklady, které si vyˇzádaj´ı plánované i neplánované obnovy zaˇr´ızen´ı bˇehem doby H, jsou tedy dány vztahem Nc = c1

H H p(T > D) + c2 (1 − p(T > D)) . ¯ ¯ tD tD

(4.13)

Vztah (4.13) lze upravit do tvaru Nc =

H (p(T > D)(c1 − c2 ) + c2 ) . t¯D

(4.14)

Pokud nyn´ı vztah (4.14) vydˇel´ıme dobou H, z´ıskáme hodnotu pr˚ umˇerných náklad˚ u Nc (D), pˇripadaj´ıc´ıch na jednotku ˇcasu, pˇri délce cyklu plánované obnovy D jako Nc =

p(T > D)(c1 − c2 ) + c2 . t¯D

(4.15)

Výraz m˚ uˇzeme s vyuˇzit´ım vztahu (4.8) upravit na tvar Nc =

p(T > D)(c1 − c2 ) + c2 . PD−1 p(T > t) t=0

(4.16)

Stanoven´ı optimáln´ıho cyklu obnovy D lze provést na základˇe vztahu (4.16) tak, ˇze postupnˇe klademe D = 1, 2, 3... a jako optimáln´ı délku cyklu obnovy D vybereme takovou, pro n´ıˇz vztah (4.16) nabývá minimáln´ı hodnoty. Pˇ r´ıklad. Stanovme optimáln´ı cyklus obnovy výbojek pro minulý pˇr´ıklad. Náklady, které si vyˇzádá plánovaná výmˇena výbojky, jsou 760 Kˇc, pˇri neplánované výmˇenˇe jsou náklady 1530 Kˇc. ˇ sen´ı: Reˇ Do vzorce (4.16) postupnˇe dosazujeme D = 1, 2, ... a výpoˇcet provád´ıme, dokud nenajdeme minimáln´ı výˇsi náklad˚ u. p(T > D)(c1 − c2 ) + c2 0, 90 · (760 − 1530) + 1530 = = 837 Kˇc, PD−1 1 t=0 p(T > t) 0, 7667 · (760 − 1530) + 1530 Nc (2) = = 495 Kˇc, 1 + 0, 9 .. . Nc (1) =

Vypoˇctené hodnoty Nc (D) jsou uvedeny v tabulce 4.3. Optimáln´ı délka cyklu obnovy je 4 roky. Výbojky by mˇely být po ˇctvrtém roce provozu vymˇenˇeny i v pˇr´ıpadˇe, ˇze jsou jeˇstˇe funkˇcn´ı. Stanovili jsme tak demontáˇzn´ı vˇek, který má zˇrejmˇe vliv na stˇredn´ı dobu ˇzivota výbojky, která se vypoˇcte podle vztahu (4.8), na poˇcty obnovovaných výbojek v jednotlivých letech (viz vztahy (4.13)) a na limitn´ı hodnotu obnovy (vztah (4.12)). Jak se hodnoty uvedených veliˇcin zmˇen´ı v pˇr´ıpadˇe uváˇzen´ı demontáˇzn´ıho vˇeku je ukázáno v pˇr´ıkladˇe z ˇcásti vˇenované rovnici procesu obnovy. 78

D [rok] 1 2 3

Nc (D) [Kˇc] 837 495 420

D [rok] 4 5 6

Nc (D) [Kˇc] 414 419 -

Tabulka 4.3: Náklady pro cyklus obnovy délky D.

Obnova zaˇ r´ızen´ı z d˚ uvodu jeho opotˇ reben´ı V pˇredchoz´ı ˇcásti jsme se vˇenovali stanoven´ı podm´ınek pro optimáln´ı obnovu zaˇr´ızen´ı, jejichˇz ekonomické provozn´ı charakteristiky (výkonnost, náklady na provoz apod.) se s ˇcasem nemˇen´ı. Nyn´ı se budeme vˇenovat problematice obnovy zaˇr´ızen´ı, jejichˇz ekonomické provozn´ı charakteristiky se s ˇcasem mˇen´ı – zhorˇsuj´ı se. Kaˇzdé zaˇr´ızen´ı se s vˇekem opotˇrebovává. Klesá jeho výkonnost, rostou náklady na u ´ drˇzbu a opravy. Tyto skuteˇcnosti zp˚ usobuj´ı, ˇze je výhodnˇejˇs´ı vymˇenit zaˇr´ızen´ı dˇr´ıve, neˇz je zcela opotˇrebováno. Optimáln´ı dobu ekonomické ˇzivotnosti (pouˇzitelnosti) zaˇr´ızen´ı, tj. dobu, po kterou je pro nás ekonomicky výhodné zaˇr´ızen´ı pouˇz´ıvat, stanovujeme zpravidla s ohledem na: • náklady na poˇr´ızen´ı nového zaˇz´ızen´ı, • náklady na provoz, • náklady na u ´ drˇzbu a opravy zaˇr´ızen´ı, • výnosy. Výpoˇcet optimáln´ı doby ekonomické ˇzivotnosti zaˇr´ızen´ı je r˚ uzný podle toho, které z uvedených veliˇcin do výpoˇctu zahrneme. Pokud budeme pˇredpokládat, ˇze v budoucnu bude moˇzné poˇr´ıdit podobné zaˇr´ızen´ı za stejnou cenu, m˚ uˇzeme hledat optimáln´ı dobu ˇzivotnosti s ohledem na náklady, které jsou spojeny s provozem zaˇr´ızen´ı a s poˇr´ızen´ım nového. Oznaˇcme • ci – náklady na u ´ drˇzbu a provoz v i-tém roce, • st – z˚ ustatková cena na konci t-tého roku, • K – poˇrizovac´ı cena nového zaˇr´ızen´ı. Známe-li tyto u ´ daje, m˚ uˇzeme provést kalkulaci celkových náklad˚ u tvoˇrených souˇctem náklad˚ u na u ´ drˇzbu a provoz a amortizaˇcn´ıch náklad˚ u (rozd´ıl mezi poˇrizovac´ı a zbytkovou cenou v dobˇe výmˇeny). Celkové náklady Nt za t let provozu jsou dány vztahem Nt =

t X i=1

ci + K − st .

Pr˚ umˇerné roˇcn´ı náklady E{Nt } po t letech provozu jsou Pt ci + K − st . E{Nt } = i=1 t

(4.17)

(4.18)

Výmˇenu je vhodné provést v takovém roce topt , ve kterém pr˚ umˇerné roˇcn´ı náklady klesnou na minimum, (4.19) E{Ntopt } = min E{Nt }. t

79

Pˇrihlédneme-li pˇri propoˇctu optimáln´ı doby ekonomické ˇzivotnosti i k velikosti výnos˚ u, budeme postupovat obdobnˇe. Vypoˇc´ıtáme celkové náklady za t let a celkové výnosy za t let. Rozd´ıl mezi výnosy a náklady tvoˇr´ı celkový zisk za t let. Pokud vydˇel´ıme celkový zisk dobou t, z´ıskáme pr˚ umˇerný roˇcn´ı zisk. Výmˇenu je pak vhodné provést tehdy, kdyˇz je pr˚ umˇerný roˇcn´ı zisk maximáln´ı. Dynamick´ e programov´ an´ı Dynamické programován´ı je metodou ˇreˇsen´ı jisté tˇr´ıdy extremáln´ıch u ´ loh, které jsou do urˇcité m´ıry rozloˇzitelné na u ´ lohy jednoduˇsˇs´ı a které maj´ı pomˇernˇe málo omezuj´ıc´ıch podm´ınek. Je moˇzno ˇr´ıci, ˇze dynamické programován´ı je specifick´ y zp˚ usob optimalizace v´ıceetapových rozhodovac´ıch proces˚ u, v nichˇz docház´ı k rozhodnut´ı v kaˇzdé z etap. Tak napˇr. v procesu obnovy zastarávaj´ıc´ıho zaˇr´ızen´ı se rozhodujeme koncem kaˇzdého roku, zda je necháme v provozu, ˇci nahrad´ıme novým. ´ Uloha dynamického programován´ı spoˇc´ıvá ve stanoven´ı optimáln´ı strategie rozhodován´ı ve ˇ sen´ı je zaloˇzeno na v´ıceetapovém procesu, vedouc´ı na nejvyˇsˇs´ı celkový efekt za celý proces. Reˇ základn´ım proncipu teorie dynamického programován´ı, na tzv. Bellmanovˇe principu optimality: • Optimáln´ı strategie má tuto vlastnost. At’ je výchoz´ı stav a výchoz´ı rozhodnut´ı jakékoliv, posloupnost následuj´ıc´ıch rozhodnut´ı mus´ı tvoˇrit optimáln´ı strategii vzhledem ke stavu, vyplynuvˇs´ımu z výchoz´ıho rozhodnut´ı. Jednoduˇsˇs´ı formulace je napˇr.: Kaˇzdá podstrategie optimáln´ı strategie je optimáln´ı. Mˇejme zaˇr´ızen´ı, jehoˇz výkonnost v ˇcase s jeho rostouc´ım stáˇr´ım klesá, klesá jeho efektivnost ´ a rostou provozn´ı náklady, z˚ ustatková cena zaˇr´ızen´ı klesá. Ulohou je nalézt optimáln´ı strategii výmˇeny zaˇr´ızen´ı bˇehem n let tak, aby celkový výnos za toto obdob´ı byl maximáln´ı. V uvaˇzovaném procesu je pˇrirozenou etapou rozhodován´ı jeden rok. V kaˇzdé etapˇe vol´ıme zda zaˇr´ızen´ı ponechat ˇci vymˇenit. Oznaˇcme: • zt roˇcn´ı zisk z provozu zaˇr´ızen´ı stáˇr´ı t let (tj. rozd´ıl mezi roˇcn´ımi výnosy z provozu zaˇr´ızen´ı a náklady na jeho provoz a u ´ drˇzbu), • st z˚ ustatkovou cenu na konci t-tého roku, • K poˇrizovac´ı cenu nového zaˇr´ızen´ı (m˚ uˇze být v ˇcase promˇenná), • fk (t) maximáln´ı moˇzný výnos zaˇr´ızen´ı za zbývaj´ıc´ıch k let uvaˇzovaného n-letého cyklu jeho uˇz´ıván´ı, je-li jeho stáˇr´ı na poˇcátku k-letého obdob´ı t let. V souladu s Bellmanovým proncipem optimality hledáme nejlepˇs´ı strategii obnovy v k-té etapˇe (roce) za pˇredpokladu, ˇze optimáln´ı strategie obnovy v uplynulých k−1 etapách je jiˇz stanovená. Soustava rekurentn´ıch vztah˚ u má tvar zt + fk−1 (t + 1) ponechán´ı fk (t) = max k = 2, 3, ..., n. (4.20) st − K + z0 + fk−1 (1) výmˇena Volbou vˇetˇs´ıho z výnos˚ u je urˇcena optimáln´ı strategie obnovy v dané etapˇe a stáˇr´ı zaˇr´ızen´ı.

80

t [rok] zt [PJ] st [PJ]

0 5 3

1 2 4 3 2 1

3 4 5 2 1 0 0 0 0

6 0 0

Tabulka 4.4: Zisk a z˚ ustatková cena zaˇr´ızen´ı. Pˇ r´ıklad. Je tˇreba urˇcit optimáln´ı strategii obnovy výrobn´ıho zaˇr´ızen´ı v desetiletém obdob´ı. Poˇrizovac´ı cena nového zaˇr´ızen´ı je 5 penˇeˇzn´ıch jednotek (PJ), zisk a z˚ ustatková cena klesaj´ı se stáˇr´ım zaˇr´ızen´ı podle tabulky 4.4. Na poˇcátku je zaˇr´ızen´ı staré 2 roky. ˇ sen´ı: Reˇ K výmˇenˇe zaˇr´ızen´ı docház´ı, aˇz kdyˇz celkový výnos pˇri výmˇenˇe pˇrevýˇs´ı celkový ˇcistý výnos pˇri ponechán´ı zaˇr´ızen´ı. Vzhledem k tomu, ˇze K = z0 = 5, zjednoduˇs´ı se uvedené rekurentn´ı vztahy na tvar zt + fk−1(t + 1) ponechán´ı k = 2, 3, ..., 10. fk (t) = max st + fk−1 (1) výmˇena zt ponechán´ı f1 (t) = max st výmˇena Hledán´ı optimáln´ı strategie obnovy lze téˇz ˇreˇsit jako u ´ lohu hledán´ı nejlevnˇejˇs´ı cesty v orientovaném grafu.

81

Literatura ˇ Praha 2001, ISBN 80-245-0162-7 ´, Operaˇcn´ı výzkum, 3. vyd., VSE, [1] J. Jablonsky ˇ, Kritická cesta a PERT v ˇr´ıd´ıc´ı praxi, SNTL, Praha 1968 [2] V. Kluson [3] O. Tyc, Operaˇcn´ı výzkum, MZLU, Brno 2003, ISBN 80-7157-726-X ˇikova ´, Matematické metody s´ıt’ové analýzy, SNTL, [4] S.J. Zuchovickij, I.A. Radc Praha 1972 [5] Peˇ sek, Operaˇcn´ı analýza, podklady k pˇrednáˇskám, 2000 ˇ ˇa, Operaˇcn´ı výzkum 2, CVUT, [6] J. Klvan Praha 1999, ISBN 80-01-01919-5 ˇˇ [7] M. Zi zka, Vybrané statˇe z operaˇcn´ıho výzkumu, Technická univerzita v Liberci, Liberec 2003, ISBN 80-7083-691-1

82

Technická univerzita v Liberci Fakulta mechatroniky, informatiky a mezioborových studií. Petr Rálek, Josef Novák, Josef Chudoba

Recommend Documents