Pendahuluan

• Tidak seperti program linier, Program Dinamik

(PD) tidak mempunyai standar formulasi
matematik.
• PD lebih merupakan suatu cara umum untuk
melakukan optimasi dengan persamaan
Program Dinamik matematik yang cocok dengan masalah yang
dihadapi.
• Insight dan ingenuity dibutuhkan untuk
Ir. Djoko Luknanto, [Link]., Ph.D. mengenali penggunaan PD dalam
menyelesaikan masalah lapangan.
Jurusan Teknik Sipil • Cara terbaik penyampaian PD adalah dengan
FT UGM mengenalkan beberapa permasalahan yang
dapat diselesaikan dengan PD.
8/24/2003 Jack la Motta 1
8/24/2003 Jack la Motta 2

Contoh Jarak Termurah Biaya dan Rute jalan

n=1 n=2 n=3 n=4
• Seorang pebisnis akan pergi dari Kota A
ke Kota J dengan menggunakan
7 1
kendaraan umum. B E H
4 4
• Banyak kemungkinan jalan yang dapat 2 6
digunakan dari A Æ J 3
• Pebisnis diatas menginginkan 4
3 6
perjalanan dari A Æ J dengan biaya A C 2 F J
paling murah 4 3
4
• Besar biaya dan rute jalan dari A Æ J 3
disajikan dalam tayangan berikut. 4 3
1
D G 3 I
5
8/24/2003 Jack la Motta 3 8/24/2003 Jack la Motta 4

Biaya dan Rute jalan Formulasi 1

n=1 n=2 n=3 n=4
• Jika hitungan diawali • Pilih variabel keputusan xn (n = 1,2,3,4) sebagai
B
7
E
1
H dari A , hasilnya: kota yang harus ditempuh pada tahap n,
AÆBÆFÆIÆJ
4 4
2 6

3
3 dengan biaya sehingga rute seluruhnya adalah x1Æx2Æx3Æx4
6
4
A C
4
2
F J 2+4+3+4 total 13 dengan x1=A dan x4=J
3

3
4 • Jika hitungan diawali • Pilih fn(s,xn) sebagai biaya total untuk kebijakan
4
1
3
dari J, hasilnya: keseluruhan dari tahapan selanjutnya dengan
JÅHÅEÅCÅA
D G 3 I
5

dengan biaya pebisnis sampai pada kondisi s, siap berangkat

• Kita coba penyelesaian
bahwa dalam setiap 3+1+3+4 total 11 ke tahap n, dengan memilih xn sebagai kota
tahap/rute kita pilih yang • Cara yang dapat tujuan berikut
biayanya termurah ditempuh adalah trial
& error

8/24/2003 Jack la Motta 5 8/24/2003 Jack la Motta 6

1
 Formulasi 2 Prosedur penyelesaian Tahap 4
n=1 n=2 n=3 n=4
• Pada kondisi s dan tahap n, gunakan xn* • Pada tahap akhir n = 4 hasil
7 ditabelkan sbb:
sebagai sembarang nilai yang B
4
E
1
4
H
6
meminimumkan fn(s,xn), gunakan fn*(s) 2
3 s f4*(s) x4*
sebagai nilai minimum dari fn(s,xn) 4
3
2
6
A C
4
F
3
J
H 3 J
• fn*(s) = min fn(s,xn) = fn(s,xn*) 3
4
4
D
1
3
G 3 I
I 4 J
dengan fn(s,xn) adalah biaya sekarang 5

(tahap n) + minimum biaya yad (tahap • Pada tahap akhir n = 4, maka

perjalanannya hanya ditentukan
tabel diatas menyajikan fakta
bahwa kalau pebisnis sudah
n+1 dan selanjutnya) atau sepenuhnya oleh kondisi s sampai di H maupun di I,
sekarang (yaitu H atau I) dan maka solusi feasible-nya
tujuan akhir J, sehingga adalah x4* = J.
fn(s,xn) = cs(xn) + fn+1*(xn) f4*(s) = f4(s,J) = cs(J)

8/24/2003 Jack la Motta 7 8/24/2003 Jack la Motta 8

