Penelitian Operasional II Rantai Markov 49

Siana Halim Teknik Industri UK. Petra

4. RANTAI MARKOV

4.1 PENDAHULUAN

Dalam masalah pengambilan suatu keputusan, seringkali kita diperhadapkandengan suatu ketidakpastian. Permasalahan ini dapat dimodelkan secaramatematis asalkan ketikdakpastian tersebut memiliki pola yang teratur sehinggadapat dinyatakan sebagai sebuah model probabilistik.

4.2 PROSES STOKASTIKSuatu proses stokastik dapat didefinisikan sebagai kumpulan peubah acakberindex {Xt}, dimana index t bergerak sepanjang himpunan T yanag diberikan.Seringkali T merupakan himpunan bilangan bulat tak negatif dan Xt mewakilisuatu 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 produktersebut tiap minggu (atau bulan).

Jika T adalah himpunan yang dapat dihitung (countable set) maka proses stokastiktersebut dikatakan sebagai Proses stokastik dengan waktu diskrit, misalnya {Xt,t=0,1,}.

Jika T adalah suatu interval pada garis real, maka proses stokastik tersebutdikatakan 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 terhadapwaktu 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 dapatdipesan mingguan. Misalkan: D1, D2, mewakili permintaan kamera tersebutselama minggu ke-1, ke-2, dan asumsikan bahwa Di independen danprobabilitas distribusinya diketahui, misalnya X0 adalah jumlah kamera yang ada

Rantai Markov 50 Penelitian Operasional II

Siana Halim Teknik Industri UK. Petra

pada keadaan awal (merupakan maksimum level inventori), X1 adalah jumlahkamera pada akhir minggu I, X2 adalah jumlah kamera pada akhir minggu II, dst.Asumsikan X0 = 3. Minggu malam toko tersebut melakukan pemesanan kameradan 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 adastok kamera) maka toko akan memesan S=3. Pada kondisi lain toko tidakmelakukan pemesanan (jika stok kamera ada, toko tidak memesan). Diasumsikanbahwa penjualan akan rugi jika permintaan melebihi persediaan yang ada.

Kasus ini merupakan proses stokastik {Xt} dengan t = 0,1, state yang ada padakasus ini adalah 0,1,2,3 yang mewakili jumlah kamera yang mungkin ada padaakhir minggu. Peubah acak Xt bukan merupakan peubah bebas dan dapatdinyatakan secara iteratif sebagai berikut :

Xt+1 =

Penelitian Operasional II Rantai Markov 51

Siana Halim Teknik Industri UK. Petra

=

m

1j

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

Matriks transisi n langkah :

state 0 1 M0 p00

(n) p01(n) p0m

(n)

P(n) = 1 p10(n) p11

(n) p1m(n)

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.M pm0

(n) pm1(n) pmm

(n)

Definisi 4.4 : Rantai MarkovSuatu proses stokastik {Xt, t = 0,1,..} dikatakan merupakan suatu rantai markovdengan state terbatas (finite state markov chain) jika memiliki sifat-sifat sebagaiberikut :

