Modul 8 Pemrograman Dinamis

MODUL 8 PEMROGRAMAN DINAMIS PRAYUDI

KONSEP-KONSEP DASAR 



 



Pemrograman dinamis adalah suatu teknik matematis untuk pembuatan serangkaian-serangkaian keputusan yang salaing berhubungan. Pemrograman dinamis menyediakan prosedur sistematis untuk menentukan kombinasi keputusan yang optimal Pemrograman dinamis pada umumnya menyelesaikan masalah dalam tahapan-tahapan, perhitungan di setiap tahapan dihubungkan melalui perhitungan rekursif yang menghasilkan solusi optimal. Pemrograman dinamis dibedakan menjadi pemrograman dinamis masalah deterministik dan probabilistik Pemrograman dinamis deterministik dicirikan dimana keadaan pada tahap berikutnya ditentukan sepenuhnya oleh keadaan dan keputusan pada tahap sekarang. Masalah deterministik dapat dibedakan antara kasus maksimum dan minimum Pemrograman dinamis probabalistik, dimana keadaan berikutnya memiliki suatu distribusi probabilitas tertentu.

CIRI-CIRI PEMROGRAMAN DINAMIS 

Permasalahan dapat dibagi dalam tahap-tahap dengan suatu keputusan kebijakan (policy decision) diperlukan di setiap tahap



Setiap tahap memiliki sejumlah keadaan (state) yang bersesuaian



Pengaruh keputusan pada setiap tahap adalah untuk merubah keadaan sekarang menjadi keadaan yang berkaitan dengan tahap berikutnya



Prosedur penyelesaian dirancang untuk menemukan kebijakanoptimal keseluruhan masalah, melalui keputusan optimal pada setiap tahap



Bila diketahui keadaan sekarang optimal, untuk tahap yang tersisa adalah bebas terhadap kebijakan yang dipakai pada tahaptahap sebelumnya



Prosedur penyelesaian dimulai dengan menentukan kebijakan optimal untuk tahap terakhir



Tersedia hubungan rekursif yang menyediakan kebijakan optimal pada tahap n, bila diketahui kebijakan optimal untuk tahap

CONTOH : MAKSIMUM Sebuah perusahaan pem bangkit m em punyai t iga usulan proposal unt uk m em bangun PLTU di t iga daerah yang pat uh dipert im bangkan. Perusahaan m enyediakan anggaran sebesar $ 10 jut a unt uk ket iga alokasi. Set iap proposal dim int a m enyam paikan usulannya dengan m eringkaskan biaya (jut a dollar) dan daya list rik (MW) yang dihasilkan ----------------------------------------------------------------------PLTU Serang PLTU Pacit an PLTU Cirebon Usulan c1 R1 c2 R2 c3 R3 --------------------------------------------------------------------1 0 0 0 0 0 0 2 2 20 1 10 3 60 3 6 80 3 50 5 80 4 5 70 ----------------------------------------------------------------------Tent ukanlah pem ecahan yang opt im al

SOLUSI MODEL DP MAKSIMUM          

Keputusan tahap 1 : mengoperasikan PLTU Serang Keputusan tahap 2 : mengoperasikan PLTU Pacitan Keputusan tahap 3 : mengoperasikan PLTU Cirebon x1 : jumlah dana yang dialokasikan untuk tahap 1 x2 : jumlah dana yang dialokasikan untuk tahap 1 dan 2 x3 : jumlah dana yang dialokasikan untuk tahap 1, 2 dan 3 Rj(kj) : pendapatan/benefit alternatif kj pada tahap j fj(xj) : pendapatan/benefit optimal tahap 1, 2, ,,,, dan jika keadaan xj. f1( x1) = maxrekursif-nya {R1(k1)} Persamaan adalah : c1(k1)≤ x1

fj(x j ) =

max {R j (k j ) + f j−1[ x j − c j (k j )]}

c j (k j )≤ x j

{R1(k1)},k1 = 1,2,3 TAHAP 1 :f1(x1) = c (max k )≤ x 1 1

1

R1(k1) Pemecahan Optimal -----------------------------------------------------------x1 k1=1 k1=2 k1=3 c1=0 c1=2 c1=6 f1(x1) k1* ------------------------------------------------------------------0 0 - - 0 1 1 0 - - 0 1 2 0 20 - 20 2 3 0 20 - 20 2 4 0 20 - 20 2 5 0 20 - 20 2 6 0 20 80 80 3 7 0 20 80 80 3 8 0 20 80 80 3 9 0 20 80 80 3 10 0 20 80 80 3 ---------------------------------------------------------------------

