Pemrograman Dinamis_Teori Optimasi


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 = 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

Pemrograman Dinamis_Teori Optimasi Rating: 4.5 Diposkan Oleh: Unknown

No comments: