1.
Definisi Pemrograman Dinamis
Pemrograman
dinamis adalah prosedur matematis yang terutama dirancang untuk memperbaiki
efisiensi perhitungan masalah pemrograman matematis tertentu dengan
menguraikannya menjadi bagian-bagian yang lebih kecil sehingga lebih sederhana
dalam perhitungan. Pemrograman dinamis pada umumnya menjawab masalah dalam
tahap-tahap dengan setiap tahap memiliki satu variabel optimasi. Perhitungan di
tahap yang berbeda dihubungkan dengan perhitungan rekursif dengan cara yang
menghasilkan pemecahan optimal yang mungkin bagi seluruh masalah.
Dikatakan dinamis, karena
penggunaan metode ini yang melibatkan pengambilan keputusan yang berkaitan
dengan waktu. Namun tidak selalu pentahapan berbasis waktu yang dapat
dilakukan, sehingga nama yang lebih tepat untuk kondisi yang demikian adalah
pemrograman multitahap (multistage programming). Program dinamis biasanya
digunakan untuk membuat suatu keputusan dari serangkaian keputusan yang saling
berkaitan. Tujuan utama model ini ialah untuk mempermudah penyelesaian
persoalan optimasi yang mempunyai karakteristik tertentu.
Tidak
seperti pemrograman linier, tidak ada bentuk matematis standar untuk perumusan
pemrograman dinamis. Akan tetapi, pemrograman dinamis adalah pendekatan umum
untuk pemecahan masalah dan persamaan tertentu yang digunakan di dalamnya harus
dibentuk sesuai dengan situasi masalah yang dihadapi.
Istilah
yang biasa digunakan antara lain:
a.
Stage(tahap)
adalah bagian persoalan yang mengandung decision variable.
b.
Alternatif,
pada setiap stage terdapat decision variable dan fungsi tujuan yang menentukan
besarnya nilai setiap alternative.
c.
State,
state menunjukkan kaitan satu stage dengan stage lainnya, sedemikian serupa
sehingga setiap stage dapat dioptimisasikan secara terpisah sehingga hasil
optimasi layak untuk seluruh persoalan.
2.
Karakteristik
Pemrograman Dinamis
Salah
satu cara untuk cara untuk mengenali suatu situasi yang dapat dirumuskan
sebagai masalah pemrograman dinamis adalah menyadari struktur dasar masalah
tersebut apakah serupa dengan masalah ekspedisi.
Sifat
dasar yang menjadi ciri masalah pemrograman dinamis antara lain:
a.
Masalah dapat dibagi menjadi tahap-tahap dengan
keputusan kebijakan yang dibuat pada masing-masing tahap.
Masalah ekspedisi secara harfiah dibagi menjadi 4 tahap yang sesuai
dengan 4 tahap perjalanan. Kebijakan keputusan pada masing-masing tahap adalah
kebijakan asuransi jiwa mana yang dipilih (sama dengan tujuan yang dipilih
untuk tahap berikutnya). Dengan cara yang sama, masalah pemrograman dinamis
lain memerlukan pembuatan suatu urutan keputusan yang saling berhubungan,
dengan setiap keputusan diambil pada satu tahap masalah.
b. Masing-masing
tahap mempunyai state yang berhubungan dengan kondisi awal tahap.
State pada masing-masing tahap pada masalah ekspedisi adalah Negara
bagian (wilayah) tempat pencari harta bisa singgah sementara ketika tiba pada
akhir suatu bagian/tahap perjalanan tersebut. Secara umum, state adalah bebagai
kondisi system yang mungkin pada suatu tahap masalah. Banyaknya state bisa
terbatas (seperti dalam masalah ekspedisi) ataupun tidak terbatas.
c. Efek
keputusan kebijakan pada setiap tahap adalah mengubah state saat ini menjadi
state lain pada awal tahap berikutnya. (mungkin mengikuti pola distribusi
tertentu.)
Keputusan pencari harta dalam bentuk tujuan berikutnya, membawanya
dari state sekarang kepada state berikutnyadalam perjalanan. Prosedur ini
menyatakan bahwa masalah pemrograman dinamis dapat dinyatakan sebagai jaringan.
Setiap simpul menyatakan state. Jaringan akan terdiri dari kolom simpul, degan
setiap kolom menyatakan tahap, sehingga aliran dari suatu simpul hanya dapat
melangkah ke kolom yang berada di sebelah kanannya. Hubungan dari suatu simpul
ke simpul pada kolom berikutnya sesuai dengan keputusan kebijakan yang mungkin
untuk menentukan state untuk langkah berikutnya. Nilai yang ditugaskan pada
setiap hubungan dapat ditafsirkan sebagai kontribusi langsung terhadap fungsi
tujuan dari pembuatan keputusan kebijakan itu. Dalam banyak kasus, mencari
solusi untuk mencapai tujuan dapat dinyatakan dengan menemukan jalur terpendak
atau terpanjang pada jaringan.
d. Prosedur
penyelesain dirancang untuk menemukan kebijakan optimal dari keseluruhan
masalah, yang menunjukkan keputusan kebijakan mana yang optimal pada setiap
tahap untuk setiap state yang mungkin.
Untuk masalah ekspedisi, prosedur penyelesaian membentuk tabel untuk
setiap tahap (n) yang menunjukkan keputusan optimal pada setiap state yang
mungkin (s). jadi, selain bisa menemukan tiga solusi optimal (rute terbaik)
untuk masalah keseluruhan, hasil yang diperoleh juga dapat dipakai sebagai
petunjuk bagi pencari harta untuk menentukan langkah jika ia terpaksa dialihkan
ke state yang tidak berada dalam rute optimal. Untuk masalah apapun pemrograman
dinamis menyediakan petunjuk mengenai kebijakan apa yang harus dilakukan pada
setiap keadaan yang mungkin terjadi (inilah alasan mengapa keputusan aktual
yang dibuat pada saat mencapai state tertentu pada tahap tertentu disebut
keputusan kebijakan). Penyedian informasi tambahan selain menyatakan solusi
optimal (urutan keputusan optimal) dapat berguna dalam berbagai hal, termasuk
untuk analisis sensitivitas.
e.
Berkaitan dengan state saat ini, kebijakan
optimal untuk langkah tersisa bersifat independen terhadap keputusan kebijakan
yang telah diambil pada tahap sebelumnya. Oleh karena itu, keputusan optimal
selanjutnya hanya tergantung pada state saat ini dan bukan cara mencapai state
saat ini. Inilah prinsip optimalitas untuk pemrograman dinamis.
Sehubungan dengan state tempat pencari harta berada sekarang,
kebijakan asuransi jiwa yang optimal (dan rute perjalanannya)dari simpul ini
sampai akhir bersifat independen dengan caranya tiba pada state itu. Untuk
masalah pemrograman dinamis pada umumnya, pengetahuan menyangkut state sekarang
dari system menyampaikan semua informasi tentang prilaku sebelumnya yang
diperlukan untuk menentukan kebijakan optimal selanjutnya (sifat ini disebut
sifat Markovian). Setiap masalah yang tidak mempunyai sifat ini tidak bisa
dirumuskan sebagai masalah program dinamis.
f.
Prosedur penyelesaian dimulai dengan mencari
kebijakan optimal untuk langkah terakhir.
Kebijakan optimal untuk langkah terakhir ini akan menentukan keputusan
kebijakan optimal untuk setiap state yang mungkin pada tahap itu. Penyelesaian
dari masalah satu tahap ini umumnya sangat mudah, seperti terlihat pada masalah
ekspedisi.
g.
Tersedia hubungan rekursif yang menunjukkan
kebijakan optimal untuk tahap n dengan dasar kebijakan optimal untuk lanhkah
n+1.
Oleh karena itu, untuk menemukan keputusan kebijakan optimal saat
mulai dari state s pada tahap n, Anda akan memerlukan nilai minimum untuk xn.
untuk masalah tertentu, biaya minimum yang diperoleh dengan menggunakan nilai
xn, kemidian mengikuti kebijakan optimal saat mulai dari state s pada tahap
n+1.
Bentuk yang tepat dari hubungan rekursif ini berbeda dalam masalah
pemrograman dinamis yang berbeda. Krterangan dari notasi tersebut:
N= jumlah tahap.
N= jumlah tahap.
n = label untuk tahap sekarang (n=1,2,…N).
= state sekarang untuk tahap n.
= variable keputusan untuk tahap n.
= kontribusi tahap n,n+1,…N pada fungsi tujuan jika system dimulai
dari state pada tahap n.
keputusan selanjutnya adalah dan keputusan optimal belum dibuat.
hubungan rekursif akan selalu berbentuk:
Pergerakan
mundur (backward) seperti yang ditunjukkan dalam masalah ekspedisi, dengan
kebijakan optimal diperoleh secara berurutan pada tahap 4,3,2, dan 14. Untuk
semua masalah pemrograman dinamis, dapat dibentuk table sebagai berikut untuk
setiap tahap (n=N,N-1,…,1).
Jika tabel seperti ini sudah diperoleh untuk tahap awal (n=1), masalah
sudah dipecahkan. Oleh karena state awal telah diketahui, keputusan awal adalah
dalam tabel ini. Nilai optimal variable keputusan lain kemudian ditetapkan dari
tabel yang lain secara bergilir menurut state sistem yang dihasilkan oleh
keputusan sebelumnya.
3.
Prinsip Dasar Program Dinamis
a.
Karena keadaan berubah dari satu tahap ke tahap
berikutnya, maka nilai setiap keadaan akan menggambarkan kondisi dari satu
proses keputusan mengubah keadaan baru (awal) menjadi keadaan baru (akhir).
b.
Keadaan baru menjadi landasan bagi keputusan baru, dan
keputusan baru mengubsh keadaan baru (awal) menjadi lebih baru lagi (akhir).
c.
Hasil yang
diharapkan satu keputusan tergantung dari awal dan akhir dari keadaan untuk
keputusan dan kemudian menjumlahkan seluruhnya sebagai rangkaian keputusan.
d.
Tugas terakhir ialah mengambil keputusan yang
memaksimumkan jumlah hasil atau perolehan.
e.
3 konsep dalam programa dinamis adalah konsep tahap,
konsep keadaan dan konsep tentang perolehan.
Dua pendekatan yang digunakan dalam Pemrograman
Dinamis:
1.
Maju (forward
atau up-down).
2.
Mundur (backward
atau bottom-up).
Misalkan x1, x2,
…, xn menyatakan peubah (variable) keputusan yang
harus dibuat masing-masing untuk tahap 1, 2, …, n. Maka,
a.
Program
dinamis maju. Program dinamis bergerak mulai dari tahap 1, terus maju ke tahap
2, 3, dan seterusnya sampai tahap n. Runtunan peubah keputusan adalah x1,
x2, …, xn.
b.
Program
dinamis mundur. Program dinamis bergerak mulai dari tahap n, terus
mundur ke tahap n – 1, n – 2, dan seterusnya sampai tahap 1.
Runtunan peubah keputusan adalah xn, xn-1,
…, x1.
·
Prinsip
optimalitas maju:
ongkos
pada tahap k +1 = (ongkos yang
dihasilkan pada tahap k ) +
(ongkos dari tahap k ke tahap k + 1)
k
= 1, 2, …, n – 1
·
Prinsip
optimalitas mundur:
ongkos
pada tahap k = (ongkos yang
dihasilkan pada tahap k + 1) +
(ongkos dari tahap k + 1 ke tahap k )
k
= n, n – 1, …, 1
No comments:
Post a Comment