Penelitian Operasional II Rantai Markov RANTAI MARKOV

Penelitian Operasional II

Rantai Markov 49 4. RANTAI MARKOV

4.1 PENDAHULUAN Dalam masalah pengambilan suatu keputusan, seringkali kita diperhadapkan dengan suatu ketidakpastian. Permasalahan ini dapat dimodelkan secara matematis asalkan ketikdakpastian tersebut memiliki pola yang teratur sehingga dapat dinyatakan sebagai sebuah model probabilistik.

4.2 PROSES STOKASTIK Suatu proses stokastik dapat didefinisikan sebagai kumpulan peubah acak berindex {Xt}, dimana index t bergerak sepanjang himpunan T yanag diberikan. Seringkali T merupakan himpunan bilangan bulat tak negatif dan Xt mewakili suatu karakteristik yang terukur pada waktu t. Contoh 4.1: Xt : Dapat menyatakan tingkat inventori dalam tiap minggu (atau bulan) dari suatu produk, atau dapat pula menyatakan jumlah permintaan dari produk tersebut tiap minggu (atau bulan). Jika T adalah himpunan yang dapat dihitung (countable set) maka proses stokastik tersebut dikatakan sebagai ‘Proses stokastik dengan waktu diskrit’, misalnya {Xt, t=0,1,…}. Jika T adalah suatu interval pada garis real, maka proses stokastik tersebut dikatakan sebagai ‘proses stokastik dengan waktu kontinu’, misalnya {Xt, t ≥ 0}. Index T seringkali menyatakan waktu, karena itu Xt disebut sebagai keadaan (state) dari proses pada saat t. Secara ringkas proses stokastitik dapat didefinisikan sebagai berikut : Definisi 4.2: Proses Stokastik merupakan serangkaian random variabel yang berubah terhadap waktu pengamatan. { X(t) , t ∈ T} dimana : X(t) = state (keadaan) yang acak t = waktu (saat pengamatan) Contoh 4.3: Sebuah toko kamera memiliki stok dari suatu model kamera tertentu yang dapat dipesan mingguan. Misalkan: D1, D2,… mewakili permintaan kamera tersebut selama minggu ke-1, ke-2,… dan asumsikan bahwa Di independen dan probabilitas distribusinya diketahui, misalnya X0 adalah jumlah kamera yang ada

Siana Halim – Teknik Industri – UK. Petra

Rantai Markov 50


pada keadaan awal (merupakan maksimum level inventori), X1 adalah jumlah kamera pada akhir minggu I, X2 adalah jumlah kamera pada akhir minggu II, dst. Asumsikan X0 = 3. Minggu malam toko tersebut melakukan pemesanan kamera dan akan dikirimkan pada hari Senin. Toko ini menggunakan kebijakan (s,S*) yaitu jika jumlah kamera yang ada pada akhir minggu kurang dari s=1 (tidak ada stok kamera) maka toko akan memesan S=3. Pada kondisi lain toko tidak melakukan pemesanan (jika stok kamera ada, toko tidak memesan). Diasumsikan bahwa penjualan akan rugi jika permintaan melebihi persediaan yang ada. Kasus ini merupakan proses stokastik {Xt} dengan t = 0,1,… state yang ada pada kasus ini adalah 0,1,2,3 yang mewakili jumlah kamera yang mungkin ada pada akhir minggu. Peubah acak Xt bukan merupakan peubah bebas dan dapat dinyatakan secara iteratif sebagai berikut :  max{(3 − D t +1 ),0} X t < 1 Xt+1 =  max{(X t − D t +1 ),0} X t ≥ 1