(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 (sebelumpesanan diterima)

Tentukan probabilitas trasnsisi 1 langkahnya !

=

33323130

23222120

13121110

03020100

pppp

pppp

pppp

pppp

P

Asumsikan Dt memiliki distribusi Poisson dengan parameter = 1.

Penyelesaian :

Xt+1 =

Rantai Markov 52 Penelitian Operasional II

Siana Halim Teknik Industri UK. Petra

Di dapat P =

368.0368.0184.0080.0

0368.0368.0264.0

00368.0632.0

368.0368.0184.0080.0

Contoh 4.6:Model dari kondisi suatu stok barang tertentu. Pada akhir suatu hari tertentukondisi sutau stok dicatat. Jika stok meningkat hari ini maka probabilitas bahwastok esok hari meningkat adalah 0.7. Jika stok hari ini menurun maka probabilitasbahwa stok esok hari meningkat adalah 0.5

Model ini merupakan rantai markov dimana :State 0 = stok meningkat danState 1 = stok menurun

Maka matriks transisinya adalah :

P =

5.05.0

3.07.0

Jika model ini dikembangkan menjadi : bahwa kondisi stok esok berubah atautidak tergantung pada hari ini dan kemarin maka kemungkinan-kemungkinanyang ada adalah sebagai berikut :

- Jika dalam 2 hari terakhir stok meningkat, besok akan meningkatdengan probabilitas 0.9

- Jika hari ini meningkat, kemarin menurun, besok akan meningkatdengan probabilitas 0.6

- Jika hari ini menurun, kemarin meningkat, besok akan meningkatdengan probabilitas 0.5

- Jika dalam 2 hari terakhir stok menurun, besok akan meningkat denganprobabilitas 0.3

Model ini juga merupakan rantai markov dengan :State 0 : stok hari ini meningkat kemarin meningkatState 1 : stok hari ini meningkat kemarin menurunState 2 : stok hari ini menurun kemarin meningkatState 3 : stok hari ini menurun kemarin menurun

Matriks transisi : Pij = P(Xt = j | Xt-1 = i)

P =

7.003.00

5.005.00

04.006.0

01.009.0

Penelitian Operasional II Rantai Markov 53

Siana Halim Teknik Industri UK. Petra

Contoh 4.7: Kasus PerjudianSeorang pemain memiliki uang 1$, dalam tiap permainan peluang untuk menangsebesar 1$ adalah p dan peluang untuk kalah sebesar 1$ adalah 1-p. Permainanini berakhir bila pemain dapat mengumpulkan $3 atau bangkrut.

Kasus ini merupakan rantai markov dengan {Xt} mewakili keberuntungan daripemain , yaitu: 0, 1$ ,2$ ,3$.

Matriks probabilitas transisinya adalah :

P =

1000

p0p10

0p0p1

0001

4.4 PERSAMAAN CHAPMAN-KOLMOGOROV

Persamaan Chapman-Kolmogorov memberikan cara untuk menghitung peluangperpindahan (Probabilitas transisi) n-langkah yaitu :

Persamaan ini menunjukkan bahwa dari state i ke state j dalam n langkah, prosesakan 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 vlangkah dan kemudikan ke state j dalan n-v langkah, maka :

Jika v = 1 maka :

Jika v = n - 1

Ini merupakan probabilitas transisi 1 langkah rekursif.

nmudann,j,iM

ok

v)(nkj

p(v)ik

p(n)ij

P =

=

kM

ok

v)(nkj

p(v)ik

p(n)ij

P =

=

n,j,iM

ok

1)(nkj

pik

p(n)ij

P =

=

=

=M

okn,j,i

kjp1)-(n

ikp(n)

ijP

Rantai Markov 54 Penelitian Operasional II

Siana Halim Teknik Industri UK. Petra

Untuk n = 2 maka

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. PP = Pn

= P. Pn-1 = Pn-1 P

Contoh 4.8Dari matriks transisi pada contoh 4.5 didapat :

P(2) = P2 =

368.0368.0184.0080.0

0368.0368.0264.0

00368.0632.0

368.0368.0184.0080.0

368.0368.0184.0080.0

0368.0368.0264.0

00368.0632.0

368.0368.0184.0080.0

=

165.0300.0286.0249.0

087.0233.0319.0351.0

233.0233.0252.0283.0

165.0300.0286.0249.0

Arti :p10

(2) : Stok kamera pada akhir minggu adalah 1, probabilitas bahwa 2 minggukemudian 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)

=

165.0300.0286.0249.0

087.0233.0319.0351.0

233.0233.0252.0283.0

165.0300.0286.0249.0

165.0300.0286.0249.0

087.0233.0319.0351.0

233.0233.0252.0283.0

165.0300.0286.0249.0

=

164.0261.0286.0289.0

177.0263.0283.0284.0

166.0268.0285.0282.0

164.0261.0286.0289.0

=

=M

okn,j,i

kjp

ikp(2)

ijP

Penelitian Operasional II Rantai Markov 55

Siana Halim Teknik Industri UK. Petra

Arti :p10

(4) : Stok kamera pada akhir minggu adalah 1, probabilitas bahwa 4 minggukemudian 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 diketahuidistribusi probabilitas dari state awal, misalnya Qx0 (i) , dimana :

Qx0(i) = P (X0 = i) I = 0,1,2,,MMaka P(Xn = j) = Qx0(0) poj

