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

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

Thêm vào BST

Báo xấu

38
lượt xem 3
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 4', 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 4

kho ng th i gian ∆t là 1 − S∆t. Lúc ñó ta có công th c sau ñây ñúng v i m i n > 0 (hãy tham kh o thêm m c 2.4, Chương IV): pn(t + ∆t) = pn(t)(1 − A∆t)(1 − S∆t) + pn−1(t)(A∆t)(1 − S∆t) + pn+1(t)(1 − A∆t)(S∆t). V i n = 0, có: p0(t + ∆t) = p0(t)(1 − A∆t) + p1(t)(1 − A∆t)(S∆t). T các công th c trên b ng cách chuy n v thích h p, chia c hai v cho ∆t và cho qua gi i h n, s có các công th c sau: dpn(t)/dt = Apn−1(t) + Spn+1(t) − (A + S)pn(t), ñúng ∀n > 0, dp0(t)/dt = −Ap0(t) + Sp1(t). Do ñó l i gi i cho tr ng thái v ng (steady state solutions) ph i tho mãn: Apn−1+ Spn+1 − (A + S)pn = 0, ∀n > 0, −Ap0 + Sp1 = 0 v i n = 0 ⇒ pn = (1 − ρ)ρn, ∀n. ∞ − T ñó tìm giá tr c a các ch s thích h p theo các công th c Ls = ∑ np n , Ws = n =0 Ls/A, Wq = Ws − 1/S, Lq = AWq. Hãy ki m tra l i các k t qu trên theo công th c (I) m c 3.3 ñã bi t. 5. Xét các ñi u ki n c a bài t p 3. Hãy xác ñ nh c n b trí bao nhiêu ch cho xe ch trư c khi vào r a ñ khi m t xe t i s d ng d ch v có ch ñ v i xác su t 90%. 6. Xét bài t p 3. Gi s tr m xe ch có 4 ch cho xe ch trư c khi s d ng d ch v và do ñó n u hàng ch ñã có 4 xe thì m t xe m i ñ n s b ñi t i ch r a xe khác. Hãy áp d ng công th c (IV) m c 3.3 ñ xác ñ nh % khách hàng b m t và th i gian trung bình r a xong m t xe tính t lúc vào hàng ch . 7. Các bài t p 3, 4 và 5 có th ñư c gi i b ng phương pháp mô ph ng như th nào? 8. Xét m t qu y bán hàng ăn nhanh v i các s li u sau: giãn cách th i gian gi a th i ñi m hai khách hàng liên ti p ñ n qu y tuân theo phân ph i ñ u trong kho ng t 1 t i 5 phút, th i gian ph c v m i m t khách hàng là ñúng 2 phút. Hãy th c hi n mô ph ng ng u nhiên và cho bi t: h s s d ng c a qu y và s khách hàng trung bình trong hàng ch . 9. Gi i l i bài t p trên, bi t r ng khách hàng chia thành hai lo i: lo i ñư c ưu tiên và lo i bình thư ng (khách thu c lo i ñư c ưu tiên khi ñ n qu y ñư c x p phía trên t t c các khách lo i bình thư ng). Ngoài ra cho bi t t l khách hàng ưu tiên so v i bình thư ng là 1/2. 10. Kh o sát 200 xung tín hi u qua các van ñi n ñ n ñi u khi n cơ c u ch p hành, ngư i ta th y trung bình 2 giây có m t chu i xung. S li u ñã kh o sát ñư c v th i gian xung c a các chu i xung ñư c cho trong b ng. Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........130
B ng phương pháp mô ph ng ng u nhiên (n u có th , l p chương trình tính toán trên máy tính) hãy xác ñ nh s van ñi n (t i thi u) c n m sao cho vi c ñi u hành cơ c u ch p hành ñư c liên t c (nói cách khác, các chu i xung luôn ñư c ph c v k p th i). Th i gian xung (giây) S ln T n su t 3 50 0,25 4 40 0,20 5 50 0,25 6 60 0,30 11. M t tr m bưu ñi n vi n thông có 13 c ng. Th i gian ph c v m i khách hàng trung bình là 5 phút. K t qu kh o sát th ng kê cho bi t s lư ng tín hi u khách hàng trung bình ñ n trong m t gi , còn k t qu thu th p phi u thăm dò ý ki n khách hàng cho bi t th i gian trung bình (s phút) m t khách hàng có th ñ i trư c khi ñư c ph c v như sau: Các giai ño n S tín hi u/gi Th i gian có th ñ i t i ña Nhu c u cao 120 5 Nhu c u trung bình 60 5,5 Nhu c u th p 30 6 S d ng mô ph ng ng u nhiên, hãy xác ñ nh quy trình tính toán tìm s c ng t i thi u c n m trong m i giai ño n ñ ñáp ng ñư c yêu c u c a khách hàng (nh ng gi thi t nào c n ñ ra ñ gi i quy t v n ñ này). 12. M t tr m rút ti n có hai máy t ñ ng, t i m i máy có hàng ch cho t i ña 4 khách hàng (k c ngư i ñang s d ng d ch v ). Các khách hàng ñ n tr m tuân theo lu t Poát − xông v i th i gian giãn cách trung bình gi a hai l n liên ti p khách ñ n là 1 phút. N u c hai hàng ch ñ u ñã có ñ s lư ng t i ña ngư i ch thì khách hàng t i tr m s b ñi. Trong trư ng h p hàng ch còn ch , khách m i t i s x p vào hàng ch ít ngư i hơn, n u hai hàng ch cùng còn ch , khách m i t i vào hàng bên ph i. Trong trư ng h p hai hàng ch ñ u còn ch , khách hàng có th chuy n t hàng dài sang hàng ng n hơn n u th y hàng ñó có ít nh t ít hơn hai ngư i so v i hàng ñang ñ ng. Gi s th i gian rút ti n t i m i máy ñ u tuân theo lu t mũ v i kì v ng là 1,5 phút. Hãy s d ng mô ph ng ng u nhiên (và vi t chương trình máy tính phù h p) ñ xác ñ nh các ch s sau: − Th i gian trung bình m t khách hàng s d ng d ch v (tính t khi vào hàng ch cho t i khi rút ñư c ti n). − Th i gian giãn cách trung bình gi a hai khách hàng b ñi. − H s s d ng c a m i máy rút ti n. − ð dài trung bình c a m i hàng ch (k c khách hàng ñang rút ti n).
Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........132
Chương V PHÂN TÍCH MARKOV VÀ NG D NG 1. CÁC KHÁI NI M CƠ B N V XÍCH MARKOV 1.1. M t s ñ nh nghĩa Nhi u mô hình ng u nhiên trong V n trù h c, Kinh t , Kĩ thu t, Dân s h c, Di truy n h c,... d a trên cơ s là quá trình Markov. ð c bi t, Tin sinh h c (Bioinformatics), m t lĩnh v c liên ngành c a Sinh h c phân t và Tin h c, hi n t i ñang ng d ng r t m nh các v n ñ c a lí thuy t các quá trình Markov. Các nhi u chuyên gia ngành ði n t vi n thông và Cơ ñi n cũng r t quan tâm t i quá trình Markov nói chung, cũng như các quá trình sinh−t hay quá trình h i ph c nói riêng. Ví d 1: Xét m t h th ng v t lí ti n tri n theo th i gian. T i th i ñi m t = 0, h th ng có th rơi vào m t trong ba tr ng thái (hay v trí) 1, 2 ho c 3 m t cách ng u nhiên. Kí hi u X(0) là v trí c a h th ng t i th i ñi m t = 0 thì X(0) là m t bi n ng u nhiên, có th nh n các giá tr 1 ho c 2 ho c 3 v i các xác su t nh t ñ nh. Gi s r ng căn c vào các k t qu quan sát hay nghiên c u, chúng ta có b ng phân ph i xác su t sau cho X(0): Các giá tr c a X(0) 1 2 3 Xác su t tương ng 0,2 0,5 0,3 T i các th i ñi m ti p theo, ch ng h n, t = 1, 2, 3,... v trí c a h th ng s ñư c mô t b i các bi n ng u nhiên X(1), X(2), X(3),... v i các b ng phân ph i xác su t tương ng. D a trên ví d này, chúng ta xét ñ nh nghĩa sau v quá trình ng u nhiên. ð nh nghĩa 1 Xét m t h th ng (có th là h th ng v t lí, h th ng sinh thái hay h th ng d ch v , …) ti n tri n theo th i gian. G i X(t) là v trí (tr ng thái) c a h t i th i ñi m t. Như v y ng v i m i th i ñi m t, X(t) chính là m t bi n ng u nhiên mô t v trí (tr ng thái) c a h th ng. Quá trình {X(t)}t≥0 ñư c g i là m t quá trình ng u nhiên. T p h p các v trí có th có c a h g i là không gian tr ng thái. Không gian tr ng thái ñư c kí hi u là S. Trong ví d trên, n u gi s r ng X(t) ch có th nh n m t trong ba giá tr 1, 2, 3 ∀t thì S = {1, 2, 3}. Gi s trư c th i ñi m s, h ñã tr ng thái nào ñó, còn t i th i ñi m s, h tr ng thái i. Chúng ta mu n ñánh giá xác su t ñ t i th i ñi m t (t >s), h s tr ng thái j. N u xác su t này ch ph thu c vào b b n (s, i, t, j), t c là P[X(t) = j/X(s) = i] = p(s, i, t, j) là ñúng ∀i, ∀j, ∀s, ∀t thì ñi u này có nghĩa là, s ti n tri n c a h trong tương lai ch
ph thu c vào hi n t i (tr ng thái c a h t i th i ñi m s) và hoàn toàn ñ c l p v i quá kh (tính không nh ). ðó chính là tính Markov. Lúc này quá trình ng u nhiên X(t) ñư c g i là quá trình Markov. Trong ví d trên P[X(1) = 2/X(0) = 1] là xác su t có ñi u ki n c a s ki n X(1) = 2 (t i th i ñi m t =1, h th ng n m t i v trí 2) v i ñi u ki n X(0) = 1 (t i th i ñi m t = 0, h th ng n m t i v trí 1). N u quá trình ng u nhiên có tính Markov thì xác su t này ch ph thu c vào tr ng thái c a h t i th i ñi m s = 0 và hoàn toàn ñ c l p v i các tr ng thái c a h trong quá kh (trư c th i ñi m s = 0). ð nh nghĩa 2 N u không gian tr ng thái S g m m t s h u h n ho c vô h n ñ m ñư c các tr ng thái thì quá trình Markov X(t) ñư c g i là xích Markov. Lúc này, có th kí hi u S = {1, 2, 3,...}, t c là các tr ng thái ñư c ñánh s . Hơn n a, n u t p các giá tr t không quá ñ m ñư c (ch ng h n, t = 0, 1, 2,... ) thì ta có xích Markov v i th i gian r i r c, hay xích Markov r i r c. N u t∈[0, ∞) thì ta có xích Markov v i th i gian liên t c, hay xích Markov liên t c. ð nh nghĩa 3 Xét m t xích Markov. N u xác su t chuy n tr ng thái p(s, i, t, j) = p(s+h, i, t+h, j),∀i, ∀j, ∀s, ∀t và ∀h > 0 thì ta nói r ng xích Markov thu n nh t theo th i gian. ðây là m t khái ni m m i và s ñư c gi i thích ngay sau ñây trong m c 1.2. Ngoài ra v i m c ñích tìm hi u bư c ñ u, trong các m c 1.2 và 1.3 chúng ta s ch xét xích Markov r i r c và thu n nh t theo th i gian. Ví d v xích Markov liên t c s ñư c xem xét trong m c 2.4 và 2.5. 1.2. Ma tr n xác su t chuy n tr ng thái và phân ph i d ng Trong m c này chúng ta ñưa ra khái ni m v ma tr n xác su t chuy n tr ng thái c a m t xích Markov r i r c và thu n nh t theo th i gian v i không gian tr ng thái g m N ph n t . Trong trư ng h p xích Markov r i r c và thu n nh t có không gian tr ng thái v i s ph n t vô h n ñ m ñư c, khái ni m v ma tr n xác su t chuy n tr ng thái s ñư c xây d ng m t cách tương t . Ví d 2: Xét l i ví d 1 trong m c 1.1, nhưng v i m t cách minh h a khác trong lĩnh v c d ch v . Trong m t khu ph 1000 dân (khách hàng) có 3 siêu th là A, B và C (A, B, C ñư c coi là các v trí 1, 2, 3 c a h th ng siêu th này). Gi s r ng, trong t ng tháng m i khách hàng luôn trung thành v i m t siêu th . Ngoài ra, cũng gi s r ng trong tháng ñ u s khách vào các siêu th l n lư t là 200, 500 và 300; t c là có 20% khách hàng vào siêu th A, 50% vào B và 30% vào C. Như v y, có th d ñoán r ng m t khách hàng vào A v i xác su t 0,2; vào B v i xác su t 0,5 và vào C v i xác su t 0,3. ð mô t tình tr ng phân chia th ph n trong tháng ñ u (tháng 0) c a h th ng siêu th trên, chúng ta thi t l p bi n ng u nhiên X(0) v i quy t c: n u khách hàng mua hàng siêu th Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........134
A thì ñ t X(0)=1, siêu th B thì ñ t X(0) = 2, còn siêu th C thì X(0) = 3. Lúc ñó, X(0) có b ng phân ph i xác su t sau: Các giá tr c a X(0) 1 2 3 Xác su t t ương n g 0,2 0,5 0,3 Kí hi u P[X(0) = 1] = π1(0), P[X(0) = 2] = π2(0), P[X(0) = 3] = π3(0) thì véc tơ Π(0) = [π1 , π2(0), π3(0)] = [0,2 0,5 0,3] ñư c g i là véc tơ phân ph i xác su t t i th i ñi m t = 0 (0) hay véc tơ phân ph i ban ñ u. Các thành ph n c a Π(0) cho bi t t l ph n trăm (%) khách hàng vào các siêu th A, B và C. Nh ng tháng sau, ta gi s xác su t ñ m t ngư i khách, ñã vào mua hàng siêu th A tháng trư c vào l i A trong tháng sau luôn là 0,8; chuy n sang mua hàng B luôn là 0,1 và chuy n sang C luôn là 0,1. Xác su t ñ m t ngư i khách, ñã vào mua hàng siêu th B tháng trư c chuy n sang A luôn là 0,07; vào l i B luôn là 0,9 và chuy n sang C luôn là 0,03. Còn xác su t ñ m t ngư i khách, ñã vào siêu th C tháng trư c chuy n sang A luôn là 0,083; chuy n sang B luôn là 0,067 và vào l i C luôn là 0,85. Lúc ñó các xác su t chuy n c a khách hàng ñư c cho thông qua ma tr n xác su t chuy n tr ng thái P (còn g i là ma tr n chuy n sau m t bư c): 0,8 0,1 0,1  P = 0,07 0,9 0,03 = [pij]3×3.   0,083 0,067 0,85   Chúng ta có th v ñư c sơ ñ chuy n tr ng thái như trên hình V.1. 0,1 1 0,8 3 0,85 0,083 0,1 0,03 0,07 0,067 2 0,9 Hình V.1. Sơ ñ chuy n tr ng thái ð mô t tình tr ng phân chia th ph n trong tháng t (t = 1, 2, 3,...) c a h th ng siêu th trên, có th thi t l p bi n ng u nhiên X(t) v i quy t c tương t như khi thi t
l p X(0): n u khách hàng mua hàng siêu th A thì ñ t X(t) = 1, siêu th B thì ñ t X(t) = 2, còn siêu th C thì X(t) = 3. V n ñ ñ t ra là X(t) có b ng phân ph i xác su t như th nào. Trư c h t ta ñi tìm b ng phân ph i xác su t cho X(1). Xét p12 = P[(X(1) = 2/X(0) = 1] = 0,1 là xác su t ñ m t ngư i khách, ñã vào mua hàng siêu th A tháng 0 chuy n sang mua hàng siêu th B trong tháng 1. Ngoài ra, P[X(t+1) = 2/X(t) = 1] = 0,1 ∀t là s t nhiên, vì theo gi thi t c a bài toán thì xác su t ñ m t ngư i khách, ñã vào mua hàng siêu th A tháng trư c chuy n sang mua hàng B luôn là 0,1. V y p12 ñư c g i là xác su t chuy n sau m t bư c t v trí 1 sang v trí 2, b i v y có th dùng kí hi u p12(1) ñ ch rõ ñây là xác su t chuy n sau m t bư c. Các ph n t pij ∀i = 1, 2, 3 và ∀j = 1, 2, 3 c a ma tr n P có ý nghĩa tương t . D th y r ng trong tháng 1 s khách hàng mua hàng t i siêu th A là 200 × 0,8 + 500 × 0,07 + 300 × 0,083 = 219,9 (≈ 220); s khách hàng mua hàng t i siêu th B là 200 × 0,1 + 500 × 0,9 + 300 × 0,067 = 490,1 (≈ 490); còn s khách hàng mua hàng t i siêu th C s là 200 × 0,1 + 500 × 0,03 + 300 × 0,85 = 290. Do t ng s khách hàng là 1000, nên X(1) có b ng phân ph i xác su t sau: Các giá tr c a X(1) 1 2 3 Xác su t t ương n g 0,2199 0,4901 0,2900 V y véc tơ phân ph i xác su t t i th i ñi m t = 1 là Π(1) = [π1(1), π2(1), π3(1)] cho bi t t l ph n trăm khách hàng vào các siêu th A, B và C trong tháng 1. B ng phép tính ma tr n cũng tìm ñư c Π(1) như sau: 0,8 0,1 0,1  Π = Π × P=[0,2 0,5 0,3]× 0,07 0,9 0,03 = [0,2199 0,4901 0,2900]. (1) (0)   0,083 0,067 0,85   Tương t có th tìm ñư c Π(2): 0,8 0,1 0,1  = Π × P = [0,2199 0,4901 0,2900] × 0,07 0,9 0,03 (2) (1) Π   0,083 0,067 0,85   = [0,234297 0,48251 0,283193]. Sau ñây ta ñi tìm ma tr n xác su t chuy n tr ng thái sau hai bư c. Kí hi u p12(2) là xác su t chuy n t v trí 1 sang v trí 2 sau hai bư c. Theo công th c xác su t toàn ph n ta có: p12(2) = P[X(2) = 2/X(0) = 1] = P[X(1) = 1/X(0) = 1] × P[X(2) = 2/X(1) = 1] + P[X(1) = 2/X(0) = 1] × P[X(2) = 2/X(1) = 2] Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........136
+ P[X(1) =3/X(0) = 1] × P[X(2) = 2/X(1) = 3] = p11(1)p12(1) + p12(1)p22(1) + p13(1)p32(1) 3 ∑p = 0,8 × 0,1 + 0,1 × 0,9 + 0,1 × 0,067 = 0,1767. (1) (1) = p 1k k 2 k =1 M t cách hoàn toàn tương t , ta có xác su t chuy n t v trí i sang v trí j sau hai 3 ∑p bư c là pij(2) = pi1(1)p1j(1) + pi2(1)p2j(1) + pi3(1)p3j(1) = (1) (1) p . V y ta có ma tr n chuy n ik kj k =1 sau hai bư c là: P(2)= [pij(2)]3×3 = P(1) × P(1)=P × P= P2 0,8 0,1 0,1  0,8 0,1 0,1  = 0,07 0,9 0,03 × 0,07 0,9 0,03 .    0,083 0,067 0,85 0,083 0,067 0,85    D th y Π(2) = Π(1)×P=Π(0)×P2. Tương t , có th ch ng minh ñư c Π(n+m) = Π(n) × P(m), trong ñó Π(n+m) và Π(n) là các véc tơ phân ph i t i các th i ñi m t = m + n và t = n, còn P(m) là ma tr n xác su t chuy n tr ng thái sau m bư c. Do P(m)= [pij(m)]3×3 nên P[X(m) = j/X(0) = i] = P[X(n + m) = j/X(n) = i] = P[X(n’ + m) = j/X(n’) = i] = pij(m), là xác su t chuy n t v trí i sang v trí j sau m bư c. ð t n = s, t = n+m và h = n’ - n thì có ngay P[X(t) = j/X(s) = i] = P[X(t + h) = j/X(s + h) = i], hay p(s, i, t, j) = p(s + h, i, t + h, j) luôn ñúng ∀s, ∀t, ∀h. T các phân tích trên ñây và ñ i chi u v i các ñ nh nghĩa 1, 2 và 3 m c 1.1, ta th y quá trình ng u nhiên X(t) v i t = 0, 1, 2,... trong ví d này chính là m t xích Markov r i r c và thu n nh t theo th i gian. ð khái quát hóa các khái ni m ñã trình bày, chúng ta xét xích Markov r i r c và thu n nh t theo th i gian X(t), t = 0, 1, 2,... v i không gian tr ng thái g m N ph n t mà ta kí hi u là S = {1, 2,..., N}. ð nh nghĩa 4 Gi s t i th i ñi m t = n, X(n) cũng có th nh n m t trong N giá tr 1, 2,…, N v i các xác su t tương ng là π1(n), π2(n),..., πN(n) (v i π1(n)+ π2(n) +…+ πN(n) = 1) thì véc tơ Π(n) = [π1(n), π2(n),..., πN(n)] ñư c g i là véc tơ phân ph i t i th i ñi m t = n. V i t = 0 ta có véc tơ phân ph i ban ñ u Π(0) = [π1(0), π2(0),..., πN(0)]. Ma tr n P = [pij]N×N, trong ñó pij = p(t, i, t + 1, j) = P[X(t + 1) = j/X(t) = i] ∀t là xác su t chuy n tr ng thái t v trí i sang v trí j sau m t bư c, ∀i = 1, 2,..., N và ∀j = 1, 2,..., N, ñ ư c g i l à ma tr n xác su t c huy n t r n g thái hay ma tr n chuy n sau m t b ư c.
Ví d 3: Ti p t c xét ví d trên, trong ñó ñã tìm ñư c Π(1) = [0,2199 0,4901 0,2900], Π(2) = =[0,234297 0,482510 0,283193]. D th y, các véc tơ phân ph i xác su t Π(1), Π(2), Π(3),... t i các th i ñi m t = 1, 2, 3,... ñư c tính theo công th c: Π(1) = Π(0) × P, Π(2) = Π(1) × P = Π(0) × P2... và Π(n+1) = Π(n) × P = Π(0) × Pn+1, ∀ n. Sau 21 bư c (21 tháng), ta có Π(21) = [0,272257 0,455523 0,272220]. Các véc tơ phân ph i (hay t l ph n trăm khách hàng vào các siêu th A, B, C) sau 1, 2, 3,..., 21 tháng ñư c cho trong b ng V.1. V n ñ ñ t ra là li u Π = limn→∞ Π(n) có t n t i không và n u t n t i thì ñư c tìm b ng cách nào. Trong ví d này, chúng ta s tìm ñư c Π = [0,273 0,454 0,273], bi u th cho t l ph n trăm cân b ng d ng (stationary equylibrium) s khách hàng vào các siêu th A, B, C sau m t th i gian ñ dài. B ng V.1. T l ph n trăm khách hàng vào các siêu th Tháng A B C 1 0,2199 0,4901 0,29 2 0,234297 0,48251 0,283193 3 0,2447183 0,476662631 0,27861905 4 0,2522664 0,472135676 0,2755979 5 0,2577373 0,46861381 0,27364893 6 0,2617056 0,465860633 0,27243373 7 0,2645868 0,463698194 0,27171505 8 0,2666806 0,461991958 0,27132742 9 0,2682041 0,460639762 0,27115613 10 0,269314 0,459563657 0,27112231 11 0,2701238 0,45870389 0,27117228 12 0,2707156 0,458014426 0,27126994 13 0,2711489 0,457459633 0,27139144 14 0,2714668 0,457011789 0,27152141 15 0,2717005 0,456649225 0,27165023 16 0,2718729 0,456354922 0,27177223 17 0,2720002 0,456115454 0,27188433 18 0,2720947 0,455920181 0,27198516 19 0,2721649 0,455760634 0,27207446 20 0,2722173 0,45563005 0,2721526 21 0,2722566 0,455523004 0,27222035 Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........138
Cách tính Π 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) nên nó là ma tr n suy bi n. Khi vi t l i dư i d ng h phương trình (3 n, 3 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= 1 và ràng bu c πk ≥ 0 (k = 1, 2, 3). Kí hi u x = π1, y = π2 và z = π3, ta s có h : 0, 2x − 0, 07y − 0, 083z = 0  x = 0, 273   −0,1x + 0,1y − 0, 067z = 0 ⇔  y = 0, 454 x + y + z = 1 z = 0, 273   V y Π = [0,273 0,454 0,273]. ð nh nghĩa 5 Xét xích Markov r i r c và thu n nh t v i ma tr n chuy n P = [pij]N×N. Lúc ñó, véc tơ phân ph i xác su t Π = [π1, π2,..., πN] th a mãn ñi u ki n Π ×(I - P) = 0 ñư c g i là phân ph i d ng c a xích Markov ñã cho. Có th th y ngay, phân ph i d ng Π không ph thu c vào Π(0) mà ch ph thu c vào ma tr n P. M t cách toán h c, ta nói mô hình xích Markov r i r c thu n nh t chính là b ba (X(tn), S/Π, P). Áp d ng mô hình xích Markov ñ phân tích m t v n ñ nào ñó trong Kinh t , Kĩ thu t, Sinh h c,... ñư c coi là vi c ng d ng phân tích Markov. 1.3. Các tính ch t và ñ nh lí Xét xích Markov r i r c và thu n nh t v i ma tr n chuy n P = [pij]N×N. Có th ch ng minh ñư c các tính ch t và ñ nh lí sau: Các tính ch t N 1/p(n+m)ij = ∑ p(n)ik p(m)kj (ñây là phương trình Chapman-Kolmogorov). k =1 (2) = P × P = P2, P(n) = Pn và P(n+m) = P(n) × P(m). 2/P 3/Π(n+m) = Π(n) × P(m). ð nh lí 1 1/Gi s P là ma tr n xác su t chuy n chính quy, t c là t n t i ch s n0, sao cho (n ) ∀ i, j thì xác su t chuy n t i ñ n j sau n0 bư c là m t s dương: pij 0 > 0. Khi ñó t n t i π1, π2,..., πN > 0 và π1 + π2 +... + πN = 1 ñ cho lim p(n)ij = πj, không ph thu c vào i. n →∞
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