4.3 RANTAI MARKOV Suatu proses stokastik {Xt} dikatakan memiliki sifat markov jika : P{Xt+1 = j  X0 = k0, X1 = k1, … Xt-1 = kt-1, Xt = I} = P{Xt+1 = j  Xt = i} Untuk t = 0,1, … dan untuk tiap i, j, k0, k1, …., kt-1. Sifat markov ini dikatakan sebagai berikut : ‘Bahwa probabilitas bersyarat dari kejadian di masa mendatang, jika diketahui kejadian dimasa lalu dan kondisi saat ini Xt = i, adalah tidak tergantung pada masa lalu dan hanya tergantung pada kondisi dari proses saat ini’ Probabilitas bersyarat P{Xt+1 = j | Xt = i} dikatakan sebagai probabilitas transisi. Jika untuk setiap i dan j : P{Xt+1 = j | Xt = i} = P{X1 = j | X0 = i}, untuk semua t = 0, 1, ….. maka probabilitas transisi (1 langkah) dikatakan stasioner, (probabilitas transisi tidak berubah terhadap waktu) dinotasikan dengan pij. Jika untuk setian i dan j : P{Xt+1 = j | Xt = i} = P{Xn = j | X0 = i}, untuk semua t = 0, 1, ….. Probabilitas bersyarat ini dinotasikan dengan pij(n) dan disebut sebagai probabilitas transisi n-langkah. pij(n) : probabilitas bersyarat dimana peubah acak X, dimulai dari state i, akan berapa pada state j setelah tepat n langkah (unit waktu). karena pij(n) adalah probabilitas bersyarat maka harus memenuhi sifat-sifat : pij(n) ≥ 0 ∀ i dan j, n = 0,1,2,… (sifat ketidaknegatifan)


Penelitian Operasional II m

∑p

(n ) ij

=1

Rantai Markov 51

∀ i dan j n = 0,1,2,… (jumlahan dari probabilitas = 1)

j =1

Matriks transisi n langkah :

P(n) =

state 0 1 . . . M

0 (n)

p00 p10(n) . . . pm0(n)

1 (n)

p01 p11(n) . . . pm1(n)

… … … . . . …

M p0m(n) p1m(n) . . . pmm(n)

Definisi 4.4 : Rantai Markov Suatu proses stokastik {Xt, t = 0,1,..} dikatakan merupakan suatu rantai markov dengan state terbatas (finite state markov chain) jika memiliki sifat-sifat sebagai berikut : (1) Memiliki jumlah state yang terbatas (2) Memiliki sifat markov (3) Probabilitas transisinya stasioner (4) Memiliki himpunan probabilitas awal P{X0 = i} ∀ i Contoh 4.5: Dari contoh 4.3, {Xt} merupakan proses stokastik dengan Xt : Jumlah kamera yang mungkin ada pada akhir minggu ke-t (sebelum pesanan diterima) Tentukan probabilitas trasnsisi 1 langkahnya ! p00 p 10 P= p 20   p30

p 03  p13  p 23   p33  Asumsikan Dt memiliki distribusi Poisson dengan parameter λ = 1. p 01 p 02 p11 p12 p 21 p 22 p 31 p 32

Penyelesaian :  max{(3 − D t +1 ),0} X t < 1 Xt+1 =  max{(X t − D t +1 ),0} X t ≥ 1  max{(3 − D t ),0} X t −1 < 1 Xt =  max{(X t −1 − D t ),0} X t −1 ≥ 1


Rantai Markov 52 0.080 0.632 Di dapat P =  0.264  0.080

Penelitian Operasional II 0.184 0.368 0.368 0.368 0 0  0.368 0.368 0   0.184 0.368 0.368

Contoh 4.6: Model dari kondisi suatu stok barang tertentu. Pada akhir suatu hari tertentu kondisi sutau stok dicatat. Jika stok meningkat hari ini maka probabilitas bahwa stok esok hari meningkat adalah 0.7. Jika stok hari ini menurun maka probabilitas bahwa stok esok hari meningkat adalah 0.5 Model ini merupakan rantai markov dimana : State 0 = stok meningkat dan State 1 = stok menurun Maka matriks transisinya adalah : 0.7 0.3 P=   0.5 0.5 Jika model ini dikembangkan menjadi : bahwa kondisi stok esok berubah atau tidak tergantung pada hari ini dan kemarin maka kemungkinan-kemungkinan yang ada adalah sebagai berikut : - Jika dalam 2 hari terakhir stok meningkat, besok akan meningkat dengan probabilitas 0.9 - Jika hari ini meningkat, kemarin menurun, besok akan meningkat dengan probabilitas 0.6 - Jika hari ini menurun, kemarin meningkat, besok akan meningkat dengan probabilitas 0.5 - Jika dalam 2 hari terakhir stok menurun, besok akan meningkat dengan probabilitas 0.3 Model ini juga merupakan rantai markov dengan : State 0 : stok hari ini meningkat kemarin meningkat State 1 : stok hari ini meningkat kemarin menurun State 2 : stok hari ini menurun kemarin meningkat State 3 : stok hari ini menurun kemarin menurun Matriks transisi : Pij = P(Xt = j | Xt-1 = i) 0.9 0 0.1 0  0.6 0 0.4 0   P=   0 0.5 0 0.5    0 0.3 0 0.7  Siana Halim – Teknik Industri – UK. Petra


