Modely a modelování
Definice modelu:
Model je napodobenina originálu nebo jeho popis pomocí vymezených prvků a vztahů mezi
nimi.
Vlastnosti dobrého modelu:
Validita – schopnost modelu vystihnout podstatné vlastnosti originálu. Je vyjádřena stupněm
shody modelu s originálem v podstatných vlastnostech.
Reliabilita – míra spolehlivosti a opakovatelnosti modelu. Vysoká reliabilita znamená, že
výsledek modelování je jen nepatrně ovlivněn náhodou a podstatné vlivy jsou v modelu
zohledněny. Reliabilní model také umožňuje při opakovaném použití za stejných podmínek
získat podobné výsledky.
Druhy modelů:
- fyzikální model: fyzicky vytvořený objekt, který napodobuje originál (model automobilu,
města, stroje, atomu, …)
- abstraktní model: soubor vzorců a pravidel, které zjednodušeně popisují originál.
Zjednodušení spočívá ve výběru těch typických vlastností originálu, které jsou významné
pro popis jeho chování.
Druhy abstraktních modelů:
- deterministický model – prvky a vztahy mezi nimi jsou pevně dány. Chování modelu za
určitých podmínek je plně předvídatelné (např. modely různých fyzikálních dějů)
- stochastický model – prvky modelu a vztahy mezi nimi mají charakter náhodných jevů či
náhodných veličin nebo náhodných procesů. V modelu vystupuje jedna nebo více
náhodných složek (např. regresní model vysvětlující závislost jedné veličiny na jiných
veličinách).
Příklady stochastických modelů:
- modely systémů hromadné obsluhy
- markovské řetězce a procesy popisující vývoj dynamických systémů
- modely zásob (umožňují optimalizovat velikost skladu)
- modely obnovy (popisují proces náhrady těch prvků, které selhaly)
- modely přežití (využití ve zdravotnictví, pojišťovnictví, průmyslu)
- modely nabídky a poptávky
Speciální metody pro práci se stochastickými modely:
- stochastické programování
- stochastická teorie řízení
- simulační metody
Specifika simulačních metod:
- používají se při studiu složitějších dějů stochastické povahy, kde se analytické řešení
získává jen obtížně
- pro experimenty jsou použita náhodná čísla. Tak lze simulovat průběhy reálných dějů při
různých hodnotách parametrů a pozorovat vlastnosti modelovaného děje.
Možné problémy při simulacích:
- neadekvátní popis modelovaného děje
- nesprávná volba pravděpodobnostních rozložení náhodných veličin vyskytujících se
v modelu
- chybné odhady parametrů
- nekvalitní generátory pseudonáhodných čísel.
Generátory náhodných čísel
Definice náhodné posloupnosti čísel:
Posloupnost čísel je náhodná, pokud neexistuje kratší způsob vyjádření dané posloupnosti než
tato posloupnost samotná, tj. tuto posloupnost nemůžeme zhustit do kratší podoby. Proto žádná
posloupnost čísel vzniklých výpočtem nemůže být náhodná, ale jen pseudonáhodná.
Náhodná čísla vznikají např. jako výsledky náhodných fyzikálních procesů. Nelze předvídat
výskyt určité hodnoty a jednotlivé hodnoty jsou nezávislé.
Náhodná čísla potřebujeme např. v těchto situacích:
- generování náhodných výběrů
- simulace fyzikálních procesů
- simulované úlohy používané k řešení složitých matematických problémů, které nelze řešit
analyticky
- modelování dějů, kde se vyskytují náhodné jevy nebo náhodné veličiny
- kryptografie
- počítačové hry
- atd.
Způsoby generování náhodných čísel
Mechanický způsob: losování čísel z osudí, házení kostkami, ruleta. Pro většinu aplikací je tento
způsob příliš pomalý.
Fyzikální způsob: je založen na měření určitého jevu, který nastává náhodně (např. rozpad
radioaktivní látky). Lze také v pravidelných intervalech měřit šum na polovodičových
přechodech. Problémem je připojení generátoru šumu k počítači.
Použití tabulek náhodných čísel: K jejich tvorbě se používaly rozsáhlé soubory dat získané
k jiným účelům (např. čísla v telefonním seznamu apod.). Např. z roku 1927 pocházejí
Tippetovy tabulky. Pro počítačové experimenty většího rozsahu jsou ovšem nevhodné.
Softwarový způsob: na základě nějakého algoritmu vytváří počítač posloupnost čísel, která má
zdánlivě vlastnosti náhodné posloupnosti, ale je pouze pseudonáhodná.
Generování pseudonáhodných čísel
Většina algoritmů pro generování pseudonáhodných čísel má rekurentní tvar
xn+1 = F(xn, xn-1, …, x0), kde x0 je vhodná počáteční hodnota zvaná násada nebo semínko (seed) a
F je příslušná funkce. Tyto algoritmy umožňují vytváření jen periodické posloupnosti.
Nejrozšířenějšími zdroji pro generování pseudonáhodných čísel jsou tzv. kongruenční
generátory.
Příklady kongruenčních generátorů:
- aditivní generátor (Fibonacciův): xn+1= xn + xn-1 (mod M)
- multiplikativní generátor (Lehmerův): xn+1= axn (mod M)
- smíšený generátor: xn+1= axn + b (mod M)
Požadavky kladné na pseudonáhodná čísla používaná v simulacích:
- dostatečně dlouhé posloupnosti bez opakování (řádově aspoň 109
hodnot)
- rychlý výpočetní algoritmus generování pseudonáhodných čísel
- splnění důležitých vlastností (musí se řídit daným typem rozložení, musí projít testy
náhodnosti a nezávislosti).
Příklady použití generátorů náhodných čísel
1. Aditivní generátor: xn+1 = xn + xn-1 (mod M)
Volíme M = 7, x0 = 100, x1 = 120
x2 = 120 + 100 (mod 7) = 220 (mod 7) = 3, náhodné číslo = 428570
7
32
,
M
x
==
x3 = 3 + 120 (mod 7) = 123 (mod 7) = 4, náhodné číslo = 571420
7
43
,
M
x
==
x4 = 4 + 3 (mod 7) = 7 (mod 7) = 0, náhodné číslo = 0
7
04
==
M
x
x5 = 0 + 4 (mod 7) = 4 (mod 7) = 4, náhodné číslo = 571420
7
45
,
M
x
==
2. Multiplikativní generátor: xn+1= axn (mod M)
Volíme M = 7, x0 = 100, a = 31
x1 = 31.100 (mod 7) = 3100 (mod 7) = 6, náhodné číslo = 857140
7
61
,
M
x
==
x2 = 31.6 (mod 7) = 186 (mod 7) = 4, náhodné číslo = 571420
7
42
,
M
x
==
x3 = 31.4 (mod 7) = 124 (mod 7) = 5, náhodné číslo = 714290
7
53
,
M
x
==
x4 = 31.5 (mod 7) = 155 (mod 7) = 1, náhodné číslo = 142860
7
14
,
M
x
==
x5 = 31.1 (mod 7) = 31 (mod 7) = 3, náhodné číslo = 428570
7
35
,
M
x
==
3. Smíšený generátor: xn+1= axn + b (mod M)
Volíme M = 7, x0 = 100, a = 31, b = 4
x1 = 31.100 + 4 (mod 7) = 3104 (mod 7) = 3, náhodné číslo = 428570
7
31
,
M
x
==
x2 = 31.3 + 4 (mod 7) = 97 (mod 7) = 6, náhodné číslo = 857140
7
62
,
M
x
==
x3 = 31.6 + 4 (mod 7) = 190 (mod 7) = 1, náhodné číslo = 142860
7
13
,
M
x
==
x4 = 31.1 + 4 (mod 7) = 35 (mod 7) = 0, náhodné číslo = 0
7
0
M
x4
==
x5 = 31.0 + 4 (mod 7) = 4 (mod 7) = 4, náhodné číslo = 57142,0
7
4
M
x5
==
Náhodná čísla a náhodné číslice
V užším slova smyslu jsou za náhodná čísla považovány realizace nezávislých náhodných
veličin z Rs(0,1), tj. hustota ( )
( )


 ∈
