Markov Chains

Rantai Markov

Pengantar
Andre: Andreevich Markov (2 juni 1856 - 20 Juli, 1922) adalah seorang fisikawan Rusia. Dalam usahanya untuk menjelaskan secara matematik gejala alam yang dikenal dengan gerak Brown (Brownian motion), ia menemukan sebuah fakta yang kemudian dikenal sebagai Rantai Markov (Markov Chain) atau (1906-1907). Konstruksi matematik proses Markov yang benar dengan trajektori -trajektori yang berkesinambungan pertama kali dilakukan oleh N. Wiener pada tahun 1923. Selanjutnya, teori umum proses Markov dikembangkan oleh A.N. Kolmagorov, W. Feller, W Doeblin, P. Levy, pada tahun 1930 dan 1940.
Temuan A.A. Markov adalah:
"Untuk setiap waktu t, ketika kejadian adalah Kt, dan seluruh kejadian s Kt(j), hanya tergantung kepada kejadian Kt(j-1) dan tidak tergantung kepada kejadian - kejadian sebelumnya yaitu Kt(j-2), Kt(j-3), …, Kt(j-n) . “ebelumnya adalah Kt(j), …, Kt(j-n) yang terjadi dari proses yang diketahui, probabilitas seluruh kejadian yang akan datang
Pada umumnya riset operasional bertujuan untuk mengambil keputusan yang optimal atas suatu permasalahan. Namun analisis markov digunakan untuk menghasilkan suatu informasi probabilistik yang dapa digunakan untuk membantu pengambilan keputusan. Dengan kata lain teknik-teknik yang lain dalam riset operasional pada umumnya merupakan teknik optimisasi sedangkan pada analisis markov merupakan teknik deskriptif.
Rantai Markov adalah suatu teknik matematik yang biasa digunakan untuk melakukan pembuatan model bermacam-macam system dan proses bisnis. Teknik ini dapat digunakan untuk memperkirakan perubahan-perubahan yang akan terjadi di waktu yang akan dating dalam variable-variabel dinamis atas dasar perubahan-perubahan variable tersebut di waktu lampau.


1. CIRI-CIRI PROSES MARKOV
Probabilitas transisi adalah perubahan dari satu status ke status yang lain pada periode (waktu) berikutnya dan merupakan suatu proses random yang dinyatakan dalam probabilitas.
Untuk lebih jelasnya akan digunakan sebuah contoh kasus pada kendaraan umum. Dalam kasus ini terdapat 2 buah state (kondisi/status) yaitu narik atau mogok. Jadi kendaraan umum tersebut akan selalu berada pada salah satu dari 2 state tersebut, jika tidak narik maka mogok.
Agar dapat digunakan dalam proses markovdibutuhkan beberapa asumsi seperti berikut:
a. Jika state kendaraan saat ini adalah nerik maka hanya ada dua kemungkinan untuk kondisi waktu(hari) berikutnya yaitu narik kembali atau mogok, sehingga jumlah probabilitas transisi pada setiap baris adalah satu.
b. Probabilitas transisi itu tidak akan berubah untuk selamanya.
c. Probabilitas transisi hanya tergantung pada status skarang bukan status periode sebelumnya.