Tahap 3 Tahap 2
n=1 n=2 n=3 n=4 n=1 n=2 n=3 n=4
• Pada tahap akhir n = 3 hasil
7 1 ditabelkan sbb: 7 1 f2 = cs+f3*
B
4
E
4
H B
4
E
4
H s f2*(s) x2*
2 6 f3 = cs+f4* 2 6 E F G
3 s f3*(s) x3 * 3
4
3
2
6 H I 4
3
2
6 B 11 11 12 11 E, F
A C F J A C F J
4 3 E 4 8 4 H 4 3
C 7 9 10 7 E
4 4
3 4 3
F 9 7 7 I 3 4 3
1 1 D 8 8 11 8 E, F
D
5
G 3 I G 6 7 6 H D
5
G 3 I

• Pada tahap n = 3, maka • E, H Æ4=1+3 • B,E Æ 11 = 7 + 4 • D,E Æ 8 = 4 + 4

perjalanannya perlu melakukan E, I Æ8=4+4 B,F Æ 11 = 4 + 7 D,F Æ 8 = 1 + 7
beberapa hitungan. Misalkan dia B,G Æ 12 = 6 + 6 D,G Æ 11 = 5 + 6
sudah sampai di kota F, maka • F, H Æ9=6+3
dia bisa menuju ke kota H atau I, F, I Æ7=3+4 • C,E Æ 7 = 3 + 4 • Bilangan yang terakhir
C,F Æ 9 = 2 + 7 setelah “+” adalah nilai
dengan biaya pada tahap 3 ini • G, H Æ6=3+3 C,G Æ 10 = 4 + 6 optimum f3*(x3)
adalah cF(H) = 6 atau cF(I) = 3 G, I Æ7=3+4
8/24/2003 Jack la Motta 9 8/24/2003 Jack la Motta 10

Tahap 1 Biaya dan Rute jalan optimum

n=1 n=2 n=3 n=4 n=1 n=2 n=3 n=4
7 1 f1 = cs+f1*
B
4
E
4
H s f1*(s) x1* 11 4 3
2 6 B C D 7 1
3 B E H
3 6 A 13 11 11 11 C, D
A
4
C
2
F J 4
4 3
4
3 4 3
1
3
7 3
D
5
G 3 I 11 4 7 F
A C 3 J
• A,B Æ 13 = 2 + 11 • Lintasan 1: AÆCÆEÆHÆJ 4
A,C Æ 11 = 4 + 7 Lintasan 2: AÆDÆEÆHÆJ
A,D Æ 11 = 3 + 8 4
Lintasan 3: AÆDÆFÆIÆJ 3
• Dari hasil di atas nilai 1 3
optimum tercapai • Lintasan tersebut disajikan
yaitu 11 dalam tayangan berikut.
D G I
8 6 4
8/24/2003 Jack la Motta 11 8/24/2003 Jack la Motta 12

2
 Karateristik Program Dinamik Karateristik Program Dinamik

1. Permasalahannya dapat dibagi 3. Pengaruh keputusan kebijakan pada

setiap tahapan adalah transformasi
menjadi tahapan dengan kondisi saat ini kepada sebuah kondisi
keputusan kebijakan pada tiap yang terkait dengan awal dari tahapan
berikutnya
tahap
4. Prosedur penyelesaian dirancang
2. Tiap tahap mempunyai sejumlah untuk mendapatkan kebijakan
optimum untuk seluruh tahapan yaitu
kondisi terkait dengan membuat kebijakan optimum
untuk setiap tahap pada setiap
kemungkinan kondisi

8/24/2003 Jack la Motta 13 8/24/2003 Jack la Motta 14

Karateristik Program Dinamik Karateristik Program Dinamik

5. Pada suatu kondisi, sebuah kebijakan 6. Prosedur penyelesaian mulai dengan

optimum untuk tahapan selanjutnya mendapatkan solusi optimum untuk tahap
terakhir.
tidak terkait oleh kebijakan optimum
dari tahapan sebelumnya. 7. Hubungan rekursif untuk memperoleh solusi
optimum untuk tahap n, dengan solusi
Jadi keputusan optimum yang diambil optimum untuk tahap n+1 telah diketahui.
hanya tergantung pada kondisi Rumus tersebut menjadi:
sekarang bukan dari bagaimana kita
sampai pada kondisi sekarang. Inilah
yang dinamai prinsip optimum dari f n* ( s ) = min{cs ( xn ) + f n*+1 ( xn +1 )}
xn
Program Dinamik.

