Program Dinamis

(Dynamic
Programming)
Program Dinamis (dynamic programming):

Program Dinamis (dynamic programming):

1. 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.
2. Terdapat sejumlah berhingga pilihan yang mungkin,
3. Solusi pada setiap tahap dibangun dari hasil solusi tahap sebelumnya,
4. Kita menggunakan persyaratan optimasi dan kendala untuk membatasi
sejumlah pilihan yang harus dipertimbangkan pada suatu tahap.
Prinsip Optimalitas
1. Pada program dinamis, rangkaian keputusan yang optimal dibuat
dengan menggunakan Prinsip Optimalitas.
2. Prinsip Optimalitas: jika solusi total optimal, maka bagian solusi
sampai tahap ke-k juga optimal.
3. Prinsip optimalitas berarti bahwa jika kita bekerja dari tahap k ke
tahap k + 1, kita dapat menggunakan hasil optimal dari tahap k
tanpa harus kembali ke tahap awal.
4. “Ongkos” pada tahap k +1 = (ongkos yang dihasilkan pada tahap k )
+ (ongkos dari tahap k ke tahap k + 1)
Prinsip Optimalitas
6. Hasil dari keputusan yang diambil pada setiap tahap ditransformasikan
dari status yang bersangkutan ke status berikutnya pada tahap
berikutnya.
7. Ongkos (cost) pada suatu tahap meningkat secara teratur (steadily)
dengan bertambahnya jumlah tahapan.
8. Ongkos pada suatu tahap bergantung pada ongkos tahap-tahap yang
sudah berjalan dan ongkos pada tahap tersebut.
9. Keputusan terbaik pada suatu tahap bersifat independen terhadap
keputusan yang dilakukan pada tahap sebelumnya.
10. Adanya hubungan rekursif (pengulangan) yang mengidentifikasikan
keputusan terbaik untuk setiap status pada tahap k memberikan
keputusan terbaik untuk setiap status pada tahap k + 1.
Dua Pendekatan Program Dinamis
Dua pendekatan yang digunakan dalam PD: maju (forward atau up-
down) dan mundur (backward atau bottom-up).
Misalkan x1, x2, …, xn menyatakan peubah (variable) keputusan yang
harus dibuat masing-masing untuk tahap 1, 2, …, n. Maka,
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.
 Dynamic Programming Examples

1. Minimum cost from Sydney to Perth (Shortest path)

2. Economic Feasibility Study
3. 0/1 Knapsack problem (Deterministic Dynamic Programming)
4. Sequence Alignment problem
 Minimum Cost from Sydney to Perth
Based on M. A. Rosenman: Tutorial - Dynamic Programming Formulation
[Link]

• Definisi masalah
– Bepergian dari rumah di Sydney ke hotel di Perth.
– Tiga persinggahan di jalan (3 Stage)
– sejumlah pilihan kota untuk setiap pemberhentian,
– sejumlah hotel untuk dipilih di setiap kota.
– Setiap perjalanan memiliki jarak tempuh yang berbeda sehingga
menghasilkan biaya (bensin) yang berbeda pula.
– Hotel memiliki biaya yang berbeda.
– Tujuannya adalah untuk memilih rute ke dan hotel di Perth
sehingga biaya keseluruhan perjalanan diminimalkan.
 Minimum Cost from Sydney to Perth
• Representasi diagram dari masalah

Stage: 0 (Sydney) 1 2 3 4 (Perth)

50

70 50

Petrol cost 50 70

80 70

70

70

80 60

Hotel cost 60
 Minimum Cost from Sydney to Perth

• Definisi solusi rekursif dalam hal solusi sub-masalah

Optimal function:
V (i, n) = min hotel _ cost (k )+ petrol _ cost ( j, i )+ V ( j, n −1)
j ,k
with base case V (i,0 )= 0
where
n = no pemberhentian,
i. = kota persinggahan n,
j = kota dari mana kita bisa sampai di I,k
k = Hotel dikota i
Minimum Cost from Sydney to Perth
Stage 1 V (i,n) = min hotel _ cost (k )+ petrol _ cost (j,i )+V (j, n −1)
j ,k
start cost from
A 22 + 70 92 S
B 8 + 80 88 S
C 12 + 80 92 S
Minimum Cost from Sydney to Perth
Stage 2
A B C cost from
D 92+8+50=150 88+25+50=163 92+13+50=155 150 A
E 92+10+70=172 88+10+70=168 92+13+70=175 168 B
Minimum Cost from Sydney to Perth
Stage 3
D E cost from
F 150+25+50=225 168+12+50=230 225 D
G 150+30+70=250 168+10+70=248 248 E
H 150+18+70=238 168+8=70=246 238 D
I 150+27+60=237 168+7+60=235 235 E
 Minimum Cost from Sydney to Perth