=ϕ
jinak0
0,1xpro1
x a za náhodné číslice (dekadické) realizace
nezávislých náhodných veličin z Rd(G), kde G = {0, 1, …, 9}, tj. pravděpodobnostní funkce
( )




∈
=π
jinak0
Gxpro
10
1
x .
Upozornění: Nezáleží na tom, zda máme k dispozici náhodná čísla nebo náhodné číslice,
protože mezi nimi platí tyto vztahy:
a) Nechť X1, X2, … jsou nezávislé náhodné veličiny, Xi ~ Rd(G), G = {0, 1, …, 9}. Pak
transformovaná náhodná veličina 
∞
=
−
=
1i
i
i
X10Y ~ Rs(0,1).
Znamená to, že když máme k dispozici náhodné číslice s rovnoměrným diskrétním rozložením,
tak jejich transformaci Y můžeme považovat za spojitou náhodnou veličinu s rovnoměrným
spojitým rozložením na intervalu (0,1).
b) Nechť náhodná veličina Y ~ Rs(0,1). Potom posloupnost čísel X1, X2, … desetinného rozvoje

∞
=
−
=
1i
i
i
X10Y tvoří posloupnost nezávislých a stejně rozložených náhodných veličin s rozložením
Rd(G), G = {0, 1, …, 9}.
Znamená to, že rozložením náhodného čísla z intervalu (0,1) na jednotlivé číslice podle
desetinného rozvoje lze tyto číslice považovat za realizace nezávislých náhodných veličin
z rovnoměrného diskrétního rozložení na množině {0, 1, …, 9}.
Generování náhodných čísel z jiných rozložení
Máme generovat posloupnost n nezávislých realizací náhodné veličiny s distribuční funkcí Φ(x).
Při metodě inverzní transformace se generují čísla z Rs(0,1) a vhodně se transformují.
a) Diskrétní náhodná veličina
Postup:
1. krok: Z rozložení Rs(0,1) vygenerujeme číslo u.
2. krok: Položíme x = ai, kde i = min{i; Φ(ai) ≥ u}.
Kroky 1 a 2 se opakují n-krát.
Příklad: Opakovaně vypisovaných výběrových řízení se účastní vždy 4 firmy, označme je A, B, C, D. Pravděpodobnost, že
jejich nabídky budou vybrány, jsou postupně 0,2; 0,3; 0,4 a 0,1. Pro n = 10 simulujte výsledky opakovaných výběrových
řízení.
Řešení: Zavedeme náhodnou veličinu X, která nabývá hodnoty 1, když vyhraje firma A, hodnoty 2, když vyhraje B,
hodnoty 3, když vyhraje C a hodnoty 4, když vyhraje D.
Najdeme distribuční funkci náhodné veličiny X.
( )
( )
)
)
)
)








