PEMOGRAMAN DINAMIS
(DYNAMIC PROGRAMMING)
Dynamic Programming (DP)
DP adalah satu metode dalam Riset Operasi
yang mempunyai model deterministik
maupun probabilistic yang dilkembangkan
oleh Richard Bellman pada tahun 1950.
DP digunakan untuk menyelesaikan
multistage problem
Pendekatan DP terdiri dari 3 langkah utama:
1. Problem dibagi ke dalam sub problem atau stage .
Walaupun demikian setiap stage atau subproblem tersebut
saling terkait.
2. Membuat suatu tabel untuk setiap sub problem atau
stage yang diselesaikan.
3. Solusi yang didapat adalah menggabungkan solusi
optimal pada masing-masing stage atau sub problem.
CIRI UTAMA : bekerja secara Backward
Prototype contoh
Joe Cougar tinggal di New York City dan ingin berkendara ke Los Angeles .
Karena dananya terbatas , Joe berencana untuk menghabiskan malam-
malam dijalan dengan menginap di rumah teman temannya. Joe
mempunyai teman di Columbus, Nashville, Louisville, Kansas City,
Omaha, Dallas, San Antonio dan Denver. Joe sadar bahwa setelah
seharian menyetir ia akan sampai di Columbus, Nashville atau Louisville.
Setelah dua hari menyetir ia akan sampai di Kansas City, Omaha atau
Dallas, dan stelah tiga hari menyetir ia akan sampai di San Antonio atau
Denver. Akhirnya, setelah 4 hari menyetir, ia akan sampai ke Los Angeles.
Untuk meminimalkan jarak tempuh, dimanakah Joe sebaiknya menginap
di malam pertama, kedua dan ketiga, serta berapah total jarak
tempuhnya dari NY ke LA ? Jarak antar kota diberikan pada gambar
berikut:
Penyelesaian:
Joe ingin mendapatkan jarak terpendek yang menghubungan New York
(NY) dengan Los Angeles (LA).
Pertama yang dilakukan adalah memutuskan untuk membagi kota kota
tempat menginap menjadi stage atau sub problem yang harus
diselesaikan.
Karena kita ingin menenyelesaikannya dengan meggunakan DP, maka
yang dilakukan adalah menentukan solusi dengan menyelesaikan secara
backward. Jadi, kita mundur dari LA.
Dari LA, kita mundur, berarti ada dua kota yang jadi pertimbangan, yaitu
Denver dan San Antonio yang ditempuh setelah 3 hari perjalanan . Sehingga
San Antonio dan Denver diletakkan sebagai stage 4 (dengan mengasumsikan
NY adalah stage 1).
Lalu, dari San Antonio atau Denver kita mundur ke 3 kota yaitu Kansas City,
Omaha dan Dallas yang menjadi Stage 3. Dari ketiga kota ini kita mundur ke
tiga kota lainnya yaitu Columbus, Nashville dan Louisville yang menjadi Stage
2., dan terakhir NY stage 1.
Perhitungan Stage 4:
Di Stage 4 kita menghitung jarak dari LA ke Denver dan
jarak dari LA ke San Antonio, karena ke LA hanya dari
kedua kota ini.
F4 (8) = 1030 ( jarak terpendek dari LA ke Denver)
F4 (9) = 1390 ( jarak terpendek dari LA ke San Antonio)
Perhitungan Stage 3:
Kota 5 :
Tanda * menyatakan bahwa melalui kota 5 lebih cepat lewat kota 8 untuk ke LA (kota
10) dengan total jarak 1640 km
Kota 6 :
Tanda * menyatakan bahwa melalui kota 6 lebih cepat lewat kota 8 untuk ke LA (kota
10) dengan total jarak 1570 km
Kota 7 :
Tanda * menyatakan bahwa melalui kota 7 lebih cepat lewat kota 9 untuk ke LA (kota
10) dengan total jarak 1660 km
Perhitungan Stage 2
Kota 2 :
Tanda * menyatakan bahwa melalui kota 2 lebih cepat lewat kota 5 dan 8 untuk ke LA
(kota 10) dengan total jarak 2320 km
Kota 3 :
Tanda * menyatakan bahwa melalui kota 3 lebih cepat lewat kota 5 dan 8
untuk ke LA (kota 10) dengan total jarak 2220 km
Kota 4 :
Tanda* menyatakan bahwa melalui kota 4 lebih cepat lewat kota 5 dan 8 untuk ke LA
(kota 10) dengan total jarak 2150 km
Perhitungan Stage 1
Kota 1 :
Tanda* menyatakan bahwa jarak optimal (paling minimum) adalah melalui kota 2
dengan jarak total 2870 km.
Bagaimana penentuan path optimal ??
Penentuan path dilakukan dengan melihat tanda (*) pada stage awal , kemudian terus ditelusuri.
Contoh, pada stage 1, tanda (*) ada di c12 + f2(2) berarti, kita ke stage 2 dan melihat f2(2).
Path sementara 1 - 2
Di stage 2, tanda (*) ada di c25 + f3(5) berarti, kita ke stage 3 dan melihat f3(5).
Path sementara 1 – 2 - 5
Distage 3, tanda (*) ada di c58 + f4(8) berarti, kita ke stage 4 dan melihat f4(8).
Path sementara 1 – 2 – 5 – 8
Distage 4 , F4 (8) = 1030 yang merupakan jarak terpendek dari kota 8 (Denver) ke LA.
Sehingga path optimal adalah : 1 – 2 – 5 – 8 – 10
Artinya Joe sebaiknya berangkat dari New York ke Columbus, lalu ke Kansas City, lalu ke Denver