Stage 4
F G H I cost from
J 225+28+50=303 248+8+50=306 238+20+50=308 235+15+50=300 300 I
K 225+13+70=308 248+10+70=328 238+10+70=318 235+10+70=315 308 F
L 225+15+60=300 248+10+60=318 238+10+60=308 235+7+60=302 300 F
 Minimum Cost from Sydney to Perth
Stage 4
F G H I cost from
J 225+28+50=303 248+8+50=306 238+20+50=308 235+15+50=300 300 I
K 225+13+70=308 248+10+70=328 238+10+70=318 235+10+70=315 308 F
L 225+15+60=300 248+10+60=318 238+10+60=308 235+7+60=302 300 F

• Menghasilkan rute solusi dengan melacak mundur melalui tabel

Solution_1 = {I, J}
 Minimum Cost from Sydney to Perth
Stage 3
D E cost from
F 150+25+50=225 168+12+50=230 225 D
G 150+30+70=250 168+10+70=248 248 E
H 150+18+70=238 168+8=70=246 238 D
I 150+27+60=237 168+7+60=235 235 E

• Menghasilkan rute solusi dengan melacak mundur melalui tabel Solusi _1 = {E, I, J}
 Minimum Cost from Sydney to Perth
Stage 2
A B C cost from
D 92+8+50=150 88+25+50=163 92+13+50=155 150 A
E 92+10+70=172 88+10+70=168 92+13+70=175 168 B

• Menghasilkan rute solusi dengan melacak mundur melalui tabel

Solusi _1 = {B, E, I, J}

• Question: Apa solusi optimal kedua?

 Economic Feasibility Study (studi kelayakan)
Feasibility study adalah studi analisis yang digunakan untuk mengukur
dan menilai tingkat kelayakan pada sebuah proyek. Kegiatan ini
dilakukan untuk dapat mengetahui seberapa layak suatu rencana
proyek tersebut. Feasibility sangatlah penting bagi perusahaan karena
dapat membantu memberitahu persepsi tentang apa saja manfaat
yang diterima dari proyek tersebut.

Waktu tepat untuk perusahaan melakukan feasibility study adalah

pada masa awal proyek dimulai terutama saat tahap desain
perencanaan. Bagi perusahaan ternama, feasibility study dibuat untuk
mengevaluasi dan menguji kelemahan dan kekuatan dari sebuah
rencana proyek secara faktual.

Economic feasibility study juga berperan sebagai tolak ukur

kemampuan proyek dan dapat meningkatkan kredibilitas proyek.
Hasilnya, perusahaan mampu dalam mengambil keputusan, sehingga
nantinya proyek tersebut dapat berdampak positif bagi ekonomi
perusahaan
Economic Feasibility Study (studi kelayakan)
Based on M. A. Rosenman: Tutorial - Dynamic Programming Formulation
[Link]

• Definisi masalah
– dimintai saran tentang cara terbaik memanfaatkan area perkotaan besar di
kota yang sedang berkembang.
– dimisalkan merupakan proyek campuran area perumahan, ritel, kantor
dan hotel.
– Pendapatan sewa adalah fungsi dari luas lantai yang dialokasikan untuk
setiap aktivitas.
– Total luas lantai dibatasi hingga 7 unit.
– Tujuannya adalah untuk menemukan campuran pengembangan
yang akan memaksimalkan pengembalian.
 Economic Feasibility Study
Laba tahunan yang diharapkan untuk area 0-7 unit yang dialokasikan untuk setiap jenis pengembangan dalam
$ 1000
 Economic Feasibility Study
Diagrammatic representation

Step 1) HtORH - ORH = Ht = 7 - 4 = 3

 Economic Feasibility Study
• Definisi solusi rekursif dalam hal solusi sub-masalah Fungsi optimal:
V (n, A)= max R  (n, a )+ V (n −1, A − a )

a=0…A
dengan kasus dasar V (n,0 )= 0
dimana
n adalah nomor tahap yang sesuai dengan tipe pengembangan
1…Housing 2…Retail
3…Office 4…Hotel
A adalah jumlah total unit area yang dialokasikan pada tahap n,
a adalah jumlah satuan luas yang dialokasikan untuk pembangunan tipe n,
R adalah pengembalian yang dihasilkan oleh unit tipe pengembangan n.
 Economic Feasibility Study
V (n, A )= max R
 (n, a )+V (n −1, A − a )


Step 4: H = 7-Ht-O-R = 7-3-0-2 = 2 Step 3) RH - H = R = 7 - 5 = 2 (cek 3+0+2=5 < 7, OK)