∞∈
∈
∈
∈
∞∈
=Φ
4,xpro1
43,xpro9,0
32,xpro5,0
21,xpro2,0
,1-xpro0
x
Vygenerujeme číslo ( )1,0u ∈ a transformujeme ho takto:







<<
≤<
≤<
≤<
=
1u0,9pro4
0,9u0,5pro3
0,5u0,2pro2
0,2u0pro1
x
Znamená to, že hodnotám veličiny X je distribuční funkcí Φ(x) přiřazena ta část intervalu (0,1), která je proporcionální
pravděpodobnosti odpovídající hodnoty X.
Je-li např. u = 0,7654321, pak nejmenší index i, pro nějž Φ(ai) ≥ 0,7654321 je 3, tedy v tomto případě vyhraje firma C.
Simulaci provedeme v MATLABu pomocí funkce simulace_DNV(n,v):
function [realizace]=simulace_DNV(n,v)
% autor: Petra Cabalková
% funkce generuje n realizaci diskretni nahodne veliciny
% pravdepodobnosti realizace zadava vektor rozlozeni pravdepodobnosti v
% syntaxe: [realizace]=simulace_DNV(n,v)
% vstupni parametr: n ... pocet kroku simulace
% v ... vektor rozlozeni pravdepodobnosti diskretni nah.veliciny
% vystupni parametr:
% realizace ... vektor realizaci diskretni nahodne veliciny
realizace=[];
m=length(v);
for i=1:n
u=unifrnd(0,1,1,1);
if u<v(1,1) x=1;end;
if u>sum(v(1,1:m-1)) x=m;end;
for j=2:(m-1)
if (u>sum(v(1,1:j-1))) & (u<=sum(v(1,1:j))) x=j;end;
end
realizace=[realizace x];
end
plot(realizace,'o')
Funkci zavoláme s parametry n = 10, v = [0.2 0.3 0.4 0.1]. Dostaneme výstup:
realizace =
2 3 3 1 1 2 4 2 3 2
Vidíme, že při 1. konkurzu vyhraje firma B, při 2. a 3. firma C atd.
Simulaci můžeme doplnit tabulkou rozložení četností:
tabulate(realizace)
Value Count Percent
1 2 20.00%
2 4 40.00%
3 3 30.00%
4 1 10.00%
b) Spojitá náhodná veličina
Metoda inverzní transformace je založena na dvou následujících větách.
Věta 1.: Nechť spojitá náhodná veličina X má rostoucí distribuční funkci Φ(x) (tzn., že k ní
existuje inverzní funkce Φ-1
(y) – tzv. kvantilová funkce). Pak transformovaná náhodná veličina
Y = Φ(X) má rozložení Rs(0,1).
Důkaz: Označme Φ*(y) distribuční funkci náhodné veličiny Y.
( ) ( ) ( )( ) ( )( ) ( )( ) ( )0,1yproyyyXPyXPyYPy 11
* ∈=ΦΦ=Φ≤=≤Φ=≤=Φ −−
,
( ) ( 0,-ypro0y* ∞∈=Φ , ( ) )∞∈=Φ ,1ypro1y*
Tedy Y ~ Rs(0,1).
Věta 2.: Nechť X ~ Rs(0,1) a nechť Φ je rostoucí spojitá distribuční funkce. Pak transformovaná
náhodná veličina Y = Φ-1
(X) má distribuční funkci Φ.
Důkaz: Označme Φ*(y) distribuční funkci náhodné veličiny Y.
( ) ( ) ( )( ) ( )( ) ( )yyXPyXPyYPy 1
* Φ=Φ≤=≤Φ=≤=Φ −
, protože X ~ Rs(0,1).
Postup:
1. krok: Z rozložení Rs(0,1) vygenerujeme číslo u.
2. krok: Číslo u transformujeme vztahem x = Φ-1
(u).
Kroky 1 a 2 se opakují n-krát.
Příklad: Generování z exponenciálního rozložení
K benzínové pumpě s jedním čerpadlem přijíždí v průměru auto každé dvě minuty.
Předpokládáme, že doba mezi příjezdy aut se řídí exponenciálním rozložením. Simulujte příjezd
10 aut k benzínové pumpě.
Řešení: Označme X dobu, která uplyne mezi dvěma po sobě následujícími příjezdy aut. Víme,
že se řídí exponenciálním rozložením s parametrem λ = 0,5.
( )


 >λ
