0% found this document useful (0 votes)
96 views38 pages

03 DynProg

Dynamic programming is an optimization technique used to solve complex problems by breaking them down into simpler sub-problems. It has the following key characteristics: problems are divided into stages with decision points; each stage has associated states; decisions transform states between stages; the goal is to find an optimal policy across all stages. Solutions can be found either forward recursively by solving earlier stages first, or backward recursively by solving later stages first. The technique uses recursive relationships to iteratively find the optimal solution moving stage-by-stage. Two examples provided apply dynamic programming to allocate funds across factories and assign medical teams to countries.

Uploaded by

Alifia
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
96 views38 pages

03 DynProg

Dynamic programming is an optimization technique used to solve complex problems by breaking them down into simpler sub-problems. It has the following key characteristics: problems are divided into stages with decision points; each stage has associated states; decisions transform states between stages; the goal is to find an optimal policy across all stages. Solutions can be found either forward recursively by solving earlier stages first, or backward recursively by solving later stages first. The technique uses recursive relationships to iteratively find the optimal solution moving stage-by-stage. Two examples provided apply dynamic programming to allocate funds across factories and assign medical teams to countries.

Uploaded by

Alifia
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 38

Operations Research

Industrial engineering
DYNAMIC
PROGRAMMING

02/10/2019 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)

02/10/2019 Operations Research 3


Characteristics of dynamic
programming problem
4. The solution procedure is designed to
find an optimal policy for the overall
problem, i.e., a prescription of the
optimal policy decision at each stage
for each of the possible states
5. Given the current state, an optimal
policy for the remaining stages is
independent of the policy adopted in
precious stages (this is the principle of
the optimality for dynamic
programming)
02/10/2019 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

02/10/2019 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

02/10/2019 Operations Research 6


n
Xn

f S   min cSX n  f
* *
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)

02/10/2019 Operations Research 7


n
Xn

f S   min cSX n  f
* *
n 1  X n 
 f n S n , 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

n
*

f Sn   f n Sn , X *
n 

02/10/2019 Operations Research 8


n
Xn

f S   min cSX n  f
* *
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
*
Xn

02/10/2019 Operations Research 9


Characteristics of dynamic
programming problem
8. When we use this recursive
relationship, the solution procedure
moves backward stage by stage –
each time finding the optimal policy
for that stage – until it finds the
optimal policy starting at the initial
stage
Xn fn(Sn, Xn)
Sn X1 X2 X3 fn*(Sn) Xn*
S1
S2
S3
02/10/2019 Operations Research 10
Kasus Pelancong
 Seorang pelancong yang berasal dari
kota A akan menuju kota J. Untuk dapat
mencapai kota J, ia harus melalui 3 kota
lainnya, dimana di masing-masing kota
terdapat beberapa alternatif desa yang
dapat dilalui: Kota K (desa B, C, D), Kota
L (desa E, F, G), Kota M (desa H, I).
 Biaya dari kota A ke kota J dengan
melalui desa di kota K, L, M disajikan
pada Tabel
 Masalah ini dapat pula disajikan sebagai
masalah network/jaringan
02/10/2019 Operations Research 11
Kasus Pelancong

02/10/2019 Operations Research 12


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.

02/10/2019 Operations Research 13


Contoh 1
Pabrik 1 Pabrik 2 Pabrik 3
Usulan c1 R1 c2 R2 c3 R3
1 0 0 0 0 0 0
2 1 5 2 8 1 3
3 2 6 3 9
4 4 12

02/10/2019 Operations Research 14


Contoh 1: stage 1
X1 f1(S1, X1)
S1 0 1 2 f1*(S1) X1*
3 x x 6 6 2
4 x 5 x 5 1
5 0 x x 0 0

02/10/2019 Operations Research 15


Contoh 1: stage 2
X2 f2(S2, X2)
S2 0 2 3 4 f2*(S2) X2*
0 x x 15 17 17 4
1 x 14 14 12 14 2 atau 3
2 x 13 9 x 13 2
3 6 8 x x 8 2
4 5 x x x 5 0
5 0 x x x 0 0

02/10/2019 Operations Research 16


Contoh 1: stage 3
X3 f3(S3, X3)
S3 0 1 f3*(S3) X3*
0 17 17 17 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
02/10/2019 Operations Research 17
Contoh 1: Rekursif Mundur
X3 f3(S3, X3)
S3 0 1 f3*(S3) X3*
0 0 0 0
1 0 3 3 1
2 0 3 3 1
3 0 3 3 1
4 0 3 3 1
5 0 3 3 1

02/10/2019 Operations Research 18


Contoh 1: Rekursif Mundur
X2 f2(S2, X2)
S2 0 2 3 4 f2*(S2) X2*
0 0 0 0
1 3 3 0
2 3 8 8 2
3 3 11 9 11 2
4 3 11 12 12 12 3 atau 4
5 3 11 12 15 15 4

02/10/2019 Operations Research 19


Contoh 1: Rekursif Mundur
X1 f1(S1, X1)
S1 0 1 2 f1*(S1) X1*
5 15 17 17 17 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
02/10/2019 Operations Research 20
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

02/10/2019 Operations Research 21


Contoh 2

Thousands of Additional Person-


Years of Life
Number of Country
Medical Teams 1 2 3
1 45 20 50
2 70 45 70
3 90 75 80
4 105 110 100
5 120 150 130

02/10/2019 Operations Research 22


Contoh 2: Stage 3
X3 f3(S3, X3)
S3 1 2 3 f3*(S3) X3*
1 45 45 1
2 45 70 70 2
3 45 70 90 90 3