Ri adalah pengembalian yang dihasilkan oleh jumlah total unit area yang dialokasikan
pada tahap ke-i.
Di adalah jumlah satuan luas yang dialokasikan pada tahap (i-1)-th.
 Economic Feasibility Study

21 1

Step 2) ORH - RH = Ht = 7 - 2 = 5 (but 3+5 = 8 < 7, Not OK, so O = 0)

 Economic Feasibility Study

Step 1) HtORH - ORH = Ht = 7 - 4 = 3 (< 7, OK)

• Pertanyaan: Dapatkah Anda menghasilkan solusi optimal dengan menelusuri tabel

ke belakang?
 Economic Feasibility Study

• Solution: Housing=2, Retail=2, Office=0, Hotel=3

Maximal return = 33
Pada persoalan ini,
Tahap (k) adalah proses memasukkan barang ke dalam knapsack (ada 3
tahap).
Status (y) menyatakan kapasitas muat knapsack yang tersisa setelah
memasukkan barang pada tahap sebelumnya.

Dari tahap ke-1, kita masukkan objek ke-1 ke dalam knapsack untuk setiap
satuan kapasitas karung sampai batas kapasitas maksimumnya. Karena
kapasitas knapsack adalah bilangan bulat, maka pendekatan ini praktis.
o Misalkan ketika memasukkan objek pada tahap k, kapasitas muat
karung sekarang adalah y – wk.
o Untuk mengisi kapasitas sisanya, kita menerapkan prinsip
optimalitas dengan mengacu pada nilai optimum dari tahap
sebelumnya untuk kapasitas sisa y – wk ( yaitu fk-1(y – wk)).
Tahap (k) adalah proses mengalokasikan dana untuk setiap pabrik (ada
3 tahap, tiap pabrik mendefinisikan sebuah tahap).

Status (xk) menyatakan jumlah modal yang dialokasikan pada pada setiap
tahap (namun terikat bersama semua tahap lainnya).

Alternatif (p) menyatakan proposal proyek yang diusulkan setiap pabrik.

Pabrik 1, 2, dan 3 masing- masing memiliki 3, 4 dan 2 alternatif proposal.

Selanjutnya, kita bandingkan nilai keuntungan dari objek pada tahap k (yaitu pk)
plus nilai fk-1(y – wk) dengan keuntungan pengisian hanya k – 1 macam objek, fk-
1(y).

Jika pk + fk-1(y – wk) lebih kecil dari fk-1(y), maka objek yang ke-k tidak
dimasukkan ke dalam karung, tetapi jika lebih besar, maka objek yang ke-k
dimasukkan.
• Relasi rekurens untuk persoalan ini adalah

f0(y) = 0, y = 0, 1, 2, …, M (basis)
fk(y) = - , y < 0 (basis)

fk(y) = max{fk-1(y), pk + fk-1(y – wk)}, (rekurens)

k = 1, 2, …, n
• fk(y) adalah keuntungan optimum dari persoalan 0/1 Knapsack pada
tahap k untuk kapasitas karung sebesar y.
• f0(y) = 0 adalah nilai dari persoalan knapsack kosong (tidak ada
persoalan knapscak) dengan kapasitas y,
• fk(y) = - adalah nilai dari persoalan knapsack untuk kapasitas
negatif. Solusi optimum dari persoalan 0/1 Knapsack adalah fn(M).
Contoh: n = 3 Tahap 1:
f1(y) = max{f0(y), p1 + f0(y – w1)}
M=5 = max{f0(y), 65 + f0(y – 2)}

Barang ke-i wi pi Solusi Optimum

y f0(y) 65 + f0(y – 2) f1(y) (x1*, x2*, x3*)
1 2 65
2 3 80 0 0 - 0 (0, 0, 0)
3 1 30 1 0 - 0 (0, 0, 0)
2 0 65 65 (1, 0, 0)
3 0 65 65 (1, 0, 0)
4 0 65 65 (1, 0, 0)
5 0 65 65 (1, 0, 0)

fk(y) = max{fk-1(y), pk + fk-1(y – wk)},

Tahap 2:
f2(y) = max{f1(y), p2 + f1(y – w2)}
= max{f1(y), 80 + f1(y – 3)}

Solusi Optimum
y f1(y) 80 + f1(y – 3) f2(y) (x1*, x2*, x3*)
0 0 80 + (- ) = - 0 (0, 0, 0)
1 0 80 + (- ) = - 0 (0, 0, 0)
2 65 80 + (- ) = - 65 (1, 0, 0)
3 65 80 + 0 = 80 80 (0, 1, 0)
4 65 80 + 0 = 80 80 (0, 1, 0)
5 65 80 + 65 = 145 145 (1, 1, 0)
 Tahap 3:
