Dynamic Programming
PROGRAM
DINAMIS (Dynamic Programming)
2.1 Dasar
Teori Dynamic Programming (Program Dinamis)
Program
dinamis adalah suatu teknik matematis yang biasanya digunakan untuk
membuat suatu keputusan dari serangkaian keputusan yang saling berkaitan. Dalam
hal ini program dinamis menyediakan prosedur sistematis untuk menentukan
kombinasi keputusan yang optimal. 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:
1. Stage (tahap)
adalah bagian persoalan yang mengandung decision variable.
2. Alternatif,
pada setiap stage terdapat decision variable dan fungsi tujuan
yang menentukan besarnya nilai setiap alternative.
3. 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.
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 yaitu 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.
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 untukanalisis
sensitivitas.
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.
Sumber : http://mohamadrisalrozakamakali.blogspot.com/2013/05/program-dinamis-dynamic-programming.html
0 komentar:
Posting Komentar