Rantai Markov 53

Contoh 4.7: Kasus Perjudian Seorang pemain memiliki uang 1$, dalam tiap permainan peluang untuk menang sebesar 1$ adalah p dan peluang untuk kalah sebesar 1$ adalah 1-p. Permainan ini berakhir bila pemain dapat mengumpulkan $3 atau bangkrut. Kasus ini merupakan rantai markov dengan {Xt} mewakili keberuntungan dari pemain , yaitu: 0, 1$ ,2$ ,3$. Matriks probabilitas transisinya adalah : 0  1 1 − p 0 P=   0 1− p  0  0

0 p 0 0

0 0  p  1

4.4 PERSAMAAN CHAPMAN-KOLMOGOROV Persamaan Chapman-Kolmogorov memberikan cara untuk menghitung peluang perpindahan (Probabilitas transisi) n-langkah yaitu : M (v) (n − v) (n) P = ∑ p ⋅p ∀i, j, n dan u ≤ m ≤ n ij ik kj k=o Persamaan ini menunjukkan bahwa dari state i ke state j dalam n langkah, proses akan berada pada state k setelah tepat v ( < n) langkah. Jadi pik(v) pkj(n-v) merupakan probabilitas bersyarat, mulai dari state i, lalu ke state k setelah v langkah dan kemudikan ke state j dalan n-v langkah, maka : M (v) (n − v) (n) P = ∑ p ⋅p ij ik kj k=o

∀k

Jika v = 1 maka : M (n) (n − 1) P = ∑ p ⋅p ij ik kj k=o

∀i, j, n

Jika v = n - 1 M (n - 1) (n) P = ∑ p ⋅p ∀i, j, n ij ik kj k=o Ini merupakan probabilitas transisi 1 langkah rekursif. Siana Halim – Teknik Industri – UK. Petra

Rantai Markov 54


Untuk n = 2 maka M (2) P = ∑ p ⋅p ij ik kj k=o

∀i, j, n

Karena pij(2) adalah elemen dari matriks P(2) maka dengan mengalikan matriks probabilitas transisi 1 langkah dengan dirinya sendiri di dapat : P(2) = P. P = P2 Secara umum : P(n) = P. P…P = Pn = P. Pn-1 = Pn-1 P Contoh 4.8 Dari matriks transisi pada contoh 4.5 didapat : 0.080 0.184 0.368 0.368 0.080 0.184 0.368 0.368 0.632 0.368 0 0  0.632 0.368 0 0  (2) 2  P =P = 0.264 0.368 0.368 0  0.264 0.368 0.368 0      0.080 0.184 0.368 0.368 0.080 0.184 0.368 0.368 0.249 0.286 0.300 0.165 0.283 0.252 0.233 0.233  =   0.351 0.319 0.233 0.087   0.249 0.286 0.300 0.165 Arti : p10(2) : Stok kamera pada akhir minggu adalah 1, probabilitas bahwa 2 minggu kemudian tidak ada stok kamera adalah 0.283 p23(2) : Stok kamera pada akhir minggu adalah 2, probabilitas bahwa 2 minggu kemudian stok kamera menjadi 3 adalah 0.097 P(4) = P4 = P(2) P(2) 0.249 0.286 0.283 0.252 =   0.351 0.319  0.249 0.286 0.289 0.286 0.282 0.285 =  0.284 0.283  0.289 0.286

0.300 0.233 0.233 0.300 0.261 0.268 0.263 0.261

0.165 0.233 0.087  0.165 0.164 0.166 0.177  0.164

0.249 0.283   0.351  0.249

0.286 0.252 0.319 0.286

0.300 0.233 0.233 0.300

0.165 0.233 0.087  0.165



Rantai Markov 55