Gambaran mengenai rantai Markov ini kemudian dituangkan ke dalam Peraga 16.1 di mana gerakan - gerakan dari beberapa variabel di masa yang akan datang bisa diprediksi berdasarkan gerakan - gerakan variabel tersebut di masa lalu. Kt4 dipengaruhi oleh kejadian Kt3, Kt3 dipengaruhi oleh kejadian Kt2, dan demikian seterusnya di mana perubahan ini terjadi karma peranan probabilitas transitional (transitional probability). Kejadian Kt2 misalnya, tidak akan mempengaruhi kejadian Kt4 Karakteristik model seperti ini telah memungkinkan eksplorasi penerapan di berbagai bidang, misalnya :
1. 1965 Mencantumkan jumlah pom bensin yang harus dibuat oleh perusahaan minyak pada suatu daerah pemasaran. ( Philip H. Harting and James L. Fisherj
2. 1966 Menentukan jumlah optimal panggilan telepon yang harus dibuat oleh seorang salesman agar dapat menghasilkan untung, sebelum ia memutuskan bahwa tiap telepon yang ia buat berikutnya adalah sia-sia. [A Shuman]
3. 1972 Mengevaluasi strategi penentuan harga [John R. Nevin]
4. 1973 Menganalisa perilaku konsumen dan pengaruh dari kesetiaan terhadap merek dan tujuan meningkatkan segmentasi pasar [Jim Wong]
5. 1973 Menganalisa fluktuasi biaya keamanan [T. M. Tynu]
6. 1973 Menentukan kebutuhan tenaga kerja [Young and Neilson]









Karena sifatnya yang berantai tersebut, maka teori ini dikenal pula dengan nama Rantai Markov. Dengan demikian Rantai Markov akan menjelaskan gerakan-gerakan beberapa variabel dalam satu periode waktu di masa yang akan datang berdasarkan pada gerakan-gerakan variabel tersebut di masa kini. Secara matematik dapat di tulis
Kt(j) = P x Kt(j-1)
Dimana,
Kt(j) = Peluang Kejadian Pada tj
P = Frobabilitas Transisional
t(j) = Waktu ke-j.
Peluang kejadian Kt(j) dalam formulasi dinyatakan ke dalam bentuk vektor sehingga jumlah seluruh selnya akan selalu 100%.

MATRIKS PROBABILITAS TRANSISIONAL
Dinamika variabel yang diobservasi yang mempengarahi setiap kejadian dalam proses Markov dituangkan ke dalam sebuah matriks yang dikenal dengan probabilitas transisional (transi¬tional probability) yang berdimensi m x n. Dalam hal ini, aij mencerminkan peluang perubahan dari keadaan i ke keadaan j atau dari keadaan j ke keadaan i, tergantung kepada penempatannya, dari i dan ke j atau atau sebaliknya. Penempatan itu tentu saja akan membawa
PERAGA 16.2 Matrik Pobalitas transisio
x


konsekuensi pada operasi matriks. Tidak ada pedoman baku mengenai hal ini, maka beberapa penulis saling menempatkannya sesuai dengan kesenangan mereka.
Jika sebuah vektor yang berdimensi (l x m) dikalikan dengan matriks yang berdimensi (m x n), maka perkalian itu akan menghasilkan vektor yang berdimensi (l x n). Sebaliknya, jika matriks - matriks yang berdmensi (m x n) dikalikan dengan vektor yang berdimensi (n x l), maka perkalian itu akan menghasilkan vektor yang berdimensi (m x l). Dimensi vektor ini, sesuai dengan penjelasan mengenai penempatan dari dan ke, tentu saja harus menyesuaikan, dengan kaidah-kaidah dalam operasi matriks. Lihat Peraga 16.3.
PERAGA 16.3 Matrik probabilitas transisional.

x =
x =




Pada dasarnya, sebuah matriks probabilitas transisional mencerminkan sebuah proses transisi yang sedang terjadi dalam sebuah sistem selama kurun waktu tertentu, yaitu dari ti ke ti+1 seperti diperlihatkan pada Peraga 16.4. Proses itu akan menjelaskan kemungkinan perubahan variabel-variabel yang sedang diobservasi,















Jika 60% kondisi A tetap seperti semula, maka 40% akan berubah ke kondisi B. Sebaliknya, ada kemungkinan 50% kondisi B akan berubah ke kondisi A dan 50% kemungkinan kondisi B akan tetap seperti semula. Pola kemungkinan ini dapat dituangkan ke dalam bentuk tabel seperti pada Peraga 16.5






PERAGA 16.5 Tabel transisional
Dari
Status(saat ini) Banyaknya Mobil
Hari 1 Hari 2
Narik 120 144
Mogok 100 76
Jumlah 220 220

Hari 1 Hari II Jumlah
Narik Mogok
Narik 70 50 120
Mogok 74 26 100
Jumlah 144 76 220

Tabel transisional pada Peraga 16.5 menjelaskan bagaimana proses transisi tersebut di tabulasi. Jika tabel itu dituangkan ke dalam sebuah matriks, maka kita akan memperoleh sebuah Matriks Probabilitas Transisional dengan dimensi (2 x 2). Lihat peraga 16.6

PERAGA 16.6 Matrik Probabilitas transisional


Hari I Hari II
Narik Mogok
Narik 70/120=0,5833 50/120=0,4167
Mogok 74/100=0,74 26/100=0,26

Namun demikian, seperti telah dibahas sebelum ini, tabulasi yang mencerminkan ke¬mungkinan proses perpindahan variabel yang diobservasi itu juga bisa disusun berbeda seperti terlihat pada Peraga 16.7.
PERAGA 16.5 Tabel transisional


AA A B
A
B 0,5833
0,74 0,4167
0,26

Maka, matriks dari tabel tersebut akan tampak seperti pada Peraga 16.8.

Vektor Kejadian dan Operasi Matriks
Sesuai dengan [16.1], peluang kejadian dituangkan ke dalam bentuk vektor yang jumlah sel¬ - selnya sebesar 1 dan dimensinya jelas akan tergantung kepada pilihan matriks probabilitas transisional yang dikehendaki. Matriks probabilitas transisional dengan format Peraga 16.6 jelas menghendaki dimensi vektor [2 x 1], jadi, dimensi vektor itu sangat vektor itu sangat tergantung format matriks probabilitas transisional yang dikehendaki agar operasi probabilitas matriks menurunkan hasil seperti dikehendaki oleh [16.1].
Jika di waktu t kemungkinan kejadian A adalah 60% dan kemungkinan kejadian 3 adalah 40%, maka distribusi kemungkinan ini bisa dituangkan ke dalam bentuk vektor dengan dimensi yang berbeda. Lihat Peraga 16.9.

PERAGA 16.9 Kejadian dan dimensi vektor
a) [0,5833 0,4167]
b) 0,5833
0,4167