(n) + Qx0(1) p1j(n) + + Qx0(M) pMj

(n)

Contoh 4.9Dari 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 minggudari awal inventori adalah 0.165, maka probabilitas tak bersyaratnya adalah :

P(X2 = 3) = Qx0 (3). P33(2)

= 1 x 0.165= 0.165

Misal diberikan bahwa Qx0 (i) = 0.25 I = 0,1,2,3 makaP(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.10Kedua 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 dariRantai 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 bahwasistem 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 Penelitian Operasional II

Siana Halim Teknik Industri UK. Petra

b. Jika state i berkomunikasi dengan state j, maka state jberkomunikasi dengan state i.

c. Jika state i berkomunikasi dengan state j dan state j berkomunikasidengan state k, maka state i berkomunikasi dengan state k.

Dari ketiga sifat ini, maka suatu state mungkin dipartisi menjadi kelas-kelasyang saling asing (disjoint classes) dengan states yang saling berkomunikasidikatakan 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. AbsorbingSuatau state i dikatakan sebagai state yang absorbing jika probabilitas transisisatu langkah pii = 1. Jadi sekali sistem memasuki state i maka sistem akantetap selamanya berada di state i tersebut.

5. Recurrent dan Transient State i dikatakan recurrent jika dan hanya jika :

=

=1n

)n(iip

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

sehingga

=

=1n

)n(iip )

State i dikatakan transient jika dan hanya jika :

=

1) sedemikianhingga pii

(n) = 0 untuk seluruh n yang bukan kelipatan t (t, 2t, 3t, ) dan tadalah bilangan bulat terbesar dengan sifat iniContoh 4.11Pada contoh 4.7, misalkan p =

P =

1000

2/102/10

02/102/1

0001

P2 =

1000

2/14/104/1

4/104/12/1

0001

P3 =

1000

*0**

**0*

0001

P4 =

1000

**0*

*0**

0001

Terlihat bahwa p11 = p22 = 0 untuk seluruh n, pada saat n = 1,3,5, berartiperiode t (bukan n) adalah 2.Artinya : proses tersebut dapat masuk ke state 1 hanya pada saat 2,4,

7. AperiodikJika terdapat 2 bilangan berurutan, s dan (s+1) sedemikian hingga prosesdapat berada pada state i pada saat s dan (s+1), state i dikatakan memilikiperiode 1 dan disebut sebagai aperiodik state.

8. Positif RecurrentJika state i recurrent, maka state i dikatakan positif recurrentJika dimulai dari state i, waktu harapan sampai proses kembali lagi ke state iadalah terbatas.

9. Null RecurrentJika state i recurrent tetapi tidak positif recurrent maka state i adalah NullRecurrent.

10. ErgodicJika suatu state bersifat positif recurrent dan aperiodik maka state tersebutdisebut ergodic.

4.9 WAKTU LINTASAN PERTAMA (FIRST PASSAGE TIME)Waktu yang dibutuhkan oleh suatu proses untuk menuju state j dari state i untukpertama kali disebut sebagai waktu lintasan pertama (first passage time, fpt).Jika j=1, waktu lintasan pertama ini merupakan jumlah transisi hingga proseskembali ke state mula-mula yaitu i. Dalam hal ini waktu lintasan pertama disebutsebagai waktu recurrence untuk state i.

Rantai Markov 58 Penelitian Operasional II

Siana Halim Teknik Industri UK. Petra

Contoh 4.12Dari 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 kestate 0 adalah 3 minggu dan waktu recurrent adalah 4 minggu.

Secara umum first passage time merupakan perubah acak dan memiliki distribusiprobabilitas yang bersesuaian dengan mereka. Distribusi probabilitas initergantung 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 sebagaiberikut :

Jadi probabilitas dari suatu first passage time dari state i ke state j dalam langkahn 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 :

=

