BAB 2 LANDASAN TEORI
2.1
Model Markov
Dalam teori probabilitas, model Markov adalah model stokastik yang digunakan untuk memodelkan sistem yang berubah-ubah secara random di mana diasumsikan bahwa kondisi masa depan tergantung hanya pada keadaan sekarang dan bukan pada urutan peristiwa yang mendahuluinya (mengasumsikan properti Markov). Umumnya, asumsi ini memungkinkan penalaran dan perhitungan, yang jika menggunakan model lain mungkin akan lebih sulit diselesaikan. Ada empat model Markov yang digunakan dalam situasi yang berbeda, tergantung pada apakah setiap kondisi berurutan dapat diamati atau tidak, dan apakah sistem ini terjadi secara acak atau kejadiannya dapat dikontrol. Berikut adalah tabel yang menunjukkan beberapa model Markov berdasarkan situasinya.
Tabel 2.1 Model Markov berdasarkan Situasinya Situasi
Dapat sepenuhnya
Dapat diamati secara parsial
diamati Mandiri Dikontrol
Markov Chain
Hidden Markov Model
Markov Decision Process
Partially Observable Markov Decision Process
Dalam skripi ini penulis menggunakan Markov chain (rantai Markov), yaitu proses acak yang mengalami transisi dari satu kondisi ke yang lain pada ruang keadaan. Model Markov ini harus memiliki properti yang biasanya ditandai sebagai "memoryless": distribusi probabilitas pada kondisi berikutnya tergantung
Universitas Sumatera Utara
hanya pada keadaan saat ini dan bukan pada urutan peristiwa yang mendahuluinya. Jenis tertentu ini disebut properti Markov. Analisis Markov hampir sama dengan decision analysis, bedanya adalah decision analysis memberikan keputusan berupa rekomendasi sedangkan analisis rantai markov tidak memberikan keputusan berupa rekomendasi. Analisis rantai markov hanya memberikan informasi probabilitas mengenai situasi keputusan yang dapat membantu proses pengambilan keputusan. Oleh karena itu, analisis rantai markov bukanlah teknik optimisasi, melainkan teknik deskriptif yang menghasilkan informasi probabilitas pada masa mendatang.
2.1.1
Rantai Markov
Rantai Markov (Markov Chain) adalah suatu model teoritis yang menerangkan keadaan sebuah sistem pada suatu tahap tertentu. Model Markov menyediakan cara yang lebih nyaman pemodelan prognosis untuk masalah klinis dengan resiko yang sedang berlangsung untuk memperkirakan perubahan-perubahan pada waktu yang akan datang (Sonnenberg, A.F, 2009). Secara umum, rumus rantai markov adalah sebagai berikut:
(
|
)
(
|
)
Persamaan di atas disebut properti Markov. Jika P tidak bergantung pada n, maka rantai Markov tersebut homogen. Jika kedua probabilitas terkondisi didefinisikan dengan baik, contoh jika
(
|
)
. Jika nilai-nilai Xi
membentuk satu set countable S maka S itu disebut ruang keadaan dari rantai. Proses Markov dikategorikan berdasarkan konstan atau tidak konstannya probabilitas state-transisi dari waktu ke waktu. Dalam jenis yang paling umum dari proses Markov, probabilitas transisi dapat berubah dari waktu ke waktu. Sebagai contoh, probabilitas transisi untuk transisi dari BAIK untuk MATI terdiri dari dua komponen. Jenis khusus dari proses Markov di mana transisi probabilitas yang konstan dari waktu ke waktu disebut Rantai Markov.
Universitas Sumatera Utara
Probabilitas yang didapat membuat transisi dari satu state selama satu siklus disebut transisi probabilitas. Proses Markov didefinisikan oleh distribusi probabilitas antara state yang pertama dan probabilitas bagi individu untuk memungkinkan terjadinya transisi. Untuk model Markov yang terdiri dari n state, akan ada probabilitas transisi n2. Untuk dapat menerapkan rantai markov ke dalam suatu kasus, ada beberapa syarat yang harus dipenuhi: 1. Jumlah probabilitas transisi untuk suatu keadaan awal dari sistem sama dengan 1 (satu) 2. Probabilitas-probabilitas tersebut berlaku untuk semua partisipan dalam sistem 3. Probabilitas transisi konstan sepanjang waktu 4. Kondisi merupakan kondisi bebas sepanjang waktu
Untuk rumus rantai markov dengan transisi ke-n adalah Pn. Sementara untuk rumus rantai markov di mana hanya memerlukan sebagian dari seluruh matriks adalah sebagai berikut:
persamaan 2.1 rumus rantai markov
Di mana xn (kondisi pada transisi ke-n) dan x0 (kondisi pada transisi awal) menggunakan matriks 1 x 3, dan Pn menggunakan matriks 3 x 3.
2.1.2
Contoh Rantai Markov
Kita anggap proses stokastik {
( )
}
yang merupakan satu set M yang terbatas (finite) atau bisa dihitung (countable).
Universitas Sumatera Utara
Contoh 1: misalkan
( )
adalah cuaca pada hari ke-n di mana menjadi *
+
Kita dapat mengikuti pelaksanaan: ( )
Contoh 2: misalkan
( )
( )
( )
( )
adalah penjualan produk pada hari ke-n di mana menjadi *
+
Kita dapat mengikuti pelaksanaan: ( )
( )
( )
( )
Lebih sederhananya kita asumsikan M, state space-nya adalah {0, 1, 2...}. Elemen pada M disebut kondisi pada proses.
2.2
Pengambilan Keputusan
Keputusan adalah hasil pemecahan masalah yang dihadapi. Hal ini berkaitan dengan jawaban atas pertanyaan-pertanyaan tentang apa yang harus dilakukan dan mengenai unsur-unsur perencanaan. Dapat juga dikatakan bahwa keputusan itu sesungguhnya merupakan hasil proses pemikiran yang berupa pemilihan satu diantara beberapa alternatif yang dapat digunakan untuk memecahkan masalah yang dihadapinya. Keputusan itu sendiri merupakan unsur kegiatan yang sangat penting. Jiwa kepemimpinan seseorang itu dapat diketahui dari kemampuan mengatasi masalah dan mengambil keputusan yang tepat. Keputusan yang tepat adalah keputusan yang berbobot di mana dapat menyelesaikan masalah dengan resiko terkecil.
Universitas Sumatera Utara
Pengambilan keputusan adalah proses kognitif yang mengakibatkan pemilihan keyakinan atau tindakan di antara beberapa kemungkinan alternatif. Setiap proses pengambilan keputusan menghasilkan pilihan akhir yang mungkin meminta atau tidak meminta tindakan. Pengambilan keputusan adalah studi tentang mengidentifikasi dan memilih alternatif yang didasarkan pada nilai-nilai dan preferensi pengambil keputusan. Pengambilan keputusan adalah salah satu kegiatan utama manajemen dan merupakan bagian besar dari setiap proses pelaksanaan. Kinerja manusia berkaitan dengan keputusan telah menjadi subjek penelitian dari beberapa sudut pandang: Psikologis: meneliti keputusan individu dalam konteks serangkaian kebutuhan, preferensi dan nilai-nilai yang dicari atau dimiliki. Kognitif: proses pengambilan keputusan dianggap sebagai proses yang berkesinambungan yang dipadukan dalam interaksi dengan lingkungan. Normatif: analisis keputusan individu yang bersangkutan dengan logika pengambilan keputusan dan rasionalitas dan hal-hal yang mengarah dari pilihan invarian (invarian adalah properti yang tetap tidak berubah ketika transformasi dari jenis tertentu diterapkan pada sebuah objek).
Pengambilan keputusan logis merupakan bagian penting dari semua profesi berbasis ilmu pengetahuan, di mana para ahli menerapkan pengetahuan mereka di bidang tertentu untuk membuat keputusan. Sebagai contoh, dalam pembuatan keputusan, ahli medis sering melakukan diagnosa dan pemilihan pengobatan yang sesuai. Dalam pengambilan keputusan harus diambil dengan pemikiran yang matang, bukan secara kebetulan, dan tidak boleh sembarangan. Adapun langkahlangkah sistematis yang perlu dilakukan dalam proses pengambilan keputusan adalah sebagai berikut :
Universitas Sumatera Utara
1. Mengidentifikasi masalah Pengambilan keputusan pada dasarnya adalah proses pemecahan masalah yang menghalangi atau menghambat tercapainya tujuan. Agar masalah dapat dipecahkan, terlebih dahulu harus dikenali apa masalahnya. 2. Mencari alternatif pemecahan Yang terpenting dalam mencari alternatif adalah dengan mengumpulkan data untuk penyelesaian masalah sebanyak mungkin. Setelah alternatif terkumpul, barulah disusun berurutan dari yang paling diinginkan sampai yang tidak diinginkan 3. Memilih alternatif Setelah tersusun, barulah memilih alternatif. Setiap alternatif perlu diteliti berdasarkan kelebihan dan kekurangan, tingkat resiko, dan tingkat efisiensi. 4. Pelaksanaan alternatif Setelah alternatif dipilih, laksanakan alternatif tersebut 5. Evaluasi Pelaksanaan alternatif harus terus diamati, untuk mengetahui keefektifan hasil dari alternatif tersebut.
2.2.1
Pengambilan Keputusan Medis
Pengambilan keputusan merupakan bagian dari suatu peristiwa yang meliputi diagnosa, seleksi tindakan dan implementasi (Beach & Connolly, 2005). Definisi lain tentang pengambilan keputusan juga dikemukakan oleh Nigro (dalam Ridho, 2003) bahwa keputusan ialah pilihan sadar dan teliti terhadap salah satu alternatif yang memungkinkan dalam suatu posisi tertentu untuk merealisasikan tujuan yang diharapkan. Perawatan medis sering disebut sebagai salah satu seni mengambil keputusan tanpa informasi yang adekuat (Sox, 1990). Para dokter sering memilih perlakuan kepada pasien, jauh sebelum para dokter tersebut mengetahui jenis penyakit yang muncul. Bahkan ketika penyakit diketahui, dokter biasanya harus memilih dari beberapa pilihan tindakan
Universitas Sumatera Utara
pengobatan dan konsekuensi dari masing-masing pengobatan tidak dapat diramalkan dengan jelas, sehingga ketidakpastian menjadi salah satu faktor intrinsik dalam praktek medis (Sox, 1990). Para dokter mengalami kesulitan dalam membuat keputusan di dunia medis. Ini disebabkan besarnya pengaruh etika di dalam proses tersebut. Untuk hal etika sendiri, hal ini mungkin berbeda-beda tergantung tempat dan zaman saat dibutuhkannya pemikiran dalam menyelesaikan masalah tertentu. Di dalam beberapa situasi, dokter harus memutuskan untuk dirinya sendiri apakah yang benar untuk dilakukan. Namun dalam mengambil keputusan tersebut, akan sangat membantu jika mereka mengetahui apa yang dilakukan dokter lain dalam situasi yang sama. Kode etik dokter dan kebijakan yang berlaku merupakan konsensus umum bagaimana seorang dokter harus bertindak dan harus diikuti kecuali ada alasan yang lebih baik mengapa harus melanggarnya. Pada umumnya dokter menganggap mereka bertanggung jawab terhadap diri mereka sendiri, kepada kolega profesi kesehatan mereka, dan terhadap agama yang dianut, kepada Tuhan. Saat ini mereka memiliki tanggung jawab tambahan – terhadap pasien mereka, kepada pihak ketiga seperti rumah sakit, organisasi yang mengambil keputusan medis terhadap pasien, kepada pemegang kebijakan dan perijinan praktek, dan bahkan sering kepada pengadilan. Berbagai tanggung jawab yang berbeda ini dapat saling bertentangan satu sama lain.
2.3
Matriks
Matriks adalah sebuah susunan persegi yang terdiri dari angka, simbol atau ekspresi yang diatur dalam baris dan kolom, di mana ditafsirkan dengan cara tertentu. Salah satu cara adalah untuk menyatakan urutan matriks. Angka, simbol atau ekspresi dalam matriks disebut entri atau elemen. Sebagai contoh, urutan matriks di bawah ini adalah 2 × 3, karena ada dua baris (horizontal) dan tiga kolom (vertikal). 0
1
Universitas Sumatera Utara
Matriks yang memiliki baris tunggal yang disebut vektor baris, dan yang memiliki satu kolom disebut vektor kolom. Sebuah matriks yang memiliki jumlah yang sama dari baris dan kolom disebut matriks persegi. Sebuah matriks dengan jumlah baris atau kolom tak terbatas (atau keduanya) disebut matriks yang tak terbatas (infinite matrix). Dalam beberapa konteks, seperti program komputer aljabar, mungkin terdapat matriks tanpa baris atau kolom yang disebut matriks kosong. Matriks biasanya ditulis dalam tanda kurung kotak atau tanda kurung besar:
]
[
(
)
.
Notasi dari matriks bervariasi. Biasanya matriks disimbolkan dengan huruf besar (seperti contoh A di atas), di mana yang menggunakan huruf kecil dengan indeks kecil (misalkan a11) merepresentasikan entri/elemen.
2.3.1 Operasi Dasar Matriks
Ada beberapa operasi dasar yang dapat diterapkan pada matriks, disebut penjumlahan matriks, perkalian skalar, transposisi, perkalian matriks, operasi baris, dan submatriks. Penjumlahan matriks adalah operasi menjumlahkan dua matriks, di mana kedua matriks tersebut harus memiliki banyak baris dan banyak kolom yang sama. Contoh: 0
1
0
1
0
1
0
1
Perkalian skalar adalah perkalian dari c (merupakan skalar) dan matriks A, di mana setiap elemen A dikalikan dengan c.
Universitas Sumatera Utara
Contoh: ,
-
,
-
,
-
Transposisi adalah saat semua elemen pada suatu matriks bertukar posisi di mana dari m x n menjadi n x m (baris awal menjadi kolom dan kolom awal menjadi baris). Contoh: 0
1
[
]
Perkalian matriks adalah perkalian antara dua matriks, di mana hanya bisa dilakukan jika banyaknya kolom dari matriks sebelah kiri sama banyak dengan baris dari matriks sebelah kanan. Misalkan A adalah matriks nxm dan B adalah matriks nxp, maka hasil kali AB adalah matriks mxp:
[
] [
]
( (
) )
( (
) )
( (
) )
(
)
(
)
(
)
[
]
di mana setiap elemen i, j didapat dengan dikalikannya elemen Aik (sepanjang baris i pada A) dengan elemen Bkj (sepanjang kolom j pada B), untuk k = 1, 2, ..., m, dan menghitung hasil terhadap k:
(
)
∑
Terlihat bahwa hasil dari AB terdefinisi jika hanya banyak kolom A sama dengan banyak kolom B, dalam hal ini m. Setiap entri mungkin dihitung satu per satu.
Universitas Sumatera Utara
Contoh: ]0
[
1
]
[
Perkalian matriks sendiri tidak komutatif, dimana AB ≠ BA Contoh 2: 0
]
1[
0
1
Untuk operasi baris, terdapat tiga tipe operasi: 1. Penjumlahan baris 2. Perkalian baris 3. Perpindahan baris Submatriks adalah penghapusan sekumpulan baris dan/atau kolom dari matriks. Contohnya, dari matriks 3x4, kita bisa membuat matriks 2x3 dengan menghapus, misalnya baris 3 dan kolom 2:
[
2.3.2
]
0
1
Contoh Matriks Transisi
Pada bagian ini, kita akan menyelidiki probabilitas transisi Pij proses rantai Markov sampai langkah ke-n. Misalkan Pij adalah probabilitas dengan memproses dari kondisi j akan berada pada kondisi i setelah terjadi transisi ke-n. Ditulis Pij(1) = Pij. Dengan demikian P(n) = Pn di mana P(n) adalah probabilitas matriks transisi n-langkah dan P adalah probabilitas matriks transisi 1-langkah.
Universitas Sumatera Utara
Akan dibuktikan proposisi dengan menggunakan induksi matematika. Jelas proposisi adalah benar ketika n = 1. Kemudian, anggap bahwa proposisi adalah benar untuk n. Diketahui bahwa:
sebanyak n
kemudian, (
)
∑
( ) ( )
,
∑
-
Dengan prinsip induksi matematika, proposisi ini berlaku untuk semua bilangan bulat non-negatif n. Kesimpulannya, dapat dilihat bahwa: ( ) ( )
(
)
Contoh 2: Anggap ada persoalan pemasaran. Dalam model yang kita miliki [
]
Jika α = 0,3 dan β = 0,4 maka didapat 0
1
[
]
Misalkan pada state awal pelanggan membeli di toko A(α). Maka dia akan membeli di toko A pada pembelian ke-4 dengan peluang membeli di toko B pada pembelian ke-4
, dan
.
Jika pada state awal pelanggan membeli di toko B (β), maka dia akan membeli di toko A pada pembelian ke-4 dengan peluang membeli di toko B pada pembelian ke-4
, dan
.
Universitas Sumatera Utara
Contoh 3: Diketahui proses pada rantai markov memiliki kondisi {0, 1, 2, ...}. Anggap kita berada pada waktu n = 0 dengan probabilitas saat pada kondisi i adalah ai, i = 0, 1, 2, .... Yang menjadi pertanyaan, berapakah probabilitas pada kondisi i setelah n transisi? Dapat diketahui probabilitasnya adalah
( )
,
- ,
di mana Pji adalah probabilitas transisi satu-langkah dari kondisi i ke kondisi j. Maka probabilitas yang diperlukan adalah: ∑ (
( )
( )
)
,
∑
-
maka .̃
( )
( )
̃(
)
/
menjadi distribusi probabilitas dari kondisi pada proses rantai Markov saat transisi ( ke-n. Di sini ̃
)
adalah probabilitas di mana proses berada pada kondisi i setelah
n transisi dan ̃(
∑
)
.
Bisa diperiksa bahwa (
)
( )
dan (
)
(
)
( )
Contoh 4: Terdapat matriks transisi di bawah ini [
]
Dan misalkan kita hanya membutuhkan baris ke-2 dari matriks di atas. Kita bisa melakukan sebagai berikut: Buat matriks 1 x 3:
,
- , di mana 0 (nol) yang pertama untuk
dikalikan ke baris ke-1 dari matriks P, 1 dikalikan ke baris ke-2 dari matriks P, 0 (nol) yang kedua untuk dikalikan ke baris ke-3 dari matriks P.
Universitas Sumatera Utara
Kemudian kalikan kedua matriks
,
-[ ,
] -
Didapatlah baris kedua dari matriks P, yaitu P’
Universitas Sumatera Utara