Karena kemungkinan kejadian itu pada t(o) maka untuk mengetahui kemungkinan kejadian pada t(l), [16.1] bisa diterapkan yaitu:
Probabilitas kendaraan narik pada period eke-I jika period eke-1 narik, dilambangkan dengan:

Probabilitas narik Nn(i) Periode ke-1



Status awal

Probabilitas kendaraan mogok pada period eke-3 jika pada periode ke-1 mogok, dilambangkan dengan:

Probabilitas Mogok Mm(3) Periode ke-3



Status awal mogok

Jika kendaraan pada hari ke-1 narik maka berlaku probabilitas sebagai berikut:
Nn(1) = 1 sedangkan Mm(3) = 0
Jika probilitas di atas disusun ke dalam vector baris, maka kita dapatkan:
Nn(1) Mm(3)) = (1 0)
Adapun rumus untuk mencari probabilitas periode berikutnya (i+1) adalah:
(Nn(i=1)) (Mn(i=1)) = (Nn(i) Mn(i)) x matrix Probabilitas Transisi
Bila rumus di atas kita gnakan untuk mencari probabilitas hari ke-2, maka:

(Nn(2) Mn(2)) = (Nn(1) Mn(1)) x 0,5833 0,4167
0,74 0,26



a) [1 0] x [16.5]



atau,
Kt(j) = K t(j-1) x P
x = [16.5]
Jadi, format manapun yang dikehendaki sebenarnya akan menghasilkan hasil yang sama. Dengan menggunakan cara yang sama kita akan dapatkan status untuk periode-periode berikutnya sebagai berikut:
(Nn(3) Mn(3)) = (0,6486 0,3514)
(Nn(4) Mn(4)) = (0,6384 0,3616)
(Nn(5) Mn(5)) = (0,6400 0,3400)
(Nn(6) Mn(6)) = (0,6397 0,3603)
(Nn(7) Mn(7)) = (0,6398 0,3602)
(Nn(8) Mn(8)) = (0,6398 0,3602)
Terlihat bahwa perubahan probabilitas semakin lama semakin mengecil sampai akhirnya tidak tampak adanya perubahan. Probabilitas tersebut tercapai mulai dari periode ke-7, dengan probabilitas status:
Nn(7) Mn(7)) = (0,6398 0,3602)
Ini berarti pemilik kendaraan dapat menarik kesimpulan bahwa jika awalnya kendaraan berstatus narik, setelah beberapa periode di masa depan probabilitasnya narik adalah sebesar 0,6398 dan probabilitasnya mogok adalah sebesar 0,3602.
Untuk perhitungan probabilitas status hari pertama mogok dapat kita cari dengan metode yang sama dan akan kita dapatkan probabilitas yang akan sama untuk periode selanjutnya, mulai dari periode ke-8. Adapun probabilitas pada periode ke-8 adalah:
(Nn(8) Mn(8)) = (0,6398 0,3602)

