Operations Research Industrial engineering
DYNAMIC PROGRAMMING
21/04/2014
Operations Research
2
Characteristics Of Dynamic Programming Problem
1
• The problem can be divided into stages, with a policy decision required at each stage
2
• Each stage has a number of states associated with it
3
• The effect of the policy decision at each stage is to transform the current state into a state associated with the next stage (possibly according to a probability distribution)
21/04/2014
Operations Research
3
Characteristics Of Dynamic Programming Problem • The solution procedure is designed to find an optimal policy for the overall problem, i.e., a prescription of 4 the optimal policy decision at each stage for each of the possible states
• Given the current state, an optimal policy for the remaining stages is independent of the policy adopted 5 in precious stages (this is the principle of the optimality for dynamic programming) 21/04/2014
Operations Research
4
Characteristics of dynamic programming problem: forward recursive
7
• The solution procedure begins by finding the optimal policy for the first stage
8
• A recursive relationship that identifies the optimal policy for stage n, given the optimal policy for stage (n - 1), is available
21/04/2014
Operations Research
5
Characteristics of dynamic programming problem: backward recursive
7
• The solution procedure begins by finding the optimal policy for the last stage
8
• A recursive relationship that identifies the optimal policy for stage n, given the optimal policy for stage (n + 1), is available
21/04/2014
Operations Research
6
f S min cSXn f * n
• • • • •
Xn
* n 1
X n
N = number of stages n = label for current stage (n = 1, 2, …, N) Sn = current state for stage n Xn = decision variable for stage n Xn* = optimal value of Xn (given Sn)
21/04/2014
Operations Research
7
f S min cSXn f * n
•
Xn
* n 1
X n
f n Sn , X n = contribution of stage n, n + 1, …, N to the objective function if the system starts in state Sn at stage n, the immediate decision id Xn, and optimal decisions are made thereafter
f Sn f n Sn , X * n
21/04/2014
Operations Research
* n
8
f S min cSXn f * n
Xn
* n 1
X n
• The recursive relationship will always be of the form
f S n max f n S n , X n * n
Xn
or f S n min f n S n , X n * n
21/04/2014
Xn
Operations Research
9
Characteristics of dynamic programming problem • When we use this recursive relationship, the solution procedure moves backward stage by stage – each 8. time finding the optimal policy for that stage – until it finds the optimal policy starting at the initial stage
Xn Sn S1 S2 S3 21/04/2014
X1
fn(Sn, Xn) X2
X3
Operations Research
fn*(Sn)
Xn*
10
Contoh 1 Sebuah perusahaan mempunyai usulan dari ketiga pabriknya untuk kemungkinan mengembangkan sarana produksi. Perusahaan tersebut menyediakan anggaran $5 juta untuk alokasi pada ketiga pabrik. Setiap pabrik diminta untuk menyampaikan usulannya yang memberikan jumlah biaya (c) dan jumlah pendapatan (R) untuk setiap usulan. 21/04/2014
Operations Research
11
Contoh 1
Usulan 1 2 3 4
21/04/2014
Pabrik 1 c1 R1 0 0 1 5 2 6
Pabrik 2 c2 R2 0 0 2 8 3 9 4 12
Operations Research
Pabrik 3 c3 R3 0 0 1 3
12
Contoh 1: stage 1 X1 S1 0 1 2 3 4 5
21/04/2014
0 0 0 0 0 0 0
f1(S1, X1) 1
2
5 5 5 5 5
6 6 6 6
Operations Research
f1*(S1) 0 5 6 6 6 6
X1* 0 1 2 2 2 2
13
Contoh 1: Stage 2 X2 S2 0 1 2 3 4 5
21/04/2014
f2(S2, X2) 0 0 5 6 6 6 6
2
3
4
8 13 14 14
9 14 15
12 17
Operations Research
f2*(S2) 0 5 8 13 14 17
X2* 0 0 2 2 2 atau 3 4
14
Contoh 1: Stage 3 X3 S3 5
f3(S3, X3) 0 17
1 17
f3*(S3) 17
X3* 0 atau 1
• Dana yang tersedia $5 juta dimanfaatkan semua • Alokasi dana pabrik 1 – pabrik 2 – pabrik 3 – 1–4–0 – 1–3–1 – 2–2–1
• Total pendapatan = $17 juta 21/04/2014
Operations Research
15
Contoh 1: Rekursif Mundur X3 S3 0 1 2 3 4 5 21/04/2014
f3(S3, X3) 0 0 0 0 0 0 0
1 3 3 3 3 3 Operations Research
f3*(S3) 0 3 3 3 3 3
X3* 0 1 1 1 1 1 16
Contoh 1: Rekursif Mundur X2 S2 0 1 2 3 4 5
21/04/2014
f2(S2, X2) 0 0 3 3 3 3 3
2
3
4
8 11 11 11
9 12 12
12 15
Operations Research
f2*(S2) 0 3 8 11 12 15
X2* 0 0 2 2 3 atau 4 4
17
Contoh 1: Rekursif Mundur X1 S1 5
0 15
f1(S1, X1) 1 17
2 17
f1*(S1) 17
X1* 1 atau 2
• Dana yang tersedia $5 juta dimanfaatkan semua • Alokasi dana pabrik 1 – pabrik 2 – pabrik 3 – 1–3–1 – 1–4–0 – 2–2–1
• Total pendapatan = $17 juta 21/04/2014
Operations Research
18
Contoh 2 Suatu organisasi kesehatan dunia menyelenggarakan program peningkatan kepedulian pada kesehatan dan memberikan pendidikan kesehatan di beberapa negara terbelakang Organisasi tersebut memiliki 5 tim medis yang siap ditugaskan di 3 negara
Satu negara paling tidak harus didatangi 1 tim medis
Performansi diukur dengan penambahan umur hidup 21/04/2014
Operations Research
19
Contoh 2
Number of Medical Teams 1 2 3 4 5 21/04/2014
Thousands of Additional PersonYears of Life Country 1 2 3 45 20 50 70 45 70 90 75 80 105 110 100 120 150 130 Operations Research
20
Contoh 2: Stage 3 X3 S3 1 2 3
21/04/2014
1 45 45 45
f3(S3, X3) 2
3
70 70
90
Operations Research
f3*(S3) 45 70 90
X3* 1 2 3
21
Contoh 2: Stage 2 X2 S2 2 3 4
21/04/2014
1 65 90 110
f2(S2, X2) 2
3
90 115
120
Operations Research
f2*(S2) 65 90 120
X2* 1 1 atau 2 3
22
Contoh 2: Stage 1 X1 S1 5
1 170
f1(S1, X1) 2 160
3 145
f1*(S1) 170
X1* 1
• Alokasi Tim Medis –1–3–1 – Total additional person-years of life = 170.000
21/04/2014
Operations Research
23
Contoh 2: asumsi suatu negara boleh tidak dikunjungi tim medis sama sekali X3 S3 0 1 2 3 4 5 X2 S2 0 1 2 3 4 5
21/04/2014
f3(S3, X3) 0 0 0 0 0 0 0
1
2
3
4
5
45 45 45 45 45
70 70 70 70
90 90 90
105 105
120
f3*(S3) 0 45 70 90 105 120
X3* 0 1 2 3 4 5
f2*(S2) 0 45 70 90 120 155
X2* 0 1 1 0 atau 1 atau 2 3 4
f2(S2, X2) 0 0 45 70 90 105 120
1
2
3
4
5
20 65 90 110 125
45 90 115 135
75 120 145
110 155
150
Operations Research
24
Contoh 2: asumsi suatu negara boleh tidak dikunjungi tim medis sama sekali X1 S1 5
f1(S1, X1) 0 155
1 170
2 160
3 150
4 145
5 130
f1*(S1) 170
X1* 1
• Alokasi tim medis –1–3–1 – Total additional person-years of life = 170.000
21/04/2014
Operations Research
25
Soal 1 A college student has 7 days remaining before final examinations begin in her four courses, and she wants to allocate this study time as effectively as possible. She needs at least 1 day on each course, and she likes to concentrate on just one course each day, so she wants to allocate 1, 2, 3, or 4 days to each course. Having recently taken an operations research course, she decides to use dynamic programming to make these allocations to maximize the total grade points to be obtained from four courses. She estimates that the alternative allocations for each course would yield the number of grade points shown in the table. Solve this problem by dynamic programming. 21/04/2014 Operations Research 26
Soal 1
number of study days 1 2 3 4
21/04/2014
1 3 5 6 7
estimated grade points courses 2 3 5 2 5 4 6 7 9 8
Operations Research
4 6 7 9 9
27
