Pemrograman Dinamis

Pemrograman Dinamis (PD; Ingg. dynamic programming, DP) — adalah metode penyelesaian masalah optimasi yang kompleks, berdasarkan pemecahan masalah asal menjadi serangkaian submasalah yang lebih sederhana. Metode ini diterapkan pada proses pengambilan keputusan bertahap, di mana solusi optimal dari keseluruhan masalah dapat dibangun dari solusi optimal submasalah-submasalahnya.

Istilah ini diperkenalkan oleh matematikawan Amerika Richard Bellman pada tahun 1950-an. Dalam konteks ini, kata «pemrograman» digunakan dalam arti «perencanaan» atau «penyusunan rencana tindakan yang optimal», bukan penulisan kode komputer.

Sifat-Sifat dan Teorema Utama

Aplikabilitas pemrograman dinamis pada suatu masalah ditentukan oleh adanya dua sifat fundamental.

Prinsip Optimalitas Bellman

Konsep sentral dari metode ini adalah prinsip optimalitas Bellman (Ingg. Bellman's principle of optimality). Prinsip ini menyatakan: bagaimanapun kondisi awal dan keputusan awal, keputusan-keputusan selanjutnya harus membentuk strategi optimal terhadap kondisi yang diperoleh sebagai hasil keputusan pertama.

Dengan kata lain, setiap bagian dari lintasan optimal itu sendiri merupakan lintasan yang optimal. Sifat ini memungkinkan pemecahan masalah umum menjadi serangkaian submasalah yang lebih sederhana dan menyelesaikannya secara rekursif.

Submasalah yang Saling Tumpang Tindih

Suatu masalah memiliki sifat submasalah yang saling tumpang tindih (Ingg. overlapping subproblems), jika dalam penyelesaiannya secara rekursif, submasalah yang sama muncul berulang kali. PD memungkinkan untuk menghindari komputasi berulang dengan menyimpan solusi dari submasalah yang telah ditemui (teknik ini disebut memoisasi atau tabulasi), sehingga secara signifikan meningkatkan efisiensi dibandingkan dengan rekursi naif.

Persamaan Bellman

Dari prinsip optimalitas diturunkan relasi rekuren utama dari metode ini — persamaan Bellman. Persamaan ini menghubungkan «nilai» (keuntungan atau biaya optimal) dari kondisi saat ini dengan nilai-nilai kondisi selanjutnya. Dalam bentuk umum untuk proses bertahap deterministik dengan fungsi tujuan aditif, persamaan ini berbentuk:

$V_{k-1}(x)=\underset{y\in U(x)}{max}\{{\phi }_k(x,y)+V_k(f_k(x,y))\}$

di mana:

• $k$ — nomor langkah (dari $m$ hingga 1);
• $x$ — kondisi sistem pada langkah $k-1$;
• $y$ — keputusan yang dikendalikan, diambil pada langkah $k$;
• ${\phi }_k(x,y)$ — keuntungan (atau biaya) pada langkah ke-k;
• $f_k(x,y)$ — fungsi yang mendefinisikan kondisi baru sistem;
• $V_k(s)$ — nilai optimal dari fungsi tujuan untuk submasalah yang dimulai pada langkah $k$ dalam kondisi $s$.

Persamaan diselesaikan secara berurutan, umumnya «dari akhir», bergerak dari langkah terakhir ke langkah pertama.

Contoh Penerapan

• Masalah lintasan terpendek dalam graf: Masalah ini memiliki sifat substruktur optimal, karena setiap bagian dari lintasan terpendek itu sendiri merupakan lintasan terpendek. Algoritma Bellman-Ford dan Floyd-Warshall adalah contoh klasik penerapan PD untuk menyelesaikan masalah ini.
• Masalah ransel (knapsack problem): Masalah pengisian ransel berkapasitas terbatas secara optimal dengan benda-benda yang memiliki nilai dan berat berbeda. PD memungkinkan penyelesaian masalah ini dengan mempertimbangkan benda-benda secara berurutan dan menghitung pada setiap langkah nilai maksimum untuk semua kemungkinan nilai kapasitas yang tersisa.
• Masalah alokasi sumber daya: Pendistribusian sumber daya yang terbatas (misalnya, investasi) di antara beberapa proyek untuk memaksimalkan efek total.

Keterbatasan

Keterbatasan utama dari metode ini adalah kutukan dimensi (Ingg. curse of dimensionality) — istilah yang diperkenalkan oleh Bellman untuk menggambarkan pertumbuhan eksponensial jumlah kondisi dan, sebagai akibatnya, kompleksitas komputasi, seiring bertambahnya jumlah variabel yang mendeskripsikan kondisi sistem. Hal ini membatasi penerapan praktis PD eksak untuk masalah-masalah berdimensi sangat besar.

Konsep Terkait

• Riset operasi
• Teori kendali optimal
• Proses keputusan Markov (generalisasi stokastik)
• Persamaan Hamilton — Jacobi — Bellman (analog untuk waktu kontinu)

Catatan

</references>