TAHAP 2 :

f2 ( x 2 ) =

R2(k2)

max

c 2 (k 2 )≤ x 2

+ f1[ x2 – c2(k2)]

{R 2 (k 2 ) + f1[ x 2 − c 2 (k 2 )]},k 2 = 1,2,3,4

Pem ecahan

Opt im al ------------------------------------------------------------------------------------x2 k2= 1 k2= 2 k2= 3 k2= 4 c2= 0 c2= 1 c2= 3 c2= 5 f2(x2) k2* --------------------------------------------------------------------------------------------0 0+ 0= 0 0 1 1 0+ 0= 0 10+ 0= 10 10 2 2 0+ 20= 20 10+ 0= 10 20 1 3 0+ 20= 20 10+ 20= 30 50+ 0= 50 50 3 4 0+ 20= 20 10+ 20= 30 50+ 0= 50 50 3 5 0+ 20= 20 10+ 20= 30 50+ 20= 70 70+ 0= 70 70 3or4 6 0+ 80= 80 10+ 20= 30 50+ 20= 70 70+ 0= 70 80 1 7 0+ 80= 80 10+ 80= 90 50+ 20= 70 70+ 20= 90 90 2or4 8 0+ 80= 80 10+ 80= 90 50+ 20= 70 70+ 20= 90 90

TAHAP 3 : R3(k3)

f3 ( x 3 ) =

max

c 3 (k 3 )≤ x 3

+ f2[ x3 – c3(k3)]

{R3 (k 3 ) + f2 [ x 3 − c 3 (k 3 )]},k 3 = 1,2,3

Pem ecahan

Opt im al ------------------------------------------------------------------------------------x3 k3= 1 k3= 2 k3= 3 c3= 0 c3= 3 c3= 5 f3(x3) k3* --------------------------------------------------------------------------------------------0 0+ 0 = 0 0 1 1 0+ 10= 10 10 1 2 0+ 20= 20 - 201 3 0+ 50= 50 60+ 0= 60 60 2 4 0+ 50= 50 60+ 10= 70 70 2 5 0+ 70= 70 60+ 20= 80 80+ 0= 80 80 2 or 3 6 0+ 80= 80 60+ 50= 110 80+ 10= 90 110 2 7 0+ 90= 90 60+ 50= 110 80+ 20= 100 110 2 8 0+ 90= 90 60+ 70= 130 80+ 50= 130 130 2 or 3 9 0+ 130= 130 60+ 80= 140 80+ 50= 130 140 2 10 0+ 130= 130 60+ 90= 150 80+ 70= 150 150 2 or 3

ANALISIS x3 k3 x2 k2 x1 k1 -----------------------------------------------------------------------------------------

2

2

7–1=6

3

4

7–5=2

2

3

5–3=2

2

4

5–5=0

1

10–3=7

10 3

10–5=5

CONTOH : MINIMUM PT. Maw ar Berduri m em iliki 3 unit pem bangkit PLTU, PLTGU, dan PLTG. Dat a-dat a t eknis unt uk pengoperasian dinyat akan pada t abel berikut : Jenis Jum lah Kapasit as Biaya Operasional Tot al biaya Pem bangkit Mesin (MW) ($ jut a) per 10 MW Opersional ---------------------------------------------------------------------------------------PLTU 1 40 1.5 6 2 80 1.0 8 PLTG 1 20 3,0 6 2 40 2.75 11 3 60 2.5 15 PLTGU 1 40 2.5 10 2 80 2.0 16 ---------------------------------------------------------------------------------------Jika PT Maw ar berduri dit ugaskan oleh PT. PLN unt uk m em asok list rik ant ara 120-200 MW, t ent ukanlah alokasi penugasannya agar biaya m inim um

SOLUSI DP : MINIMUM          

Keputusan tahap 1 : mengoperasikan PLTU Keputusan tahap 2 : mengoperasikan PLTG Keputusan tahap 3 : mengoperasikan PLTGU y1 : daya listrik yang dibutuhkan tahap 1 y2 : daya listrik yang dibutuhkan tahap 1 dan 2 y3 : daya listrik yang dibutuhkan pada tahap 1,2 dan 3 Rj(kj) : daya listrik yang tersedia pada tahap j Cj(kj) : total biaya alternatif kj pada tahap j fj(yj) : total biaya optimal pada tahap 1,2,… pada kondisi kj Persamaan rekursif-nya adalah f1( y1) = fj(y j ) =

