Bahan kuliah
Riset Operasional
DYNAMIC PROGRAMMING
(OPTIMUM PATH PROBLEM)
Oleh:
Darmansyah Tjitradi, MT.
PROGRAM MAGISTER TEKNIK SIPIL
UNLAM
2005
1
Background Dynamic Programming
Metode ini dikembangkan oleh Richard E.
Bellman pada tahun 1957.
Programasi Dinamis adalah suatu
kumpulan teknik-teknik programasi
matematis yang digunakan untuk
mengambil keputusan yang terdiri dari
banyak tahap (multistage).
Dalam programasi dinamis tidak ada
rumusan (formulasi) matematis standar.
2
MASALAH JALUR OPTIMUM
Permasalahan jalur optimum mempunyai
tujuan untuk memilih route yang paling
rendah biayanya (minimum total cost) untuk
sampai ke tempat tujuan.
Route dengan biaya yang paling rendah
sering disebut Jalur Optimum (Optimum
Path).
Dalam masalah-masalah yang hampir sama,
mungkin tujuannya adalah untuk
meminimumkan jarak atau periode waktu di
samping biaya.
3
MASALAH JALUR OPTIMUM
Contoh kasus:
Sebuah truck paket dapat melakukan
pengiriman barang dari tempat asal ke
tujuan pengiriman terakhir dengan
melalui route yang bermacam-macam
(lihat Network Flowchart Route).
Lingkaran 1 adalah tempat asal dan
Lingkaran 10 adalah tujuan pengiriman
akhir.
4
MASALAH JALUR OPTIMUM
Mulai dari lingkaran 1, truck paket harus
memutuskan mana route yang akan diambil,
melalui lingkaran 2 atau 3. Ini adalah segmen
pertama dari route pengiriman dan sering
disebut stage (tahap)
Ada 4 tahap dalam masalah ini setiap tahap
mempunyai sub masalah sebagai bagian dari
masalah yang lebih besar.
Pengambilan keputusan untuk memilih route
sering disebut states (ketetapan).
Setiap ketetapan harus diputuskan route khusus
untuk melakukan pengiriman sampai tempat
tujuan terakhir tercapai.
5
NETWORK FLOWCHART
5 7
4 4
7 10
2 6
8 8
1 5 8 8 10
9
3
5 3 5 9
4 6 6 9
5 9
I II III IV TAHAP
6
PROSEDUR PERHITUNGAN
Teknik perhitungan programasi dinamis
terutama didasarkan pada prinsip optimasi
recursive (bersifat pengulangan) yang
diketahui sebagai prinsip optimalisasi
(principle of optimality).
Prinsip ini mengandung arti bahwa bila
dibuat keputusan multistage mulai pada
tahap tertentu, kebijaksanaan optimal untuk
tahap-tahap selanjutnya tergantung pada
ketetapan tahap permulaan tanpa
menghiraukan bagaimana diperoleh suatu
ketetapan tertentu tsb.
7
PROSEDUR PERHITUNGAN
Bila fn(C) menunjukkan biaya total minimum yang
dihubungkan dengan jalur optimum dalam
network.
fj(C) adalah biaya minimum perjalanan dari
lingkaran ke-j dalam satu tahap ke lingkaran
terakhir. Persamaan ini disebut recursive equation.
Notasi Cij menunjukkan biaya yang terlibat dalam
pergerakan dari lingkaran ke-i pada tahap tertentu
ke lingkaran ke-j dalam tahap berikutnya.
Persamaan untuk kebijaksanaan optimal dapat
dinyatakan sbb.:
f n (C) = min {C ij + f j (C)}
8
PROSEDUR PERHITUNGAN
Dengan bergerak ke belakang dari lingkaran
terakhir ke tiga lingkaran yang menunjukkan tiga
ketetapan dalam Tahap IV, didapatkan biaya-biaya
pemakaian route-route ini sebesar:
TAHAP IV:
f7(C) = C7,10 = 10
f8(C) = C8,10 = 8 <--- Dipilih
f9(C) = C9,10 = 9
9
PROSEDUR PERHITUNGAN
TAHAP III:
⎧C 4, 7 + f 7 (C) = 5 + 10 = 15⎫
f 4 (C) = min ⎨ ⎬ = 15
⎩ C 4,8 + f 8 (C) = 8 + 8 = 16 ⎭
⎧C 5, 7 + f 7 (C) = 7 + 10 = 17 ⎫
⎪ ⎪
f 5 (C) = min ⎨ C 5,8 + f 8 (C) = 3 + 8 = 11 ⎬ = 11 <--- Dipilih
⎪ C + f (C) = 6 + 9 = 15 ⎪
⎩ 5,9 9 ⎭
⎧C 6,8 + f 8 (C) = 9 + 8 = 17 ⎫
f 6 (C) = min ⎨ ⎬ = 14
⎩C 6,9 + f 9 (C) = 5 + 9 = 14⎭
10
PROSEDUR PERHITUNGAN
TAHAP II:
⎧C 2, 4 + f 4 (C) = 4 + 15 = 19⎫
f 2 (C) = min ⎨ ⎬ = 17
⎩ C 2,5 + f 5 (C) = 6 + 11 = 17 ⎭
⎧C 3, 4 + f 4 (C) = 9 + 15 = 24 ⎫
⎪ ⎪
f 3 (C) = min ⎨ C 3,5 + f 5 (C) = 5 + 11 = 16 ⎬ = 16 <--- Dipilih
⎪ C + f (C) = 4 + 14 = 18 ⎪
⎩ 3, 6 6 ⎭
11
PROSEDUR PERHITUNGAN
TAHAP I:
⎧C1, 2 + f 2 (C) = 8 + 17 = 25⎫
f1 (C) = min ⎨ ⎬ = 21
⎩ C1,3 + f 3 (C) = 5 + 16 = 21⎭
Kesimpulan:
• Jalur optimum: 1 – 3 – 5 – 8 – 10
• Biaya total sebesar 21
12
JALUR OPTIMUM
5 7
4 4
7 10
2 6
8 8
1 5 8 8 10
9
3
5 3 5 9
4 6 6 9
5 9
I II III IV TAHAP
13