Penelitian Operasional II Programa Dinamik 1 1. PROGRAM DINAMIK

Penelitian Operasional II

Programa Dinamik 1 1. PROGRAM DINAMIK

1.1 PENDAHULUAN Definisi 1.1: Program dinamik adalah suatu teknik matematik untuk menentukan serangkaian keputusan yang saling terkait, serta memberikan suatu prosedur yang sistematik untuk menentukan kombinasi optimal dari keputusan yang hendak ditentukan itu. Perbedaan antara program dinamik dengan program linear adalah : ! Pada masalah program dinamik tidak terdapat rumusan matematika secara baku ! Progam dinamik adalah suatu tipe penyelesaian masalah yang didekati secara umum. 1.2 CONTOH PROTOTYPE Contoh 1.2: Ada seorang pengembara yang hendak berjalan dari Kota A menuju Kota J, ditangannya terbentang sehelai peta yang mengambarkan arah perjalanan beserta jaraknya. Jalan-jalan yang manakah yang harus dipilih oleh pengembara ini agar jarak tempuh yang akan dilaluinya sependek mungkin. 7 B

E

4 6

1 4 H

2

3

A

4

6 2 4

C

3

F

J

3

3 I

3 state

stage1

D

4

1 5

stage2

G

3

stage3

Gb.1.1 Peta dari kota A menuju ke Kota J

Siana Halim – Teknik Industri – UK. Petra

4

stage4

Programa Dinamik 2


Penyelesaian Permasalahan di atas dapat dibagi menjadi 4 tahapan (stage) seperti terlihat pada gambar. Pada tiap tahapan ini akan ditentukan : ! Peubah keputusan : xn (n = 1,2,3,4) adalah tujuan langsung pada stage n ! Jalur yang dipilih : A x1 x2 x3 x4 = J ! Misalkan fn(s,xn) adalah total jarak yang terpendek ditempuh dari seluruh kebijakan (polcy) untuk tahapan-tahapan yang tersisa, pada saat pengembara ini berada di state s dan siap untuk memulai tahapan ke-n serta memilih xn sebagai tujuan berikutnya. ! Diberikan s dan n Misalkan xn* menunjukkan nilai xn yang meminimumkan fn(s,xn) dan fn*(s) adalah nilai minimumnya, yaitu : fn*(s) = min fn(s,xn) = fn(s,xn*) dimana Xn

fn(s,xn) = Biaya pada tahapan ke-n + Biaya minimum pada tahapan ke-n+1 = C sxn + f*n+1(xn) karena tujuan akhir (state J) dicapai pada tahapan terakhir yaitu tahapan ke-4, maka f*5(J) = 0 * ! Tujuan : mendapatkan f 1(A) dan jalur-jalur yang bersesuaian. Ada dua kemungkinan, yaitu : - Mundur : f*5(J) f*4(s) f*3(s) f*2(s) f*1(A) * * * * - Maju :f 1(A) f 2(s) f 3(s) f 4(s) f*5(J) Prosedur Penyelesaian n=4 S

f4*(s)

x4 *

H

3

J

I

4

J

n=3 x3 s E F G

f3(s,x3)=csx3 + f4*(x3) H I 1+3=4 4+4=8 6+3=9 3+4=7 3+3=6 3+4=7

f3*(s)

x3 *

4 7 6

H I H



Programa Dinamik 3

n=2 x2 S

B C D

f2(s,x2)=csx2 + f3*(x2) E F G 7+4=11 4+7=11 6+6=12 3+4=7 2+7=9 4+6=10 4+4=8 1+7=8 5+6=11

f2*(s)

x2 *

11 7 8

E/F E E/F

f1(s,x1)=csx1 + f2*(x1) B C D 2+11=13 4+7=11 3+8=11

f1*(s)

x1 *

11

C/D

n=1 x1 S

A

Biaya minimum adalah 11 Jalur yang ditempuh adalah : A A

C D

E E F

H H I

J J J

atau

1.3 KARAKTERISTIK DARI MASALAH-MASALAH PADA PROGRAM DINAMIK (1) Masalah tersebut dapat dibagi ke dalam tahapan-tahapan, serta membutuhkan sebuah keputusan kebijakan (policy decision) pada tiap tahapan. (2) Tiap tahapan memiliki sejumlah state yang bersesuaian dengannya. Secara umum, state memiliki berbagai macam kemungkinan kondisi tergantung pada sistem yang ada pada tahapan masalah tersebut. Jumlah dari state mungkin terbatas mungkin pula tak terbatas. (3) Efek dari kebijakan keputusan yang diambil pada tiap tahapan adalah untuk mentransformasikan state pada saat itu ke state yang bersesuaian pada tahapan berikutnya (dimungkinkan juga sebuah sebuah distribusi probabilitas) (4) Prosedur penyelesaian dirancang untuk mendapatkan kebijakan optimal untuk seluruh permasalahan, yaitu, suatu perumusan dari keputusan kebijakan optimal pada tiap tahapan untuk tiap state yang mungkin. (5) Diberikan state saat ini, kebijakan optimal untuk tahapan yang tersisa independen terhadap kebijakan yang diambil pada tahapan-tahapan sebelumnya. (Principle of optimality for dinamic programming) (6) Prosedur penyelesaian diambil dengan mendapatkan kebijakan optimal pada tahapan terakhir. (7) Tersedia suatu relasi rekursif yang mengidentifikasikan kebijakan optimal untuk tahapan ke-n, jika diberikan kebijakan optimal pada tahapan ke-n+1 Siana Halim – Teknik Industri – UK. Petra

