program dinamis

31
PROGRAM DINAMIS (DYNAMIC PROGRAMMING) Oleh : Harri Trianto Sinaga 100423028 Bresman Siahaan 100423032 RNF.P. Adi Putra S. 100423034

Upload: putra-manullang

Post on 29-Jun-2015

211 views

Category:

Documents


5 download

TRANSCRIPT

Page 1: Program Dinamis

PROGRAM DINAMIS(DYNAMIC PROGRAMMING)

Oleh :

Harri Trianto Sinaga 100423028

Bresman Siahaan 100423032

RNF.P. Adi Putra S. 100423034

Page 2: Program Dinamis

PROGRAM DINAMIS

Program Dinamis (dinamic programing) adalah suatu kumpulan teknik-teknik programisasi matematis yang digunakan untuk mengambil keputusan yang terdiri dari banyak tahap (multistage).

Page 3: Program Dinamis

APLIKASI PROGRAM DINAMIS

scheduling produksi

pengendalian persediaan

analisa network

proyek-proyek penelitian

pengembangan.

Page 4: Program Dinamis

KONSEP-KONSEP DAN KARAKTERISTIKDASAR

1. Masalah Jalur- OptimumTujuan :

memilih route yang paling rendah biayanya

(minimum total cost) untuk sampai ketujuan. Route dengan biaya yang palingrendah disebut jalur optimum

Page 5: Program Dinamis

Dalam network ada 10 lingkaran dengan nomor yang telah ditentukan. Lingkaran 1 adalah asal dan 10 adalah tujuan. Mulai dari lingkaran 1 harus menentukan mana route yang akan diambil melalui lingkaran 2 atau 3. ini adalah segmen pertama yang disebut stage (tahap). Pemilihan jalur optimum memerlukan pemakaian keijakan yang memberikan hasil yang baik (optimal policy)

Page 6: Program Dinamis

NETWORK FLOWCHART

1 5

3

8

7

9

2

4

6

10

I II III IV

12

10

11

98

87

6

10 5

6

7

7

7

10

10

11

tahap

Page 7: Program Dinamis

2. PROSEDUR PERHITUNGAN

Teknik perhitungan programasi dinamis didasarkan pada prinsip optimisasi recursive (bersifat pengulangan).

di mana:

fn(C) menunjukkan biaya total minimum yang dihubungkan dengan jalur optimum dalam network.

fn(C) = min Cij + fj (C)

Page 8: Program Dinamis