=ϕ
λ−
jinak0
0xproe
x
x
, ( )


 >−
=Φ
λ−
jinak0
0xproe1
x
x
. Odtud odvodíme:
( ) ( )u1ln
1
xe1xu x
−
λ
−=−=Φ= λ−
.
V našem případě λ = 0,5, tedy ( )u1ln2x −−= .
Samotnou simulaci provedeme v MATLABu pomocí funkce sim_expon(n,lambda):
function x=sim_expon(n,lambda)
% funkce generuje n realizaci spojite nahodne veliciny s exp. rozlozenim
% syntaxe: x=sim_expon(n,lambda)
% vstupni parametry:
% n ... pocet realizaci
% lambda ... parametr exponencialniho rozlozeni
% vystupni parametr:
% x ... vektor realizaci nahodne veliciny s exp. rozlozenim
u=unifrnd(0,1,n,1);
x=-(1/lambda)*log(1-u);
plot(x,'o')
pocet=[1:n]';
t=cumsum(x);
figure
stairs(t,pocet)
x =
3.3718 4.7245 0.2716 4.8924 2.0013 0.2053 0.6528 1.5832 6.3168 6.6985
1 2 3 4 5 6 7 8 9 10
0
1
2
3
4
5
6
7
Znamená to, že při této simulaci první auto přijede 3,3718 min po začátku sledování, druhé auto
přijede 4,7245 min po prvním autu atd.
Příklad: Generování z normálního rozložení
Náhodná čísla z normálního rozložení nemůžeme generovat metodou inverzní transformace,
protože nelze analyticky vyjádřit inverzní funkci k distribuční funkci ( )
( )
dte
2
1
x
2
2
2
tx
σ
µ−
−
∞−
 πσ