min

{C1(k1)}

min

{C j (k j ) + f j−1[R j (k j ) − y j ]}

R1(k1)≥ y1 R j (k j )≤ y j

BENTUK BAKU DP Tabel : Rencana usulan pengoperasioan PLTU, PLTG dan PLTGU dan perkiraan daya yang dibutuhkan serta biayanya --------------------------------------------------------PLTU PLTG PLTGU -----------------------------------------------------------Usulan R1 c1 R2 c2 R3 c3 --------------------------------------------------------------------1 0 0 0 0 0 0 2 40 6 20 6 40 10 3 80 8 40 11 80 16 4 60 15 -----------------------------------------------------------------------

TAHAP 1 :

f1( y1) =

max

R1(k1)≥ y1

{C1(k1)},k1 = 1,2,3

C1(k1) Pem ecahan ------------------------------------------------------------ Opt im al y1 k1= 1,R1= 0 k1= 2,R2= 40 k1= 3,R1= 80 f1(y1) k1* --------------------------------------------------------------------------------------0 0 6 8 0 1 20 6 8 6 2 40 6 8 6 2 60 8 8 3 80 8 8 3 100 - 120 - 140 - 160 180 200 ------------------------------------------------------------------------------------

{C2 (k 2 ) + f1[R 2 (k 2 ) − y 2 ]},k 2 = 1,2,3,4 TAHAP 2 :f2(y2 ) = R (min k )≥ y 2

2

2

C2(k2) Solusi opt im al -------------------------------------------------------y2 k2= 1, k2= 2, k2= 3, k2= 4 f2(y2) k2* R2= 0 R2= 20 R2= 40 R2= 60 --------------------------------------------------------------------------------------0 0+ 0= 0 6+ 0= 6 11+ 0= 11 15+ 0= 15 0 1 20 0+ 6= 6 6+ 0= 6 11+ 0= 11 15+ 0= 15 6 1 40 0+ 6= 6 6+ 6= 12 11+ 0= 11 15+ 0= 15 6 1 60 0+ 8= 8 6+ 6= 12 11+ 6= 17 15+ 0= 15 8 1 80 0+ 8= 8 6+ 8= 14 11+ 6= 17 15+ 6= 21 8 1 100 6+ 8= 14 11+ 8= 19 15+ 6= 21 14 2 120 11+ 8= 19 15+ 8= 23 19 3 140 15+ 8= 23 23 4 160 180 200 ----------------------------------------------------------------------------------------

{C3 (k 3 ) + f2 [R3 (k 3 ) − y 3 ]}, k 3 = 1,2,3 TAHAP 3 : f3 (y3 ) = R (min k )≥ y 3

3

3

C3(k3) Solusi opt im al ----------------------------------------------------y3 k3= 1, k3= 2, k3= 3, f3(y3) k3* R3= 0 R3= 40 R3= 80 --------------------------------------------------------------------------------------0 0+ 0= 0 10+ 0= 10 16+ 0= 16 0 1 20 0+ 6= 6 10+ 0= 10 16+ 0= 16 6 1 40 0+ 6= 6 10+ 0= 10 16+ 0= 16 6 1 60 0+ 8= 8 10+ 6= 16 16+ 0= 16 8 1 80 0+ 8= 8 10+ 6= 16 16+ 0= 16 8 1 100 0+ 14= 14 10+ 8= 18 16+ 6= 15 14 1 120 0+ 19= 19 10+ 8= 18 16+ 6= 22 18 2 140 0+ 23= 23 10+ 14= 24 16+ 8= 24 23 1 160 10+ 19= 29 16+ 8= 24 24 3 180 10+ 23= 33 16+ 14= 30 30 3 200 16+ 19= 35 35 3 ----------------------------------------------------------------------------------------

SOLUSI y3 k3 y2 k2 y1 k1 -------------------------------------------------------------------------120

2

120-40=80

1

80-0=80

3

140

1

140-0=140

4

140-60=80

3

160

3

160-80=80

1

80-0=80

3

180

3

180-80=100

2

100-20=80

3

200

3

200-80=120

3

120-60=60

3