Programa Dinamik 4


(8) Jika relasi rekursif ini digunakan, prosedur penyelesaian berpindah mundur tahapan demi tahapan. Tiap kali mendapatkan kebijakan optimal untuk tahapan tersebut hingga didapat kebijakan optimal yang diawali pada tahapan mula-mula. 1.4 PROGRAM DINAMIK DETERMINISTIK Pada masalah-masalah deterministik, state yang berada pada tahapan berikutnya ditentukan seluruhnya berdasarkan state dan kebijakan keputusan pada tahapan saat ini. Sedangkan pada masalah probabilistik, state berikutnya ditentukan pada distribusi probabilitas yang berlaku pada masalah tersebut. Program Dinamik Deterministik Tahapan ke-n State :

Sn

Tahapan ke-n+1 Sn

Kontribusi dari xn fn(sn,xn)

f*n+1(sn+1)

Salah satu cara untuk mengkatagorikan program dinamik deterministik adalah melalui bentuk fungsi obyektifnya. Sebagai contoh, fungsi obyektif tersebut mungkin saja merupakan minimum dari jumlahan kontribusi-kontribusi dari tiaptiap tahapan. Secara khusus, state sn mungkin saja berupa peubah diskrit, kontinu atau mungkin saja berupa suatu vektor. Contoh 1.3: WHO bermaksud untuk menyempurnakan pelayanan kesehatan di negara-negara yang sedang berkembang. Saat ini WHO mempunyai 5 team kesehatan yang harus ditempatkan di 3 negara. WHO harus menentukan berapa team yang harus ditempatkan di tiap-tiap negara, sehingga keefektifan total dari kelima tim ini dapat dimaksimumkan. Sebagai alat ukur dari keefektifan ini ialah pertambahan umur (ribuan orang/tahun) jika tim ini datang ke negara itu. Tabel 1.1 pertambahan umur Pertambahan Umur(Ribuan Orang/Tahun) Jumlah Team yang dialokasikan 1 2 3 0 0 0 0 1 45 20 50 2 70 45 70 3 90 75 80 4 105 110 100 5 120 150 130 Siana Halim – Teknik Industri – UK. Petra


Programa Dinamik 5

Penyelesaian ! Tahapan : Negara (1,2,3) Peubah keputusan : xn = jumlah team yang akan dialokasikan di negara n (n = 1,2,3) State dari sistem : sn = jumlah team medis yang masih tersedia untuk dialokasikan pada negara-negara yang belum menerima bantuan, yaitu n,…,3 !

Membangun fungsi obyektif, berupa fungsi rekursif Misalnya : pI(xi) : ukuran performansi dari pengalokasian xi team medis ke negara-i. 3

∑ p (x )

Fungsi obyektif : max

i

i

i =1

3

Kendala

:

∑x

i

= 5 , xi nonnegatif integer

i =1

dengan menggunakan stuktur dasar program dinamik, dibentuk : 3

fn(sn,xn) = pn(xn) + max

∑ p (x ) i

i

i = n +1

dimana nilai max diambil untuk seluruh xn+1, … , x3 sedemikian hingga 3

∑x

i

= sn ,

xi nonnegatif integer, n = 1,2,3

i =1

selanjutnya : f*n(sn) =

max

fn(sn,xn)

x n = 0 ,1,...,s n

karena itu : fn(sn,xn) = pn(xn) + f *n+1(sn-xn) dengan f*4 = 0 berarti relasi rekursifnya adalah : f*n(sn) =

max { pn(xn) + f

* n+1(sn-xn)},

n=1,2

x n = 0 ,1,...,s n

Tahapan ke-n state

Sn

Tahapan ke-n+1 xn

fn(sn,xn) pn(xn) = pn(xn) + f *n+1(sn-xn)


f

Sn - Xn * n+1(sn-xn)

Programa Dinamik 6 Prosedur n=3 s3 0 1 2 3 4 5


f3*(s3) 0 50 70 80 100 130

x3* 0 1 2 3 4 5

n=2

0 0 50 70 80 100 130

f2(s2,x2) = p2(x2) + f *3(s2-x2) 1 2 3 4 20 15 70 90 75 95 100 115 110 125 120 125 145 160

0 160

f1(s1,x1) = p1(x1) + f *2(s1-x1) 1 2 3 4 165 160 155 170

x2 s2 0 1 2 3 4 5

5 150

f2*(s2)

x2*

0 50 70 95 125 160

0 0 0/1 2 3 4

f1*(s1)

x1*

170

1

n=1 x1 s1 5

5 120