Arti : p10(4) : Stok kamera pada akhir minggu adalah 1, probabilitas bahwa 4 minggu kemudian tidak ada stok kamera adalah 0.282 p23(4) : Stok kamera pada akhir minggu adalah 2, probabilitas bahwa 4 minggu kemudian stok kamera menjadi 3 adalah 0.171 Probabilitas transisi n langkah pij(n) = P{Xn = j | X0 = i} merupakan probabilitas bersyarat. Jika dicari probabilitas tak bersyarat P(Xn = j), maka harus diketahui distribusi probabilitas dari state awal, misalnya Qx0 (i) , dimana : Qx0(i) = P (X0 = i) ∀ I = 0,1,2,…,M Maka P(Xn = j) = Qx0(0) poj(n) + Qx0(1) p1j(n) + … + Qx0(M) pMj(n) Contoh 4.9 Dari contoh 4.5 asumsikan bahwa stok awal =3 kamera, jadi : Qx0 (0) = Qx0 (1) = Qx0 (2) = 0; Qx0 (3) = 1 Diketahui bahwa probabilitas bersyarat bahwa terdapat 3 kamera setelah 2 minggu dari awal inventori adalah 0.165, maka probabilitas tak bersyaratnya adalah : = Qx0 (3). P33(2) P(X2 = 3) = 1 x 0.165 = 0.165 Misal diberikan bahwa Qx0 (i) = 0.25 ∀ I = 0,1,2,3 maka P(X2 = 3) = Qx0 (0) p03(2) + Qx0 (1) p13(2) + Qx0 (2) p23(2) + Qx0 (3) p33(2) = 0.25 (0.165) + 0.25 (0.233) + 0.25(0.097) + 0.25(0.165) = 0.165 Catatan 4.10 Kedua nilai tersebut di atas sama, ini hanya kebetulan saja.

4.5 KLASIFIKASI STATE DALAM RANTAI MARKOV Berikut ini merupakan beberapa difinisi yang berkaitan dengan state-state dari Rantai Markov. 1. Dapat dicapai (Accessible) State j dikatakan dapat dicapai (accessible) dari state i jika pij(n) > 0 untuk beberapa n > 0. State j dapat dicapai (accessible) dari state i berarti bahwa sistem bisa mencapai state j jika berangkat dari state i. 2. Berkomunikasi (Communicate) jika state j dapat dicapai dari state i, dan state i dapat dicapai dari state j, maka state i dan j dikatakan berkomuniasi (communicate) . Secara umum : a. setiap state berkomunikasi dengan dirinya sendiri. Karena : pii(0) = P{X0 = i | X0 = i} = 1).


Rantai Markov 56


b. Jika state i berkomunikasi dengan state j, maka state j berkomunikasi dengan state i. c. Jika state i berkomunikasi dengan state j dan state j berkomunikasi dengan state k, maka state i berkomunikasi dengan state k. Dari ketiga sifat ini, maka suatu state mungkin dipartisi menjadi kelas-kelas yang saling asing (disjoint classes) dengan states yang saling berkomunikasi dikatakan berada dalam satu kelas. 3. Tak dapat direduksi (Irreducible) Rantai markov dikatakan irreducible jika hanya mempunyai satu kelas saja, jadi semua keadaan saling berkomunikasi. 4. Absorbing Suatau state i dikatakan sebagai state yang absorbing jika probabilitas transisi satu langkah pii = 1. Jadi sekali sistem memasuki state i maka sistem akan tetap selamanya berada di state i tersebut. 5. Recurrent dan Transient • State i dikatakan recurrent jika dan hanya jika : ∞

∑p

(n) ii

=∞

n =1

mulai dari state i, setelah keluar dari state i sistem pasti akan dapat kembali lagi ke state i (karena pasti maka nilai peluangnya adalah 1 ∞

sehingga

∑p

(n) ii

= ∞)

n =1

•

State i dikatakan transient jika dan hanya jika : ∞

∑p

(n) ii

<∞

n =1

Relevansi : • Jika state i recurrent , maka di mulai dari state i, sistem akan kembali lagi dan kembali lagi ke state i berulang-ulang sampai tak berhingga kali. • Sebaliknya jika state i transient , sekali saja sistem memasuki state i maka terdapat suatu peluang positif yang akan membawa sistem ini untuk tidak pernah lagi memasuki state i. • Jika state i recurrent dan state i berkomunikasi dengan state j, maka state j juga bersifat recurrent. • Semua state dalam suatu rantai markov dengan state yang bersifat irreducible terbatas adalah recurrent berarti juga seluruh state dalam proses berkomunikasi.


Penelitian Operasional II 6.

Rantai Markov 57

