Các mô hình mạng 5

Chia sẻ: Thi Sms | Ngày: | Loại File: PDF | Số trang:11

Thêm vào BST

Báo xấu

40
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo tài liệu 'các mô hình mạng 5', công nghệ thông tin, quản trị mạng phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Các mô hình mạng 5

Các s π1, π2,..., πN ñư c tìm t h phương trình N N ∑x x j = ∑ x k p kj , j = 1, 2,..., N , xj ≥ 0 ∀j và = 1. j j=1 k =1 2/N u có các s π1, π2,..., πN tho mãn ñi u ki n π1+ π2+... + πN = 1 và lim p(n)ij = πj, không ph thu c vào i thì ma tr n P là ma tr n chính quy. n →∞ Chú ý: Phân ph i [π1, π2,..., πN] tho mãn ñi u ki n π1 + π2 +... + πN = 1 và lim p(n)ij = πj, không n →∞ ph thu c vào i, ñư c g i là phân ph i gi i h n. Ngoài ra, n u ñi u ki n πj > 0, ∀j ñư c th a mãn thì phân ph i này ñư c g i là phân ph i Ergodic. Có th ch ng minh ñư c r ng, n u phân ph i gi i h n t n t i thì ñó là phân ph i d ng (duy nh t). Tuy nhiên, ñi u ngư c l i không luôn ñúng. 2. M T S NG D NG C A PHÂN TÍCH MARKOV Phân tích Markov có nhi u ng d ng trong Kinh t , Qu n tr kinh doanh, Kĩ thu t, Sinh h c, Xã h i h c… Trong m c này, chúng ta s xem xét các ng d ng như tìm cân b ng th ph n, xác ñ nh chính sách thay th v t tư thi t b , d báo th t thu cho các h p ñ ng th c hi n trư c, tìm phân ph i gi i h n c a m t h th ng kĩ thu t và m t ng d ng c a quá trình sinh − t cho h th ng hàng ch . 2.1. Tìm cân b ng th ph n Ta nh c l i m t cách v n t t bài toán cho m c 1.2: Trong m t khu ph 1000 dân (khách hàng) có 3 siêu th là A, B và C. Gi s , trong tháng ñ u, s khách vào các siêu th l n lư t là 200, 500 và 300. Nh ng tháng sau ñó, ta gi s xác su t ñ m t khách hàng (ñã vào siêu th A lúc trư c) vào l i A luôn là 0,8; chuy n sang B luôn là 0,1 và chuy n sang C luôn là 0,1... Các xác su t chuy n khác c a khách hàng ("tr l i" B, chuy n sang A, chuy n sang C...) ñư c cho thông qua ma tr n chuy n P 0,8 0,1 0,1  P = 0,07 0,9 0,03   0,083 0,067 0,85   Lúc ñó, theo k t qu ñã bi t, t l ph n trăm cân b ng d ng (khi th i gian ñ dài) s khách hàng vào các siêu th A, B, C là 27,3%, 45,4% và 27,3% có th tìm ñư c t h Π ×(I - P) = 0. 2.2. Chính sách thay th v t tư thi t b Trong m t h th ng ñi n kĩ thu t, các thi t b cùng m t lo i ñư c phân ra các tr ng thái sau ñây: v a m i thay, còn t t, v n dùng ñư c và ñã b h ng. Theo s li u th ng kê ñư c, ta có ma tr n xác su t chuy n tr ng thái như sau: Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........140
0,8 0,2 0  0  0 0,6 0,4 0  P=  , 0 0,5 0,5 0   0 0 0 1,0 trong ñó, sau m i tu n (xem hàng ñ u c a ma tr n P) có 0%, 80%, 20% và 0% s các thi t b m i thay chuy n sang tr ng thái m i thay, còn t t, v n dùng ñư c và ñã b h ng. Các hàng khác c a ma tr n P ñư c gi i thích m t cách tương t . Ta ñi tìm phân ph i d ng b ng phương pháp ñã bi t. Xu t phát t Π(n+1) = Π(n) × P, cho qua gi i h n c hai v khi n→∞ ta có: Π = Π × P, hay Π ×(I - P) = 0. Do P là ma tr n ñ c bi t (ma tr n chuy n xác su t) nên nó là ma tr n suy bi n. Khi vi t l i dư i d ng h phương trình (4 n, 4 phương trình) ta ph i lo i b t m t phương trình ñi và thêm vào h th c π1+ π2+ π3 + π4 = 1 và ràng bu c πk ≥ 0 (k = 1, 2, 3, 4). Kí hi u x1 = π1, x2 = π2, x3 = π3 và x4 = π4 ta s có h :  x1 − x 4 = 0 −0,8x + 0, 4x = 0 1   x1 = x 4 = 6  1 2   −0, 2x1 − 0, 4x 2 + 0, 5x 3 = 0 ⇔  x = x = 1 . −0,5x + x = 0 2 3   3 4 3  x1 + x 2 + x 3 + x 4 = 1  V y phân ph i d ng Π = [1/6 1/3 1/3 1/6]. Gi s r ng chi phí thay m i m t thi t b là 25 nghìn (ñ ng) và th t thu khi m i m t thi t b h ng là 18,5 nghìn thì m i tu n h th ng trên ph i chi trung bình trên m t thi t b s ti n là: (1/6)×25 + (1/6)×18,5 = 7,25 nghìn/thi t b /tu n. Ta xét phương án th hai cho vi c thay th v t tư thi t b v i ma tr n xác su t chuy n tr ng thái sau ñây: 0 0, 8. 0, 2   P = 0 0, 6 0, 4  .  0 1,0 0   Ma tr n này tương ng v i chính sách m i v thay th v t tư thi t b là: thay th m i thi t b m t khi ki m tra và phát hi n thi t b tr ng thái v n dùng ñư c. ði u này có th d n t i vi c gi m thi u th t thu do thi t b h ng gây nên. Th t v y, ng v i ma tr n P trên ñây, phân ph i d ng Π = [1/4 1/2 1/4]. Lúc này, m i tu n h th ng trên ph i chi trung bình trên m t thi t b s ti n là: (1/4)×25 + (0)×18,5 = 6,25 nghìn/thi t b /tu n. Như v y h th ng s ti t ki m ñư c 1 nghìn/thi t b /m t tu n. N u h th ng có 2000
thi t b thì nh chính sách thay th v t tư m i, m i tu n h th ng s ti t ki m ñư c 2 tri u (ñ ng). 2.3. Phân tích Markov trong d báo th t thu cho các h p ñ ng th c hi n trư c M t công ti kinh doanh trong ngành ñi n chuyên v s a ch a và thay th ph tùng ñ ra chính sách tín d ng: ñáp ng yêu c u c a khách hàng trư c, thanh toán sau. Ph n nhi u h p ñ ng s ñư c thanh toán ñúng th i h n, m t t l nh t ñ nh s ñư c công ti cho thanh toán ch m, còn m t s ít không thanh toán ñư c. Theo kinh nghi m, sau hai hay ba h p ñ ng thanh toán ch m c a m t khách hàng nào ñó là h p ñ ng không thanh toán ñư c sau m t th i gian dài, công ti coi ñây là h p ñ ng “x u” và s c t b chính sách tín d ng v i khách hàng ñó. Như v y t i t ng th i ñi m các h p ñ ng có th rơi vào m t trong các tr ng thái sau: − S0: h p ñ ng ñư c thanh toán, − S1: h p ñ ng không ñư c thanh toán, − S2: h p ñ ng s ñư c thanh toán ñúng th i h n, − S3: h p ñ ng s ñư c thanh toán ch m. Sau ñây là ma tr n xác su t chuy n tr ng thái (sau t ng tháng): 1 0 0 0 0 1 0 0 P=   0,5 0 0,3 0,2   0,4 0,3 0,2 0,1  Hi n t i công ti có các h p ñ ng ph i thanh toán ñúng h n v i t ng s 500 tri u và các h p ñ ng cho thanh toán ch m v i t ng s 100 tri u. Hãy xác ñ nh trong t ng trên có bao nhiêu s ñư c thanh toán, còn bao nhiêu s là n “x u” không ñòi ñư c. ðây là bài toán khá ph c t p liên quan t i phân lo i các tr ng thái c a xích Markov là v n ñ chúng ta s không trình bày trong giáo trình này. Tuy nhiên, có th th y ngay r ng các tr ng thái S0 và S1 là các tr ng thái “h p th ” (absorbing state), t c là m i h p ñ ng dù hi n ñang tr ng thái nào thì cu i cùng sau m t th i gian nh t ñ nh cũng s rơi vào m t trong hai tr ng thái trên. Trong khi ñó các tr ng thái S2 và S3 ñư c g i là các tr ng thái truy n ng (hay các tr ng thái di chuy n). ð tìm câu tr l i cho v n ñ ñ t ra, chúng ta c n th c hi n các bư c sau: Trư c h t, ta chia ma tr n P theo kh i. J Ο  1 0 0,5 0  0 0 0,3 0, 2  P=   v iJ= 0 1  , K= 0,4 0,3 , O = 0 0 , M = 0,2 0,1  . Κ Μ          Sau ñó, ta tìm ma tr n R = I - M và ma tr n ngh ch ñ o c a nó R−1, ñây I là ma tr n ñơn v cùng c v i ma tr n M. Ta có: Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........142
1,5254 0,3390 R− 1 =  , 0,3390 1,1864  và tính ñư c: 0,8983 0,1017  R− 1 × K =  . 0,6441 0,3559 Các ph n t trong ma tr n trên có ý nghĩa ñ c bi t. Trong s các h p ñ ng hi n t i tr ng thái S2 (ph i thanh toán ñúng kì h n) cu i cùng sau m t th i gian nh t ñ nh có 89,83% s rơi vào tr ng thái S0 (ñư c thanh toán) và 10,17% s rơi vào tr ng thái S1 (không dư c thanh toán). Còn trong s các h p ñ ng hi n t i tr ng thái S3 (thanh toán ch m) cu i cùng sau m t th i gian nh t ñ nh có 64,41% s rơi vào tr ng thái S0 (ñư c thanh toán) và 35,59% s rơi vào tr ng thái S1 (không ñư c thanh toán). Th c hi n phép tính: 0,8983 0,1017  [500 100]×   = [459,32 140,68], 0,6441 0,3559 ta th y trong 500 tri u ph i thanh toán ñúng kì h n và 100 tri u thanh toán ch m cu i cùng s có 459,32 tri u ñư c thanh toán và 140,68 tri u là n “x u” không ñòi ñư c. ð c i thi n tình tr ng này, công ti c n nghiên c u tìm ra m t chính sách tín d ng h p lí hơn. Ngoài ra, ma tr n R−1 còn cho bi t các thông tin sau: − T ng c a các ph n t trên hàng th nh t là 1,8644 là th i gian trung bình (tháng) mà m t h p ñ ng d ng ph i thanh toán ñúng kì h n s tr i qua trư c khi rơi vào m t trong các tr ng thái h p th , t c là tr thành h p ñ ng thanh toán ñư c ho c h p ñ ng “x u”. − T ng các ph n t trên hàng th hai c a R−1 cũng có ý nghĩa tương t ñ i v i các h p ñ ng d ng thanh toán ch m. − Ph n t n m trên hàng 1 và c t 1 c a R−1 cho bi t th i gian trung bình (tháng) mà m t h p ñ ng d ng ph i thanh toán ñúng h n s trong tr ng thái S2 trư c khi nó rơi vào m t trong các tr ng thái h p th là 1,5254 tháng. Ph n t n m trên hàng 1 và c t 2 cho bi t th i gian trung bình (tháng) mà m t h p ñ ng d ng ph i thanh toán ñúng h n s trong tr ng thái S3 trư c khi nó rơi vào m t trong các tr ng thái h p th là 0,3390 tháng. − Các ph n t n m trên hàng 2 c a ma tr n R-1 có ý nghĩa tương t ñ i v i m t h p ñ ng d ng ñư c thanh toán ch m. Sau ñây, chúng ta s ñưa ra m t s công th c gi i thích các phân tích trên ñây cho trư ng h p ma tr n xác su t chuy n tr ng thái c a xích Markov có d ng sau:
0 0 1 0  1 0 0 0 0 0  0 1 0 0 1 0 P=   =  (như trong bài toán trên),  p 20 p 23  0,5 0 0,3 0,2 p 21 p 22    p31 p32  p30 p33  0, 4 0,3 0,2 0,1    J Ο   p 20 p 21   p 22 p 23  1 0 0 0 =  v i J = 0 1  , K= p p  , O =   , M= p p  , Κ Μ  0 0    30 31   32 33  trong ñó pij là xác su t chuy n t tr ng thái Si sang tr ng thái Sj sau m t bư c. Không gian tr ng thái g m b n tr ng thái S0, S1, S2 và S3; các tr ng thái S0 và S1 là các tr ng thái h p th , còn S2 và S3 là các tr ng thái truy n ng. Chúng ta dùng các kí hi u:  u 20 u 21  U=  ,  u 30 u 31  v i uik là xác su t h p th vào tr ng thái Sk khi tr ng thái ban ñ u là Si, k = 0, 1, còn i = 2, 3. v2  V =  ,  v3  v i vi là th i gian trung bình cho t i khi rơi vào m t trong các tr ng thái h p th n u tr ng thái ban ñ u là Si, i = 2, 3.  w 22 w 23  W=  ,  w 32 w 33  v i wij là th i gian trung bình xích Markov trong tr ng thái Sj trư c khi nó rơi vào m t trong các tr ng thái h p th n u tr ng thái ban ñ u là Si, i = 2, 3. Lúc ñó: 1 1 0 U = (I - M)−1, V = (I - M)−1×   và W = (I - M)−1× 0 1  . 1   Chú ý: Vi c ch ng minh các công th c trên cho trư ng h p t ng quát th c ra cũng không quá khó, có th tìm th y trong các sách tham kh o v quá trình Markov. Cách ng d ng phân tích Markov như trong m c này còn có th ñư c áp d ng r ng rãi trong nhi u lĩnh v c khác như Sinh h c, Xã h i h c, Lí thuy t nh n d ng và Thi t k các h th ng kĩ thu t, trong ñó có Kĩ thu t ñi n. 2.4. Tìm phân ph i gi i h n cho m t h th ng kĩ thu t M t h th ng kĩ thu t có hai chi ti t có th b h ng b t kì th i ñi m nào. T i m i th i ñi m h th ng có th rơi vào m t trong nh ng tr ng thái sau (xem hình V.2): S0: c 2 chi ti t t t; S1: chi ti t 1 h ng, chi ti t 2 bình thư ng; Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........144
S2: chi ti t 1 bình thư ng, chi ti t 2 h ng; S3: c hai chi ti t ñ u h ng. S0 S1 S2 S3 Hình V.2. Sơ ñ các tr ng thái Nói cách khác, t i m i th i ñi m t, bi n X(t) có th rơi vào m t trong các v trí/tr ng thái S0, S1, S2 và S3. Chú ý r ng lúc này ta có xích Markov (th i gian) liên t c v i không gian tr ng thái S ={S0, S1, S2, S3}. Sau ñây, chúng ta s tìm cách xác ñ nh phân ph i gi i h n (long run distribution) c a {X(t)}t≥0. ðây là m t v n ñ khá ph c t p nên chúng ta ch có th trình bày v n ñ m t cách v n t t. Trư c h t ta nh c l i v phân ph i Poát−xông và phân ph i mũ. Gi s dòng tín P (λ) v hi u ñ n (hay x y ra) tuân theo phân ph i Poát−xông i λ là s tín hi u ñ n trung bình trong m t kho ng th i gian nh t ñ nh (coi là m t ñơn v th i gian), λ còn ñư c g i là cư ng ñ c a dòng tín hi u ñ n. Lúc ñó, trong kho ng th i gian như trên thì λ k e−λ s tín hi u x y ra s nh n giá tr k v i xác su t . Ta g i ph n t xác su t P là xác k! su t xu t hi n (ít nh t) m t tín hi u trong kho ng th i gian ∆ t. Th thì, do tính “ñơn nh t” c a quá trình Poát−xông, P cũng là xác su t xu t hi n ñúng m t tín hi u trong kho ng th i gian ∆ t. Theo công th c ñã bi t thì P = λ∆t (chính xác t i vô cùng bé o( ∆ t)). Ch ng h n, n u λ = 6 tín hi u/1 phút và ∆t = 2 giây, ta s có P = λ∆t = 6 × (1/30) = 1/5 = 0,2. T ñó, ta th y xác su t ñ có 1 tín hi u ñ n trong kho ng th i gian 2 giây là 0,2. Xét bi n ng u nhiên T (ch ng h n th i gian ph c v m t tín hi u trong m t h d ch v ), có phân ph i mũ ε(µ) v i hàm m t ñ là f(τ) = µe−µτ. µ cũng ñư c g i là cư ng ñ ph c v hay cư ng ñ c a “dòng ph c v ”. Hàm phân ph i xác su t c a T s là τ τ F (τ) = P (T ≤ τ) = ∫ f (t)dt = ∫ µe −µt dt =1 − e −µτ . 0 0 Còn kì v ng toán và ñ l ch chu n c a bi n ng u nhiên T là
1 +∞ +∞ 1 , σT = . −µt ∫ ∫ µte tf (t)dt = dt = mT = µ µ 0 0 Ta nh n th y ngay r ng: P (0 ≤ T ≤ ∆t) = F(∆t) - F(0) = 1 − e −µ∆t - [1 − e 0] = 1 − e −µ∆t = µ ∆t (chính xác t i vô cùng bé o( ∆ t)). P (λ) thì th Chú ý: N u dòng tín hi u ñ n có phân ph i Poát−xông i gian gi a hai tín hi u liên ti p có phân ph i mũ ε(λ). Chúng ta quay l i bài toán ñang xét. G i λ1 s l n chi ti t 1 h ng và λ2 s l n chi ti t 2 h ng (tính trung bình) trên 1 ñơn v th i gian. Lúc ñó, ta có th coi dòng tín hi u chi ti t 1 và 2 h ng là dòng Poát−xông v i các tham s λ1 và λ2. G i T1 và T2 là th i gian s a ch a chi ti t 1 và 2, có phân ph i mũ v i các kì v ng tsc1 và tsc2 là th i gian s a ch a (trung bình) chi ti t 1 và chi ti t 2. V y T1 và T2 có phân ph i mũ ε(µ1) và ε(µ2), v i µ1 = 1/tsc1 và µ2 = 1/tsc2. T i th i ñi m t ta có bi n ng u nhiên X(t) = Xt v i phân ph i xác su t sau ñây: Xt S0 S1 S2 S3 π0 (t) π1 (t) π2 (t) π3 (t) P Ta tính π0(t + ∆t ) t i th i ñi m ti p theo (t + ∆t ) trong hai trư ng h p sau ñây: − Trư ng h p 1: T i th i ñi m t, h th ng tr ng thái S0 và t i th i ñi m t + ∆t , h th ng v n tr ng thái S0 (không h ng). − Trư ng h p 2: T i th i ñi m t, h th ng tr ng thái S1 ho c S2, còn t i th i ñi m t + ∆t h th ng tr ng thái S0. Do ñó, π0(t + ∆t) = π0(t) [1 − (λ1 + λ2)∆t] + π1(t) µ1 ∆t + π2(t) µ2 ∆t (*). Th t v y, xác su t do trư ng h p 2 gây nên là π1(t)µ1 ∆t + π2(t)µ2 ∆t, v i µ1∆t = P(0 ≤ T1 ≤ ∆t) là xác su t s a ch a xong chi ti t 1 trong kho ng th i gian ∆t và µ2∆t= P(0 ≤ T2 ≤ ∆t) là xác su t s a ch a xong chi ti t 2 trong kho ng th i gian ∆t. Trong khi ñó, xác su t do trư ng h p 1 gây nên là π0(t)[1 − (λ1 + λ2)∆t], v i λ1∆t: xác su t h ng chi ti t 1 trong kho ng ∆t, còn λ2∆t: xác su t h ng chi ti t 2 trong kho ng ∆t. Nói cách khác, chúng ta ñã th c hi n công th c xác su t ñ y ñ π0(t + ∆t) = π0(t)p00 + π1(t)p10 + π2(t)p20, trong ñó: pi0 là xác su t h tr ng thái Si t i th i ñi m t và chuy n sang tr ng thái S0 t i th i ñi m (t+ ∆t). π0 (t + ∆t) − π0 (t) = π1 (t)µ1 + π2 (t)µ 2 − π0 (t)λ1 − π0 (t)λ 2 . T (*) ta có: ∆t Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........146
Cho ∆t → 0 (v ph i không liên quan v i ∆t) thì dπ0 (t) = π1 (t)µ1 + π2 (t)µ 2 − π0 (t)λ1 − π0 (t)λ 2 dt Khi t r t l n (h th ng ho t ñ ng trong m t kho ng th i gian ñ dài) thì h th ng d n n ñ nh v i phân ph i gi i h n có th tìm ñư c, t c là: [π0(t), π1(t), π2(t), π3(t)] → [π0, π1, π2, π3]. V y ta có: dπ0 (t) = 0 khi t ñ l n). π1µ1 + π1µ2 − π0λ1 − π0λ2 = 0 (vì dt M t cách tương t , ta ñi ñ n h phương trình:  dπ0  dt = µ1π1 + µ 2 π2 − (λ1 + λ 2 )π0 = 0   dπ1 = λ π + µ π − (λ + µ )π = 0  dt 10 23 2 1 1   dπ2 = λ π + µ π − (λ + µ )π = 0 20 13 1 2 2  dt  dπ  3 = λ 2 π1 + λ1π2 − (µ1 + µ 2 )π3 = 0  dt ∑π q M t cách t ng quát, phân ph i gi i h n ñư c tìm t h phương trình: −π jq jj = i ij i≠ j ∑π q = 0 ,∀j ∈S (**) và ∑ πi = 1 , trong ñó − qii là cư ng ñ chuy n t tr ng thái hay i ij i∈S i∈S i sang các tr ng thái khác (không k i), còn qij là cư ng ñ chuy n t tr ng thái i sang tr ng thái j, ñư c ñ nh nghĩa như sau: qii = − lim∆t→0 (P[X(t + ∆t) ≠ i / X(t) = i] / ∆t) , qij = lim∆t→0 (P[X(t + ∆t) = j/ X(t) = i] / ∆t) , Lúc ñó, Q = [qij] ñư c g i là ma tr n cư ng ñ . T ñi u ki n (**) ta th y, ñ tìm phân ph i gi i h n c n ph i gi i h [π0 π1 π2 π3]Q = 0 hay QT[π0 π1 π2 π3]T = 0. Ví d 1: Cho λ1 = 1, λ2 = 2, µ1 = 2, µ2 = 3. T sơ ñ cư ng ñ chuy n tr ng thái cho trên hình V.3, có th tìm ñư c ma tr n cư ng ñ Q, v i QT có d ng sau:  −3 2  30  1 −4 0  3 QT =    2 0 −4 2    1 −5 0 2 
S0 µ1 µ2 λ1 λ2 S1 S2 µ1 µ2 µ S3 λ2 λ1 Hình V.3. Sơ ñ cư ng ñ chuy n tr ng thái Gi i thích: q00 = − 3 do cư ng ñ chuy n t tr ng thái S0 sang các tr ng thái khác là λ1+ λ2 = 3, còn q10 = 2 là cư ng ñ chuy n t tr ng thái S1 vào tr ng thái S0. Gi i h [π0 π1 π2 π3]Q = 0 hay QT[π0 π1 π2 π3]T = 0 (v i ñi u ki n b tr π0 + π1 + π2 + π3 = 1) có k t qu : π0 = 6 /15 = 0, 4 ; π1 = 3/15 = 0,2 ; π2 = 4/15 = 0,27 ; π3 = 2/15 = 0,13 . C n chú ý r ng, h [π0 π1 π2 π3] Q = 0 theo m t nghĩa nh t ñ nh là tương t v i h Π ×(I - P) = 0, như ñã trình bày trong các m c 1.2 và 2.1. Gi s l i nhu n/1 ñơn v th i gian h th ng mang l i trong các trư ng h p có th x y ra như sau: n u h th ng trong tr ng thái S0 thì l i nhu n là 8 USD, t i S1 là 3 USD, t i S2 là 5 USD, t i S3 là 0 USD. V y l i nhu n trung bình/1 ñơn v th i gian là 8 × 0,4 + 3 × 0,2 + 5 × 0,27 = 5,15 (USD). Qua ví d ta th y π0, π1, π2, π3 ñư c xác ñ nh căn c vào các giá tr ñã bi t λ1, λ2, µ1, µ2. λ1, λ2: s l n chi ti t h ng (tuỳ thu c h th ng c th ), µ1, µ2: các tham s s a ch a c n ñưa vào. L i nhu n cu i cùng c a h th ng ph thu c vào λ1, λ2, µ1, µ2 và ñư c xác ñ nh b ng cách gi i bài toán t i ưu sau: L i nhu n L = c0π0 + c1π1 + c2π2 → Max (c0, c1, c2: l i nhu n t ng tr ng thái) v i các ràng bu c: µ1π1 + µ 2 π2 − (λ1 + λ 2 )π0 = 0  λ1π0 + µ 2 π3 − (λ 2 + µ1 )π1 = 0  λ 2 π0 + µ1π3 − (λ1 + µ 2 )π2 = 0   λ 2 π1 + λ1π2 − (µ1 + µ 2 )π3 = 0  π0 + π1 + π2 + π3 = 1  π0 , π1 , π2 , π3 ≥ 0; µ1 , µ 2 ≥ 0  Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........148
Lưu ý: Bài toán trên ñây có 6 bi n (λ1, λ2 ñã bi t). Ta ph i tìm ñư c µ1, µ2 t bài toán ñ có phương hư ng xây d ng h th ng v i l i nhu n l n nh t. 2.5. M t ng d ng c a quá trình sinh - t cho h th ng hàng ch Quá trình sinh−t ñư c ng d ng khá r ng rãi trong Lí thuy t ñ tin c y, là m t môn h c c a ngành ði n/ði n t và m t s ngành khoa h c kĩ thu t khác cũng như trong Qu n tr kinh doanh và V n trù h c. Quá trình sinh − t là trư ng h p riêng c a xích Markov thu n nh t th i gian liên t c, v i không gian tr ng thái S không quá ñ m ñư c S = {S0, S1, S2,..., Sn,...} và ma tr n cư ng ñ Q = [qij] có tính ch t qij = 0 v i i − j≥ 2. ði u này có nghĩa là vi c chuy n tr ng thái trong quá trình sinh−t ch có th t i “1 ñơn v lên ho c xu ng” (xem hình V.3). λn-1 λn λ0 λ1 … … S0 S1 S2 Sn-1 Sn Sn+1 … µ1 µ2 µn µn+1 Hình V.3. Sơ ñ chuy n tr ng thái trong quá trình sinh− t T tr ng thái Sn t i th i ñi m t h X(t) ch có th chuy n t i m t trong các tr ng thái Sn+1, Sn ho c Sn−1. Vì v y chúng ta có các cư ng ñ chuy n: µ0 = λ−1 = 0, q00 = − λ0, qn, n+1 = λn, qn, n−1 = µn và qn, n = − (λn +µn) ∀n. Trong trư ng h p λn, µn > 0, ∀n > 0, theo ñ nh lí ñã ñư c ch ng minh, phân ph i gi i h n có th tìm ñư c b ng cách gi i h : [π0 π1 π2 π3...]Q = 0, v i ma tr n cư ng ñ Q ñã bi t. Ma tr n chuy n v c a Q có d ng: q10 ... q n 0 q n +1,0 ... q 00  q11 ... q n1 q n +1,1 ... q 01  Q = ... T ... ... ... ... ...   q 0n q1n ... q nn q n +1,n ... .... ... ... ... ... ...   Ta có [π0 π1 π2 π3...]Q = 0 ⇔ QT[π0 π1 π2 π3...]T = 0 ⇔ q 20 ...  π0   0  q 00 q10 q q 21 ...  π1   0  q11  01 ×  =   . q 22 ...  π2   0  q 02 q12      ... ... ... ...  ...  ... hay:
q00π0 + q10π1 + q20π2 +... = 0, q01π0 + q11π1 + q21π2 +... = 0, q02π0 + q12π1 + q22π2 +... = 0, .... Do tính ch t ñ c bi t, như ñã phân tích trên, c a ma tr n cư ng ñ Q c a quá trình sinh−t , h trên ñư c vi t m t cách tư ng minh hơn như sau: −λ0π0 + µ1π1 +... = 0, λ0π0 − (λ1 + µ1)π1 + µ2π2 +... = 0, λ1π1 − (λ2 + µ2)π2 + µ3π3 +... = 0, ... T ñây ñ dàng tìm ñư c πn+1 = (λn/µn+1)πn, ∀n = 1, 2, 3,... ñ ñi t i công th c tính πi,∀i. π1 = (λ0/µ1)π0, π2 = (λ1/µ2)π1 = (λ1λ0/µ2µ1)π0, π3 = (λ2/µ3)π2 = (λ2λ1/µ3µ2)π1 = (λ2λ1λ0/µ3µ2µ1)π0, ... πn+1 = (λn/µn+1)πn =... = (λnλn−1... λ0/µn+1µn... µ1)π0, ... ∞ ∑π = 1, cu i cùng ta có: V i ñi u ki n i i =0 ∞ ∑ π0 = 1/(1 + (λkλk−1... λ0/µk+1µk... µ1)). k =0 ð c bi t khi µn = 0, ∀n thì quá trình sinh−t tr thành quá trình sinh thu n khi t (pure birth process). Quá trình sinh thu n khi t v i λn = λ là quá trình Poát−xông v i tham s λ. Ví d 2: Gi s dòng khách hàng ñ n mua vé m t văn phòng bán vé v i M qu y ph c v là dòng Poát−xông v i tham s λ = 6 khách hàng/1 phút (ñi u này cũng có nghĩa là khách hàng ñ n phòng bán vé v i các th i ñi m ñ n tuân theo lu t phân ph i mũ v i tham s λ = 6). Ngoài ra, còn bi t nguyên t c ph c v là FCFS (First come first served) và th i gian ph c v t i m i qu y có lu t phân ph i mũ v i kì v ng 1/3 (phút). C n tr l i hai câu h i sau ñây: Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........150