f3(y) = max{f2(y), p3 + f2(y – w3)} == max{f2(y), 30 + f2(y – 1)}

Solusi Optimum
y f2(y) 30 + f2(y – 1) f3(y) (x1*, x2*, x3*)
0 0 30 + (- ) = - 0 (0, 0, 0)
1 0 30 + (- ) = - 0 (0, 0, 0)
2 65 30 + 0 = 30 65 (1, 0, 0)
3 80 30 + 65 = 95 95 (1, 0, 1)
4 80 30 + 80 = 110 110 (0, 1, 1)
5 145 30 + 80 = 110 145 (1, 1, 0)

Solusi optimum X = (1, 1, 0) dengan p = f = 145.

45
 1/0 Knapsack problem
Based on Dr. Shieu-Hong Lin lecture notes:
[Link]

• Problem definition
– Input: satu set S={s1,…, sn} dari item n di mana setiap si
memiliki nilai vi dan bobot wi, dan kapasitas knapsack W.
– Tujuannya adalah untuk memilih subset O dari S sedemikian rupa
sehingga berat total item yang dipilih tidak melebihi W dan
jumlah item vi dalam O maksimal terhadap subset lain yang
memenuhi kendala.
– Perhatikan bahwa setiap item si dipilih atau tidak untuk O.
Question: Apa strategi yang berhasil untuk menemukan solusi
optimal jika kita diizinkan untuk menambahkan pecahan xi dari setiap
item ke ransel?
 1/0 Knapsack problem
• Uraikan masalah menjadi masalah yang lebih kecil.
• Mari kita asumsikan urutan item S={s1, s2, s3, …, sn}.
• Misalkan solusi optimal untuk S dan W adalah himpunan bagian O={s2, s4, sk}, di mana
sk adalah item bernomor tertinggi dalam urutan item:
S={s1, s2, s3, s4, …, sk-1, sk, …,sn}
• Maka, O-{sk} adalah solusi optimal untuk sub-masalah Sk-1={s1, …, sk-1} dan kapasitas
W-wk.
• Nilai dari masalah lengkap S hanya akan menjadi nilai yang dihitung untuk sub-masalah
Sk-1 ini ditambah nilai vk.
 1/0 Knapsack problem
• Definisi solusi rekursif dalam hal solusi sub-masalah.
Buat matriks V[0..n, 0..W].
Untuk 0≤i≤n, dan 0≤w≤W, entri V[i, w] akan menyimpan nilai maksimum (gabungan) dari setiap
subset item {1, 2, …, i} dari bobot (gabungan) pada kebanyakan w.
Setiap nilai V(i,w) mewakili solusi optimal untuk sub-masalah ini: Berapa nilainya jika bobot
ransel kita hanya w dan kita hanya memilih di antara k item pertama?
Jika kita dapat menghitung semua entri larik ini, maka entri larik V(n, W) akan berisi bobot
maksimal (paling banyak W) item yang dipilih dari seluruh himpunan S, yaitu, solusi untuk
masalah kita.
 1/0 Knapsack problem
• Definisi solusi rekursif dalam hal solusi sub-masalah Fungsi optimal:

leave item i take item i

V (i, w ) = max V (i −1, w ), vi + V (i −1, w − wi )
for 1  i  n, 0  w  W

with base cases

V (0, w ) = 0
V (i, w) = 0 for w  0
 1/0 Knapsack problem
• Perhitungan dari bawah ke atas :
V (0, w) = 0 for all 0  w  W , V (i,0) = 0 for 1  i  n

Hitung tabelnya menggunakan

V (i, w ) = max V
 (i −1, w ), vi + V (i −1, w − wi ) , for 1  i  n, 0  w  W
baris demi baris.
 1/0 Knapsack problem
• Contoh: Misalkan W = 10 (kapasitas Maximal)

• Output akhir V(4, 10)=90.

Question: Bagaimana kita menemukan subset item yang optimal?
 1/0 Knapsack problem
• Memulihkan item yang menghasilkan nilai optimal:
• – Mulai dari V[n, W] dan lacak mundur melalui tabel.
Remind: V (i, w ) = max  (i −1, w ), vi +V (i −1, w − wi )
V
1in,0wW

– If V(i, w)=V(i-1, w) maka item sk tidak ditambahkan ke knapsack, Lanjutkan jejaknya di

V[i-1, w].
– If V(i, w)>V(i-1, w) then item sk was added to the knapsack. maka item sk ditambahkan ke
knapsack. di Lanjutkan jejak satu baris lebih tinggi di V(i-1, w-wi).

• Subset optimal adalah O={2, 4} dalam kasus ini.