Dynamic Programming
(Pemrograman Dinamik)
Penelitian Operasional (Pertemuan 15)
Pendahuluan
▪ Program dinamik adalah suatu teknik matematik untuk menentukan serangkaian
keputusan yang saling terkait, serta memberikan suatu prosedur yang sistematik
untuk menentukan kombinasi optimal dari keputusan yang hendak ditentukan itu.
▪ Perbedaan antara program dinamik dengan program linear adalah:
▪ Pada masalah program dinamik tidak terdapat rumusan matematika secara baku
▪ Progam dinamik adalah suatu tipe penyelesaian masalah yang didekati secara umum.
Model Keputusan Pemrograman Dinamis
▪ Tahap (stage): titik suatu keputusan
Model Keputusan Tahap Majemuk
▪ Status (state): parameter masukan
▪ Transformasi (transformation): aturan yang mengarahkan
Tahap
1
… Tahap
n-1
Tahap
n
Tahap
n+1
… Tahap
N
keputusan
Xn
Keputusan (decision)
~
Sn
𝑺n
Model Keputusan Tahap Masukan/Status input Tahap Keluaran/Status Output
Tunggal (Input State) (n) (Output State)
Transformasi/Fungsi Kontribusi
(Contribution Function)
𝒈𝒏 = 𝒓𝒏(𝑺𝒏, 𝑿𝒏)
Pendekatan Pemrograman Dinamis
1. Pemrograman Dinamis Maju. Pemrograman dinamis bergerak mulai dari tahap
1, terus maju ke tahap 2, 3, dan seterusnya sampai tahap n. Runtunan peubah
keputusan adalah X1, X2,…, Xn.
X1 Xn-1 Xn Xn+1 XN
Sn
Tahap … Tahap Tahap
Sn
Tahap Sn+1
… Tahap
~ 1 ~ n-1 ~ ~ ~
𝑺1 S1
𝑺n-1 𝑺n n
𝑺n+1 n+1
𝑺N
N SN
g1 gn-1 gn gn+1 gN
Pendekatan Pemrograman Dinamis
2. Pemrograman Dinamis Mundur. Pemrograman 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.
X1 Xn-1 Xn Xn+1 XN
Sn
Tahap … Tahap Tahap
Sn
Tahap Sn+1
… Tahap
~ 1 ~ n-1 ~ ~ ~
𝑺1 S1
𝑺n-1 𝑺n n
𝑺n+1 n+1
𝑺N
N SN
g1 gn-1 gn gn+1 gN
Tahap (n)
Variabel Status
(Sn)
Variabel
Keputusan (Xn)
Komponen .
Fungsi kontribusi
Maju
Prosedur
Fungsi Transisi
Pemrograman Pemecahan
Dinamis Mundur
Deterministik Hubungan
rekursif
Minimasi Ongkos
Maksimasi
Tipe Persoalan
Income
Penugasan
Langkah-Langkah Pemecahan Masalah Pemrograman
Dinamis
1. Tentukan prosedur pemecahan (maju atau mundur)
2. Definisikan tahap (n)
3. Definisikan variabel status pada tiap tahap (Sn)
4. Definisikan variabel keputusan pada tiap tahap (Xn)
5. Definisikan fungsi kontribusi pada tiap tahap.
6. Definisikan fungsi transisi
7. Definisikan hubungan rekursif
8. Lakukan perhitungan
9. Tentukan kebijakan optimal
Tahap (n)
Contoh Kasus
Variabel Status
(Sn)
Variabel
Keputusan (Xn)
Komponen .
Fungsi kontribusi
Maju
Prosedur
Fungsi Transisi
Pemrograman Pemecahan
Dinamis Mundur
Deterministik Hubungan
rekursif
Minimasi Ongkos
Maksimasi
Tipe Persoalan
Income
Penugasan
Kasus Minimasi Cost
▪ Seorang pengusaha yang akan pergi dari kota A ke kota J dengan menggunakan
kendaraan umum.
▪ Banyak kemungkinan jalan yang dapat digunakan dari A menuju J.
▪ Pengusaha tersebut menginginkan perjalanan dari A menuju J dengan biaya paling
murah.
Kasus Minimasi Cost
▪ Besar biaya dan rute jalan dari A menuju J disajikan dengan gambar berikut:
▪ Definisi masalah:
Tahap/stage (n) : daerah simpul
Status/kondisi tahap n : Sn = kota pada tahap n
Keputusan pada tahap n : Xn = kota yang harus ditempuh
Fungsi transisi : Sn+1 = Xn
Fungsi kontribusi pada tahap n : gn = Cs(Xn)
Hubungan rekursif : fn*(Sn) = min fn(Sn,Xn)
dengan
fn(Sn,Xn) = Cs(Xn); n = 4
fn(Sn,Xn) = Cs(Xn) + fn+1*(Xn); n = 1,2,3
Sn+1 = Xn
n=1 n=2 n=3 n=4
Tahap 4
Pada tahap akhir n = 4, maka perjalanannya hanya
ditentukan sepenuhnya oleh kondisi s sekarang (yaitu H
atau I) dan tujuan akhir J sehingga f4*(s) = f4(s,J) =
Cs(J).
Pada tahap akhir n = 4 hasil ditabelkan
sebagai berikut:
f 4 = C4
S f4*(S) X4*
J
H 3 3 J
I 4 4 J
Tabel di atas menyajikan fakta bahwa jika
pebisnis sudah sampai di H maupun di I maka
solusi feasible nya adalah X4* = J n=1 n=2 n=3 n=4
f 4 = C4
S f4*(S) X4*
J
Tahap 3 H 3 3 J
I 4 4 J
Pada tahap n = 3, maka perjalanannya perlu melakukan
beberapa hitungan. Misal sudah sampai di kota F, maka
dia bisa menuju ke kota H atau I, dengan biaya pada
tahap ini adalah Cf(H) = 6 atau Cf(I) = 3.
Pada tahap akhir n = 3 hasil ditabelkan sebagai
berikut:
f3 = C3+f3*
S f3*(S) X3*
H I
E 1+3=4 4+4=8 4 H
F 6+3=9 3+4=7 7 I
G 3+3=6 3+4=7 6 H
n=1 n=2 n=3 n=4
f3 = C3+f3*
S f3*(S) X3*
H I
E 4 8 4 H
Tahap 2 F 9 7 7 I
G 6 7 6 H
Pada tahap akhir n = 2 hasil ditabelkan sebagai berikut:
f2 = C2+f2*
S f2*(S) X2*
E F G
B 7+4=11 4+7=11 6+6=12 11 E,F
C 3+4=7 2+7=9 4+6=10 7 E
D 4+4=8 1+7=8 5+6=11 8 E,F
n=1 n=2 n=3 n=4
f2 = C2+f2*
S f2*(S) X2*
E F G
B 11 11 12 11 E,F
Tahap 1 C 7 9 10 7 E
D 8 8 11 8 E,F
Pada tahap akhir n = 1 hasil ditabelkan sebagai berikut:
f1 = C1+f1*
S f1*(S) X1*
B C D
A 2+11=13 4+7=11 3+8=11 11 C,D
n=1 n=2 n=3 n=4
f3 = C3+f3*
f 4 = C4 S/X3 f3*(S) X3*
S/X4 f4*(S) X4* H I
J
E 4 8 4 H
H 3 3 J F 9 7 7 I
I 4 4 J G 6 7 6 H
f2 = C2+f2*
S/X2 f2*(S) X2*
E F G f1 = C1+f1*
S/X1 f1*(S) X1*
B 11 11 12 11 E,F B C D
C 7 9 10 7 E A 13 11 11 11 C,D
D 8 8 11 8 E,F
Lintasan 1: A – C – E – H – J
Lintasan 2: A – D – E – H – J
Lintasan 3: A – D – F – I – J
n=1 n=2 n=3 n=4
Lintasan 1: A – C – E – H – J
Lintasan 2: A – D – E – H – J
Lintasan 3: A – D – F – I – J
Tahap (n)
Contoh Kasus
Variabel Status
(Sn)
Variabel
Keputusan (Xn)
Komponen .
Fungsi kontribusi
Maju
Prosedur
Fungsi Transisi
Pemrograman Pemecahan
Dinamis Mundur
Deterministik Hubungan
rekursif
Minimasi Ongkos
Maksimasi
Tipe Persoalan
Income
Penugasan
Kasus Maksimasi Income (Return)
▪ Sebuah perusahaan memiliki kapasitas produksi sebesar 700 ton per bulan.
Distribusi produk dilakukan melalui transportasi darat dan untuk menghemat
biaya pengirimannya. Pasar yang dituju adalah pasar A, B, dan C.
▪ Dari pengalaman yang ada, return dari setiap pasar dilihat pada table berikut:
Jumlah Produk Return dari kota A Return dari kota B Return dari kota C
(ratus ton) (Rp) (Rp) (Rp)
Bagaimana distribusi
0 0 0 0
produk harus dilakukan
1 0.8 0.6 0.6 agar diperoleh hasil atau
2 1.5 1.2 1..2 return yang optimal?
3 2.3 2 1.9
4 3 2.8 2.8
5 3.6 3.6 3.6
6 4 4 4.7
7 4.4 4.3 5.4
Kasus Maksimasi Income (Return)
▪ Definisi Masalah:
Tahap : n = pasar yang dituju ▪ Perhitungan akan dimulai dari pasar A, B, dan
diakhiri dengan perhitungan return di pasar C.
Status/kondisi tahap n : Sn = jumlah hasil produksi yang
Dengan persamaan dasar:
masih tersisa pada tahap n
Keputusan pada tahap n : Xn = jumlah (dalam ratusan ton) 𝐹𝑛(𝑋 ) = max{𝑟𝑛(𝑋𝑛) + 𝑓𝑛−1(𝑋 − 𝑋𝑎)}
barang yang didistribusikan untuk tahap n ▪ Dengan persamaan dasar di atas, berarti nilai
f1(X) akan menentukan nilai f2(X), dan nilai f2(X)
Fungsi transisi : Sn-1 = Sn – Xn
akan menentukan nilai f3(X).
Fungsi kontribusi pada tahap n : gn = rn(Xn); rn = return
pada tahap n
Hubungan rekursif : fn*(Sn) = max fn(Sn,Xn); dengan
fn(Sn,Xn) = rs(Xn); n = 1
fn(Sn,Xn) = rs(Xn)+fn-1*(Sn-1); n = 2,3
Tahap 1
▪ Bila semua produk hanya dipasarkan di kota A, maka return atau penghasilan yang diperoleh mulai dari ada
pengiriman hingga 7 kiriman (setiap pengiriman berisi 100 ton), adalah:
Jika tidak ada pengiriman f1(0) = r1 = 0
Jika ada 1 pengiriman f1(1) = r1(1) = 0.8
dst.
Jumlah Produk Return dari kota A Return dari kota B Return dari kota C
(ratus ton) (Rp) (Rp) (Rp)
0 0 0 0
1 0.8 0.6 0.6
2 1.5 1.2 1..2
3 2.3 2 1.9
4 3 2.8 2.8
5 3.6 3.6 3.6
6 4 4 4.7
7 4.4 4.3 5.4
Tahap 1: Kota A
f1(S) = r1(X) Jumlah Return dari
S/X1 f1* x1* Produk kota A
0 1 2 3 4 5 6 7 (ratus ton) (Rp)
0 0 0 0 0 0
1 0 0.8 0.8 1 1 0.8
2 0 0.8 1.5 1.5 2 2 1.5
3 0 0.8 1.5 2.3 2.3 3 3 2.3
4 0 0.8 1.5 2.3 3 3 4 4 3
5 0 0.8 1.5 2.3 3 3.6 3.6 5 5 3.6
6 0 0.8 1.5 2.3 3 3.6 4 4 6 6 4
7 0 0.8 1.5 2.3 3 3.6 4 4.4 4.4 7 7 4.4
f1(S) = r1(X) Jumlah Produk Return dari kota B
S/X1 f1* x1*
Tahap 2: Kota B 0 1 2 3 4 5 6 7 (ratus ton) (Rp)
0 0 0 0 0 0
1 0 0.8 0.8 1 1 0.6
2 0 0.8 1.5 1.5 2 2 1.2
3 0 0.8 1.5 2.3 2.3 3 3 2
4 0 0.8 1.5 2.3 3 3 4 4 2.8
5 0 0.8 1.5 2.3 3 3.6 3.6 5 5 3.6
6 0 0.8 1.5 2.3 3 3.6 4 4 6 6 4
7 0 0.8 1.5 2.3 3 3.6 4 4.4 4.4 7 7 4.3
f2(S) = r2(X)+f2(S-X2)
S/X2 f2* x2*
0 1 2 3 4 5 6 7
0 0+ 0 0
1 0+0.8=0.8 0.6+0=0.6 0.8 0
2 0+1.5=1.5 0.6+0.8=1.4 1.2+0=1.2 1.5 0
3 0+2.3=2.3 0.6+1.5=2.1 1.2+0.8=2 2+0=2 2.3 0
4 0+3=3 0.6+2.3=2.9 1.2+1.5=2.7 2+0.8=2.8 2.8+0=2.8 3 0
5 0+3.6=3.6 0.6+3=3.6 1.2+2.3=3.5 2+1.5=3.5 2.8+0.8=3.6 3.6+0=3.6 3.6 0,1,4,5
6 0+4=4 0.6+3.6=4.2 1.2+3=4.2 2+2.3=4.3 2.8+1.5=4.3 3.6+0.8=4.4 4+0=4 4.4 5
7 0+4.4=4.4 0.6+4=4.6 1.2+3.6=4.8 2+3=5 2.8+2.3=5.1 3.6+1.5=5.1 4+0.8=4.8 4.3+0=4.3 5.1 4,5
f2(S) = r2(X)+f2(S-X2) Jumlah Produk Return dari kota C
Tahap 3: S/X2
0 1 2 3 4 5 6 7
f2* x2*
(ratus ton) (Rp)
Kota C 0 0 0 0 0 0
1 0.8 0.6 0.8 0 1 0.6
2 1.5 1.4 1.2 1.5 0
2 1..2
3 2.3 2.1 2 2 2.3 0
3 1.9
4 3 2.9 2.7 2.8 2.8 3 0
4 2.8
5 3.6 3.6 3.5 3.5 3.6 3.6 3.6 0,1,4,5
5 3.6
6 4 4.2 4.2 4.3 4.3 4.4 4 4.4 5 6 4.7
7 4.4 4.6 4.8 5 5.1 5.1 4.8 4.3 5.1 4,5
7 5.4
f3(S) = r3(X)+f3(S-X3)
S/X3 f3* x3*
0 1 2 3 4 5 6 7
0 0+ 0 0
1 0+0.8=0.8 0.6+0=0.6 0.8 0
2 0+1.5=1.5 0.6+0.8=1.4 1.2+0=1.2 1.5 0
3 0+2.3=2.3 0.6+1.5=2.1 1.2+0.8=2 1.9+0=1.9 2.3 0
4 0+3=3 0.6+2.3=2.9 1.2+1.5=2.7 1.9+0.8=2.7 2.8+0=2.8 3 0
5 0+3.6=3.6 0.6+3=3.6 1.2+2.3=3.5 1.9+1.5=3.4 2.8+0.8=3.6 3.6+0=3.6 3.6 0,1,4,5
6 0+4.4=4.4 0.6+3.6=4.2 1.2+3=4.2 1.9+2.3=4.2 2.8+1.5=4.3 3.6+0.8=4.4 4.7+0=4.7 4.7 6
7 0+5.1=5.1 0.6+4.4=5 1.2+3.6=4.8 1.9+3=4.9 2.8+2.3=5.1 3.6+1.5=5.1 4.7+0.8=5.5 5.4+0=5.4 5.5 6
Kasus Maksimasi Income (Return)
▪ Dengan cara yang sama, apabila diteruskan dengan 4 pengiriman, 5 pengiriman, hingga 7 pengiriman maka
akan diperoleh tabel sebagai berikut:
Pasar A Pasar B Pasar C
S
f1* x1* f2* x2* f3* x3*
0 0 0 0 0 0 0
1 0.8 1 0.8 0 0.8 0
2 1.5 2 1.5 0 1.5 0
3 2.3 3 2.3 0 2.3 0
4 3 4 3 0 3 0
5 3.6 5 3.6 0,1,4,5 3.6 0,1,4,5
6 4 6 4.4 5 4.7 6
7 4.4 7 5.1 4,5 5.5 6
Contoh Soal:
Contoh Soal