Penyelesaian optimal : x1* = 1, s2 = 5 -1 = 4 x2* = 3, s2 = 4 -3 = 1 x3* = 1, dengan f1*(s) = 170 Contoh 1.4: Nasa sedang mengadakan riset untuk mengatasi masalah rekayasa tertentu yang harus diselesaikan sebelum orang dapat terbang ke planet Mars dengan selamat. Tiga team ilmuwan sedang mencoba tiga pendekatan untuk menyelesaikan masalah ini. Diberikan tabel estimasi probabilitas yang menyatakan kegagalan bila ditambahkan 0,1,2 ilmuwan pada team tersebut. Jumlah ilmuwan Probabilitas Kegagalan baru Team 1 2 3 0 0.40 0.60 0.80 1 0.20 0.40 0.50 2 0.15 0.20 0.30 Siana Halim – Teknik Industri – UK. Petra


Programa Dinamik 7

Bagaimana cara mengalokasikan ilmuwan-ilmuwan baru ini agar didapat probabilitas kegagalan minimum. Penyelesaian Tahapan : Team peneliti (n = 1,2,3) State Sn : Jumlah ilmuwan baru yang masih tersedia untuk dialokasikan pada team yang tersisa. Peubah keputusan : xn : jumlah ilmuwan tambahan yang dialokasikan pada team n Mis : pi(xi) = probabilitas kegagalan dari team I jika diberi tambahan xI ilmuwan Fungsi obyektif : 3

∏

Min

pi(xi)

i =1

3

∑

Kendala :

xi =2, xi nonnegatif integer

i =1

Fungsi rekursifnya : fn(sn,xn) = pn(xn) 3

= Min

∏

pi(xi)

i =1

dimana nilai minimum diambil atas xn+1, … , x3 sedemikian hingga : 3

∑

xi = sn ,

xi nonnegatif integer

i =1

Tahapan ke-n state

Sn

Tahapan ke-n+1 xn

fn(sn,xn) pn(xn) = pn(xn) . f *n+1(sn-xn) Jadi untuk n = 1,2,3 : fn*(sn) =

Min fn(sn,xn) xn ≤ sn

fn(sn,xn) = pn(xn) f*n+1(sn-xn) fn*(sn) = Min { pn(xn) f*n+1(sn-xn)} n = 1,2 xn ≤ sn

f3*(s3) =

Min p3(x3) x3 ≤ s 3


f

Sn - Xn * n+1(sn-xn)

Programa Dinamik 8 Prosedur n=3 s3 0 1 2


f3*(s3) 0.80 0.50 0.30

x3* 0 1 2

n=2 x2 s2 0 1 2

f2(s2,x2) = p2(x2) . f3*(s2 – x2) 0 1 2 0.6*0.8=0.48 0.6 *0.5=0.30 0.4*0.8=0.32 0.6*0.3=0.18 0.4*0.5=0.20 0.2*0.8=0.16

f2*(s2)

x2 *

0.48 0.30 0.16

0 0 2

n=1 x1 s1 2

F1(s1,x1) = p1(x1) . f2*(s1 – x1) 0 1 2 0.4*0.16=0.064 0.2*0.3=0.06 0.15*0.48=0.072

f1*(s1)

x1*

0.060

1

x1*= 1, s2 = 2-1 = 1 x2*= 0, s3 = 1-0 = 1 x3*= 1, f1*(s1) = 0.060 Contoh 1.5 Beban kerja pada suatu perusahaan yang menerapkan local job shop berfluktuasi secara musiman. Namun demikian, terdapat kesulitan untuk mempekerjakan operator-operator mesin dan biaya trainingnya mahal. Karena itu pihak manajer agak segan untuk mengurangi jumlah pekerja selama jumlah permintaan sedikit. Dia lebih menyukai untuk mengeluarkan pembayaran seperti pada saat jumlah permintaan banyak walaupun hal ini tidak diperlukan. Dia juga tidak menyukai kerja lembur. Karena seluruh pekerjaan dilakukan dengan cara-cara biasa, tidaklah dimungkinkan adanya inventori selama jumlah permintaan sedikit. Bagaimana kebijakan yang harus diambil oleh manajer ini ? Diberikan estimasi jumlah tenaga kerja minimum adalah sbb : Musim Semi Panas Gugur Dingin Kebutuhan 255 220 240 200

Semi 255

Jumlah pekerja tidak boleh lebih rendah dari kebutuhan di atas. Jika jumlah pekerja melebihi kebutuhan, akan terjadi pemborosan sebesar $2000/orang/musim. Estimasi dari biaya mengangkat dan memecat pegawai sedemikian hingga total biaya dari perubahan jumlah pekerja dari satu musim ke musim berikutnya adalah $200 kali kuadrat beda jumlah / level pekerja. Jumlah pekerja ini mungkin berupa pecahan, karena adanya pekerja paruh waktu, demikian juga dengan upahnya. Siana Halim – Teknik Industri – UK. Petra

Penelitian Operasional II Programa Dinamik 1 1. PROGRAM DINAMIK

Recommend Documents