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
untuk analisis 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.
DOWNLOAD FULL PAGE
No comments:
Post a Comment