Multi stage (Dynamic) Programming

Pada umumnya permasalahan riset operasi diselesaikan dengan serangan tunggal arinya seluruh atau semua persoalan diselesaikan dengan sekali pukul. Namun sering terdapat masalah yang hanya dapat diselesaikan dengan memecahkan menjadi bagian-bagian kecil yang kemudian menggabungkannya kembali untuk mendapatkan jawaban yang diinginkan.
Multi stage programming lebih dikenal dengan nama dynamic programming, karena kegunaannya melibatkan pengambilan keputusan yang melewati waktu. Namun, pada situasi lain dimana waktu bukan sebagai faktor. Dynamic programming dikenalkan oleh Ricard Bellman. Dynamic programming lebih luwes disbanding kebanyakan model dan metode matematik dalam riset operasi. Dynamic programming digunakan untuk menyelesaikan masalah seperti: alokasi, muatan, (knapsack), capital budgeting, pengawasan persediaan dll.
Ciri-ciri pokok masalah dynamic programming
a. Keputusan tentang suatu masalah ditandai dengan optimasi pada tahap berikutnya, bukan keserentakan.
b. Berkaitan dengan masalah dimana pilihan atau keputusan dibuat pada masing-masing tahap.
c. Setiap keputusan pada setiap tahap adalah return function yang mengevaluasi pilihan yang dibuat dalam arti sumbangan yang diberikan kepada tujuan keseluruhan (maks / min)
d. Setiap tahap keputusan dihubungkan dengan tahap yang berdekatan melalui fungsi transisi. Fungsi ini berupa kuantitas diskrit maupun kontinu tergantung sifat masalahnya.
e. Suatu hubungan rekursif digunakan untuk menghubungkan kebijaksanaan optimum pada tahap n dengan n-1. Ada dua macam prosedur rekursif yaitu foreward dan backward.

Penerapan dynamic programming
Masalah dynamic programming tak ada formulasi matemati yang baku. Pada umunya, persamaan rekrusif melibatkan dua jenis perhitungan, sesuai dengan sistemnya kontinu atau diskrit. Dalam kasus pertama keputusan optimum pada setiap saat diperoleh dengan menggunakan metode optimasi klasik biasa. Dalam kasus kedua, digunakan perhitungan tabel. Banyaknya baris dalam setiap tabel sama dengan banyaknya state an banyaknya kolom sama dengan banyaknya alternative (keputusan yang mungkin).

Sumber;
Mulyono. Sri, S.E.,M.Sc. Riset Operasional. Fakultas Ekonomi Universitas Indonesia. 2002.