fj(C) adalah biaya minimum perjalanan dari lingkaran ke j dalam satu tahap ke lingkaran terakhir (recurcive equation

Cij menunjukkan biaya yang terlibat dalam pergerakan lingkaran i pada tahap tertentu ke lingkaran bej.

Page 9: Program Dinamis

f7 (C) = C7,10 =12

f8(C) = C8,10 =10

f 9(C) = C9,10 =11

Kemudian dalam hal ini ada tiga lingkaran dalam tahap III. Harus diputuskan jalur dengan biaya terendah melalui lingkaran perantara. Lingkaran 4 mempunyai dua route yang menuju ke lingkaran terakhir 10 melalui linkaran perantara 7 dan 8, maka didapatkan hasil sebagai berikut:

Page 10: Program Dinamis

f4(C) = min C4,7 + f7(C) = 7 +12 =19 =19

C4,8 + f8(C) =10 +10 =20

Dengan dapat dipilihnya tiga route dari lingkaran 5untuk mencapai lingkaran 10, didapatkan hasil:

f5(C) = min C5,7 + f7(C) = 7 +12 =19

C5,8 + f8(C) = 5 +10 =15 =15

C5,8 + f9(C) = 8 +11 =19

Page 11: Program Dinamis

Sama dengan cara diatas, dua jalur dari lingkaran 6 ke 10 mempunyai biaya-biaya :

f6(C) = min C6,8 + f8(C) = 11 +10 =21 =18

C6,9 + f9(C) = 7 +11 =18

Dengan membanginkan ketiga biaya minimum diatas, 19,15 dan 18, maka dipilih nilai terkecil dari ketiganya yaitu 15. ini menunjukkan jalur dengan biaya terendah dari tahap III. Jadi, jalur tersebut adalah 5 8 10

Page 12: Program Dinamis

Sekarang, route diperluas dengan mengikut sertakan lingkaran dari tahap Iidan mencari jalan dengan biaya terendah yang mencakup tahap II,III,IV. Karena ada dua lingkaran dalam tahap II, didapatkan hasil sebagai berikut:

f2(C) = min C2,4 + f4(C) = 6 +17 =23 =21

C2,5 + f5(C) =8 +13 =21

Page 13: Program Dinamis

f3(C) = min C3,4 + f4(C) =11 +17 =28 C3,5 + f5(C) = 7 +13 =20 = 20

C3,6 + f6(C) = 6 +16 =22

Dipilih nilai yang paling kecil yaitu 20 diantara dua nilai minimum dari persamaan diatas, jadi least-cost part menghubungkan lingkaran-lingkaran

3 5 8 10

Akhirnya, dihitung biaya untuk keseluruhan tahap. Persamaan recurvice untuk route yang dimulai dari lingkaran 1 termasuk seluruh tahap adalah

Page 14: Program Dinamis

f1(C) = min C1,2 + f2(C) = 8 +17 =25 =21

C1,3 + f3(C) =5 +16 =21

Page 15: Program Dinamis

MATEMATIS PROGRAMASI DINAMISMaksimumkan fn (X) = Σ rj (Xj)

Dengan batasan : X = Σ Xj

Dan Xj ≥ 0 (j = 1,2,......,n)

Dimana :

fn (X) = penghasilan total dari seluruh kegiatan

Xj = kuantitas smber daya yg dialokasikan ke kegiatan (tahap) ke- j.

rj (Xj) = penghasilan (reward) dari kegiatan ke -j.

µ = jumlah kegiatan (tahap) bebas (independent)

X = sumber daya total yang tersedia untuk µ kegiatan-kegiatan

Page 16: Program Dinamis

CONTOH APLIKASI PROGRAMASI DINAMIS1. Masalah Scheuduling Prroduksi dan Pengendalian Persediaan

Perusahaan “Dilarang Rugi” adalah sebuah perusahaan kecil yang memproduksi hanya satu produk. Permintaan (penjualan) untuk produk tersebut dalam tiga periode 1,2, dan 3, secara berturut-turut 20, 30 dan 40 unit. Produk sekarang diproses dalam beberapa tahap sebesar 10 unit setiap periode. Pada permulaan setiap periode dilakukan penyetelan mesin untuk memproduksi sebesar kuantitas yang dibutuhkan. Biaya produksi set up untuk 10 unit pertama adalah Rp 20 setiap periode dan naik dengan Rp 2 untuk setiap tambahan 10 unit yang diproduksi. Biaya produksi dan overhead sehubungan dengan produksi 70 unit dalam keseluruhan periode tidak dipengaruhi oleh keputusan produksi, oleh sebab itu hal tersebut tidak ikut dipertimbangkan dalam kasus ini

Page 17: Program Dinamis

Perusahaan dapat memproduksi 70 unit dalam sesuatu periode. Produk yang tidak terjual dalam sesuatu periode, disimpan sebagai persediaan. Biaya penyimpanan persedaan untuk 10 unit adalah Rp 3 dalam setiap periode. Karena keterbatasan gudang penyimpanan, persediaan maksimum tidak dapat lebih dari 30 unit setiap periode. Dianggap tidak ada persediaan pada permulaan periode pertama. Oleh karena itu, total biaya terdiri dari biaya set up produksi dan biaya penyimpanan persediaan. Masalah yang timbul pada perusahaan adalah penentuan skedul dalam setiap periode agar total biaya untuk keseluruhan periode adalah minimum dan dapat memenuhi kebutuhan pejualan. Anggap semua biaya dalam ratusan ribu rupiah.

Page 18: Program Dinamis

Meminimumkan :

C = [ (20 + 0,2 (Xi – 10)] + 0,3 Ii }

dengan batasan :

X1 ≥ 20

X1 + X2 ≥ 40

X1 + X2 + X3 = 70

I1 ≤ 30

I2 ≤ 30

Dan X2, X3 , I1 , I2 ≥ 0

Dimana C = biaya total

Xi = jumlah produk yang diproduksi dalam periode i.

Ii = jumlah persediaan akhir periode i (jumlah ini sama dengan jumlah persedian awal periode i + I)

3

1i

Page 19: Program Dinamis

Penyelesaian yang optimal dapat ditentukan dengan persamaan recursive :

fn (X) = max [ rn (Xn ) + fn-1 (X-Xn ) ]

n = 2,3, .............Setelah persediaan akhir setiap periode diukur dari perbedaan antara

jumlah persediaan awal, ditambah produksi dan volume penjualan (penjualan awal = produksi – penjualan) :

Ii = Ii-1 + X1 – S1

AtauIi-1 = Ii + Si – Xi (untuk i = 1, 2, 3)

Dimana Si adalah jumlah dalam periode i.

Penyimpanan persediaan tidak dapat melebihi 30 unit dalam setiap periode; jadi didapatkan :

0 ≤ Ii-1 ≤ 30

Jumlah produksi Xi dapat ditunjukan sebagai

Ii + Si – 30 ≤ Xi ≤ Ii + Si

Page 20: Program Dinamis

Persamaan recursive dalam bentuk :

fn (In ) = min [Cn (Xn + In ) + fn-1 (In – 1)]

In + Sn – 30 ≤ Xn ≤ In + Sn

Persamaan recursive dapat ditulis dengan pers. 9.1 :

fn (In ) = min [Cn (Xn + In ) + fn-1 (In + Sn – Xn )]

In + Sn – 30 ≤ X ≤ In + Sn

Dalam persamaan 9.4, C adalah fungsi dari jumlah produksi dan persediaan. Sebagai langkah pertama, f1 (I1 ) harus ditentukan karena akan mempengaruhi nilai f2 (I2 ). Persamaan recursive untuk periode pertama adalah :

F1 (I1 ) = min { C1 (X1 + I1 ) }

20 ≤ X1

Page 21: Program Dinamis

Diketahui S1 = 20 (jumlah penjualan dalam

periode pertama dan 0 ≤ I1 ≤ 30, dari hal ini

didapatkan hasil berikut ini:f1(0) = C1(20 + 0) = 22+0 =22

f1(10) = C1(30 +10) =24+3 =27

f1(20) = C1(40 +20) = 26+6 =32

f1(30) = C1(50 +30) = 28+9 =37

Page 22: Program Dinamis

Hasil ini dimasukkan ke kolom periode 1Sebagai langkah selanjutnya, nilai dari

f2(I2)

harus ditentukan atas dasar f1(I1).

Persamaanrecurvise untuk tahap kedua adalah:

f2(I2) = min {C2(X2+I2) + f1(I2+S2– X2)}

I2+S2–30 ≤ X2 ≤I2+ S2

Page 23: Program Dinamis

Bila I2 = 0

f2(0) = min {C2(X2+0) + f1(0+S2– X2)}

0 ≤ X2 ≤ 20

Nilai-nilai f2(0) bila 0 ≤ X2 ≤ 20 adalah

C2 (0+0) + f1 (0 +20 -0) = 0 + 32 =32

f2(0) = C2 (10+0) + f1 (0 +20 -10) = 20 + 27 =47 =32 C2 (20+0) + f1 (0 +20 -20) = 22 + 22 =44

Jadi didapatkan nilai minimum =32 pada X2= 0

Page 24: Program Dinamis

Bila I2 = 10

f2(10) = min { C2(X2 + 10) + f1(10 + 20 – X2)}

0 ≤ X2 ≤ 30

Nilai-nilai f2(10) bila 0 ≤ X2 ≤ 30 adalah

C2(0 + 10) + f1(10 + 20 - 0) = 0 +3 + 7 = 40

f2 (10) =min C2(10 + 10) + f1(10+20-10)= 20 +3 + 32 = 55 = 40

C2(20 + 10) + f1(10+20-20)= 22 +3 + 27 = 52 C2(30 + 10) + f1(10+20-30)= 24 +3 + 22 = 49

Nilai minimum f2(10)= 40 diperoleh pada X2 = 0

Page 25: Program Dinamis

Bila I2 = 20

f2(20) = min { C2(X2 + 20) + f1(20 + 20 – X2)}

10 ≤ X2 ≤ 40

Nilai-nilai f2(20) bila 0 ≤ X2 ≤40 adalah

C2(10 + 20) + f1(20+20-10)= 20 +6 + 37 = 63

f2 (20)=min C2(20 + 20) + f1(20+20-20)= 22 +6 + 32 = 60 = 54

C2(30 + 20) + f1(20+20-30)= 24 +6 + 27 = 57

C2(40 + 20) + f1(20+20-40)= 26 +6 + 22 = 54

Nilai minimum f2(10)= 54 diperoleh pada X2 = 40

Page 26: Program Dinamis

Bila I2 = 20

f2(20) = min { C2(X2 + 20) + f1(20 + 20 – X2)}

10 ≤ X2 ≤ 40

Nilai-nilai f2(20) bila 0 ≤ X2 ≤40 adalah

C2(10 + 20) + f1(20+20-10)= 20 +6 +37=63

f2 (20) = min C2(20 + 20) + f1(20+20-20)= 22 +6 +32=60 = 54

C2(30 + 20) + f1(20+20-30)= 24 +6 +27=57

C2(40 + 20) + f1(20+20-40)= 26 +6 +22=54

Nilai minimum f2(10)= 54 diperoleh pada X2 = 40

Page 27: Program Dinamis

Bila I2 =30

f2(30) = min {C2(X2+30) + f1(30+20 – X2)}

10 ≤ X2 ≤ 50

Untuk 20 ≤ X2 ≤ 50, maka nilai-nilai f2 (30) adalah

C2(20+30)+f1(30 +20 -20) = 22+9+37=8

f2(30)=min C2(30+30)+f1(30 +20 -30)= 24+9+32=65 =59

C2(40+30)+f1(30 +20 -40) = 26+9+27=62

C2(50+30)+f1(30 +20 -50) = 28+9+22=59

Maka didapatkan nilai minimum f2(30) =59. hasil ini diperoleh pada X2= 50. Jadi perhitungan untuk tahap kedua telah selesai.

Page 28: Program Dinamis

Tabel .1 Tabel hasil perhitungan

Akhirnya diperoleh nilai f3 (I3 ) dengan cara yang sama persamaan recursivenya adalah :

f3 (I3 ) = min { C3 (X3 + I3 ) + f2 (I3 + S3 – X3 ) }

I3 + S3 – 30 ≤ X3 ≤ I3 + S3

I1 Periode 1 Periode 2 Periode 3

X1 f(I1 ) X2 f2 (I2 ) X3 f3 (I3 )

0102030

203040*

50

22273237

0*

04050

32405459

30* 56

Page 29: Program Dinamis

f3 (I3 ) = min { C3 (X3 + I3 ) + f2 (I3 + S3 – X3 ) }

I3 + S3 – 30 ≤ X3 ≤ I3 + S3

Untuk 0 ≤ X3 ≤ 30, didapatkan :

C3(0 + 0) + f1(0+30-10)= 0 +0 + 37 = 63

f3 (20) = min C3(10 + 0) + f1(0+30-20)= 20 +0 + 32 = 60 = 56

C3(20 + 0) + f1(0+30-30)= 22 +0 + 27 = 57

C3(30 + 0) + f1(0+30-40)= 24 +0 + 22 = 54

Nilai minimum f3 (0 ) = 56 pada X3 = 30. Nilai ini dimasukkan

padakolom periode ketiga tabel 1. Untuk I3 > 0 tidak diperlukan

dalam masalah tiga tahap ini, maka perhitungan untuk tiap

periode telah selesai. 

Page 30: Program Dinamis

Dari tabel 1. di Rp. 56 pada X3=30. Karena I2 = I3 + S3 – X3 dari persamaan 9.1 didapatkan I2 = 0 (yaitu 0 = 0 + 30 – 30). Selanjutnya total biaya pada periode ketiga adalah Rp24. Selisihnya = Rp32 (56-24) didapatkan pada X2 =0. Oleh sebab itu, jumlah tersebut pasti berasal dari kolom periode 1. Didapatkan f1(20) = Rp32 pada X1=40. Ini juga memenuhi persamaan 9.1 I1 = I2 + S2 – X2 (yaitu, 20 = 0 + 20 – 0).

Page 31: Program Dinamis

tabel 2. Hasil optimal

Periode Produksi Penjualan Persediaan

Biaya

1 40 20 20 26 +6 =32

2 0 20 0 o

3 30 30 0 24 +0 = 24

Total 70 70 20 Rp 56