modul 8 pemrograman dinamis

MODUL 8PEMROGRAMAN 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 kebijakan optimal keseluruhan masalah, melalui keputusan optimal pada setiap tahap

Bila diketahui keadaan sekarang optimal, untuk tahap yang tersisa adalah bebas terhadap kebijakan yang dipakai pada tahap-tahap 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 (n+1)

CONTOH : MAKSIMUM

Sebuah perusahaan pembangkit mempunyai tiga usulan proposal untuk membangun PLTU di tiga daerah yang patuh dipertimbangkan. Perusahaan menyediakan anggaran sebesar $ 10 juta untuk ketiga alokasi. Setiap proposal diminta menyampaikan usulannya dengan meringkaskan biaya (juta dollar) dan daya listrik (MW) yang dihasilkan----------------------------------------------------------------------- PLTU Serang PLTU Pacitan PLTU CirebonUsulan 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-----------------------------------------------------------------------Tentukanlah pemecahan yang optimal

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. Persamaan rekursif-nya adalah :

)]}k(cx[f)k(R{max)x(f

)}k(R{max)x(f

jjj1jjjx)k(c

jj

11x)k(c

11

jjj

111

TAHAP 1 : 3,2,1k)},k(R{max)x(f 111x)k(c

11111

R1(k1) Pemecahan Optimal ------------------------------------------------------------ x1 k1=1 k1=2 k1=3 c1=0 c1=2 c1=6 f1(x1) k1*-------------------------------------------------------------------0 0 - - 0 11 0 - - 0 12 0 20 - 20 23 0 20 - 20 24 0 20 - 20 25 0 20 - 20 26 0 20 80 80 37 0 20 80 80 38 0 20 80 80 39 0 20 80 80 310 0 20 80 80 3---------------------------------------------------------------------

TAHAP 2 :

4,3,2,1k)]},k(cx[f)k(R{max)x(f 2222122x)k(c

22222

R2(k2) + f1[x2 – c2(k2)] Pemecahan Optimal ------------------------------------------------------------------------------------- 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 11 0+0=0 10+0=10 - - 10 22 0+20=20 10+0=10 - - 20

13 0+20=20 10+20=30 50+0=50 - 50

34 0+20=20 10+20=30 50+0=50 - 50

35 0+20=20 10+20=30 50+20=70 70+0=70

70 3or46 0+80=80 10+20=30 50+20=70 70+0=70

80 17 0+80=80 10+80=90 50+20=70 70+20=90

90 2or48 0+80=80 10+80=90 50+20=70 70+20=90

90 2or49 0+80=80 10+80=90 50+80=130 70+20=90

130 310 0+80=80 10+80=90 50+80=130 70+20=90

130 3---------------------------------------------------------------------------------------------

TAHAP 3 : 3,2,1k)]},k(cx[f)k(R{max)x(f 3333233x)k(c

33333

R3(k3) + f2[x3 – c3(k3)] Pemecahan Optimal ------------------------------------------------------------------------------------- x3 k3=1 k3=2 k3=3 c3=0 c3=3 c3=5 f3(x3) k3*---------------------------------------------------------------------------------------------0 0+0 =0 - - 0 11 0+10=10 - - 10 12 0+20=20 - - - 20 13 0+50=50 60+0=60 - 60 24 0+50=50 60+10=70 - 70 25 0+70=70 60+20=80 80+0=80 80 2 or 36 0+80=80 60+50=110 80+10=90 110

27 0+90=90 60+50=110 80+20=100 110 28 0+90=90 60+70=130 80+50=130 130

2 or 39 0+130=130 60+80=140 80+50=130 140

210 0+130=130 60+90=150 80+70=150 150 2 or 3---------------------------------------------------------------------------------------------

ANALISIS

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

2

3

10–3=7

10

2

4

7–1=6

7–5=2

3

2

10–5=5

3

4

5–3=2

5–5=0

2

1

CONTOH : MINIMUM

PT. Mawar Berduri memiliki 3 unit pembangkit PLTU, PLTGU, dan PLTG. Data-data teknis untuk pengoperasian dinyatakan pada tabel berikut :Jenis Jumlah Kapasitas Biaya Operasional Total biaya Pembangkit Mesin (MW) ($ juta) per 10 MW Opersional----------------------------------------------------------------------------------------PLTU 1 40 1.5 6

2 80 1.0 8PLTG 1 20 3,0 6 2 40 2.75 11 3 60 2.5 15PLTGU 1 40 2.5 10

2 80 2.0 16----------------------------------------------------------------------------------------Jika PT Mawar berduri ditugaskan oleh PT. PLN untuk memasok listrik antara 120-200 MW, tentukanlah alokasi penugasannya agar biaya minimum

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

]}y)k(R[f)k(C{min)y(f

)}k(C{min)y(f

jjj1jjjy)k(R

jj

11y)k(R

11

jjj

111

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 :

C1(k1) Pemecahan ------------------------------------------------------------ Optimal y1 k1=1,R1=0 k1=2,R2=40 k1=3,R1=80 f1(y1) k1* --------------------------------------------------------------------------------------- 0 0 6 8 0 120 - 6 8 6 240 - 6 8 6 260 - - 8 8 380 - - 8 8 3100 - - - - -120 - - - - -140 - - - - -160 - - - 180 - - -200 - - -------------------------------------------------------------------------------------

3,2,1k)},k(C{max)y(f 111y)k(R

11111

TAHAP 2 :

C2(k2) Solusi optimal -------------------------------------------------------- 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 120 0+6=6 6+0=6 11+0=11 15+0=15 6

140 0+6=6 6+6=12 11+0=11 15+0=15 6 160 0+8=8 6+6=12 11+6=17 15+0=15 8 180 0+8=8 6+8=14 11+6=17 15+6=21 8 1100 - 6+8=14 11+8=19 15+6=21 14

2120 - - 11+8=19 15+8=23 19 3140 - - - 15+8=23 23 4160 - - - -180 - - - -200 - - - -----------------------------------------------------------------------------------------

4,3,2,1k]},y)k(R[f)k(C{min)y(f 2222122y)k(R

22222

TAHAP 3 :

C3(k3) Solusi optimal ----------------------------------------------------- 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 120 0+6=6 10+0=10 16+0=16 6 140 0+6=6 10+0=10 16+0=16 6

160 0+8=8 10+6=16 16+0=16 8 180 0+8=8 10+6=16 16+0=16 8

1100 0+14=14 10+8=18 16+6=15 14 1120 0+19=19 10+8=18 16+6=22 18 2140 0+23=23 10+14=24 16+8=24 23 1160 - 10+19=29 16+8=24 24 3180 - 10+23=33 16+14=30 30 3200 - - 16+19=35 35 3----------------------------------------------------------------------------------------

3,2,1k]},y)k(R[f)k(C{min)y(f 3333233y)k(R

33333

SOLUSI

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

2120-

40=801 380-0=80

140

160

180

200

1

2

1

4 3

3

3

3 3

3

3

3

140-0=140

120-60=60

100-20=80

80-0=80

140-60=80

160-80=80

180-80=100

200-80=120