21.03
Program dinamis (dynamic programming) merupakan suatu metode pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan langkah (step) atau tahapan (stage) sedemikian sehingga solusi dari persoalan dapat dipandang dari serangkaian keputusan yang saling berkaitan. Pada penyelesaian persoalan dengan metode ini terdapat sejumlah berhingga pilihan yang mungkin, solusi pada setiap tahap dibangun dari hasil solusi tahap sebelumnya, dan menggunakan persyaratan optimasi dan kendala untuk membatasi sejumlah pilihan yang harus dipertimbangkan pada suatu tahap. Krakteristik program dinamis adalah sebagai berikut:
1. Persoalan dapat dibagi menjadi beberapa tahap (stage), yang pada setiap tahap hanya diambil satu keputusan.
2. Masing-masing tahap terdiri dari sejumlah status (state) yang berhubungan dengan tahap tersebut. Secara umum, status merupakan bermacam kemungkinan masukan yang ada pada tahap tersebut.
3. Hasil dari keputusan yang diambil pada setiap tahap ditransformasikan dari status yang bersangkutan ke status berikutnya pada tahap berikutnya.
4. Ongkos (cost) pada suatu tahap meningkat secara teratur (steadily) dengan bertambahnya jumlah tahapan.
5. Ongkos pada suatu tahap bergantung pada ongkos tahap-tahap yang sudah berjalan dan ongkos pada tahap tersebut.
6. Keputusan terbaik pada suatu tahap bersifat independen terhadap keputusan yang dilakukan pada tahap sebelumnya.
7. Adanya hubungan rekursif yang mengidentifikasikan keputusan terbaik untuk setiap status pada tahap k memberikan keputusan terbaik untuk setiap status pada tahap k + 1.
8. Prinsip optimalitas berlaku pada persoalan tersebut.
Terdapat dua solusi pendekatan programa dinamis, yaitu pendekatan maju (forward atau up-down) dan pendekatan mundur (backward atau bottom-up).
1. 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.
2. 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.
Konsep dasar programa dinamis adalah sebagai berikut:
• Berdasarkan prinsip optimisasi Bellman (1950):
An optimal policy has the property that whatever the initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision
• Suatu masalah dapat dibagi menjadi beberapa tahap
• Dalam rangkaian keputusan yang telah diambil, hasil dari masing-masing terpengaruh pada hasil keputusan sebelumnya.
• Rangkaian keputusan yang diambil mesti membentuk kebijakan yang optimal secara keseluruhan.
• Bagi tahap persoalan yang masih tersisa kita diizinkan mengambil keputusan yang layak tanpa tergantung dari keputusan-keputusan yang telah diambil sebelumnya èoptimisasi prinsip.
• Prosedur pemecahan masalah dalam program dinamik dilakukan secara rekursif
• Pada setiap tahap, nilai keadaan tahap sebelumnya merupakan masukan untuk tahap sekarang dan keluarannya menjadi masukan untuk tahap berikutnya. Pada setiap tahap kita diharuskan mengambil keputusan optimal.
Sumber:mufidnilmada.staff.gunadarma.ac.id/.../files/.../Program+Dinamis.ppt, www.mie.unja.ac.id/pustaka/risetop.ppt
1. Persoalan dapat dibagi menjadi beberapa tahap (stage), yang pada setiap tahap hanya diambil satu keputusan.
2. Masing-masing tahap terdiri dari sejumlah status (state) yang berhubungan dengan tahap tersebut. Secara umum, status merupakan bermacam kemungkinan masukan yang ada pada tahap tersebut.
3. Hasil dari keputusan yang diambil pada setiap tahap ditransformasikan dari status yang bersangkutan ke status berikutnya pada tahap berikutnya.
4. Ongkos (cost) pada suatu tahap meningkat secara teratur (steadily) dengan bertambahnya jumlah tahapan.
5. Ongkos pada suatu tahap bergantung pada ongkos tahap-tahap yang sudah berjalan dan ongkos pada tahap tersebut.
6. Keputusan terbaik pada suatu tahap bersifat independen terhadap keputusan yang dilakukan pada tahap sebelumnya.
7. Adanya hubungan rekursif yang mengidentifikasikan keputusan terbaik untuk setiap status pada tahap k memberikan keputusan terbaik untuk setiap status pada tahap k + 1.
8. Prinsip optimalitas berlaku pada persoalan tersebut.
Terdapat dua solusi pendekatan programa dinamis, yaitu pendekatan maju (forward atau up-down) dan pendekatan mundur (backward atau bottom-up).
1. 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.
2. 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.
Konsep dasar programa dinamis adalah sebagai berikut:
• Berdasarkan prinsip optimisasi Bellman (1950):
An optimal policy has the property that whatever the initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision
• Suatu masalah dapat dibagi menjadi beberapa tahap
• Dalam rangkaian keputusan yang telah diambil, hasil dari masing-masing terpengaruh pada hasil keputusan sebelumnya.
• Rangkaian keputusan yang diambil mesti membentuk kebijakan yang optimal secara keseluruhan.
• Bagi tahap persoalan yang masih tersisa kita diizinkan mengambil keputusan yang layak tanpa tergantung dari keputusan-keputusan yang telah diambil sebelumnya èoptimisasi prinsip.
• Prosedur pemecahan masalah dalam program dinamik dilakukan secara rekursif
• Pada setiap tahap, nilai keadaan tahap sebelumnya merupakan masukan untuk tahap sekarang dan keluarannya menjadi masukan untuk tahap berikutnya. Pada setiap tahap kita diharuskan mengambil keputusan optimal.
Sumber:mufidnilmada.staff.gunadarma.ac.id/.../files/.../Program+Dinamis.ppt, www.mie.unja.ac.id/pustaka/risetop.ppt
0 Responses to "Programa Dinamis"
Posting Komentar