penyelesaian model tahap terhingga dan … · model tersebut diaplikasikan dalam bidang pertanian,...
TRANSCRIPT
PENYELESAIAN MODEL TAHAP TERHINGGA DAN
TAKHINGGA PADA PROSES KEPUTUSAN MARKOV
DAN APLIKASINYA DI BIDANG PERTANIAN
BILYAN USTAZILA
DEPARTEMEN MATEMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
INSTITUT PERTANIAN BOGOR
BOGOR
2014
PERNYATAAN MENGENAI SKRIPSI DAN
SUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA*
Dengan ini saya menyatakan bahwa skripsi berjudul Penyelesaian Model Tahap
Terhingga dan Takhingga pada Proses Keputusan Markov dan Aplikasinya di
Bidang Pertanian adalah benar karya saya dengan arahan dari komisi pembimbing
dan belum diajukan dalam bentuk apa pun kepada perguruan tinggi mana pun.
Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun
tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan
dalam Daftar Pustaka di bagian akhir skripsi ini.
Dengan ini saya melimpahkan hak cipta dari karya tulis saya kepada Institut
Pertanian Bogor.
Bogor, April 2014
Bilyan Ustazila
NIM G54100101
ABSTRAK
BILYAN USTAZILA. Penyelesaian Model Tahap Terhingga dan Takhingga pada
Proses Keputusan Markov dan Aplikasinya di Bidang Pertanian. Dibimbing oleh I WAYAN MANGKU dan HADI SUMARNO.
Proses keputusan Markov adalah suatu proses pengambilan keputusan
menggunakan rantai Markov untuk model-model stokastik. Tujuan karya ilmiah
ini adalah merumuskan model stokastik yang melibatkan state, tindakan dan
reward. Lalu, model tersebut diaplikasikan dalam bidang pertanian, yaitu
menentukan keuntungan optimal dengan memberikan suatu tindakan, serta
menentukan kebijakan optimal yang memaksimumkan keuntungan (reward).
Metode yang digunakan untuk menentukan kebijakan optimal adalah
enumerasi lengkap, iterasi kebijakan dan formulasi pemrograman linear. Diantara
metode yang digunakan, metode iterasi kebijakan yang paling efisien.
Berdasarkan data yang digunakan dalam kasus ini, penentuan kebijakan dengan
ketiga metode ini menghasilkan kesimpulan yang sama yaitu petani tidak akan
menggunakan pupuk saat kondisi tanah baik, dan akan menggunakan pupuk saat
kondisi tanah sedang atau buruk. Pada kasus dengan faktor diskonto sebesar 0.7,
masalah pertanian ini menghasilkan kebijakan yang sama dengan kasus tanpa
diskonto.
Kata kunci: enumerasi, iterasi kebijakan, pemrograman linear, proses keputusan
Markov
ABSTRACT
BILYAN USTAZILA. Solution of Finite and Infinite Stage Models in Markov
Decisicion Processes and Its Application in Agricultural Sector. Supervised by I
WAYAN MANGKU and HADI SUMARNO.
Markov decision process is a decision making process using Markov chain
for stochastic models. The aim of this paper is to formulate a stochastic model
involving states, actions and rewards. Further, the model is applied into
agricultural sector, especially on determination of the optimal revenue based on
actions specified. Also to determine an optimal policy that maximizes the reward.
The methods used in this study are the complete enumeration, the policy
iteration and the linear programming methods. Among the methods used, the most
efficient method is the policy iteration. Based on the data used, determination of
the policy using those three methods concluded that farmers would not use
fertilizer when the soil fertility is good, and will use fertilizer when the soil
fertility are moderate or low. Especially, for the case of the discount 0.7, the
agricultural problem resulting the same policy with the case of no discount rate.
Keywords: enumeration, linear programming, Markov decision process, policy
iteration.
Skripsi
sebagai salah satu syarat untuk memperoleh gelar
Sarjana Sains
pada
Departemen Matematika
PENYELESAIAN MODEL TAHAP TERHINGGA DAN
TAKHINGGA PADA PROSES KEPUTUSAN MARKOV
DAN APLIKASINYA DI BIDANG PERTANIAN
BILYAN USTAZILA
DEPARTEMEN MATEMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
INSTITUT PERTANIAN BOGOR
BOGOR
2014
Judul Skripsi : Penyelesaian Model Tahap Terhingga dan Takhingga pada Proses
Keputusan Markov dan Aplikasinya di Bidang Pertanian.
Nama : Bilyan Ustazila
NIM : G54100101
Disetujui oleh
Prof Dr Ir I Wayan Mangku, MSc
Pembimbing I
Dr Ir Hadi Sumarno, MS
Pembimbing II
Diketahui oleh
Dr Toni Bakhtiar, MSc
Ketua Departemen
Tanggal Lulus:
PRAKATA
Puji dan syukur penulis panjatkan kepada Allah SWT atas segala
karunia-Nya sehingga karya ilmiah yang berjudul Model Tahap Terhingga dan
Takhingga pada Proses Keputusan Markov dan Aplikasinya di Bidang Pertanian
berhasil diselesaikan. Skripsi ini merupakan syarat bagi penulis untuk dapat meraih
gelar Sarjana Sains pada Mayor Matematika. Terima kasih penulis ucapkan kepada
Bapak Prof Dr Ir I Wayan Mangku, MSc dan Bapak Dr Ir Hadi Sumarno, MS
selaku dosen pembimbing dan Bapak Ir Ngakan Komang Kutha Ardana, MSc
selaku dosen penguji yang telah memberi masukan dalam penulisan skripsi. Selain
itu, penulis juga mengucapkan terima kasih kepada bapak, ibu, kakak Bellya Saksilia,
atas doa dan kasih sayangnya serta teman-teman matematika 47, Ayun, Alin, Jupe,
Pupu, Leni, pembahas seminar Marin, Safi’i dan Novia, dan anak kosan Tyas, Kak
Mira, Kak Ira, Iis, Admas
Penulis menyadari bahwa penulisan skripsi ini kurang sempurna. Oleh
karena itu, kritik dan saran yang membangun sangat penulis harapkan. Penulis juga
berharap skripsi ini dapat memberikan pengetahuan dan manfaat.
Bogor, April 2014
Bilyan Ustazila
DAFTAR ISI
DAFTAR TABEL vi
DAFTAR LAMPIRAN vi
PENDAHULUAN 1
Latar Belakang 1
Tujuan 1
TINJAUAN PUSTAKA 2
APLIKASI DI BIDANG PERTANIAN 4
Aplikasi Model Pemrograman Dinamis Tahap Terhingga 4
Aplikasi Model Pemrograman Dinamis Tahap Takhingga 7
Metode Enumerasi Lengkap 8
Masalah Petani dengan Tahap Perencanaan Periode Takhingga 8
Metode Iterasi Kebijakan 10
Metode Iterasi Kebijakan tanpa Diskonto 12
Metode Iterasi Kebijakan dengan Diskonto 13
Penyelesaian Pemrograman Linear untuk Masalah Keputusan Markov 15
Masalah Keputusan Markov tanpa Diskonto 15
Masalah Keputusan Markov dengan Diskonto 17
SIMPULAN DAN SARAN 18
Simpulan 18
Saran 18
DAFTAR PUSTAKA 18
LAMPIRAN 20
RIWAYAT HIDUP 24
DAFTAR TABEL
1 Nilai-nilai 6
2 Hasil perhitungan pada n = 3 6
3 Hasil perhitungan pada n = 2 6
4 Hasil perhitungan pada n = 1 6
5 Nilai-nilai 7
6 Kebijakan yang terjadi 8
7 Nilai-nilai setiap state 9
8 Nilai dan semua kebijakan 10
9 Hasil iterasi kebijakan tanpa diskonto pada iterasi pertama 12
10 Hasil iterasi kebijakan tanpa diskonto pada iterasi kedua 13
11 Hasil iterasi kebijakan tanpa diskonto pada iterasi ketiga 13
12 Hasil iterasi kebijakan dengan diskonto iterasi pertama 14
13 Hasil iterasi kebijakan dengan diskonto iterasi kedua 15
DAFTAR LAMPIRAN
1 Keuntungan per tahap kebijakan tahap takhingga 20
2 Proses perhitungan pada metode iterasi kebijakan tanpa diskonto 22
3 Proses perhitungan pada metode iterasi kebijakan dengan diskonto 23
PENDAHULUAN
Latar Belakang
Dalam kehidupan sehari-hari, manusia sering menemukan suatu
permasalahan, baik permasalahan kecil maupun besar. Setiap menghadapi
permasalahan, manusia dituntut untuk mengambil suatu tindakan atau kebijakan.
Dalam proses stokastik, tindakan atau kebijakan tersebut dikenal dengan
keputusan. Dalam proses pengambilan keputusan akan ada risiko yang harus
ditanggung. Risiko menjadi salah satu pertimbangan untuk mengambil keputusan.
Keputusan yang sederhana hanya akan berpengaruh pada risiko yang kecil,
sedangkan untuk keputusan besar akan mengakibatkan risiko yang besar, sehingga
perlu pertimbangan yang matang. Dalam praktiknya, terdapat banyak alternatif
pilihan keputusan, sehingga diperlukan teknik-teknik dalam pemilihannya agar
memperoleh hasil yang optimal. Alternatif keputusan tersebut memiliki unsur
probabilitas karena dalam pembuatan keputusan dihadapkan pada ketidakpastian.
Proses keputusan Markov (Markov Decision Process) menjelaskan model
dinamika dari pengambilan keputusan yang mengandung unsur ketidakpastian.
Pada setiap langkah proses keputusan Markov dipilih tindakan tertentu dan
tindakan tersebut akan menghasilkan keuntungan (reward) yang sesuai. Untuk
mendapatkan keuntungan yang optimal, diperlukan kebijakan yang optimal pula.
Kebijakan optimal dapat diperoleh dengan menggunakan tiga metode yaitu
metode enumerasi, metode iterasi kebijakan (policy iteration method), dan metode
solusi program linear (linear program solution method).
Pembahasan utama dalam karya ilmiah ini yakni metode iterasi kebijakan
dan metode pemrograman linear. Metode iterasi kebijakan ini diawali dengan
mengambil sebuah kebijakan dan menghitung nilainya yang dalam
perhitungannya terdapat faktor diskonto (α) maupun tidak terdapat faktor
diskonto. Faktor diskonto adalah pengali untuk menghitung nilai uang yang akan
datang bila dinilai dalam waktu sekarang. Adanya faktor diskonto (α < 1) dapat
menghasilkan perubahan dalam kebijakan optimal, dibandingkan dengan kasus
tanpa diskonto (α = 1). Setelah itu, memperbaiki kebijakan secara iteratif sesuai
algoritme yang ada hingga kebijakan tersebut tidak dapat diperbaiki, dengan kata
lain telah mencapai kondisi optimal.
Masalah keputusan Markov tahap takhingga dengan ataupun tanpa
menggunakan faktor diskonto dapat dirumuskan dan diselesaikan sebagai sebuah
pemrograman linear. Batasan atau kendala dari metode pemrograman linear
adalah peluang steady-state dari rantai Markov. Secara khusus, setiap kebijakan
dinyatakan sebagai kelompok tindakan yang tetap.
Penentuan kebijakan optimal di bidang manajemen pemasaran dan produksi
telah dijelaskan pada Hidayah (2013) dengan menggunakan algoritme
Discounted-Return Policy-Improvement.
Dalam karya ilmiah ini digunakan metode enumerasi lengkap, iterasi
kebijakan, formulasi pemrograman linear pada aplikasi di bidang pertanian. Setiap
tahap, di awal musim tanam, petani menggunakan pengujian kimia untuk
memeriksa kondisi tanah. Dari hasil pengujian tersebut, produktivitas sawah
untuk setiap musim dikelompokkan dalam beberapa kategori. Petani dapat
2
melakukan tindakan yaitu menggunakan pupuk untuk memperbaiki kondisi tanah.
Petani melihat bahwa produktivitas tahap yang akan datang dapat diasumsikan
hanya bergantung pada kondisi tanah sekarang dan memerlukan penentuan arah
tindakan terbaik yang harus dilakukan berdasarkan hasil dari pengujian kimia.
Proses optimisasi didasari oleh pemaksimuman keuntungan yang diperkirakan.
Proses keputusan Markov adalah salah satu cara yang cocok untuk menyelesaikan
masalah ini.
Tujuan
Tujuan karya ilmiah ini adalah
1 Merumuskan suatu model stokastik yang melibatkan state, tindakan, dan
reward.
2 Mengaplikasikan model tersebut dalam bidang pertanian, yaitu menentukan
keuntungan dengan memberikan beberapa alternatif tindakan.
3 Menentukan kebijakan optimal yaitu memaksimumkan keuntungan (reward).
TINJAUAN PUSTAKA
Proses keputusan Markov (Markov Decision Process/ MDP) awalnya
diperkenalkan oleh Andrey Markov, seorang matematikawan Rusia pada awal
abad ke-20 (Tijms 1994). Proses keputusan Markov berguna untuk mempelajari
berbagai masalah optimasi yang dipecahkan melalui dynamic programming.
Proses keputusan Markov adalah sebuah sistem yang dapat memindahkan satu
keadaan yang khusus ke keadaan lainnya yang mungkin. Proses keputusan
Markov pada dasarnya merupakan perluasan dari rantai Markov sehingga harus
memenuhi syarat Markov. Menurut Grimmet dan Stirzaker (1992) suatu proses S
disebut sebagai rantai Markov jika memenuhi syarat Markov, yaitu
P(St = s | S0 = s0, S1 = s1,…, St-1 = st-1)= P(St = s | St-1 = st-1).
Dalam proses keputusan Markov memungkinkan adanya pilihan tindakan
(action) yang menghasilkan keuntungan. Oleh karena itu, dapat dikatakan proses
keputusan Markov merupakan kerangka matematika untuk memodelkan
pembuatan keputusan di situasi yang hasilnya bersifat acak dan berada di bawah
kontrol dari pembuat keputusan. Proses keputusan Markov memiliki unsur-unsur
yaitu
1 State
State adalah suatu keadaan, akibat, atau kejadian (alamiah) pada suatu
waktu dimana pengambil keputusan hanya mempunyai sedikit kontrol atau
bahkan tidak memiliki kontrol terhadapnya. State dilambangkan i dengan i =
1, 2,…,m . Setiap i 𝜖 I dengan I himpunan state (Rosadi 2000).
2 Tindakan
Tindakan adalah suatu bagian dari aksi atau strategi yang mungkin
dipilih oleh pengambil keputusan di setiap state. Tindakan dilambangkan k
dengan k = 1, 2,..., K. Setiap k 𝜖 dengan himpunan tindakan (Rosadi
2000).
3
3 Probabilitas transisi
Menurut Taylor dan Karlin (1998), probabilitas transisi disebutkan
sebagai peluang n-step
, yaitu peluang bahwa suatu proses yang mula-
mula berada pada state i akan berada pada state j setelah n tambahan transisi.
Menurut Heymen dan Sobel (2004), probabilitas transisi adalah suatu
fungsi yang menyatakan peluang perpindahan dari suatu state ke state
lainnya. Probabilitas transisi pada proses keputusan Markov harus memenuhi
asumsi sifat Markov seperti yang dijelaskan sebelumnya yaitu ketika tindakan
diambil di state , maka state telah ditentukan dengan sebuah cara
yang hanya bergantung pada dan . Sehingga berlaku persamaan
P( ∈ I| , = P( ∈ I | =i, = k).
Notasi I melambangkan himpunan state dan menyatakan kejadian
lampau hingga waktu pengambilan keputusan ke-n diambil. Bentuk notasinya
sebagai berikut =( , , , , ..., , , ).
Pengambilan keputusan masa yang akan datang didasarkan pada
keadaan sekarang, bukan berdasarkan pada keadaan di masa lalu. Hal ini
dikarenakan keadaan di masa lalu dianggap bebas dengan keadaan di masa
yang akan datang. Dalam prosesnya, pembuat keputusan harus mengambil
suatu tindakan dari alternatif-alternatif yang ditetapkan. Tindakan sekarang
mempengaruhi peluang transisi pada perpindahan yang akan datang dan
mendatangkan sebuah keuntungan atau kerugian setelah itu. Nilai peluang
adalah tak negatif dan karena proses tersebut harus mengalami transisi ke
suatu state maka ≥ 0, untuk semua ∈ , ∑
= 1
untuk semua ∈ . Secara umum, probabilitas transisi tidak perlu
sama setiap tahap.
4 Reward transisi
Keuntungan yang diperoleh sebagai implikasi terjadinya transisi antar
state pada tindakan ke-k yang dilambangkan . Jika matriks probabilitas
transisi P berukuran dan elemen-elemennya , maka matriks reward
R juga berukuran dengan elemen-elemennya (Rosadi 2000).
Menurut Taha (1987), proses perhitungan reward dapat menggunakan faktor
diskonto maupun tanpa faktor diskonto.
5 Kebijakan optimal
Suatu kebijakan terbaik dari sekian banyak tindakan yang mungkin,
sebagai hasil menjalankan serangkaian proses pengambilan keputusan. Secara
matematis dinyatakan sebagai himpunan semua keputusan di setiap state yang
memberikan reward maksimal atau cost minimal (Rosadi 2000).
6 Ekspektasi reward
Ekspektasi reward adalah pengembalian yang diperkirakan dan
dihasilkan dari satu transisi pada keadaan i dengan tindakan k. Ekspektasi
reward dilambangkan dengan
∑
. Kebijakan optimal
adalah kebijakan yang menghasilkan keuntungan terbesar dilambangkan .
4
7 Aplikasi pada masalah manajerial
Solusi yang didapatkan oleh Hidayah (2013) pada masalah manajerial
dengan konsep proses keputusan Markov menggunakan algoritme Discounted-
Return Policy-Improvement memberikan keuntungan optimal.
Beberapa metode dalam proses keputusan Markov yaitu, enumerasi lengkap
(iterasi nilai), formulasi pemrograman linear, dan metode iterasi kebijakan (policy
iteration method). Dalam karya ilmiah ini metode yang digunakan adalah
enumerasi lengkap, policy iteration dengan algoritma perbaikan kebijakan, dan
formulasi pemrograman linear baik dengan maupun tanpa faktor diskonto. Faktor
diskonto adalah pengali untuk menghitung nilai uang yang akan datang bila dinilai
dalam waktu sekarang. Faktor diskonto yang digunakan dalam karya ilmiah ini
sebesar 0.7.
APLIKASI DI BIDANG PERTANIAN
Aplikasi Model Pemrograman Dinamis Tahap Terhingga
Penerapan pemrograman dinamis (DP) untuk pemecahan suatu proses
keputusan stokastik dapat dijabarkan oleh sejumlah state yang terhingga.
Probabilitas transisi antara state dijabarkan dengan sebuah rantai Markov.
Keuntungan (reward) dari proses ini juga dijabarkan oleh sebuah matriks dengan
elemen-elemen individual yang merepresentasikan keuntungan atau biaya yang
dihasilkan oleh pergerakan dari satu state ke state lainnya.
Setiap tahap, di awal musim tanam, petani menggunakan pengujian kimia
untuk memeriksa kondisi tanah. Dari hasil pengujian tersebut, produktivitas
sawah untuk setiap musim dikelompokkan dengan kategori baik (state 1), sedang
(state 2), dan buruk (state 3). Selama beberapa tahap, petani hanya melihat bahwa
produktivitas tahap yang akan datang dapat diasumsikan hanya bergantung pada
kondisi tanah sekarang.
Probabilitas transisi dalam 1 tahap dari satu state produktivitas ke state
lainnya dengan tindakan tanpa menggunakan pupuk dapat dipresentasikan dalam
bentuk rantai Markov berikut
State yang akan datang
State sekarang (
).
Jika petani melakukan tindakan yaitu menggunakan pupuk untuk memperbaiki
kondisi tanah, yang menghasilkan matriks transisi
(
).
Untuk setiap tindakan yang diambil petani tersebut terdapat pengembalian
keuntungan (reward) dengan transisi dari satu state ke state lainnya.
5
Pengembalian tersebut adalah keuntungan atau kerugian dalam periode 1 tahap,
bergantung pada state yang terjadi dalam transisi.
Matriks dan adalah fungsi pengembalian dalam jutaan rupiah yang
berkaitan dengan matriks dan secara berturut-turut.
(
) (
).
Jika petani menggunakan pupuk hanya saat kondisi tanah buruk (state 3)
atau tindakan 3. Kebijakan yang menyatakan penggunaan pupuk hanya ketika
kondisi tanah buruk, matriks transisi dan matriks reward yang dihasilkan, P dan R
adalah
(
) (
).
Petani merencanakan untuk “Berhenti bekerja” setelah N tahap, sehingga
optimisasinya adalah akumulasi keuntungan tertinggi yang diperoleh petani di
akhir N tahap. Tindakan yang tersedia bagi petani k = 1 dan k = 2 dengan
adalah probabilitas transisi untuk tindakan k dan adalah fungsi pengembalian
untuk tindakan k. Jumlah state untuk setiap tahap adalah m = 3 dan definisikan
adalah keuntungan optimal yang diperkirakan untuk tahap n, dengan
diketahui kondisi tanah di awal tahap n adalah i. Persamaan rekursif mundur yang
mengaitkan dan dapat ditulis
Persamaan ini menyatakan bahwa keuntungan kumulatif, ,
yang dihasilkan dari tercapainya state j di tahap dari state i di tahap n
terjadi dengan probabilitas . Jika
mewakili pengembalian yang
diperkirakan dan dihasilkan dari satu transisi dari state i dengan diketahui
tindakan k, maka dapat ditulis sebagai
∑
.
Persamaan rekursif pemograman dinamik dapat ditulis sebagai
{ ∑
}
Berikut perhitungan untuk mengevaluasi tindakan 1 (tanpa menggunakan pupuk)
dan tindakan 2 (menggunakan pupuk)
= 0.1(7) + 0.5(6) + 0.4(3) = 4.9
= 0 + 0.4(5) + 0.6(1) = 2.6
= 0 + 0 + 1( 1) = 1
= 0.2(6) + 0.6(4) + 0.2( 1) = 3.4
= 0.1(7) + 0.6(4) + 0.3(0) = 3.1
= 0.05(6)+ 0.45(3) + 0.5( 2) = 0.65
𝑓𝑛 𝑖 𝑘 ∑ 𝑝𝑖𝑗𝑘 𝑟𝑖𝑗
𝑘 𝑓𝑛 𝑗 𝑚𝑗 𝑛 𝑁 dengan 𝑓𝑁 𝑗 = 0.
6
Jika kondisi tanah baik (state 1) dengan tindakan tanpa menggunakan pupuk di
awal tahap, satu transisi diperkirakan menghasilkan reward 4.9, sedangkan jika
petani menggunakan pupuk maka akan menghasilkan reward 3.4.
Tabel 1 Nilai-nilai
Tahap 3 (n = 3)
Tabel 2 Hasil perhitungan pada n = 3
State Kebijakan optimal
i k = 1 k = 2
1 4.9 3.4 4.9 1
2 2.6 3.1 3.1 2
3 1.0 0.65 0.65 2
adalah kebijakan optimal pada saat kondisi tanah ke i.
Tahap 2 (n = 2)
Tabel 3 Hasil perhitungan pada n = 2
Tahap 1 (n = 1)
Tabel 4 Hasil perhitungan pada n = 1
i
Kebijakan optimal
k = 1 k = 2
1
4.9+0.1(7.2)+0.5(5.645) +
0.4(2.615)=9.4885
3.4+0.2(7.2)+0.6(5.645)+
0.2(2.615)=8.75 9.489 1
2 2.6+0(7.2)+0.4(5.645)+
0.6(2.615)=6.427
3.1+0.1(7.2)+0.6(5.645)+
0.3(2.615)=7.992 7.992 2
3 1+0(7.2)+0(5.645)+
1(2.615)=1.615
0.65+0.05(7.2)+
0.45(5.645)+ 0.5(2.62)=4.86 4.86 2
i
1 4.9 3.4
2 2.6 3.1
3 1.0 0.65
i
Kebijakan optimal
k = 1 k = 2
1 4.9+0.1(4.9)+0.5(3.1)+
0.4(0.65)=7.2
3.4+0.2(4.9)+0.6(3.1)+
0.2(0.65)=6.37 7.2 1
2 2.6+0(4.9)+0.4(3.1)+
0.6(0.65)=4.23
3.1 +0.1(4.9)+0.6(3.1)+
0.3(0.65)=5.645 5.645 2
3 1+0(4.9)+0(3.1)+ 1(0.65)
= 0.35
0.65+0.05(4.9)+
0.45(3.1)+0.5(0.65) =2.615 2.615 2
7
Kebijakan optimal dari masalah ini adalah setiap tahap petani sebaiknya tidak
menggunakan pupuk ( = 1) saat tanah dalam state baik (state) 1, tetapi
menggunakan pupuk saat tanah dalam state sedang atau buruk (state 2 atau 3).
Reward (keuntungan) yang diperkirakan untuk tiga tahap adalah = 9.489 jika state tanah dalam tahap 1 baik, = 7.992 jika sedang, dan
= 4.86 jika buruk.
Selanjutnya untuk mengevaluasi tindakan 3 yang menyatakan penggunaan
pupuk hanya saat kondisi tanah buruk (state 3)
(
) (
).
= 0.1(7) + 0.5(6) + 0.4(3) = 4.9
= 0 + 0.4(5) + 0.6(1) = 2.6
= 0.05(6) + 0.45(3) + 0.5( 2) = 0.65.
Tabel 5 Nilai-nilai
i 3
1 4.9 6.95 8.566
2 2.6 4.03 5.646
3 0.65 2.39 4.006
= 4.9; = 2.6; = 0.65
= 4.9 + 0.1(4.9) + 0.5(2.6) + 0.4 (0.65) = 6.95
= 2.6 + 0(4.9) + 0.4(2.6) + 0.6 (0.65) = 4.03
= 0.65 + 0.05 (4.9) + 0.45(2.6) + 0.5(0.65) = 2.39
= 4.9 + 0.1 (6.95) + 0.5(4.03) + 0.4(2.39) = 8.566
= 2.6 + 0 (6.95) + 0.4(4.03) + 0.6(2.39) = 5.646
= 0.65 + 0.05(6.95) + 0.45 (4.03) + 0.5(2.39) = 4.006
Reward yang diperkirakan untuk tiga tahap dengan tindakan menggunakan pupuk
saat state buruk adalah 8.566 jika tanah dalam tahap 1 baik, = 5.646
jika sedang, dan 4.006 jika buruk. Dari perhitungan ini, dapat
disimpulkan bahwa akan lebih menguntungkan jika menggunakan pupuk saat
kondisi tanah sedang dan buruh dibandingkan hanya menggunakan pupuk saat
kondisi tanah buruk saja.
Aplikasi Model Pemrograman Dinamis Tahap Takhingga
Evaluasi penentuan kebijakan jangka panjang model tahap takhingga dari
sebuah masalah keputusan Markov didasarkan dari sebuah kebijakan berdasarkan
pemaksimuman keuntungan yang diperkirakan per periode transisi. Dalam
masalah pertanian, pemilihan kebijakan terbaik untuk tahap takhingga didasari
oleh keuntungan maksimum yang diperkirakan per tahap.
Terdapat tiga metode untuk memecahkan permasalahan model tahap
takhingga yaitu
1 Enumerasi (pendaftaran) lengkap, dengan cara mengevaluasi setiap kebijakan
maka kebijakan optimal dapat ditentukan. Metode ini dapat digunakan jika
kebijakan sedikit.
8
2 Iterasi kebijakan, yaitu menentukan kebijakan optimal dengan beberapa
iterasi.
3 Penyelesain pemrograman linear, yaitu merubah kondisi rantai Markov dalam
bentuk kendala linear. Formulasi LP cukup menarik, tetapi tidak efisien secara
perhitungan jika dibandingkan dengan algoritma iterasi kebijakan. Untuk
permasalahan dengan K tindakan dan state, model LP akam memiliki
( ) kendala dan variabel
Metode Enumerasi Lengkap
Misalkan masalah keputusan ini memiliki S kebijakan, dan adalah
matriks transisi dan matriks keuntungan yang berkaitan dengan kebijakan ke- ,
1, 2, …, S. Langkah-langkah dari enumerasi sebagai berikut
1 Hitung keuntungan satu langkah (satu periode) yang diperkirakan dari
kebijakan k dengan diketahui state ke-i, i = 1, 2, …, m.
2 Hitung , probabilitas jangka panjang dari matriks transisi yang
berkaitan dengan kebijakan k. Probabilitas dihitung dari persamaan
dengan
dan
3 Tentukan keuntungan yang diperkirakan dari kebijakan k per periode,
dengan menggunakan rumus ∑
4 Tentukan kebijakan optimal sehingga menghasilkan keuntungan yang
maksimum atau biaya yang minimum (Taha 1987).
Masalah Petani dengan Tahap Perencanaan Periode Takhingga
Tabel 6 Kebijakan yang terjadi
Kebijakan Tindakan
1 Tidak menggunakan pupuk
2 Menggunakan pupuk tanpa bergantung pada state
3 Menggunakan pupuk ketika state 3
4 Menggunakan pupuk ketika state 2
5 Menggunakan pupuk ketika state 1
6 Menggunakan pupuk ketika state 1 atau 2
7 Menggunakan pupuk ketika state 1 atau 3
8 Menggunakan pupuk ketika state 2 atau 3
Matriks dan untuk kebijakan 3 sampai 8 didapatkan dari matriks
untuk kebijakan 1 dan 2.
9
(
) (
)
(
) (
)
(
) (
)
(
) (
)
(
) (
)
(
) (
)
(
) (
)
(
) (
)
Tabel 7 Nilai-nilai setiap state
Kebijakan State
i = 1 i = 2 i = 3
1 4.9 2.6 1
2 3.4 3.1 0.65
3 4.9 2.6 0.65
4 4.9 3.1 1
5 3.4 2.6 1
6 3.4 3.1 1
7 3.4 2.6 0.65
8 4.9 3.1 0.65
10
Perhitungan dari probabilitas tersebut dicapai dengan menggunakan persamaan
Sebagai ilustrasi, saat = 2. Persamaannya adalah
0.2 + 0.1 + 0.05 =
0.6 + 0.6 + 0.45 =
0.2 + 0.3 + 0.5 =
+ +
maka didapatkan =
, =
, =
. Keuntungan yang diperoleh per
tahap adalah ∑
= 1
11[ 1(3.4) 6(3.1) 4( .65 ]= 2.236. Hasil
perhitungan lainnya disajikan dalam Tabel 8 (proses perhitungan terdapat pada
Lampiran 1).
Tabel 8 Nilai dan semua kebijakan
Tabel ini menunjukkan bahwa kebijakan 8 menghasilkan keuntungan per tahap
yang diperkirakan terbesar. Akibatnya, kebijakan jangka panjang yang optimal
adalah dengan menggunaan pupuk saat tanah dalam kondisi sedang atau buruk.
Jika metode enumerasi lengkap diterapkan untuk masalah petani dengan 4
arah tindakan yaitu tidak menggunakan pupuk, menggunakan pupuk satu kali
selama musim tersebut, menggunakan pupuk dua kali, dan menggunakan pupuk
tiga kali, maka petani secara keseluruhan memiliki 43 = 256 kebijakan. Mencari
solusi optimal dengan metode enumerasi dari semua kebijakan secara eksplisit
sulit dan jumlah perhitungan yang terlibat dalam evaluasi kebijakan sangat besar.
Untuk mengatasi hal ini maka dikembangkan metode iterasi kebijakan.
Metode Iterasi Kebijakan
Pengembalian total yang diperkirakan di tahap dinyatakan dengan
persamaan rekursif
∑ .
1 0 0 1 1
2 1/11 6/11 4/11 2.236
3 3/100 43/100 54/100 1.616
4 0 0 1 1
5 0 0 0 1
6 0 0 1 1
7 1/30 13/30 16/30 1.587
8 13/161 86/161 62/161 2.302
11
Persamaan rekursif ini adalah dasar untuk pengembangan metode iterasi
kebijakan. Untuk melihat asimtot, persamaan ini harus dimodifikasi terlebih
dahulu. Misalkan sebagai jumlah tahap yang tersisa untuk dipertimbangkan,
) adalah keuntungan kumulatif yang diperkirakan dan berbeda dengan
dalam persamaan di atas, yang mendefinisikan tahap ke- . Jadi, persamaan
rekursif dapat ditulis
∑ .
Dengan definisi baru, perilaku asimtot dapat diketahui dengan menganggap
→∞. Vektor = ( , adalah probabilitas steady-state dari matriks
transisi = dan = +... + adalah keuntungan yang
diperkirakan per tahap.
Untuk yang sangat besar, dengan adalah konstanta
yang mewakili titik potong asimtot dari Nilai adalah pengembalian
optimal kumulatif untuk tahap pada state i dan E adalah pengembalian yang
diperkirakan per tahap, maka sama dengan ditambah faktor koreksi yang memperhitungkan state i. Hasil ini mengasumsikan bahwa sangat besar.
Dengan demikian, persamaan rekursif dapat ditulis sebagai
∑
Secara sedehana persamaan rekursif dapat ditulis sebagai
E ∑
yang menghasilkan persamaan dan variabel yang tidak diketahui,
dengan dan adalah variabel yang tidak diketahui.
Nilai E yang optimal tidak dapat ditentukan dalam satu langkah, karena
terdapat persamaan dengan variabel yang tidak diketahui. Oleh karena
itu, suatu pendekatan iteratif merupakan salah satu cara mendapatkan nilai E
optimal. Pendekatan iteratif diawali dengan mengambil satu kebijakan secara
sembarang, kemudian menentukan suatu kebijakan baru yang menghasilkan nilai
E yang lebih baik. Proses iteratif berhenti jika ada dua kebijakan yang berturut-
turut identik. Proses iteratif ini terdiri dari dua komponen dasar yaitu penentuan
nilai (value determination) dan perbaikan kebijakan (policy improvement).
1 Penentuan nilai
Pilih satu kebijakan k secara sembarang. Gunakan matriks dan
yang berkaitan dan asumsikan bahwa = 0,
∑
dengan variabel yang tidak diketahui , ,…, dan
. Iterasi
dilanjutkan ke tahap perbaikan kebijakan.
2 Langkah perbaikan kebijakan
Untuk setiap state i, tentukan tindakan k yang menghasilkan
{ ∑
}
12
Nilai-nilai , = , adalah nilai-nilai yang ditentukan dalam
langkah penentuan nilai.
Kebijakan untuk state membentuk kebijakan baru . Jika
dan adalah identik, maka iterasi berhenti dan adalah optimal. Jika tidak
identik, tetapkan dan kembali ke langkah penentuan nilai. Persamaan
∑ tidak bergantung pada tindakan pemaksimuman
di semua tindakan setara dengan masalah pemaksimuman dalam langkah
perbaikan kebijakan (Taha 1987).
Metode Iterasi Kebijakan tanpa Diskonto
Iterasi 1
Dengan mengambil kebijakan sembarang yang menyatakan tidak
menggunakan pupuk maka
(
) (
).
Persamaan dalam langkah iterasi nilai adalah
.
Dengan menganggap , maka solusinya , ,
(proses perhitungan terdapat pada Lampiran 2).
Tabel 9 Hasil iterasi kebijakan tanpa diskonto pada iterasi pertama
Kebijakan
optimal Tindakan
i = 1
1 4.9+0.1(9.89)+0.5(6)+0.4(0) =
8.889
3.4+0.2(9.89)+0.6(6)+0.2(0)
= 8.978 8.978 2
2 2.6+0(9.89)+0.4(6)+ 0.6(0) = 5 3.1+0.1(9.89)+0.6(6)+0.3(0)
= 7.689 7.689 2
3 1.0+0(9.89)+0(6)+1(0) = 1 0.65+0.05(9.89)+0.45(6)+
0.5(0) = 3.845 3.845 2
Kebijakan baru ini menyatakan penggunaan pupuk tidak bergantung pada state.
Kebijakan baru ini berbeda dari kebijakan sebelumnya, maka langkah penentuan
nilai dilakukan kembali.
Iterasi 2
Persamaan-persamaan dari kebijakan sebelumnya
Dengan solusi persamaan (proses
perhitungan terdapat pada Lampiran 2).
13
Tabel 10 Hasil iterasi kebijakan tanpa diskonto pada iterasi kedua
Kebijakan
optimal Tindakan
i = 1
1 4.9+0.1(3.78)+0.5(3.105)+
0.4(0) = 6.83
3.4+0.2(3.78)+0.6(3.105)+
0.2(0) = 6.019 6.83 1
2 2.6+0(3.78)+0.4(3.105)+
0.6(0) = 3.842
3.1+0.1(3.78)+0.6(3.105)+
0.3(0) = 5.34 5.34 2
3 1.0+0(3.78)+0(3.105)+1(0) =
1
0.65+0.05(3.78)+
0.45(3.105)+0.5(0)=2.24 2.24 2
Kebijakan baru menyatakan penggunaan pupuk tidak bergantung pada state saat
kondisi tanah dalam state sedang atau buruk (state 2 atau 3) dan tidak
menggunakan pupuk saat kondisi tanah baik. Kebijakan berbeda dengan kebijakan
pada iterasi 1, maka iterasi dilanjutkan.
Iterasi 3
Persamaan-persamaan dari kebijakan sebelumnya {1,2,2} yaitu
.
Dengan solusi persamaan (proses
perhitungan terdapat pada Lampiran 2).
Tabel 11 Hasil iterasi kebijakan tanpa diskonto pada iterasi ketiga
Kebijakan
optimal Tindakan
i = 1
1 4.9+0.1(4.64)+0.5(3.155)+
0.4(0) = 6.94
3.4+0.2(4.64)+0.6(3.155)+
0.2(0) = 6.221 6.94 1
2 2.6+0(4.64)+0.4(3.155)+
0.6(0) = 3.862
3.1+0.1(4.64)+0.6(3.155)+
0.3(0) = 5.46 5.46 2
3 1.0+0(4.64)+0(3.155)+1(0) =
1
0.65+0.05(4.64)+
0.45(3.155)+ 0.5(0) = 2.3 2.3 2
Kebijakan baru menyatakan penggunaan pupuk tidak bergantung pada state saat
kondisi tanah dalam state sedang atau buruk (state 2 atau 3) dan tidak
menggunakan pupuk saat kondisi tanah baik. Kebijakan ini sama dengan
sebelumnya maka proses iteratif berhenti. Jadi kebijakan optimal dengan metode
iterasi kebijakan sama dengan kebijakan yang diperoleh dengan metode enumerasi
lengkap.
Metode Iterasi Kebijakan dengan Diskonto
Dengan α < 1 adalah faktor diskonto, persamaan rekursif tahap terhingga
dapat ditulis sebagai
14
{ ∑
}
Dapat dibuktikan bahwa untuk →∞ (tahap takhingga), , dengan
adalah nilai sekarang (yang didiskonto) dari keuntungan yang diperkirakan
ketika sistem berada dalam state ke- dan berjalan dalam tahap waktu yang
takhingga.
Hal ini berlawanan dengan kasus tanpa diskonto, dimana . Dalam kasus diskonto, pengaruh keuntungan masa mendatang akan menurun
menjadi nol. Jadi pada kenyataannya, nilai sekarang akan mendekati nilai
konstan saat →∞.
Langkah kebijakan iterasi dengan diskonto dimodifikasi sebagai berikut
1 Langkah penentuan nilai. Untuk sebuah kebijakan sembarang k dengan
matriks dan , ∑
.
2 Langkah perbaikan kebijakan. Untuk setiap tahap i, tentukan tindakan k yang
menghasilkan
{ ∑
}
dengan adalah nilai-nilai yang diperoleh dari langkah penentuan nilai. Jika
kebijakan yang dihasilkan s sama dengan k, maka iterasi berhenti. Jadi adalah
kebijakan optimal. Jika tidak sama, tetapkan s = k dan kembali ke langkah
penentuan nilai (Taha 1987).
Dalam kasus yang sama, dengan faktor diskonto α = 0.7.
Iterasi 1
Misalkan kebijakan awal k = {1,1,1}. Matriks P dan R menghasilkan
persamaan
[ ] [ ]
[ ]
didapatkan solusinya (proses perhitungan
terdapat pada Lampiran 3).
Tabel 12 Hasil iterasi kebijakan dengan diskonto iterasi pertama
[ ]
Kebijakan
optimal Tindakan
i = 1 k = 2
1 4.9+0.7[0.1(4.89)+0.5(1.67)+
0.4( 3.33)] = 4.89
3.4+ 0.7[0.2(4.89)+0.6(1.67)
+0.2( 3.33)] = 4.32 4.89 1
2 2.6+0.7[0(4.89) + 0.4(1.67)+
0.6( 3.33)] = 1.67
3.1+0.7[0.1(4.89)+0.6(1.67)+
0.3( 3.33)] = 3.44 3.44 2
3 1.0 + 0.7[0(4.89) + 0(1.67)
+1( 3.33)] = 3.33
0.65+0.7[0.05(4.89)+
0.45(1.67)+ 0.5( 3.33)]=0.18 0.18 2
15
Kebijakan baru yang didapat adalah {1,2,2} berbeda dengan kebijakan awal
{1,1,1}, maka iterasi dilanjutkan.
Iterasi 2
Langkah penentuan nilai dari kebijakan {1,2,2} menghasilkan persamaan-
persamaan
[ ] [ ]
[ ]
didapatkan solusinya (proses perhitungan
terdapat pada Lampiran 3).
Tabel 13 Hasil iterasi kebijakan dengan diskonto iterasi kedua
[ ]
Kebijakan
optimal
Tindakan
i = 1 k = 2
1 4.9+0.7[0.1(10.26)+0.5(8.67)+
0.4(5.75)] = 10.26
3.4+0.7[0.2(10.26)+0.6(8.67)
+0.2(5.75)] = 9.28 10.26 1
2 2.6+0.7[0(10.26) + 0.4(8.67)+
0.6(5.75)] = 7.44
3.1+0.7[0.1(10.26)+0.6(8.67)
+0.3(5.75)] = 8.67 8.67 2
3 1.0 +0.7[0(10.26) + 0(8.67) +
1(5.75)] = 3.025
0.65+0.7[0.05(10.26)+
0.45(8.67)+ 0.5(5.75)] = 5.75 5.75 2
Kebijakan baru {1,2,2} identik dengan kebijakan sebelumnya {1,2,2} maka iterasi
berhenti. Oleh karena itu kebijakan ini optimal. Kebijakan diskonto menghasilkan
kebijakan optimal yang sama dengan kebijakan tanpa diskonto, tetapi ini tidak
berlaku secara umum.
Penyelesaian Pemrograman Linear untuk Masalah Keputusan Markov
Masalah keputusan Markov tahap takhingga, dengan ataupun tanpa
menggunakan faktor diskonto, dapat dirumuskan dan diselesaikan sebagai sebuah
pemrograman linear.
Masalah Keputusan Markov tanpa Diskonto
Masalah keputusan Markov tahap takhingga tanpa diskonto pada akhirnya
menyempit menjadi masalah penentuan kebijakan optimal , yang bersesuaian
dengan
∑
dan adalah kumpulan dari semua kebijakan yang mungkin terjadi. Batasan dari
masalah ini adalah , mewakili probabilitas steady-state dari
16
rantai Markov . Secara spesifik, setiap kebijakan k dinyatakan dengan
sekelompok tindakan.
Jadi, masalah ini dapat diekspresikan sebagai
E =∑ (∑
)
dengan kendala
∑
dan k
dengan adalah probabilitas kondisional dari memilih tindakan k dengan
sistem berada dalam state i dan adalah fungsi dari kebijakan yang dipilih, oleh
karena itu merupakan fungsi dari tindakan spesifik k dari kebijakan tersebut.
Didefinisikan
, untuk semua i dan k. Berdasarkan definisinya,
mewakili probabilitas gabungan dalam state i dan membuat keputusan k. Dari
teori probabilitas ∑
maka
∑
. Jadi kendala ∑
dapat ditulis sebagai ∑ ∑
dan kendala batasan ∑
dalam bentuk . Jadi masalah ini dapat ditulis sebagai
∑∑
dengan kendala
∑
∑ ∑
∑∑
Model yang dihasilkan ini merupakan sebuah pemrograman linear dalam
Solusi optimalnya secara otomatis menjadi
untuk satu k untuk
setiap i. Pemrograman linear ini memiliki persamaan bebas. Oleh karena itu,
masalah ini harus memiliki variabel dasar. Nilai harus positif untuk paling
sedikit satu k untuk setiap i. Dari kedua hasil ini, dapat disimpulkan bahwa
∑
hanya dapat memiliki nilai biner (0 atau 1), seperti yang
diharapkan. Dapat dilihat bahwa adalah tindakan yang bersesuaian dengan
Formulasi LP untuk masalah petani tanpa diskonto
maksimumkan
dengan kendala
17
, untuk semua i dan k.
Solusi optimalnya adalah
dan
13/161,
86 161, dan = 62/161. Hasil ini berarti bahwa
. Jadi,
kebijakan optimalnya yaitu melakukan tindakan 1 (tidak memberi bubuk saat
kondisi tanah baik) dan melakukan tindakan 2 (memberi pupuk) i = 2 dan 3. Nilai
optimal dari E adalah 2.3018.
Nilai-nilai dari sama dengan nilai-nilai yang berkaitan dengan
kebijakan optimal (kebijakan 8) dalam metode enumerasi lengkap. Hal ini
menunjukkan adanya hubungan langsung antara metode enumerasi lengkap dan
pemrograman linear.
Masalah Keputusan Markov dengan Diskonto
Masalah ini diekspresikan dengan persamaan rekursif
{ ∑
}
Persamaan ini setara dengan ∑
dengan ketentuan
bahwa mencapai nilai minimum untuk setiap i dan fungsi tujuan ∑
dengan adalah konstanta sembarang. Jadi masalah ini dapat ditulis sebagai
∑
dengan kendala
∑
dan k
tidak terbatas, i = 1, 2, …, m.
Masalah dual dari masalah ini adalah
∑∑
dengan kendala
∑
∑
, untuk i = 1, 2, …, m; k = 1,2, …, K (Taha 1987).
Fungsi tujuan memiliki bentuk yang sama seperti kasus tanpa diskonto, sehingga
dapat diinterpretasikan dengan cara yang sama.
Pada permasalahan yang sama dan faktor diskonto α = 0.7, misalkan
, masalah dual dari LP ini dapat ditulis sebagai
maksimumkan
dengan kendala
18
(
)
, untuk semua i dan k.
Solusi optimalnya adalah
. Solusi ini memperlihatkan bahwa kebijakan optimal
adalah {1,2,2}. Nilai optimal dari E adalah 24.6805.
SIMPULAN DAN SARAN
Simpulan
Sebuah permasalahan untuk menduga state di masa mendatang yang
diasumsikan hanya bergantung pada state sekarang seperti kasus dalam karya
ilmiah ini dapat dirumuskan dalam suatu model stokastik dengan mendifinisikan
state, tindakan dan reward.
Untuk aplikasi di bidang pertanian, reward diasumsikan berasal dari
keuntungan dan diasumsikan biaya pemeriksaan kondisi tanah setiap tahap tidak
ada. Model stokastik tersebut dapat digunakan untuk menentukan keuntungan
(reward) optimal, sehingga dengan keuntungan yang optimal ini petani dapat
mengambil tindakan yang seharusnya dilakukan.
Proses keputusan Markov adalah model matematika yang bisa digunakan
untuk menyelesaikan penentuan pengambilan keputusan seperti kasus dalam
penentuan tindakan di bidang pertanian ini. Tindakan yang bisa dilakukan dalam
kasus ini adalah memberikan pupuk dan tidak memberikan pupuk. Adanya faktor
diskonto dapat menghasilkan perubahan dalam kebijakan optimal, dibandingkan
dengan kasus tanpa diskonto, tetapi dalam kasus ini faktor diskonto tidak
mempengaruhi kebijakan optimal.
Saran
Penulisan karya ilmiah ini menggunakan faktor diskonto hipotetik dan data
yang digunakan sederhana maka karya ilmiah ini dapat dikembangkan dengan
menyesuaikan antara data dengan faktor diskonto yang berlaku saat itu.
DAFTAR PUSTAKA
Grimmet GR, Stirzaker DR. 1992. Probability and Random Processes. Ed ke-2.
Oxford (GB): Clarendon Press.
Heymen DP, Sobel MJ. 2004. Stochastic Models in Operation Research. Volume
ke-2. New York (US): Publications.inc.Mineola.
Hidayah N. 2013. Penyelesain Masalah Manajerial dengan Metode Iterasi
Kebijakan pada Discounted Markov Decision Processes [skripsi]. Bogor:
Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam,
Institut Pertanian Bogor.
19
Rosadi D. 2000. Pengambilan Keputusan Markov dan Aplikasinya di Bidang
Periklanan. Integral. 5(2): 75-82.
Taha HA. 2011. Operations Research An Introduction. Volume ke-9. New York
(US): Macmillan Publishing Company.
Taylor HM, Karlin S. 1998. An Introduction to Stochastic Modeling. Ed ke-3. San
Diego (US): Academic Press.
Tijms HC. 1994. Stochastic Models: An Algorithmic Approach. Amsterdam (NL):
John Wiley and Sons.
20
Lampiran 1 Keuntungan per tahap kebijakan tahap takhingga
=1
0.1 =
0.5 + 0.4 =
0.4 + 0.6 + =
+ +
maka solusi dari persamaan ini adalah = = 0. Keuntungan yang
diperoleh per tahap ∑
= 0(4.9) + 0(2.6) + 1( 1) = 1.
=2
0.2 + 0.1 + 0.05 =
0.6 + 0.6 + 0.45 =
0.2 + 0.3 + 0.5 =
+ +
maka solusi dari persamaan ini adalah =
, =
, =
. Keuntungan yang
diperoleh per tahap adalah = 1
11[ 1(3.4) 6(3.1) 4( .65 ] = 2.236
= 3
0.1 + 0.05 =
0.5 + 0.4 + 0.45 =
0.4 + 0.6 + 0.5 =
+ +
maka solusi dari persamaan ini adalah =
, =
, =
. Keuntungan
yang diperoleh per tahap = 1
1 [3(4.9) + 43(2.6) + 54(0.65)]=1.616.
= 4
0.1 + 0.1 =
0.5 + 0.6 =
0.4 + 0.3 + =
+ +
maka solusi dari persamaan ini adalah = 0, = 0, = 1. Keuntungan yang
diperoleh per tahap = 0(4.9) + 0(3.1) + 1( 1) = 1.
= 5
0.2 =
0.6 + 0.4 =
0.2 + 0.6 + =
+ +
maka solusi dari persamaan ini adalah = 0, = 0, = 1. Keuntungan yang
diperoleh per tahap = 0(3.4) + 0(2.6) + 1( 1) = 1.
= 6
0.2 + 0.1 =
0.6 + 0.6 =
0.2 + 0.3 + =
21
+ +
maka solusi dari persamaan ini adalah = 0, = 0, = 1. Keuntungan yang
diperoleh per tahap = 0(3.4) + 0(3.1) + 1( 1) = 1.
= 7
0.2 + 0.05 =
0.6 + 0.4 + 0.45 =
0.2 + 0.6 + 0.5 =
+ +
maka solusi dari persamaan ini adalah =
, =
, =
. Keuntungan yang
diperoleh per tahap = 1
3 [1(3.4) + 13(2.6) + 16(0.65)]=1.587.
= 8
0.1 + 0.1 + 0.05 =
0.5 + 0.6 + 0.45 =
0.4 + 0.3 + 0.5 =
+ +
maka solusi dari persamaan ini adalah =
, =
, =
. Keuntungan
yang diperoleh per tahap = 1
161[13(4.9) + 86(3.1) + 62(0.65)] =2.30.
22
Lampiran 2 Proses perhitungan pada metode iterasi kebijakan tanpa diskonto
Iterasi pertama
(1)
(2) (3)
Dengan menganggap =0, maka dari persamaan (3) diperoleh E = 1.
Subtitusi ke persamaan (2) yaitu 1 + 0.6 = 2.6, maka = 6.
Subtitusi ke persamaan (1) yaitu 1 + 0.9 0.5(6) = 4.9, maka = 9.89.
Iterasi kedua
Dengan menganggap = 0, maka persamaan berubah menjadi
(4)
(5)
(6)
Eliminasi persamaan (4) dan (5)
(7)
Eliminasi persamaan (5) dan (6)
(8)
Eliminasi persamaan (7) dan (8)
0.85
1
+
sehingga dengan subtitusi diperoleh .
Iterasi ketiga
Proses perhitungan sama dengan proses pada iterasi 2. Hasil perhitungannya yaitu .
23
Lampiran 3 Proses perhitungan pada metode iterasi kebijakan dengan diskonto
Iterasi pertama
[ ] (9) [ ] (10)
[ ] (11)
Dari persamaan (11) didapat 0.3 = , maka .
Subtitusi ke persamaan (10) yaitu 0.72 0.42( 3.33) = 2.6 maka .
Subtitusi ke persamaan (9) yaitu 0.93 ,
maka .
Iterasi kedua
[ ]
0.93 (12)
[ ]
0.07 (13)
[ ]
0.035 (14)
Eliminasi persamaan (12) dan (13)
0.93 0.07
0.07 0.93
0.0651
0.0651 + 0.5394 0.1953 = 2.883 +
0.5149 (15)
Eliminasi persamaan (13) dan (14)
0.07 0.5
0.035 1
0.035
0.035
0.605 (16)
Eliminasi persamaan (15) dan (16)
0.5149 0.605
0.605 0.5149
0.31
0.31
0.259 = 1.48832
= 8.67
sehingga dengan subtitusi diperoleh =1 .26, = 5.75.
24
RIWAYAT HIDUP
Penulis dilahirkan di Belitung Timur pada tanggal 31 Oktober 1992 dari
ayah Rinto dan ibu Khusaenah. Penulis adalah putri kedua dari dua bersaudara.
Tahun 2010 penulis lulus dari SMA Negeri 1 Kelapa Kampit dan pada tahun yang
sama penulis lulus seleksi masuk Institut Pertanian Bogor (IPB) melalui jalur
Beasiswa Utusan Daerah IPB dan diterima di Departemen Matematika, Fakultas
Matematika dan Ilmu Pengetahuan Alam.
Selama mengikuti perkuliahan, penulis aktif mengajar mata kuliah Landasan
Matematika, Pengantar Matematika dan Kalkulus di bimbingan belajar dan privat
mahasiswa GUMATIKA dan MAFIA CLUBS . Penulis pernah menjadi asisiten
mata kuliah Persamaan Diferensial Parsial, Pemograman Tak Linear dan Proses
Stokastik Dasar. Penulis juga pernah aktif sebagai staf divisi keilmuan
GUMATIKA selama dua periode kepengurusan.