02/10/2019 Operations Research 23


Contoh 2: Stage 2
X2 f2(S2, X2)
S2 1 2 3 f2*(S2) X2*
2 65 65 1
3 90 90 90 1 atau 2
4 110 115 120 120 3

02/10/2019 Operations Research 24


Contoh 2: Stage 1
X1 f1(S1, X1)
S1 1 2 3 f1*(S1) X1*
5 170 160 145 170 1

 Alokasi Tim Medis


◦1–3–1
◦ Total additional person-years of life =
170.000

02/10/2019 Operations Research 25


Contoh 2: asumsi suatu negara boleh
tidak dikunjungi tim medis sama sekali

02/10/2019 Operations Research 26


Contoh 2: asumsi suatu negara boleh
tidak dikunjungi tim medis sama sekali

02/10/2019 Operations Research 27


Contoh 2: asumsi suatu negara boleh
tidak dikunjungi tim medis sama sekali
X3 f3(S3, X3)
S3 0 1 2 3 4 5 f3*(S3) X3*
0 0 0 0
1 0 45 45 1
2 0 45 70 70 2
3 0 45 70 90 90 3
4 0 45 70 90 105 105 4
5 0 45 70 90 105 120 120 5

X2 f2(S2, X2)
S2 0 1 2 3 4 5 f2*(S2) X2*
0 0 0 0
1 45 20 45 1
2 70 65 45 70 1
3 90 90 90 75 90 0 atau 1 atau 2
4 105 110 115 120 110 120 3
5 120 125 135 145 155 150 155 4

02/10/2019 Operations Research 28


Contoh 2: asumsi suatu negara boleh
tidak dikunjungi tim medis sama sekali
X1 f1(S1, X1)
S1 0 1 2 3 4 5 f1*(S1) X1*
5 155 170 160 150 145 130 170 1

 Alokasi tim medis


◦1–3–1
◦ Total additional person-years of life =
170.000

02/10/2019 Operations Research 29


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.

02/10/2019 Operations Research 30


Soal 1
estimated grade points
number of courses
study days 1 2 3 4
1 3 5 2 6
2 5 5 4 7
3 6 6 7 9
4 7 9 8 9

02/10/2019 Operations Research 31


Soal 2
 Sebuah lembaga penelitian merencanakan
suatu proyek penelitian. Terdapat tiga tim
yang akan menyelesaikan proyek tersebut
dengan pendekatan yang berbeda. Ketiga tim
mempunyai kemungkinan gagal berturut-turut
sebesar 0,4; 0,6; dan 0,8 sehingga
kemungkinan proyek tersebut gagal adalah
sebesar 0,4 x 0,6 x 0,8 = 0,192.
 Untuk mengurangi tingkat kegagalan proyek,
ada dua pakar yang ditugaskan untuk
membantu kerja tim peneliti. Seorang pakar
hanya bisa bergabung di satu tim. Tapi satu
tim boleh dibantu oleh lebih dari satu pakar.

02/10/2019 Operations Research 32


Soal 2
 Data perkiraan tingkat kegagalan tim
apabila dibantu oleh pakar:
Jumlah pakar Tingkat kegagalan
yang bergabung Tim 1 Tim 2 Tim 3
0 0,40 0,60 0,80
1 0,20 0,40 0,50
2 0,15 0,20 0,30

 Tujuan: minimasi tingkat kegagalan

02/10/2019 Operations Research 33


Soal 3
 Selama satu horizon perencanaan
produksi yang terdiri dari tiga bulan,
permintaan akan produk A adalah satu
unit produk per bulan
 Jika inventory di awal dan akhir horizon
perencanaan harus nol dan tidak
diijinkan terjadi stok kosong pada saat
permintaan datang, maka dalam tiap
bulannya minimal harus tersedia satu
unit produk. Pada bulan pertama harus
diproduksi minimal satu unit produk. Stok
pada bulan ketiga harus nol.

02/10/2019 Operations Research 34


Soal 3
 Untuk memenuhi permintaan selama
tiga bulan tersebut, produk dapat
diproduksi sekaligus dalam satu bulan
tertentu dengan resiko biaya simpan
tinggi atau diproduksi dalam tiap bulan
dengan resiko biaya setup tinggi
 Tujuan: menentukan kebijakan
produksi yang menghasilkan ongkos
total minimum.

02/10/2019 Operations Research 35


Soal 3
 Rincian biaya
Biaya Bulan ke-

1 2 3
Setup cost/run production
14 8 12
Production cost/unit
10 8 10
Holding cost/unit ending in inventory
4 2 6

02/10/2019 Operations Research 36


Soal 4
 Perusahaan X mempunyai data
kebutuhan produksi dari produk A
untuk 3 periode ke depan:

Periode Kebutuhan Produksi

1 2 unit
2 2 unit
3 3 unit
02/10/2019 Operations Research 37
Soal 4
 Setiap kali run produksi dihasilkan 1 unit produk A.
Biaya setup untuk run pertama (1 unit pertama) adalah
$20 dalam setiap periode dan naik sebesar $2 untuk
setiap tambahan 1 unit yang diproduksi pada periode
tersebut.
 Biaya produksi + overhead untuk tiap periode konstan
sehingga dapat diabaikan dalam perhitungan
 Biaya simpan untuk setiap 1 unit kelebihan produk
adalah $3 per periode
 Kapasitas maksimum gudang adalah 3 unit per periode
 Inventori awal periode 1 = 0, inventori akhir periode 3 =
0
 Tujuan: menentukan kebijakan produksi yang
menghasilkan ongkos total minimum

02/10/2019 Operations Research 38

You might also like