Proses Keputusan Markovian
1
Pengantar • Proses keputusan Markovian adalah proses keputusan stokastik/probabilistik dimana banyaknya state adalah hingga (finit). • Melibatkan dua buah matriks: matriks transisi (P) dan reward (R) (revenue/cost) bergantung kepada alternatif keputusan yang tersedia. • Tujuannya adalah menentukan kebijakan optimal yang memaksimumkan revenue yang diharapkan atas sejumlah hingga atau takhingga tahapan (stage).
2
The Gardener Problem • Produktivitas (P1) dan fungsi return (R1) tanah tanpa ferlitizer: (1) good, (2) fair, dan (3) poor untuk tahun sekarang dan berikutnya adalah sbb: 1
2
3
1
.2
.5
.3
2
0
.5
3
0
0
1
2
3
1
7
6
3
.5
2
0
5
1
1
3
0
0
-1
3
• Produktivitas (P2) dan fungsi return (R2) tanah dengan ferlitizer: (1) good, (2) fair, dan (3) poor untuk tahun sekarang dan tahun berikutnya adalah sbb: 1
2
3
1
6
5
-1
.3
2
7
4
0
.55
3
6
3
-2
1
2
3
1
.3
.6
.1
2
.1
.6
3
.05
.4
4
• Apa keputusan yang akan diambil ? – Bila aktivitas akan berlanjut dalam waktu yang terhingga / terbatas (finite): Model tahapan terbatas (finite-stage). – Bila aktivitas akan berlanjut dalam waktu yang takterhinnga / takterbatas (infinite): Model tahapan takterbatas (infinite-stage).
5
Model Finite-Stage • m = banyak state pada setiap stage (year) ( misalkan 3) • fn(i) = revenue optimal yang diharapkan dari stage (tahun) n, n+1, …, N (dalam hal ini N=3); i adalah state dari sistem (yaitu: (1) good, (2) fair dan (3) poor). • k=1,2 (yaitu banyaknya alternatif tersedia: tanpa dan dengan fertilizer) 6
• Rumus persamaan rekursif programa dinamis yang digunakan adalah: m
v = ∑ pijk rijk k i
j =1
{ }
f N (i ) = max vik k
k m k f n (i ) = max vi + ∑ pij f n +1 ( j ), n = 1, 2,..., N − 1 k j =1
7
Solusi Stage 3 :
v ik
Solusi Optimal
i
k=1
k=2
f3(i)
k*
1
5.3
4.7
5.3
1
2
3
3.1
3.1
2
3
-1
.4
.4
2
8
Stage 2 :
i
vik + pi1k f3(1)+ pi2k f3(2) + pi3k f3(3) k=1 k=2
1 5.3 + .2x5.3 + .5x3.1 +
Solusi Optimal f2(i)
k*
8.19
8.19 2
5.61
5.61 2
2.13
2.13 2
.3x.4 = 8.03
2 3
3 + 0x5.3 + .5x3.1 + .5x.4 = 4.75 -1 + 0x5.3 + 0x3.1 + 1x.4 = -6
9
Stage 1:
i
vik + pi1k f2(1)+ pi2k f2(2) + pi3k f2(3) k =1 k=2
1
10.38
10.74
10.74
2
2
6.87
7.92
7.92
2
3
1.13
4.23
4.23
2
Solusi Optimal f1(i) k*
10
• Kesimpulan: – Solusi optimal menunjukkan bahwa untuk tahun 1 dan 2 harus menerapkan fertilizer (k* = 2). – Tahun ke 3, fertilizer diterapkan hanya jika sistem dalam state 2 atau 3 (kondisi fair atau poor). – Total revenue yang diharapkan untuk tiga tahun adalah f1(1)=10.74 jika state sistem di tahun 1 adalah good, f1(2)=7.92 jika fair dan f1(3)=4.23 jika poor.
11
Problem set 19.2A No. 1 Sebuah perusahaan akan menilai status produk pentingnya setiap tahun dan memutuskan apakah berhasil (status 1) atau gagal (status 2). Ada dua perlakuan yang akan diambil yaitu dengan mengiklankan (k=1) atau tidak (k=2). Matriks P1 dan P2 adalah probabilitas transisi dengan mengiklankan dan tidak mengiklankan selama sebarang tahun. Matriks return yang terkait dengan P1 dan P2 adalah R1 dan R2. Carilah keputusan optimal selama tiga tahun berikutnya.
.9 P1 = .6 .7 P2 = .2
.1 2 −1 R1 = .4 1 − 3 .3 4 1 R2 = .8 2 − 1
12
Problem set 19.2A No. 2 Sebuah perusahaan dapat mengiklankan melalui radio, Tv atau surat kabar. Biaya iklan per minggu pada tiga media diperkirakan sebesar $200, $900 dan $300. Perusahaan dapat menggolongkan volume penjualannya selama setiap minggu dengan (1) gagal, (2) bagus atau (3) sangat bagus. Probabilitas transisi yang terkait dengan media iklan adalah sebagai berikut:
PRadio
.4 .5 .1 .7 .2 .1 .2 .5 .3 = .1 .7 .2 ; PTV = .3 .6 .1 ; PSK = 0 .7 .3 .1 .2 .7 .1 .7 .2 0 .2 .8
Return per minggu (dalam ribuan dollar) untuk ketiga media iklan berturut-turut adalah sebagai berikut. Carilah kebijakan mengiklankan optimal selama tiga minggu berikutnya. RRadio
400 520 600 1000 1300 1600 400 530 710 = 300 400 700 ; RTV = 800 1000 1700 ; RSK = 350 450 800 200 250 500 600 700 1100 250 400 650
13
Model Infinite-Stage • Ada dua metode untuk menyelesaikan masalah infinite-stage: – Exhaustive Enumeration Method (mengevaluasi semua stationary policies yang mungkin dari masalah keputusan) – Policy iteration (secara umum lebih efisien karena hal ini menentukan kebijakan optimum secara iteratif)
14
Metode Exhaustive Enumeration • Misalkan masalah keputusan mempunyai S stationary policies, dan asumsikan Ps dan Rs berturut-turut adalah matriks transisi dan revenue terhadap kebijakan s=1,2,…,S. Langkah metode enumersi adalah: 1. Hitung vis, untuk setiap kebijakan s dan state i=1,2,…,m. 2. Hitung πis,long-run probabilities dari matriks transisi Ps dengan rumus: πs Ps = πs π1s + π2s +…+ πms =1 dengan πs = (π1s , π2s ,…, πms ) 3. Tentukan Es = jumlah semua πis vis ; (i=1,…,m). 4. ES* = maks {Es}
15
Example 19.3-1 Gardener problem mempunyai total 8 kebijakan statinary, seperti ditunjukkan dalam tabel berikut. Kebijakan stasionary
Action
1
Do not fertilize
2
Fertilize regardless of the state
3
Fertilize if in state 1
4
Fertilize if in state 2
5
Fertilize if in state 3
6
Fertilize if in state 1 or 2
7
Fertilize if in state 1 or 3
8
Fertilize if in state 2 or 3 16
Matriks Ps dan Rs kebijakan 3 hingga 8 diturunkan dari matriks kebijakan 1 dan 2 yang diberikan oleh:
17