Periode Periode dari state i didefinisikan sebagai bilangan bulat t (t > 1) sedemikian hingga pii(n) = 0 untuk seluruh n yang bukan kelipatan t (t, 2t, 3t, …) dan t adalah bilangan bulat terbesar dengan sifat ini Contoh 4.11 Pada contoh 4.7, misalkan p = ½ 0 0 0  0 0 0   1  1 1 / 2 1 / 4 0 1 / 4 1 / 2 0 1 / 2 0    P=  P2 =  1 / 4 0 1 / 4 1 / 2  0 1 / 2 0 1 / 2     0 0 1  0 0 1   0  0 1 0 0 0 1 0 0 0 * 0 * *  * * 0 *  3 4    P = P =  * * 0 *  * 0 * *      0 0 0 1  0 0 0 1  Terlihat bahwa p11 = p22 = 0 untuk seluruh n, pada saat n = 1,3,5,… berarti periode t (bukan n) adalah 2. Artinya : proses tersebut dapat masuk ke state 1 hanya pada saat 2,4,…

7.

Aperiodik Jika terdapat 2 bilangan berurutan, s dan (s+1) sedemikian hingga proses dapat berada pada state i pada saat s dan (s+1), state i dikatakan memiliki periode 1 dan disebut sebagai aperiodik state.

8.

Positif Recurrent Jika state i recurrent, maka state i dikatakan positif recurrent Jika dimulai dari state i, waktu harapan sampai proses kembali lagi ke state i adalah terbatas.

9.

Null Recurrent Jika state i recurrent tetapi tidak positif recurrent maka state i adalah Null Recurrent.

10. Ergodic Jika suatu state bersifat positif recurrent dan aperiodik maka state tersebut disebut ergodic. 4.9 WAKTU LINTASAN PERTAMA (FIRST PASSAGE TIME) Waktu yang dibutuhkan oleh suatu proses untuk menuju state j dari state i untuk pertama kali disebut sebagai waktu lintasan pertama (first passage time, fpt). Jika j=1, waktu lintasan pertama ini merupakan jumlah transisi hingga proses kembali ke state mula-mula yaitu i. Dalam hal ini waktu lintasan pertama disebut sebagai waktu recurrence untuk state i. Siana Halim – Teknik Industri – UK. Petra

Rantai Markov 58


Contoh 4.12 Dari contoh 4.5 (level inventori). Diketahui X0 = 3 (inventori awal). Andaikan : X1 = 2, X2 = 1, X3 =0, X4 = 3 dan X5 = 1. Dalam hal ini FPT dari state 3 ke state 1 adalah 2 minggu, FPT dari state 3 ke state 0 adalah 3 minggu dan waktu recurrent adalah 4 minggu. Secara umum first passage time merupakan perubah acak dan memiliki distribusi probabilitas yang bersesuaian dengan mereka. Distribusi probabilitas ini tergantung pada peluang transisi dari proses. Misalkan : Fij(n) : merupakan probabilitas bahwa first passage time dari state i ke state j sama dengan n. Dapat ditunjukkan bahwa probabilitas ini memenuhi hubungan rekursif sebagai berikut : n −1

(k) (n − k) f ij(n) = p (n) ij − ∑ f ij .p jj k =1

Jadi probabilitas dari suatu first passage time dari state i ke state j dalam langkah n dapat dihitung secara rekursif dari probabilitas transisi satu langkah. Contoh 4.13: Dari contoh 4.5 : f30(1) = 0.080 f30(2) = 0.249 - (0.080) (0.080) = 0.243 untuk i dan j yang tetap, fij(n) merupakan bilangan nonnegatif sedemikian hingga : ∞

∑f n =1

(n) ij

≤1

sayangnya, jumlahan ini sangatlah mungkin kurang dari 1, yang berarti bahwa suatu proses yang diawali dari state i tidak pernah mencapai state j. Jika jumlahan = 1, fij(n) (untuk n = 1 , 2,…) dapat dianggap sebagai distribusi probabilitas untuk peubah acak, FPT. Menghitung, fij(n) untuk seluruh n mungkin sulit, relatif lebih sederhana untuk menghitung FPT harapan dari state i ke state j. Diberikan nilai harapan µij yang didefinisiakan sebagai berikut : ∞  jika f ij( n ) < 1 ∞ ∑  n =1 µ ij =  ∞ ∞ ∑ n f ij( n ) jika ∑ f ij( n ) = 1  n =1 n =1


Penelitian Operasional II ∞

Bila

∑f n =1

Rantai Markov 59

= 1 maka µij memenuhi persamaan berikut secara unik.

(n) ij

µij = 1 +

∑p k≠ j

ik

µ kj