=Φ .
a) Metoda založená na centrální limitní větě
Nechť { }∞
=1nnX je posloupnost náhodných veličin definovaných na témž pravděpodobnostním prostoru, která
splňuje tyto podmínky:
- náhodné veličiny X1, X2, … jsou stochasticky nezávislé
- náhodné veličiny X1, X2, … mají všechny stejné rozložení se střední hodnotou μ a rozptylem σ2
.
Pak posloupnost standardizovaných součtů
Un =
n
nX
n
1i
i
σ
µ−=
, n = 1, 2, ...
konverguje v distribuci k náhodné veličině U ~ N(0,1), tj. platí:
)x()xU(Plim:Rx n
n
Φ=≤∈∀
∞→
, kde Φ(x) je distribuční funkce rozložení N(0,1).
Zvolíme náhodné veličiny s Rs(0,1):
Nechť X1, …, Xn jsou stochasticky nezávislé náhodné veličiny, Xi ~ Rs(0,1), tedy
( ) ( ) n,,1i,
12
1
XD,
2
1
XE ii K=== . Pak ( )
2
n
XEXE
n
1i
i
n
1i
i ==





 ==
, ( )
12
n
XDXD
n
1i
i
n
1i
i ==





 ==
.
Podle CLV náhodná veličina
( )1,0N
12
n
2
n
X
n
nX
U
n
1i
i
n
1i
i
n ≈
−
=
σ
µ−
=
 ==
.
Stačí volit n = 12 a pak ( )1,0N6XU
12
1i
i12 ≈−= =
.
Generování provedeme v MATLABu pomocí funkce clv(mi,sigma,n):
function [realizace]=clv(mi,sigma,n)
% funkce generuje cisla z normalniho rozlozeni pomoci CLV
% syntaxe: realizace=clv(mi,sigma, n)
% vystupni parametr:
% realizace ... vektor realizaci nahodne veliciny s rozlozenim N(mi, sigma^2)
% vstupni parametry:
% mi ... stredni hodnota
% sigma ... smerodatna odchylka
% n ... pocet realizaci
realizace=[];
for i=1:n
u=unifrnd(0,1,12,1);
x=sum(u)-6;
realizace=[realizace;x];
end
sh=mi*ones(n,1);
realizace=sh+sigma*realizace;
hist(realizace)
Nevýhody:
- na jedno náhodné číslo z N(μ, σ2
) je zapotřebí vygenerovat 12 čísel z Rs(0,1);
- rozložení takto vygenerovaných náhodných čísel je oboustranně useknuté v bodech -6, 6;
- Aproximace není uspokojivá vně intervalu ( )σ+µσ−µ 3,3 .
Tento nedostatek lze částečně napravit tak, že vygenerovaná náhodná čísla budeme
transformovat pomocí polynomu.
b) Aproximace polynomem
Realizace generované v bodě (a) upravíme takto:
y=0,25x
u=a1y + a3y3
+ a5y5
+ a7y7
+ a9y9
,
kde koeficienty jsou:
a1 = 3,949846138
a3 = 0,252408784
a5 = 0,076542912
a7 = 0,008355968
a9 = 0,029899776.
Hodnoty u lze považovat za realizace náhodné veličiny s rozložením N(0,1).
Funkci clv.m upravíme tak, aby poskytovala uspokojivější realizace normálního rozložení:
function [realizace]=clv_polynom(mi,sigma,n)
% funkce generuje cisla z normalniho rozlozeni pomoci CLV
% pouziva aproximaci polynomem
% syntaxe: realizace=clv_polynom(mi,sigma, n)
% vystupni parametr:
% realizace ... vektor realizaci nahodne veliciny s rozlozenim N(mi, sigma^2)
% vstupni parametry:
% mi ... stredni hodnota
% sigma ... smerodatna odchylka
% n ... pocet realizaci
a1 = 3.949846138;
a3 = 0.252408784;
a5 = 0.076542912;
a7 = 0.008355968;
a9 = 0.029899776;
realizace=[];
for i=1:n
u=unifrnd(0,1,12,1);
x=sum(u)-6;
y=0.25*x;
u=a1*y+a3*y^3+a5*y^5+a7*y^7+a9*y^9;
realizace=[realizace;u];
end
sh=mi*ones(n,1);
realizace=sh+sigma*realizace;
hist(realizace)
c) Metoda založená na Boxově – Müllerově transformaci
Nechť x1, x2 jsou dvě nezávislá čísla z Rs(0,1). Pak transformovaná čísla
212211 x2sinxln2z,x2cosxln2z π−=π−= lze považovat za realizace náhodné veličiny
s rozložením N(0,1).
Funkce BM_transformace(mi,sigma,n) generuje náhodná čísla z normálního rozložení právě
tímto způsobem.
function [realizace]=BM_transformace(mi,sigma,n)
% funkce generuje cisla z normalniho rozlozeni pomoci BM transformace
% syntaxe: realizace=BM_transformace(mi,sigma, n)
% vystupni parametr:
% realizace ... vektor realizaci nahodne veliciny s rozlozenim N(mi, sigma^2)
% vstupni parametry:
% mi ... stredni hodnota
% sigma ... smerodatna odchylka
% n ... pocet realizaci (musi byt sude cislo)
realizace=[];
for i=1:n/2
u1=unifrnd(0,1,1,1);
u2=unifrnd(0,1,1,1);
x1=sqrt(-2*log(u1))*cos(2*pi*u2)
x2=sqrt(-2*log(u1))*sin(2*pi*u2)
realizace=[realizace;x1;x2];
end
sh=mi*ones(n,1);
realizace=sh+sigma*realizace;
hist(realizace)