Dynamic Programming

Deskripsi (1)Dynamic programming adalah suatu prosedur matematik yang dibuat terutama untuk memperbaiki efisiensi komputasi pencarian solusi masalah mathematical programming dengan memecahnya ke dalam subproblems yang lebih kecil dan dengan demikian komputasinya lebih sederhana.

Dynamic programming mencari solusi permasalahan dalam stages (tahap-tahap). Setiap tahap melibatkan satu variabel optimisasi.

Deskripsi (2)Komputasi pada stages yang berbeda dihubungkan melalui komputasi rekursif sedemikian rupa sehingga menghasilkan solusi optimal yang layak untuk keseluruhan permasalahan ketika sampai pada stage yang terakhir.

Dynamic programming didasarkan atas Bellmans Principle of Optimality, yang menggambarkan bagaimana suatu masalah dapat diselesaikan dalam stages melalui komputasi rekursif.

Bellmans Principle of OptimalitySuatu optimal policy memiliki sifat bahwa apapun initial state dan initial decision-nya, keputusan-keputusan selanjutnya harus merupakan optimal policy terhadap state yang dihasilkan dari keputusan yang pertama.

Ini berarti bahwa:

Pada setiap stage di dalam suatu serial system, informasi yang dibutuhkan untuk menentukan suatu solusi optimal untuk stages selanjutnya dari sistem tersebut adalah hanya informasi input terhadap stage yang sedang ditinjau.

Komputasi rekursifKomputasi pada stage yang sedang ditinjau dilaksanakan dengan menggunakan ikhtisar informasi dari keseluruhan stages yang telah ditinjau sebelumnya.

State (1)State menyatakan hubungan antara stages yang saling berurutan sehingga ketika pada masing-masing stage dilakukan optimisasi, keputusan yang dihasilkan secara otomatis layak untuk keseluruhan permasalahan.

Selanjutnya, keberadaan state memungkinkan pengambilan keputusan optimum untuk stages yang tersisa tanpa harus memeriksa efek keputusan yang akan datang kepada keputusan yang telah dibuat sebelumnya.

State (2)Alat bantu untuk menentukan state adalah dua pertanyaan berikut:

Hubungan apa yang mengikat stages, satu terhadap yang lain?

Informasi apa yang diperlukan untuk mengambil keputusan layak pada stage yang sedang ditinjau tanpa memeriksa kelayakan keputusan yang telah diambil pada stages yang sedang ditinjau?

Contoh: Capital Budgeting (1)Sebuah perusahaan sedang melakukan penilaian terhadap proposal yang diajukan oleh tiga buah anak perusahaannya untuk peningkatan fasilitas. Anggarantotal yang dapat dialokasikan untuk ketiga anak perusahaan tersebut adalah $5 juta. Setiap anak perusahaan mengajukan proposal yang memuat biaya total (c) dan pendapatan total (R) untuk setiap proposal seperti yang terlihat pada tabel berikut. Zero-cost proposal dicantumkan untuk memperhitungkan alternatif tidak mengalokasikan anggaran untuk anak perusahaantertentu. Sasaran perusahaan adalah memaksimalkan pendapatan dari pengalokasian anggaran total $5 juta tersebut.

Contoh: Capital Budgeting (2)Proposal dari masing-masing anak perusahaan:

A. Per. 1 A. Per. 2 A. Per. 3Proposalc1R1c2R2c3R31000000215281332639--4--412--

012340123405(0)Stage 0(j = 0)Stage 1 (j=1)Stage 2(j = 2)Stage 3(j = 3)x355x1x3(0)(8)(9)(12)(12) (0)(5)(6)(6)(6)(6)(3)(3)(3)(3)(3)(0)(0)(0)(8)(9)(12)(0)(0)(0)(0)(0)(8)(0)(0)(8)(9)

012340123405Stage 1 Stage 2

Stage 3

55012345012345506666005666605813141705813141717f0f1f1f2f2f3(1)(2)(3)(3)(3)(3)(2)(1)(1)(1)(2)(2)(3)(2)(4)

Misalkan fj(xj) adalah pendapatan yang tertinggi (jalan yang terpanjang)sampai pada simpul xj pada stage j. Karena j = 0 adalah initial stage, maka f0(0) = 0.

Dengan demikian persamaan rekursif untuk setiap stage dapat dituliskan sebagai berikut:

Stage 1: f1(x1) = f0(0) + R1(0, x1)dimana R1(0, x1) adalah pendapatan pada stage 1 yang dinyatakan oleh busur (0, x1)

Stage 2: f2(x2) = max {f1(x1) + R2(x1, x2)untuk busur yang layak (x1,x2)

Stage 3: f3(x3) = max {f2(x2) + R3(x2, x3)untuk busur yang layak (x2, x3)

Persamaan rekursif untuk masalah ini secara umum adalah:

f0(x0) = 0fj(xj) = max {Rj(kj) + fj-1(xj cj(kj))}dimana cj(kj) xj

Contoh: Work-Force SizeA contractor needs to decide on the size of his work force over the next 5 weeks. He estimates the minimum force size bj for the 5 weeks to be 5, 7, 8, 4, and 6 workers forj = 1, 2, 3, 4, and 5, respectively.

The contractor can maintain the required minimum number of workers by exercising theoptions of hiring and firing. However, additional hiring cost is incurred every time thework-force size of the current week exceeds that of last week. On the other hand, if hemaintains a work force for any week that exceeds the minimum requirement, an excesscost is incurred for that week.

Let yj represent the number of workers for the jth week. Define C1(yj - bj) as the excesscost when yj exceeds bj, C2(yj yj-1) as the cost of hiring new workers (yj > yj-1). Thecontractors data show that

C1(yj bj) = 3(yj bj), j = 1.2,.., 5C2(yj yj-1) = 4 + 2(yj yj-1), if yj > yj-1 and = 0 if yj < yj-1 (firing incurs no additional cost)

If the initial work force y0 at the beginning of the first week is 5 workers, it is required todetermine the optimum sizes of the work force for the 5-week planning horizon.

Contoh:

Perencana kota harus menentukan alokasi optimal stasiun pemadam kebakaran bagi 3 wilayah di dalam kota tersebut .Tabel berikut memperlihatkan hubungan antara jumlah stasiun yang dialokasikan di suatu wilayah dengan ekspektasi kerusakan property per tahun akibat kebakaran didasarkan atas data statistik. Perbedaan antar wilayah disebabkan oleh populasi, material konstruksi, dsb. Kendala anggaran mengakibatkan jumlah total stasiun yang dapat dialokasikan terbatas sebanyak 5 buah. Gunakan dynamic programming untuk menentukan alokasi stasiun yang optimal untuk setiap wilayah. Gambarkan networknya. Bagaimana persamaan rekursifnya?

WilayahJumlah stasiun per wilayah012312,00,90,30,220,50,30,20,131,51,00,70,3