Multi
Stage 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 dibanding kebanyakan model dan
metode matematik dalam riset operasi. Dynamic
Programming digunakan untuk menyelesaikan masalah seperti : Alokasi, Muatan
(Cargo - Loading), Capital Budgeting,
Pengendalian 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).
Masalah Alokasi
Keuntungan pada empat macam
kegiatan merupakan fungsi dari jam kerja yang dialokasikan pada masing-masing
kegiatan dituangkan dalam tabel di bawah ini . Jika setiap hari tersedia 4 jam
kerja, bagaimana alokasi waktu sehingga keuntungan perharinya maksimum ???
•
Kegiatan à Tahap ( stage )
•
Xj à adalah banyaknya jam kerja
yang dialokasikan pada tahap j.
•
Pj(Xj) adalah
keuntungan dari alokasi X jam kerja pd kegiatan j.
•
Maks :
Z = P1(X1) + P2(X2) + P3(X3)
+ P4(X4)
•
Kendala : X1 + X2 + X3
+ X4 = 4 dan X1 , X2, X3 , X4
≥ 0
State ( keadaan) nya disimbolkan dengan Yj
, dimana :
1. Y1
= juml jam kerja yang disediakan pada tahap 1,2,3,4.
2. Y2
= juml jam kerja yang disediakan pada tahap 2,3,4.
3. Y3
= juml jam kerja yang disediakan pada tahap 3,4.
4. Y4
= juml jam kerja yang disediakan pada tahap 4.
Sedangkan fungsi keuntungan tiap stage (tahap)
adalah :
1. f*4(Y4)=
keuntungan optimum pada tahap 4 denganY4 tertentu.
2. f*3(Y3)=
keuntungan optimum pada tahap 3,4 dengan Y3 tertentu.
3. f*2(Y2)=
keuntungan optimum pada tahap 2,3,4 dengan Y2 tertentu.
4. f*1(Y1)=
keuntungan optimum pada tahap 1,2,3,4 dengan Y1 tertentu.
Tahap
1 : f*1(Y1) = maks
{P1(X1) + f*2(Y2) }
Tahap 2 : f*2(Y2) =
maks {P2(X2) + f*3(Y3)
}
Tahap
3 : f*3(Y3) =maks
{P3(X3) + f*4(Y4) }
Tahap
4 : f*4(Y4)
=maks {P4(X4)} dgn f5(Y5) = 0
Jadi
keuntungan maks adalah 12, dengan beberapa alokasi alternatif sebagai berkut :
Masalah Muatan (Cargo -
Loading)
Sebuah perusahaan angkutan
sedang mempertimbangkan mengangkut 3 jenis barang. Berat masing-masing barang
dan biaya angkutannya seperti pada tabel di bawah . Armada tersebut memiliki
kapasitas maks. W = 5 ton. Barang apa saja yang harus diangkut dan berapa
banyaknya agar penerimaan maksimum ??
SUMBER :
Mulyono. Sri, S.E.,M.Sc. Riset Operasional.
Fakultas Ekonomi Universitas Indonesia. 2002.
