PROSES KEPUTUSAN MARKOVIAN
TEKNIK RISET OPERASI
Contoh
TIA 310
3
Contoh
TIA 310
4
TIA 310
5
TIA 310
6
TIA 310
7
TIA 310
8
Cara Perhitungan 0.2 x 7 + 0.5 x 6 + 0.3 x 3 = 5.3 0 x 0 + 0.5 x 5 + 0.5 x 1 = 3 0 x 0 + 0 x 0 + 1 x -1 = -1 0.3 x 6 + 0.6 x 5 + 0.1 x -1 = 4.7 0.1 x 7 + 0.6 x 4 + 0.3 x 0 = 3.1 0.05 x 6 + 0.4 x 3 + 0.55 x -2 2 = 0.4
9
-0.6 TIA 310
10
Cara Perhitungan 5.3 + 0.2 x 5.3 + 0.5 x 3.1 + 0.3 x 0.4 = 8.03 3 + 0 x 5.3 + 0.5 x 3.1 + 0.5 x 0.4 = 4.75 -1 + 0 x 5.3 + 0 x 3.1 + 1 x 0.4 = -0.6 4.7 + 0.3 x 5.3 + 0.6 x 3.1 + 0.1 x 0.4 = 8.19 3.1 + 0.1 x 5.3 + 0.6 x 3.1 + 0.3 x 0.4 = 5.61 0.4 + 0.05 x 5.3 + 0.4 x 3.1 + 0.55 x 0.4 = 2.13
TIA 310
12
Cara Perhitungan 5.3 + 0.2 x 8.19 + 0.5 x 5.61 + 0.3 x 2.13 = 10.38 3 + 0 x 8.19 + 0.5 x 5.61 + 0.5 x 2.13 = 6.87 -1 1 + 0 x 8.19 + 0 x 5.61 + 1 x 2.13 = 1.13 4.7 + 0.3 x 8.19 + 0.6 x 5.61 + 0.1 x 2.13 = 10.74 3.1 + 0.1 x 8.19 + 0.6 x 5.61 + 0.3 x 2.13 = 7.92 0.4 + 0.05 x 8.19 + 0.4 x 5.61 + 0.55 x 2.13 = 4.23
14
15
16
17
18
Metode Enumerasi Lengkap Contoh 1: Masalah petani dengan horison perencanaan periode tak hingga
Di sini ada 8 kebijakan stasioner, stasioner yaitu:
Kebijakan Stasioner s
Tindakan
1
Tidak menggunakan pupuk sama sekali
2
Menggunakan pupuk tanpa bergantung pada keadaan
3
Gunakan pupuk ketika keadaan 1
4
Gunakan pupuk ketika keadaan 2
5
Gunakan pupuk ketika keadaan 3
6
Gunakan pupuk ketika keadaan 1 atau 2
7
Gunakan pupuk ketika keadaan 1 atau 3
8
Gunakan pupuk ketika keadaan 2 atau 3 TIA 310
19
Metode Enumerasi Lengkap
Matriks Pk dan Rk untuk kebijakan 3 sampai 8 diturunkan dari matriks untuk kebijakan 1 dan 2. Karena itu kita memiliki P1 =
0,2 0 0
0,5 0,5 0
0,3 0,5 1
P2 =
0,3 0,1 0,05
0,6 0,6 0,4
0,1 0,3 0,55
P3 =
0,3 0 0
0,6 0,5 0
0,1 0,5 1
P4 =
0,2 0,1 0
0,5 0,6 0
0,3 0,3 1
R1 =
7 0 0
6 5 0
3 1 -1
R2 =
6 7 6
5 4 3
-1 0 -2
R3 =
6 0 0
5 5 0
-1 1 -1
R4 =
7 7 0
6 4 0
3 0 -1 20
Metode Enumerasi Lengkap
P5 =
0,2 0 0,05
0,5 0,5 0,4
0,3 0,5 0,55
P6 =
0,3 0,1 0
0,6 0,6 0
0,1 0,3 1
P7 =
0,3 0 0,05
0,6 0,5 0,4
0,1 0,5 0,55
P8 =
0,2 0,1 0,05
0,5 0,6 0,4
0,3 0,3 0,55
R5 =
7 0 6
6 5 3
3 1 -2
R6 =
6 7 0
5 4 0
-1 0 -1
R7 =
6 0 6
5 5 3
-1 1 -2
R8 =
7 7 6
6 4 3
3 0 -2
Nilai-nilai vik karena itu dapat dihitung seperti diberikan dalam tabel berikut ini: 21
Metode Enumerasi Lengkap
s
i=1
i=2
i=3
1
5,3
3
-1
2
4,7
3,1
0,4
3
4,7
3
-1
4
5,3
3,1
-1
5
5,3
3
0,4
6
4,7
3,1
-1
7
4,7
3
0,4
8
5,3
3,1
0,4
Perhitungan dari probabilitas stasioner tersebut dicapai dengan menggunakan persamaan: πsPs = πs π1 + π2 + … + πm = 1 22
Metode Enumerasi Lengkap
Sebagai ilustrasi, pertimbangkan s = 2. Persamaan yang berkaitan adalah: 0,3π1 + 0,1π2 + 0,05π3 = π1 0,6π1 + 0,6π2 + 0,4π3 = π2 0,1π1 + 0,3π2 + 0,55π3 = π3 π1 + π2 + π3 = 1
Berdasarkan hasil eliminasi dan substitusi didapatkan : π12 = 6/59, π22 = 31/59, π32 = 22/59
Dalam kasus ini, pendapatan tahunan yang diperkirakan adalah: 2
E
3
i 1
i 2 vi 2
1 6 x 4 ,7 31x3,1 22 x0 ,4 2 ,256 59
Tabel berikut ini meringkaskan πk dan Ek untuk semua kebijakan stasioner. 23
Metode Enumerasi Lengkap
s
π1s
π2s
π3s
Es
1
0
0
1
-1
2
6/59
31/59
22/59
2,256
3
0
0
1
-1
4
0
0
1
-1
5
5/154
69/154
80/154
1,724
6
0
0
1
-1
7
5/137
62/137
70/137
1,734
8
12/135
69/135
54/135
2,216
Tabel terakhir ini menunjukkan bahwa kebijakan 2 menghasilkan pendapatan tahunan yang diperkirakan terbesar. Akibatnya, Akibatnya kebijakan jangka panjang optimum menyatakan penggunaan pupuk tanpa bergantung pada keadaan sistem. 24
Metode Iterasi Kebijakan Tanpa Diskonto
Bayangkan jika metode enumerasi lengkap diterapkan untuk masalah petani dengan 4 arah tindakan (bukan dua): tidak menggunakan pupuk, menggunakan pupuk satu kali selama musim tersebut, menggunakan pupuk dua kali, dan menggunakan pupuk tiga kali.
Dalam kasus ini, petani tersebut secara keseluruhan memiliki 43 = 256 kebijakan stasioner. Melakukan enumerasi dari semua kebijakan secara eksplisit bukan hanya sulit, tetapi juga jumlah perhitungan yang terlibat dalam evaluasi kebijakan ini dapat sangat besar. Karena itu dikembangkan metode iterasi kebijakan sebagai berikut. Di bagian sebelumnya sudah diperlihatkan bahwa pengembalian total yang diperkirakan di tahap n dinyatakan dengan persamaan rekursif: m
f n i vi
pij f n 1 j ,
i 1,2 ,..., m
j 1
Persamaan rekursif ini adalah dasar untuk pengembangan metode iterasi kebijakan. Tetapi, bentuk ini harus sedikit dimodifikasi untuk memungkinkan kita untuk mempelajari perilaku asimtut dari proses ini. 25
Metode Iterasi Kebijakan Tanpa Diskonto
Pada intinya, kita mendefinisikan η sebagai jumlah tahap yang tersisa untuk dipertimbangkan. Ini adalah berbalikan dengan n dalam persamaan di atas, yang mendefinisikan tahap ke-n. Jadi, persamaan rekursif itu dapat ditulis: m
f i vi
pij f1 j,
i 1,2,...,m
j 1
Catat bahwa fη adalah pendapatan kumulatif yang diperkirakan dengan diketahui η adalah jumlah tahap yang tersisa untuk dipertimbangkan. Dengan definisi baru ini, perilaku asimtut dari proses ini dapat diketahui dengan menganggap η→∞. Dengan diketahui bahwa π = (π1, π2, …, πm) adalah vektor probabilitas steady state dari matriks transisi P = ||pij|| dan E = π1v1 + π2v2 + … πmvm adalah pendapatan yang diperkirakan per tahun seperti dihitung di bagian sebelumnya, dapat diperlihatkan bahwa untuk η yang sangat besar, fη(i) = ηE +f(i) 26
Metode Iterasi Kebijakan Tanpa Diskonto dengan f(i) adalah sebuah bagian konstan yang mewakili titik potong asimtut dari f η(i) dengan diketahui keadaan i.
Karena fη(i) adalah pengembalian optimum kumulatif untuk η tahap dengan diketahui keadaan i dan E adalah pengembalian yang diperkirakan per tahap, kita dapat secara intuitif melihat mengapa fη(i) sama dengan ηE ditambah faktor koreksi f(i) yang memperhitungkan keadaan spesifik i. Hasil ini tentu saja mengasumsikan bahwa η sang besar. Menggunakan informasi ini, persamaan rekursif tersebut dapat ditulis:
m
E f i vi
pij 1E f j,
i 1,2,...,m.
i 1
Dengan menyederhanakan persamaan di atas, kita memperoleh:
m
E f i vi
pij 1E f j ,
i 1,2,...,m.
i 1
yang menghasilkan m persamaan dan m + 1 variabel yang tidak diketahui, di mana variabel yang tidak diketahui itu adalah f(1), f(2), …, f(m), dan E. 27
Metode Iterasi Kebijakan Tanpa Diskonto
Tujuan akhir adalah menentukan kebijakan optimum yang menghasilkan nilai E maksimum. Karena terdapat m persamaan dengan m+1 variabel yang tidak diketahui, nilai E optimum tidak dapat ditentukan dalam satu langkah. Sebaliknya, suatu pendekatan iteratif dimanfaatkan yang, dengan memulai di satu kebijakan secara sembarang, lalu akan menentukan suatu kebijakan baru yang menghasilkan nilai E yang lebih baik. Proses iteratif tersebut berakhir ketika dua kebijakan yang berturutturut adalah identik. Proses iteratif ini terdiri dari dua komponen dasar, yang disebut langkah penentuan nilai (value determination) dan langkah perbaikan kebijakan (policy improvement). 1. Langkah penentuan nilai. Pilihlah satu kebijakan s secara sembarang. Gunakan matriks Ps dan Rs yang berkaitan dan secara sembarang asumsikan bahwa fs(m) = 0, pecahkan persamaan s
s
E vi
m
s
p ij f
s
j
f
s
i ,
i 1, 2 ,..., m
( b . 1)
j 1
dengan variabel yang tidak diketahui Es, fs(1), …, dan fs(m-1). Lanjutkan ke tahap perbaikan kebijakan.
28
Metode Iterasi Kebijakan Tanpa Diskonto
2. Langkah Perbaikan Kebijakan.. Untuk setiap keadaan i, tentukan alternatif k yang menghasilkan:
m k max vi pij k f s j , i 1,2 ,..., m k j 1 [Nilai-nilai fs(j), j = 1, 2, …, m, adalah nilai-nilai nilai yang ditentukan dalam langkah penentuan nilai.]
Keputusan optimum yang dihasilkan k untuk keadaan 1, 2, …, m membentuk kebijakan baru t. Jika s dan t adalah identik, berhenti; t adalah optimum. Jika tidak identik, tetapkan = t dan kembali ke langkah penentuan nilai.
Masalah optimisasi dari langkah perbaikan kebijakan memerlukan penjelasan. Tujuan kita dalam langkah ini adalah memperoleh max{E}. Seperti diketahui:
m
E vi
pij f j f i j 1 29
Metode Iterasi Kebijakan Tanpa Diskonto
Karena f(i) tidak bergantung pada alternatif k, disimpulkan bahwa maksimisasi E di semua alternatif k adalah setara dengan masalah maksimisasi yang diketahui dalam langkah perbaikan kebijakan.
Contoh: Kita mmecahkan contoh petani tersebut dengan metode iterasi kebijakan. Iterasi 1
Kita mulai dengan kebijakan sembarang yang menyatakan tidak diperguna-kannya diperguna pupuk. Matriks yang berkaitan adalah: P=
Persamaan dalam langkah iterasi nilai adalah:
0,2
0,5
0,3
0
0,5
0,5
0
0
1
R=
7
6
3
0
5
1
0
0
-1
E + f(1) – 0,2f(1) – 0,5f(2) – 0,3f(3) = 5,3 E + f(2) E + f(3)
- 0,5f(2) – 0,5f(3) = 3 - f(3)
= -1 -
Jika kita secara sembarang menganggap f(3) = 0, persamaan-persamaan persamaan tersebut menghasilkan pemecahan: E = -1, f(1) = 12,88, f(2) = 8, f(3) = 0 30
Metode Iterasi Kebijakan Tanpa Diskonto
Selanjutnya, kita menerapkan langkah perbaikan kebijakan. Perhitungan yang berkaitan diperlihatkan dalam tabel berikut ini. vik+ pi1kf(1) + pi2kf(2) + pi3kf(3) i 1 2 3
k=1
k=2
5,3+0,2x12,88+0,5x8+0,3x0 = 11,875
4,7+0,3x12,88+0,6x8+0,1x0 = 13,36
3,0+0x12,88+0,5x8+0,5x0 = 7
3,1+0,1x12,88+0,6x8+0,3x0 = 9,19
-1,0+0x12,88+0x8+1x0 = -1
0,4+0,05x12,88+0,4x8+0,55x0 = 4,24
Pemecahan optimal f(i) k* 13,36 2 9,19 2 4,24 2
Kebijakan baru ini menyatakan penggunaan pupuk tanpa bergantung pada keadaan. Karena kebijakan baru ini berbeda dari yang sebelumnya, langkah penentuan nilai kembal dilakukan.
Iterasi 2
Matriks yang berkaitan dengan kebijakan baru ini adalah: P=
0,3 0,1 0,05
0,6 0,6 0,4
0,1 0,3 0,55
R=
6 7 6
5 4 3
-1 0 -2
Matriks ini menghasilkan persamaan-persamaan persamaan berikut: E + f(1) – 0,3f(1) – 0,6f(2) – 0,1f(3) = 4,7 TIA 310
31
Metode Iterasi Kebijakan Tanpa Diskonto E + f(2) – 0,1f(1) – 0,6f(2) – 0,3f(3)
= 3,1
E + f(3) – 0,05f(1) – 0,4f(2) – 0,55f(3) = 0,4
Sekali lagi, dengan menganggap f(3) = 0, kita memperoleh pemecahan: E = 2,26, f(1) = 6,75, f(2) = 3,79, f(3) = 0
Perhitungan dalam langkah perbaikan kebijakan diberikan dalam tabel berikut ini: vik+ pi1kf(1) + pi2kf(2) + pi3kf(3)
Pemecahan optimal
i
k=1
k=2
f(i)
k*
1
5,3+0,2x6,75+0,5x3,79+0,3x0 = 8,54
4,7+0,3x6,75+0,6x3,79+0,1x0 = 8,99
8,99
2
2
3,0+0x6,75+0,5x3,79+0,5x0 = 4,89
3,1+0,1x6,75+0,6x3,79+0,3x0 = 6,05
6,05
2
3
-1,0+0x6,75+0x3,79+1x0 = -1
0,4+0,05x6,75+0,4x3,79+0,55x0 = 2,25
2,25
2
Kebijakan baru ini, yang menyatakan penggunaan pupuk tanpa bergantung pada keadaan adalah identik dengan yang sebelumnya. Jadi, kebijakan terakhir ini optimal dan proses iteratif berakhir. Secara alamiah, kesimpulan dengan metode ini sama dengan kesimpulan yang diperoleh dengan metode enumerasi lengkap. 32
Metode Iterasi Kebijakan Dengan Diskonto
Dengan diketahui bahwa α (< 1) adalah faktor diskonto, persamaan rekursif tahap terhingga dapat ditulis sebagai: m k k f i max vi pij f 1 j k j 1
(Perhatikan bahwa η mewakili sejumlah tahap yang masih harus dilalui).
Dapat dibuktikan bahwa sementara η→∞ →∞ (model tahap tak hingga), fη(i) = f(i), dengan f(i) adalah nilai sekarang (yang didiskonto) dari pendapatan yang diperkirakan dengan diketahui bahwa sistem tersebut berada dalam keadaan i dan beroperasi dalam horison waktu yang tak terhingga. Jadi perilaku jangka panjang dari fη(i) sementara η→∞ tidak bergantung dari nilai η. Ini berlawanan dengan kasus tanpa diskonto, di mana fη(i) = ηE + f(i), seperti disebutkan di atas. Hasil ini dapat diperkirkan karena dalam kasus diskonto, pengaruh pendapatan masa mendatang akan menurun menjadi nol secara asimtut. Pada kenyataannya, nilai sekarang f(i) akan mendekati nilai konstan sementara η→∞.
33
Metode Iterasi Kebijakan Dengan Diskonto
1.
Langkah kebijakan iterasi dimodifikasi sebagai berikut. Langkah penentuan nilai. Untuk sebuah kebijakan sembarang s dengan matriks Ps dan Rs, pecahkan m persamaan:
f
s
i
s
vi
m
s
p ij f
s
j ,
i 1, 2 ,..., m
(b.2 )
j 1
dalam m nilai yang tidak diketahui fs(1), fs(2), …, fs(m). (Catat bahwa di sini terdapat m persamaan dengan tepat m variabel yang tidak diketahui) 2.
Langkah perbaikan kebijakan. Untuk setiap tahap i, tentukan alternatif k yang menghasilkan m k max v i p ij k f 1 j , i 1 ,2 ,..., m k j 1
di mana fs(j) adalah nilai-nilai yang diperoleh dari langkah penentuan nilai. Jika kebijakan yang dihasilkan t adalah sama dengan s, berhenti; t optimum. Jika tidak sama, tetapkan s = t dan kembali ke langkah penentuan nilai
34
Metode Iterasi Kebijakan Dengan Diskonto Contoh:: Kita akan menyelesaikan contoh terdahulu dengan α = 0,6
Dengan dimulai dari satu kebijakan sembarang s = {1,1,1}. Matriks P dan R (P1 dan R1 dalam contoh terdahulu) menghasilkan persamaan: f(1) – 0,6[0,2f(1) + 0,5f(2) + 0,3f(3)] = 5,3 f(2) – 0,6[
0,5f(2) + 0,5f(3)] = 3
f(3) – 0,6[
f(3)] = -1
Pemecahan dari persamaan-persamaan persamaan ini menghasilkan: f(1) = 6,6, f(2) = 3,21, f(3) = -2,5
Ringkasan iterasi perbaikan kebijakan diberikan dalam tabel berikut ini: vik+ 0,6[pi1kf(1) + pi2kf(2) + pi3kf(3)] i 1
k=1
k=2
5,3+0,6[0,2x6,6+0,5x3,21+0,3x-2,5] = 6,61
4,7+0,6[0,3x6,6+0,6x3,21+0,1x 4,7+0,6[0,3x6,6+0,6x3,21+0,1x-2,5] = 6,89
Pemecahan optimal f(i) k* 6,89 2
2
3,0+0,6[0x6,6+0,5x3,21+0,5x-2,5] = 3,21
3,1+0,6[0,1x6,6+0,6x3,21+0,3x 3,1+0,6[0,1x6,6+0,6x3,21+0,3x-2,5] = 4,2
4,2
2
3
-1,0+0,6[0x6,6+0x3,21+1x-2,5] = -2,5
0,4+0,6[0,05x6,6+0,4x3,21+0,55x 0,4+0,6[0,05x6,6+0,4x3,21+0,55x-2,5] = 0,54
0,54
2 35
Metode Iterasi Kebijakan Dengan Diskonto
Langkah penentuan nilai yang menggunakan P2 dan R2 dalam contoh sebelumnya menghasilkan persamaan--persamaan berikut: f(1) – 0,6[0,3f(1) + 0,6f(2) + 0,1f(3)] = 4,7 f(2) – 0,6[0,1f(1) + 0,6f(2) + 0,3f(3)] = 3,1 f(3) – 0,6[0,05f(1) + 0,4f(2) + 0,55f(3)] = 0,4
Pemecahan dari persamaan-persamaan persamaan ini menghasilkan: f(1) = 8,88, f(2) = 6,62, f(3) = 3,57
Ringkasan iterasi perbaikan kebijakan diberikan dalam tabel berikut ini: vik+ 0,6[pi1kf(1) + pi2kf(2) + pi3kf(3)] i 1 2 3
k=1
k=2
5,3+0,6[0,2x8,88+0,5x6,62+0,3x3,37] = 8,95 3,0+0,6[0x8,88+0,5x6,62+0,5x3,37] = 5,99 -1,0+0,6[0x8,88+0x6,62+1x3,37] = 1,02
4,7+0,6[0,3x8,88+0,6x6,62+0,1x3,37] = 8,88 3,1+0,6[0,1x8,88+0,6x6,62+0,3x3,37] = 6,62 0,4+0,6[0,05x8,88+0,4x6,62+0,55x3,37] = 3,37
Pemecahan optimal f(i) k* 8,95 1 6,62 2 3,37 2
36
Metode Iterasi Kebijakan Dengan Diskonto
Karena kebijakan baru {1,2,2} berbeda dengan kebijakan di atas, langkah penentuan nilai dimasuki kembali dengan menggunakan P8 dan R8 dalam conto sebelumnya menghasilkan persamaan-persamaan persamaan berikut: f(1) – 0,6[0,2f(1) + 0,5f(2) + 0,3f(3)] = 5,3 f(2) – 0,6[0,1f(1) + 0,6f(2) + 0,3f(3)] = 3,1 f(3) – 0,6[0,05f(1) + 0,4f(2) + 0,55f(3)] = 0,4
Pemecahan dari persamaan-persamaan persamaan ini menghasilkan: f(1) = 8,98, f(2) = 6,63, f(3) = 3,38
Ringkasan iterasi perbaikan kebijakan diberikan dalam tabel berikut ini: vik+ 0,6[pi1kf(1) + pi2kf(2) + pi3kf(3)] i 1
k=1
k=2
5,3+0,6[0,2x8,98+0,5x6,63+0,3x3,38] = 8,98
4,7+0,6[0,3x8,98+0,6x6,63+0,1x3,38] = 8,91
Pemecahan optimal f(i) k* 8,98 1
2
3,0+0,6[0x8,98+0,5x6,63+0,5x3,38] = 6,00
3,1+0,6[0,1x8,98+0,6x6,63+0,3x3,38] = 6,63
6,63
2
3
-1,0+0,6[0x8,98+0x6,63+1x3,38] = 1,03
0,4+0,6[0,05x8,98+0,4x6,63+0,55x3,38] = 3,37
3,37
2 37
Metode Iterasi Kebijakan Dengan Diskonto
Karena kebijakan baru ini {1,2,2} adalah identik dengan kebijakan sebelumnya, kebijakan ini optimal. Catat bahwa kebijakan diskonto menghasilkan kebijakan optimal yang berbeda, yang menyatakan tidak digunakannya pupuk jika keadaan sistem adalah baik (keadaan 1).
38
Pemecahan Pemrograman Linear untuk Masalah Keputusan Markov
Masalah keputusan Markov tahap tak hingga, hingga baik dengan maupun tanpa diskonto, dapat dirumuskan dan dipecahkan sebagai sebuah program linear. Masalah Keputusan Markov tanpa diskonto. diskonto
Di bagian seblumhya, sudah diperlihatkan bahwa masalah Markov tahap tak hingga tanpa diskonto pada akhirnya menyempit menjadi masalah penentuan kebijakan optimal s*, yang bersesuaian dengan: m s s s s s s s s s max i vi | P , 1 2 .... m 1, i 0 , i 1,2 ,..., m s S i 1
dengan S adalah kumpulan dari semua kebijakan yang mungkin dalam masalah itu. Batasan dari masalah ini memastikan bahwa πis, i = 1, 2, …, m mewakili probabilitas steady-state dari rantai Markov Ps.
Secara spesifik, setiap kebijakan s dinyatakan dengan sekelompok tindakan yang tetap (stasioner). Kita harus memodifikasi variabel yang tidak diketahui dari masalah ini sedemikian rupa sehingga pemecahan optimal akan secara otomatis menentukan tindakan optimal k ketika sistem tersebut berada dalam keadaan i. Kumpulan dari semua tindakan optimal ini lalu akan mendefinisikan s*, kebijakan optimal. 39
Pemecahan Pemrograman Linear untuk Masalah Keputusan Markov
Tujuan ini dicapai sebagai berikut. Anggaplah qik = probabilitas kondisional dari memilih alternatif k dengan diketahui sistem tersebut berada dalam keadaan i
Jadi, masalah ini dapat diekspresikan sebagai m
K maksimumka n E i q i k vi k i 1 k 1
dengan batasan m
j
i p ij ,
j 1 ,2 ,..., m
i 1
1 2 ... m 1 q i1 q i 2 ... q i K 1 , i 1 ,2 ,..., m
i 0 , q i k 0 , i dan k
Catat bahwa pij adalah fungsi dari kebijakan yang dipilih dan karena itu merupakan fungsi dari alternatif spesifik k dari kebijakan tersebut. 40
Pemecahan Pemrograman Linear untuk Masalah Keputusan Markov
Masalah ini dapat dikonversikan menjadi sebuah program linear dengan membuat substitusi yang tepat yang melibatkan qik. Amati bahwa formulasi tersebut adalah setara dengan masalah semula hanya jika qik = 1 untuk tepat satu k untuk setiap i, karena hal ini akan mengurangi jumlah menjadi vik, di mana k* adalah alternatif optimal yang dipilih. K
qi k vi k k 1
Untungnya, program linear yang kita kembangkan di sini memperhitungkan kondisi ini secara otomatis.
Definisikan wik = πi qik , untuk semua i dan k
Berdasarkan definisinya, wik mewakili probabilitas gabungan untuk berada dalam keadaan i dan membuat keputusan k. Dari teori probabilitas kita mengetahui bahwa: K i
w ik
k 1
41
Pemecahan Pemrograman Linear untuk Masalah Keputusan Markov
Karena itu w ik
qik
K
w ik
k 1 m
i 1 Jadi kita melihat bahwa batasan dapat ditulis sebagai i 1 m
K
w ik i 1 k 1
1
K
qi k
1
k 1
Juga batasan secara otomatis tersirat berdasarkan cara kita mendefinisikan qik dalam bentuk wik. Jadi masalah ini dapat ditulis sebagai m
K maksimumka n E i q i k vi k i 1 k 1
42
Pemecahan Pemrograman Linear untuk Masalah Keputusan Markov
dengan batasan m
m
w jk
i 1 m K
K
p ij k w ik 0 ,
j 1 ,2 ,..., m
i 1 k 1
w ik 1
i 1 k 1
w ik 0 , i 1 ,2 ,..., m ; k 1 ,2 ,..., K
Model yang dihasilkan ini merupakan sebuah program linear dalam wik. Di sini akan diperlihatkan bahwa pemecahan optimalnya secara otomatis menjadi qik = 1 untuk satu k untuk setiap i. Pertama, catat bahwa program linear ini memeliki m persamaan independen (satu persamaan yang berkaitan dengan π = πP adalah berlebihan). Karena itu, masalah ini harus memiliki m variabel dasar. Tetapi, dapat diperlihatkan bahwa wik harus positif secara ketat untuk setidaknya satu k untuk setiap i. Dari kedua hasil ini, kita menyimpulkan bahwa: qik
w ik K
TIA 310 k 1
w ik 43
Pemecahan Pemrograman Linear untuk Masalah Keputusan Markov hanya dapat memiliki nilai biner (0 atau 1), seperti yang diinginkan. (Pada kenyataannya, hasil di atas juga memperlihatkan bahwa di mana k* adalah alternatif yang bersesuaian dengan wik >0) K i
w ik
w ik *
k 1
Contoh:: Formulasi LP untuk masalah petani tadi tanpa diskonto: maksimumkan E = 5,3w11 + 4,7w12 + 3w21 + 3,1w22 – w31 + 0,4w32 dengan batasan w11 + w12 – (0,2w11 + 0,3w12
+ 0,1w22
w21 + w22 – (0,5w11 + 0,6w12 + 0,5w21 + 0,6w22
+ 0,05w32) = 0 + 0,4w32) = 0
w31 + w32 – (0,3w11 + 0,1w12 + 0,5w21 + 0,3w22 + w31 + 0,55w32) = 0 w11 + w12 + w21 + w22 + w31 + w32 = 1 wik ≥ 0, untuk semua i dan k
Pemecahan optimalnya adalah w11 = w12 = w31 = 0 dan w12 = 6/59, w22 = 31/59, dan w32 = 22/59. Hasil ini berarti bahwa q12 = q22 = q32 = 1. Jadi, kebijakan optimal menyatakan dipilihnya alternatif 2 (k = 2) untuk i = 1, 2, dan 3. Nilai optimal dari E adalah 2,256. TIA 310
44
Pemecahan Pemrograman Linear untuk Masalah Keputusan Markov
Adalah menarik bahwa nilai-nilai positif dari wik tepat setara dengan nilai-nilai πi yang berkaitan dengan kebijakan optimal dalam prosedur enumerasi lengkap. Observasi ini menunjukkan hubungan langsung di antara kedua metode pemecahan ini.
Masalah Keputusan Markov dengan diskonto. diskonto
Masalah ini diekspresikan dengan persamaan rekursif m k k f i max vi pij f j , i 1,2 ,..., m k j 1
Persamaan ini adalah setara dengan k
m
f i vi
pij k f j ,
i dan k
j 1
dengan ketentuan bahwa f(i) mencapai nilai minimum untuk setiap i.
Sekarang pertimbangkan fungsi tujuan m
min imumkan
bi f i i 1 45
Pemecahan Pemrograman Linear untuk Masalah Keputusan Markov dengan bi (> 0 untuk semua i) adalah sebuah konstanta sembarang. Dapat diperlihatkan bahwa optimisasi dari fungsi ini dengan dikenakan pertidaksamaan yang diberikan akan menghasilkan nilai minimum dari f(i), seperti yang diinginkan. Jadi masalah ini dapat ditulis sebagai m min imumkan
bi f i i 1
dengan batasan
m
f i
pij k f j vi k ,
i dan k
j 1
f(i) tidak dibatasi, i = 1, 2, …, m.
Sekarang, masalah dual dari masalah ini adalah 46
Pemecahan Pemrograman Linear untuk Masalah Keputusan Markov m K
maksimumka n
vi k wik
i 1 k 1
dengan batasan K
k 1
m K
w jk
pij k wik b j ,
j 1,2 ,..., m
i 1 k 1
wik ≥ 0, untuk i = 1, 2, …, m; k = 1,2, …, K
Perhatikan bahwa fungsi tujuan ini memiliki bentuk yang sama seperti kasus tanpa diskonto, sehingga wik dapat diinterpretasikan dengan cara serupa.
Contoh:: Contoh petani tadi dengan faktor diskonto α = 0,6. Jika kita menganggap b1 = b2 = b3 = 1, masalah dual dari LP ini dapat ditulis sebagai TIA 310
47
Pemecahan Pemrograman Linear untuk Masalah Keputusan Markov maksimumkan 5,3w11 + 4,7w12 + 3w21 + 3,1w22 – w31 + 0,4w32 dengan batasan w11 + w12 – 0,6[0,2w11 + 0,3w12 + 0,1w22 + 0,05w32] = 1 w21 + w22 – 0,6[0,5w11 + 0,6w12 + 0,5w21 + 0,6w22 + 0,4w32] = 1 w31 + w32 – 0,6[0,3w11 +0,1w12+0,5w21+ 0,3w22 + w31 + 0,55w32] = 1 wik ≥ 0, untuk semua i dan k
Pemecahan optimalnya adalah w12 = w21 = w31 = 0 dan w11 = 1,5678, w22 = 3,3528, dan w32 = 2,8145. Pemecahan ini memperlihatkan bahwa pemecahan optimal adalah {1,2,2}, seperti yang diperoleh pada contoh terdahulu..
48