jika i = j, µii disebut recurrent time harapan. Contoh 4.14: Dari contoh 4.5. Persamaan di atas dapat digunakan untuk menghitung waktu harapan hingga kamera habis. Asumsikan proses dimulai dengan persediaan kamera = 3 lintasan waktu pertama harapan, µ30 dapat dicapai karena seluruh state recurrent, maka : µ30 = 1 + p31 µ10 + p32 µ20 + p33 µ30 µ20 = 1 + p21 µ10 + p22 µ20 + p23 µ30 µ10 = 1 + p11 µ10 + p12 µ20 + p13 µ30 atau µ30 = 1 + 0.184 µ10 + 0.368 µ20 + 0.368 µ30 µ20 = 1 + 0.368 µ10 + 0.368 µ20 µ10 = 1 + 0.368 µ10 Di dapat : µ10 = 1,58 minggu µ20 = 2,51 minggu µ30 = 3,50 minggu Waktu yang dibutuhkan agar kamera kehabisan stok adalah 3,5 minggu.

4.5 RANTAI MARKOV DALAM JANGKA PANJANG (Long Run Properties of Markov Chain) 4.5.1 Probabilitas pada keadaan stabil (steady state probabilities) Untuk rantai markov yang irreducible ergodic dapat ditunjukkan bahwa : lim pij( n ) ada dan independen terhadap i. n → ∞

Selanjutnya lim pij( n ) = πj

n → ∞

dimana πj secara unik memenuhi persamaan-persamaan steady state berikut : πj > 0 πj =

M

∑π i =0

M

∑π j =0

j

i

pij untuk j = 0,1,2,…, M

=1


Rantai Markov 60


πj disebut sebagai probabilitas pada keadaan stabil dari rantai markov dan memiliki hubungan resiprokal terhadap waktu recurrent harapan. 1 πj = untuk j = 0,1,…, M µ jj ! Steady state probability artinya adalah : bahwa probabilitas bahwa untuk mendapatkan proses dalam suatu state tertentu, katakan j, setelah sejumlah besar transisi cenderung menuju nilai πj . Independen dari distribusi probabilitas awal yang telah didefinisikan terhadap states tersebut. ! πj dapat juga diinterpretasikan sebagai probabilitas stasioner. Contoh 4.15 Dari contoh 4.5 π0 = π0 p00 + π1 p10 +π2 p20 +π3 p30 π1 = π0 p01 + π1 p11 +π2 p21 +π3 p31 π2 = π0 p02 + π1 p12 +π2 p22 +π3 p32 π3 = π0 p03 + π1 p13 +π2 p23 +π3 p33 1 = π0 + π1 + π2 + π3 substitutikan nilai pij ke dalam persamaan di atas, didapat : π0 = (0.080) π0 + (0.632) π1 + (0.264) π2 + (0.080) π3 π1 = (0.184)π0 + (0.368) π1 + (0.368) π2 + (0.184) π3 π2 = (0.368)π0 + (0.368) π2 + (0.368) π3 π3 = (0.368)π0 + (0.368) π3 1 = π0 + π1 + π2 + π3 di dapat : π0 = 0.285 π1 = 0.285 π2 = 0.264 π3 = 0.166

µ00 = 1/ π0 = 3.51 minggu µ11 = 1/ π1 = 3.51 minggu µ22 = 1/ π2 = 3.79 minggu µ33 = 1/ π3 = 6.02 minggu

Catatan 4.16 Pada steady state probabilitas berlaku : ! Jika i dan j merupakan states yang recurrent dengan kelas-kelas yang berbeda maka : pij(n) = 0 untuk setiap n ! Jika j merupakan state yang transient maka pij(n) = 0 Berarti bahwa probabilitas untuk mendapatkan suatu proses dalam suatu state yang transient setelah sejumlah besar transisi cenderung menuju ke nol. 4.5.2 Biaya rata-rata harapan/unit waktu Untuk suatu rantai markov yang irreducible dengan recurent state positif, suatu rantai dengan state terbatas, berlaku : Siana Halim – Teknik Industri – UK. Petra


Rantai Markov 61

1 N  lim  ∑ pij( k )  = π j n → n  N k =1  dimana πj memenuhi persamaan-persamaan stedy state. Andaikan bahwa suatu biaya (atau fungsi penalti lainnya) C(Xt) terjadi ketika proses berada di state Xt pada saat t, untuk t = 0,1,2,… Catatan 4.17 C(Xt) adalah peubah acak dengan nilai C(0), C(1), …, C(N) dan fungsi C(Xt) independen terhadap t.


Penelitian Operasional II Rantai Markov RANTAI MARKOV

Recommend Documents