Program Dinamik (Dynamic Programming) Riset Operasi TIP – FTP – UB
Program Dinamik : Pendahuluan (1)
Program dinamik merupakan suatu pendekatan solusi bukan suatu teknik
Pendekatan solusi adalah merinci suatu masalah menjadi masalah-masalah yang lebih kecil tahapan (stages)
Tidak terbatas pada golongan masalah tertentu
Penyelesaian tahapan secara berurutan
Hasil dari suatu keputusan (solusi) pada suatu tahap akan mempengaruhi keputusan tahap berikutnya
Program Dinamik : Pendahuluan (2)
Pemrograman dinamik merupakan teknik matematis yang dapat berguna untuk membuat suatu urutan keputusan yang saling berkaitan Pemrograman dinamis tidak mempunyai rumusan yang baku Tiap permasalahan memerlukan perumusan tertentu Teknik pemrograman dinamis dikenal juga dengan multistage programming
Klasifikasi Program Dinamis Status Diskret
Tunggal
Deterministik
Probabilistik
Majemuk
Status Kontinyu
Tunggal
Majemuk
Prosedur Pemecahan Masalah
Prosedur pemecahan
Perbedaan prosedur
Rekursi maju (forward recursion) Rekursi mundur (backward recursion) Cara mendefinisikan status dalam sistem.
Prosedur rekursi mundur secara umum lebih efisien
Langkah-langkah Pemecahan
Tentukan prosedur pemecahan (maju atau mundur). Tentukan tahap (stage). Definisikan variabel status (state) pada tiap tahap. Definisikan variabel keputusan pada tiap tahap. Definisikan fungsi pengembalian pada tiap tahap. Definisikan fungsi transisi. Definisikan fungsi rekursif. Perhitungan. Tentukan solusi optimal dengan backtracking.
Permasalahan
Sebuah perusahaan membagi wilayah pemasarannya menjadi tiga: utara, timur, selatan. Perusahaan tersebut memilliki 3 tenaga penjual yang akan dialokasikan ke tiga wilayah tersebut tanpa membatasi jumlah tenaga penjual di setiap wilayah sdrs hasil penjualan maksimum.
Contoh Program Dinamik (1) Permasalahan Alternatif Keputusan Salesman/Daerah
Tingkat Pengembalian/Daerah Utara
Timur
Selatan
0
0
0
2
1
7
9
6
2
12
15
10
3
20
18
16
Contoh Program Dinamik (2) Model Matatematika Masalah Maksimum R1+R2+R3 Ditujukan D1+D2+D3 ≤ 3 Dimana R1, R2, R3 = pengembalian dari tiap 3 daerah D1, D2, D3 = keputusan penempatan salesman ke tiap 3 daerah
Contoh Program Dinamik (3) Tahap 1 : Alokasi ke Daerah Selatan Keadaan 1 (S1): Salesman Tersedia
Keputusan 1 (D1): Alokasi Salesman
Pengembalian 1(R1): Jumlah Penjualan
0
0
2
1
0
2
1
6
0
2
1
6
2
10
0
2
1
6
2
10
3
16
2
3
Contoh Program Dinamik (4) Tahap 1 : Alokasi ke Daerah Selatan (Opt) Keadaan 1 (S1): Salesman Tersedia
Keputusan 1 (D1): Alokasi Salesman
Pengembalian 1(R1): Jumlah Penjualan
0
0
2
1
0
2
1
6
0
2
1
6
2
10
0
2
1
6
2
10
3
16
2
3
Contoh Program Dinamik (5) Tahap 2 : Alokasi ke Daerah Timur Keadaan 2 (S2): Salesman Tersedia
Keputusa 2 (D2): Alokasi Salesman
Pengembali an 2 (R2): Jumlah Penjualan
Keadaan 1 (S1): Salesman Tersedia
0
0
0
0
2
2
1
0
0
1
6
6
1
9
0
2
11
0
0
2
10
10
1
9
1
6
15
2
15
0
2
17
0
0
3
16
16
1
9
2
10
19
2
15
1
6
21
3
18
0
2
20
2
3
Pengembali Total an 1(R1): Pengembali Jumlah an (R1+R2) Penjualan
Contoh Program Dinamik (6) Tahap 2 : Alokasi ke Daerah Timur (Opt) Keadaan 2 (S2): Salesman Tersedia
Keputusa 2 (D2): Alokasi Salesman
Pengembali an 2 (R2): Jumlah Penjualan
Keadaan 1 (S1): Salesman Tersedia
0
0
0
0
2
2
1
0
0
1
6
6
1
9
0
2
11
0
0
2
10
10
1
9
1
6
15
2
15
0
2
17
0
0
3
16
16
1
9
2
10
19
2
15
1
6
21
3
18
0
2
20
2
3
Pengembali Total an 1(R1): Pengembali Jumlah an (R1+R2) Penjualan
Contoh Program Dinamik (7) Tahap 3 : Alokasi ke Daerah Utara Keadaan 3 (S3): Salesman Tersedia 3
Pengemba Keputusa lian 3 3 (D3): (R3): Alokasi Jumlah Salesman Penjualan
Keadaan 2 (S2): Salesman Tersedia
Total Pengemba Pengemba lian 2(R2): lian Jumlah (R1+R2+R Penjualan 3)
0
0
3
21
21
1
7
2
17
24
2
12
1
11
23
3
20
0
2
22
Contoh Program Dinamik (8) Tahap 3 : Alokasi ke Daerah Utara (Opt) Keadaan 3 (S3): Salesman Tersedia 3
Pengemba Keputusa lian 3 3 (D3): (R3): Alokasi Jumlah Salesman Penjualan
Keadaan 2 (S2): Salesman Tersedia
Total Pengemba Pengemba lian 2(R2): lian Jumlah (R1+R2+R Penjualan 3)
0
0
3
21
21
1
7
2
17
24
2
12
1
11
23
3
20
0
2
22
Contoh Program Dinamik (8) Urutan Keputusan Optimal Keadaan (daerah)
Alokasi Pengembalian Salesman
1. Selatan
0
2
2. Timur
2
15
3. Utara
1
7
Total
3
24
Problem Knapsack
Permasalahan mengenai berapa jumlah tiap jenis barang yang berbeda dapat dimasukkan ke dalam sebuah ransel guna memaksimumkan pengembalian dari barangbarang tersebut. Ransel punya kapasitas tertentu (5 ruang)
Contoh Problem Knapsack (1) Permasalahan Alternatif Barang yang Dibawa
X Y Z
Berat Laba 2 90 3 150 1 30
Contoh Problem Knapsack (2) Model Matatematika Masalah Maksimum R1D1+R2D2+R3D3 Ditujukan W1D1+W2D2+W3D3 ≤ 5 Dimana R1, R2, R3 = pengembalian dari tiap barang D1, D2, D3 = keputusan jumlah barang yang dibawa W1, W2, W3 = berat barang yang dibawa
Contoh Problem Knapsack (3) Tahap 1 : Keputusan X Keadaan 1 (S1): Ruang Tersedia
Keputusan 1 (D1): Jumlah Barang
Kebutuhan Ruang
Pengembalian 1(R1)
5
2
4
180
4
2
4
180
3
1
2
90
2
1
2
90
1
0
0
0
0
0
0
0
Contoh Problem Knapsack (4) Tahap 1 : Keputusan X (Opt) Keadaan 1 (S1): Ruang Tersedia
Keputusan 1 (D1): Jumlah Barang
Kebutuhan Ruang
Pengembalian 1(R1)
5
2
4
180
4
2
4
180
3
1
2
90
2
1
2
90
1
0
0
0
0
0
0
0
Contoh Problem Knapsack (5) Tahap 2 : Keputusan Y Keput Kebutu Penge Keada Keadaa usan han mbalia an 1 n 2 (S2) 2 Ruang n 2(R2) (S1) (D2) 5
Keputu san 1 (D1)
Penge mbalia n1 (R1)
Penge mbalia n Total (R)
1
3
150
2
1
90
240
0
0
0
5
2
180
180
1
3
150
1
0
0
150
0
0
0
4
2
180
180
1
3
150
0
0
0
150
0
0
0
3
1
90
90
2
0
0
0
2
1
90
90
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4 3
Contoh Problem Knapsack (6) Tahap 2 : Keputusan Y (Opt) Keput Kebutu Penge Keada Keadaa usan han mbalia an 1 n 2 (S2) 2 Ruang n 2(R2) (S1) (D2) 5
Keputu san 1 (D1)
Penge mbalia n1 (R1)
Penge mbalia n Total (R)
1
3
150
2
1
90
240
0
0
0
5
2
180
180
1
3
150
1
0
0
150
0
0
0
4
2
180
180
1
3
150
0
0
0
150
0
0
0
3
1
90
90
2
0
0
0
2
1
90
90
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4 3
Contoh Problem Knapsack (7) Tahap 3 : Keputusan Z Keput Kebutu Penge Keada Keadaa usan han mbalia an 2 n 3 (S3) 3 Ruang n 3(R3) (S2) (D3) 5
Keputu san 2 (D2)
Penge mbalia n2 (R2)
Penge mbalia n Total (R)
5
5
150
0
0
0
150
4
4
120
1
0
0
120
3
3
90
2
0
90
180
2
2
60
3
1
150
210
1
1
30
4
0
180
210
0
0
0
5
1
240
240
Contoh Problem Knapsack (8) Tahap 3 : Keputusan Z Keput Kebutu Penge Keada Keadaa usan han mbalia an 2 n 3 (S3) 3 Ruang n 3(R3) (S2) (D3) 5
Keputu san 2 (D2)
Penge mbalia n2 (R2)
Penge mbalia n Total (R)
5
5
150
0
0
0
150
4
4
120
1
0
0
120
3
3
90
2
0
90
180
2
2
60
3
1
150
210
1
1
30
4
0
180
210
0
0
0
5
1
240
240
Contoh Problem Knapsack (9) Keputusan Optimal Keadaan Jumlah Kebutuhan (Barang) Barang Ruang
Pengem balian
X
1
2
90
Y
1
3
150
Z
0
0
0
5
240
Total
Problema Stagecoach
Suatu jaringan pengarahan perjalanan dimana seorang pengarah jalan (abad 19) ingin menentukan rute terpendek antara dua kota (1 dan 7) berdasarakan rute alternatif yang tersedia.
Problema Stagecoach (1) Tahap 1 Keadaan 1 (S1): Keputusan 1 Lokasi Truk (D1): Rute
Pengembalian 1 (R1): Waktu Tempuh
5
57
8
6
67
14
Problema Stagecoach (1) Tahap 1 (Opt) Keadaan 1 (S1): Keputusan 1 Lokasi Truk (D1): Rute
Pengembalian 1 (R1): Waktu Tempuh
5
57
8
6
67
14
Problema Stagecoach (1) Tahap 2 Keputus Penge Pengem Keadaa Keadaa an 2 mbalian balian 1 n 2 (S2) n 1 (S1) (D2) 2 (R2) (R1) 2 3 4
Pengem balian Total (R)
25
25
5
8
33
26
17
6
14
31
35
14
5
8
22
36
17
6
14
31
45
26
5
8
34
46
22
6
14
36
Problema Stagecoach (1) Tahap 2 (Opt) Keputus Penge Pengem Keadaa Keadaa an 2 mbalian balian 1 n 2 (S2) n 1 (S1) (D2) 2 (R2) (R1) 2 3 4
Pengem balian Total (R)
25
25
5
8
33
26
17
6
14
31
35
14
5
8
22
36
17
6
14
31
45
26
5
8
34
46
22
6
14
36
Problema Stagecoach (1) Tahap 3 Keputus Penge Pengem Keadaa Keadaa an 3 mbalian balian 2 n 3 (S3) n 2 (S2) (D3) 3 (R3) (R2) 1
Pengem balian Total (R)
12
16
2
31
47
13
35
3
22
57
14
9
5
34
43
Problema Stagecoach (1) Tahap 3 (Opt) Keputus Penge Pengem Keadaa Keadaa an 3 mbalian balian 2 n 3 (S3) n 2 (S2) (D3) 3 (R3) (R2) 1
Pengem balian Total (R)
12
16
2
31
47
13
35
3
22
57
14
9
5
34
43
Problema Stagecoach (1) Keputusan Optimal
Rute yang diambil 1 4 5 7 dengan jarak tempuh 43.
Terima kasih