HIGH ORDER DAN LOW ORDER MARKOV
Probabilitas Transisional dalam pembahasan selama ini selalu sama untuk seluruh j. Probabilitas Transisional yang selalu sama untuk setiap j disebut Low Order. Beberapa aplikasi telah membuktikan bahwa penggunaan Low Order Markov pada bidang - bidang tertentu valid pada j yang berbeda. Untuk kasus Low Order Markov, [ 16.9] bisa digunakan.
Namun demikian, untuk kasns - kasus tertentu pula pengaruh perubahan lingkungan mungkin menguhah peluang perubahan pada setiap j. Hal ini menyebabkan probabilitas transisional pada setiap j bisa berbeda. Probabilitas transisional yang berbeda untuk setiap j disebut High Order Markov. Tentu saja [16.9] tidak bisa digunakan dan [16.1] harus digunakan untuk setiap J.


Steady State Probability
Dalam banyak kasus, proses markov akan menuju pada Steady State (keseimbangan) artinya setelah proses berjalan selama beberapa periode, probabilitas yang dihasilkan akan bernilai tetap, dan probabilitas ini dinamakan Probabilitas Staedy State.
Untuk mencari Probabilitas Steady State dari suatu matrix Transisi, maka kita dapat menggunakan rumus:
(Nn(i=1) Mn(i=1)) = (Nn(i) Mn(i)) x Matrix Probabilitas Transisi
Karena Steady State akan menghasilkan probabilitas yang sama pada period eke depan maka rumus tersebu akan berubah menjadi”
(Nn(i) Mn(i)) = (Nn(i) Mn(i)0 x Matrix Probabilitas Transisi
Dari contoh kasus di atas dengan hari ke-1 narik, maka kita dapatkan:\
0,5833 0.4167

0,74 0,26



Untuk mengurangi keruwetan, periode (i) dapat di hilangkan, karena pada saat Steady State tercapai periode tidak mempengaruhi perhitungan. Sehingga perhitungan di atas akan menjadi:
(Nn Mn) = (Nn Mn) x 0,5833 0,4167
0,74 0,26



Dari perhitungan di atas akan menghasilkan persamaan berikut:
Nn = 0,5833 +0,74Mn……………………………………(1)
Mn = 0,4167 = 0,26Mn…………………………………..(2)
Karena salah satu ciri proses Markov adalah:
Nn(i) = Mn(i) = 1, maka:
Nn = Mn = 1 Mn = 1 – Nn
Dengan menstubstitusikan Mn = 1 – Nn ke persamaan (1) didapatkan:
Nn = 0,5833Nn + 0,74(1-Nn)
Nn = 0,5833Nn = 0,74 – 0,74Nn
1,1567Nn = ),74
Nn = 0,6398
Lalu kita masukkan nilai Nn = 0,6398 ke dalam persamaan (2) didapatkan:
Mn = 0,3602
Dari contoh kasus kita ketahui bahwa pemilik kendaraan memiliki 220 kendaraan. Dengan menggunakan Probabilitas Steady State yang sudah kita dapatkan, pemilik dapat menharapkan jumlah kendaraan setiap harinya narik atau mogok sebanyak:
Narik : Nn x 220 = 0,6398 x 220 = 140,756 atau sebanyak 141 kendaraan.
Mogok : Mn x 220 = 0,3602 x 220 = 79,244 atau sebanyak 79 kendaraan.
Terlihat dari contoh kasus di atas, menunjukkan bahwa Analisis Markov sebenarnya tidak memberikan solusi atau keputusan, namun analisis tersebut memberikan informasi yang dapat membantu pembuatan keputusan.