1n

)n(ij 1f

sayangnya, jumlahan ini sangatlah mungkin kurang dari 1, yang berarti bahwasuatu 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 :

=

Penelitian Operasional II Rantai Markov 59

Siana Halim Teknik Industri UK. Petra

Bila

=

=1n

)n(ij 1f maka ij memenuhi persamaan berikut secara unik.

ij = 1 + jk

kjikp

jika i = j, ii disebut recurrent time harapan.

Contoh 4.14:Dari contoh 4.5. Persamaan di atas dapat digunakan untuk menghitung waktuharapan hingga kamera habis. Asumsikan proses dimulai dengan persediaankamera = 3 lintasan waktu pertama harapan, 30 dapat dicapai karena seluruh staterecurrent, maka :

30 = 1 + p31 10 + p32 20 + p33 3020 = 1 + p21 10 + p22 20 + p23 3010 = 1 + p11 10 + p12 20 + p13 30 atau

30 = 1 + 0.184 10 + 0.368 20 + 0.368 3020 = 1 + 0.368 10 + 0.368 2010 = 1 + 0.368 10

Di dapat : 10 = 1,58 minggu 20 = 2,51 minggu 30 = 3,50 mingguWaktu yang dibutuhkan agar kamera kehabisan stok adalah 3,5 minggu.

4.5 RANTAI MARKOV DALAM JANGKA PANJANG (Long RunProperties of Markov Chain)

4.5.1 Probabilitas pada keadaan stabil (steady state probabilities)Untuk rantai markov yang irreducible ergodic dapat ditunjukkan bahwa :

)n(ij

nplim

ada dan independen terhadap i.

Selanjutnya

)n(ij

nplim

= j

dimana j secara unik memenuhi persamaan-persamaan steady state berikut :

j > 0

j = =

M

0iiji p untuk j = 0,1,2,, M

=

=M

0jj 1

Rantai Markov 60 Penelitian Operasional II

Siana Halim Teknik Industri UK. Petra

j disebut sebagai probabilitas pada keadaan stabil dari rantai markov danmemiliki hubungan resiprokal terhadap waktu recurrent harapan.

j = jj

1

untuk j = 0,1,, M

! Steady state probability artinya adalah : bahwa probabilitas bahwa untukmendapatkan proses dalam suatu state tertentu, katakan j, setelah sejumlahbesar transisi cenderung menuju nilai j . Independen dari distribusiprobabilitas awal yang telah didefinisikan terhadap states tersebut.

! j dapat juga diinterpretasikan sebagai probabilitas stasioner.

Contoh 4.15Dari contoh 4.5

0 = 0 p00 + 1 p10 +2 p20 +3 p301 = 0 p01 + 1 p11 +2 p21 +3 p312 = 0 p02 + 1 p12 +2 p22 +3 p323 = 0 p03 + 1 p13 +2 p23 +3 p331 = 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) 31 = (0.184)0 + (0.368) 1 + (0.368) 2 + (0.184) 32 = (0.368)0 + (0.368) 2 + (0.368) 33 = (0.368)0 + (0.368) 31 = 0 + 1 + 2 + 3

di dapat :0 = 0.285 00 = 1/ 0 = 3.51 minggu1 = 0.285 11 = 1/ 1 = 3.51 minggu2 = 0.264 22 = 1/ 2 = 3.79 minggu3 = 0.166 33 = 1/ 3 = 6.02 minggu

Catatan 4.16Pada 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 stateyang transient setelah sejumlah besar transisi cenderung menuju ke nol.

4.5.2 Biaya rata-rata harapan/unit waktuUntuk suatu rantai markov yang irreducible dengan recurent state positif, suaturantai dengan state terbatas, berlaku :

Penelitian Operasional II Rantai Markov 61

Siana Halim Teknik Industri UK. Petra

j

N

1k

)k(ij

nnp

N

1lim =

=

dimana j memenuhi persamaan-persamaan stedy state. Andaikan bahwa suatubiaya (atau fungsi penalti lainnya) C(Xt) terjadi ketika proses berada di state Xtpada saat t, untuk t = 0,1,2,

Catatan 4.17C(Xt) adalah peubah acak dengan nilai C(0), C(1), , C(N) dan fungsi C(Xt)independen terhadap t.

4.3 RANTAI MARKOVstate

Tentukan probabilitas trasnsisi 1 langkahnya !Di dapat P =Contoh 4.6:Contoh 4.8Contoh 4.9Catatan 4.10

4.5 KLASIFIKASI STATE DALAM RANTAI MARKOVContoh 4.11Pada contoh 4.7, misalkan p = 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.

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).Contoh 4.12

Dari contoh 4.5Catatan 4.16Catatan 4.17