8/24/2003 Jack la Motta 15 8/24/2003 Jack la Motta 16

Alokasi air dengan DP Formulasi Alokasi Air

xj R1(x1) R2(x2) R3(x3) • Sebuah kawasan • Alokasi air agar keuntungan bersih total
akan membagi air maksimum dirumuskan:
0 0,0 0,0 0,0
kepada 3 f j (s j ) = max [ R j ( x j ) + f j +1 ( s j − x j )]
1 -0,5 6,5 -6,9 pengguna, xj
dengan 0≤ x j ≤ s j
2 3,0 10,1 0 keuntungan
bersih masing- • Karena sifatnya yang rekursif, maka hitungan
3 6,6 10,9 6,3
paling mudah dimulai dari tahap (j) akhir
masing pengguna
4 10,0 9,6 11,5 disajikan dalam • Prosedur lengkap cara penyelesaian lebih
tabel. mudah kalau dijelaskan dengan tabel pada
5 13,1 7,0 15,6 tayangan berikut.
8/24/2003 Jack la Motta 17 8/24/2003 Jack la Motta 18

3
 Jawaban: Tahap Akhir Jawaban: Tahap Kedua
OPTIMUM NET BENEFIT COMPUTATION =========================================================
USING DYNAMIC PROGRAMMING Stage 2: NB2(X2) + OptNB3(State2 - X2)
(BACKWARD METHOD) ---------------------------------------------------------
0.0 6.5 10.1 10.9 9.6 7.0 NB2
State --------------------------------- [Link]:
THESE ARE INTERMEDIATE RESULTS X:0 1 2 3 4 5 NB X's
========================================================= ---------------------------------------------------------
NB3(X3) 0 0.0 - - - - -
State 3 --------------------------------- [Link]: 0.0 - - - - - 0.00 0
X:0 1 2 3 4 5 NB X's 1 0.0 0.0 - - - -
0.0 6.5 - - - - 6.50 1
---------------------------------------------------------
2 0.0 0.0 0.0 - - -
0 0.0 - - - - - 0.00 0 0.0 6.5 10.1 - - - 10.10 2
1 0.0 -6.9 - - - - 0.00 0 3 6.3 0.0 0.0 0.0 - -
2 0.0 -6.9 0.0 - - - 0.00 0,2 6.3 6.5 10.1 10.9 - - 10.90 3
3 0.0 -6.9 0.0 6.3 - - 6.30 3 4 11.5 6.3 0.0 0.0 0.0 -
4 0.0 -6.9 0.0 6.3 11.5 - 11.50 4 11.5 12.8 10.1 10.9 9.6 - 12.80 1
5 0.0 -6.9 0.0 6.3 11.5 15.6 15.60 5 5 15.6 11.5 6.3 0.0 0.0 0.0
15.6 18.0 16.4 10.9 9.6 7.0 18.00 1
=========================================================
=========================================================

8/24/2003 Jack la Motta 19 8/24/2003 Jack la Motta 20

Jawaban: Tahap Pertama Program Dinamik

=========================================================
Stage 1: NB1(X1) + OptNB2(State1 - X1)
• Untuk kepentingan kuliah, maka telah disediakan
--------------------------------------------------------- Program Dinamik sederhana yang dikembangkan:
0.0 -0.5 3.0 6.6 10.0 13.1 NB1
State --------------------------------- [Link]:
X:0 1 2 3 4 5 NB X's **********************************
---------------------------------------------------------
5 18.0 12.8 10.9 10.1 6.5 0.0 * Djoko Luknanto *
18.0 12.3 13.9 16.7 16.5 13.1 18.00 0
=========================================================
* Research Engineer *
* Hydraulic Laboratory *
THESE ARE FINAL RESULTS
====================================== * Civil Engineering Department *
The optimum value is 18.00000
======================================
* College of Engineering *
The alternative optimal solutions * Gadjah Mada University *
[ X(Optimum) ] at each stage are
====================================== * Tahun 1992 *
Stage : 1 2 3
--------------------------------------
**********************************
0 1 4 • Hasil-hasil diatas adalah output dari program ini.
======================================
Note: The unit of X(Optimum) is 1.00

8/24/2003 Jack la Motta 21 8/24/2003 Jack la Motta 22