Pemrograman Dinamis dan Contoh Studi Kasus (1)

Pemrograman dinamis ini pertama kali dikembangkan oleh seorang ilmuwan benama Richard Bellman pada tahun 1957. Pemrograman dinamis merupakan suatu teknik analisa kuantitatif untuk membuat tahapan keputusan yang saling berhubungan. Teknik ini menghasilkan prosedur yang sistematis untuk mencari keputusan dengan kombinasi yang optimal. Pemrograman dinamis adalah metode pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan langkah (step) atau tahapan (stage) sedemikian sehingga solusi dari persoalan dapat dipandang  dari serangkaian keputusan  yang saling berkaitan (Pangestu, 2004). 

Program dinamis adalah suatu teknik matematis yang biasanya digunakan untuk membuat suatu keputusan dari serangkaian keputusan yang saling berkaitan. Program dinamis menyediakan prosedur sistematis untuk menentukan kombinasi keputusan yang optimal. Tujuan utama model ini ialah untuk mempermudah penyelesaian persoalan optimasi yang mempunyai karakteristik tertentu. Tidak seperti pemrograman linier, tidak ada bentuk matematis standar untuk perumusan pemrograman dinamis. Pemrograman dinamis adalah pendekatan umum untuk pemecahan masalah dan persamaan tertentu yang digunakan di dalamnya harus dibentuk sesuai dengan situasi masalah yang dihadapi berkaitan. Karakteristik persoalan pemrograman dinamis adalah sebagai berikut (Pangestu, 2004):

1.        Persoalan dapat dibagi menjadi beberapa tahap (stage), yang pada setiap tahap hanya diambil satu keputusan.

2.        Masing-masing tahap terdiri dari sejumlah status (state) yang berhubungan dengan tahap tersebut. Secara umum, status merupakan bermacam kemungkinan masukan yang ada pada tahap tersebut.

3.        Hasil dari keputusan yang diambil pada setiap tahap ditransformasikan dari status yang bersangkutan ke status berikutnya pada tahap berikutnya.

4.        Ongkos (cost) pada suatu tahap meningkat secara teratur (steadily) dengan bertambahnya jumlah tahapan.

5.        Ongkos pada suatu tahap bergantung pada ongkos tahap-tahap yang sudah berjalan dan ongkos pada tahap tersebut.

6.        Keputusan terbaik pada suatu tahap bersifat independen terhadap keputusan yang dilakukan pada tahap sebelumnya.

7.        Adanya hubungan rekursif yang mengidentifikasikan keputusan terbaik untuk setiap status pada tahap k memberikan keputusan terbaik untuk setiap status pada tahap k + 1.

8.        Prinsip optimalitas berlaku pada persoalan tersebut.

      Dalam   proses   penye1esaian menggunakan   program   dinamis,   pendekatan   yang dilakukan  bisa jadi ada dua macam, yaitu pendekatan  maju (forward) dan mundur (backward), dan perlu untuk diketahui pula bahwa solusi yang dihasilkan dari kedua pendekatan  itu adalah  sama. Solusi dari program  dinamis  bisa jadi lebih dari satu macam (Pangestu, 2004).

1.  Karakteristik Program Dinamis

          Salah satu cara untuk cara untuk mengenali suatu situasi yang dapat dirumuskan sebagai masalah pemrograman dinamis adalah menyadari struktur dasar masalah tersebut apakah serupa dengan masalah ekspedisi.        Masalah dapat dibagi menjadi tahap-tahap dengan keputusan kebijakan yang dibuat pada masing-masing tahap. Masalah ekspedisi secara harfiah dibagi menjadi 4 tahap yang sesuai dengan 4 tahap perjalanan. Kebijakan keputusan pada masing-masing tahap adalah kebijakan asuransi jiwa mana yang dipilih (sama dengan tujuan yang dipilih untuk tahap berikutnya). Cara yang sama, masalah pemrograman dinamis lain memerlukan pembuatan suatu urutan keputusan yang saling berhubungan, dengan setiap keputusan diambil pada satu tahap masalah. Masing-masing tahap mempunyai state yang berhubungan dengan kondisi awal tahap.

          State pada masing-masing tahap pada masalah ekspedisi adalah Negara bagian (wilayah) tempat pencari harta bisa singgah sementara ketika tiba pada akhir suatu bagian atau tahap perjalanan tersebut. Secara umum, state adalah bebagai kondisi sistem yang mungkin pada suatu tahap masalah. Banyaknya state bisa terbatas (seperti dalam masalah ekspedisi) ataupun tidak terbatas. Efek keputusan kebijakan pada setiap tahap adalah mengubah state saat ini menjadi state lain pada awal tahap berikutnya (Hasan, 2002).

          Keputusan pencari harta dalam bentuk tujuan berikutnya, membawanya dari state sekarang kepada state berikutnya dalam perjalanan. Prosedur ini menyatakan bahwa masalah pemrograman dinamis dapat dinyatakan sebagai jaringan. Setiap simpul menyatakan state. Jaringan akan terdiri dari kolom simpul, degan setiap kolom menyatakan tahap, sehingga aliran dari suatu simpul hanya dapat melangkah ke kolom yang berada di sebelah kanannya. Hubungan dari suatu simpul ke simpul pada kolom berikutnya sesuai dengan keputusan kebijakan yang mungkin untuk menentukan state untuk langkah berikutnya. Nilai yang ditugaskan pada setiap hubungan dapat ditafsirkan sebagai kontribusi langsung terhadap fungsi tujuan dari pembuatan keputusan kebijakan itu. Mencari solusi dalam banyak kasus adalah untuk mencapai tujuan dapat dinyatakan dengan menemukan jalur terpendak atau terpanjang pada jaringan (Hasan, 2002).

          Prosedur penyelesain dirancang untuk menemukan kebijakan optimal dari keseluruhan masalah, yang menunjukkan keputusan kebijakan mana yang optimal pada setiap tahap untuk setiap state yang mungkin. Masalah ekspedisi salah satunya prosedur penyelesaian membentuk tabel untuk setiap tahap (n) yang menunjukkan keputusan optimal pada setiap state yang mungkin (s), selain bisa menemukan tiga solusi optimal (rute terbaik) untuk masalah keseluruhan, hasil yang diperoleh juga dapat dipakai sebagai petunjuk bagi pencari harta untuk menentukan langkah jika terpaksa dialihkan ke state yang tidak berada dalam rute optimal. Masalah apapun pada pemrograman dinamis menyediakan petunjuk mengenai kebijakan apa yang harus dilakukan pada setiap keadaan yang mungkin terjadi (inilah alasan mengapa keputusan aktual yang dibuat pada saat mencapai state tertentu pada tahap tertentu disebut keputusan kebijakan). Penyediaan informasi tambahan selain menyatakan solusi optimal (urutan keputusan optimal) dapat berguna dalam berbagai hal, termasuk untuk analisis sensitivitas (Hasan, 2002).

          Berkaitan dengan state saat ini, kebijakan optimal untuk langkah tersisa bersifat independent terhadap keputusan kebijakan yang telah diambil pada tahap sebelumnya. Keputusan optimal selanjutnya hanya tergantung pada state saat ini dan bukan cara mencapai state saat ini. Inilah prinsip optimalitas untuk pemrograman dinamis (Hasan, 2002).

          Sehubungan dengan state tempat pencari harta berada sekarang, kebijakan asuransi jiwa yang optimal (dan rute perjalanannya) dari simpul ini sampai akhir bersifat independen dengan caranya tiba pada state itu. Masalah pemrograman dinamis pada umumnya, pengetahuan menyangkut state sekarang dari sistem menyampaikan semua informasi tentang prilaku sebelumnya yang diperlukan untuk menentukan kebijakan optimal selanjutnya (sifat ini disebut sifat Markovian). Setiap masalah yang tidak mempunyai sifat ini tidak bisa dirumuskan sebagai masalah program dinamis. Prosedur penyelesaian dimulai dengan mencari kebijakan optimal untuk langkah terakhir. Kebijakan optimal untuk langkah terakhir ini akan menentukan keputusan kebijakan optimal untuk setiap state yang mungkin pada tahap itu. Penyelesaian dari masalah satu tahap ini umumnya sangat mudah, seperti terlihat pada masalah ekspedisi. Tersedia hubungan rekursif yang menunjukkan kebijakan optimal untuk tahap n dengan dasar kebijakan optimal n+1 (Hasan, 2002).

          Menemukan keputusan kebijakan optimal saat mulai dari state s pada tahap n, anda akan memerlukan nilai minimum untuk x_n. Masalah tertentu yaitu biaya minimum yang diperoleh dengan menggunakan nilai x_n, kemudian mengikuti kebijakan optimal saat mulai dari state s pada tahap n+1 (Hasan, 2002).

2.    Program Dinamis Probablistik

            Perbedaan pengunaan program dinamis probablistik dari program dinamis deterministik adalah state pada tahap berikutnya tidak hanya ditentukan oleh state dan keputusan kebijakan pada tahap saat ini, melainkan juga terdapat distribusi probablitas untuk state pada tahap berikutnya. Distribusi probablitas ini dapat ditentukan berdasarkan state dan keputusan kebijakan pada tahap saat ini (Hasan, 2002).

            Pemrograman dinamis bila dikembangkan hingga meliputi semua tahap yang mungkin dan keputusan pada semua tahap, biasanya gambar dikenal dengan nama pohon keputusan. Pohon keputusan jika tidak terlalu besar, ia akan menyediakan cara yang berguna untuk merangkum variasi kemungkinan yang mungkin terjadi, oleh karena struktur probablitas tersebut, hubungan antara fungsi dan yang diperlukan lebih rumit daripada pemrograman dinamis deterministik. Bentuk tepat yang dari hubungan ini tergantung pada bentuk fungsi tujuan secara keseluruhan (Hasan, 2002).

            Pemrograman dinamis adalah prosedur matematis yang terutama dirancang untuk memperbaiki efisiensi perhitungan masalah pemrograman matematis tertentu dengan menguraikannya menjadi bagian masalah yang lebih kecil. Pemrograman dinamis pada umumnya menjawab masalah dalam tahap– tahap dengan setiap tahap meliputi tepat satu variabel optimasi. Perhitungan ditahap yang berbeda–beda dihubungkan melalui perhitungan rekursif dengan cara yang menghasilkan pemecahan optimal yang mungkin bagi seluruh masalah (Hasan, 2002).

3. Studi Kasus Pemrograman Dinamis

            Terdapat dua jenis pembahasan studi kasus dalam Program Dinamis yaitu dinamik mundur dan knapsack. Perbedaan antara keduanya terletak pada mulai melakukan penyelesaian permasalahan. Dinamik mundur berarti pembahasan persoalan dimulai dari ujung masalah tersebut, sedangkan untuk knapsack dimulai dari pangkal masalah tersebut.

3.1  Studi Kasus Dinamik Mundur (Backward)

           PT. Bangkrut Abadi yang menjual pakan ternak ingin memasarkan produknya ke wilayah Bogor dari lokasi pabrik yang terletak di Bekasi. Perencanaan rutenya mencakup Cileungsi, Jalur alternatif Cibubur, Jakarta, Citeurup, Karanggan, Depok, Cibinong dan Sentul. Dia ingin meminimalkan biaya operasional yang timbul untuk distribusi koran tersebut meliputi biaya bahan bakar kendaraan, biaya loper koran, dan operasional kendaraan lainnya, hal ini disebabkan loper koran tersebut harus melewati banyak pilihan rute untuk dapat mendistribusikan koran. Apabila rute yang dilalui semakin panjang maka biaya yang timbul akan semakin besar, maka keuntungannya pun semakin sedikit. Oleh karena itu, PT. Bangkrut Abadi ingin mengetahui rute terdekat untuk dapat meminimalisir biaya operasional agar mendapat keuntungan lebih besar. Berikut adalah rute yang dapat diambil.

Graf Lintasan Distribusi Produk

Keterangan :

1 : Bekasi                                            5 : Karanggan                            9 : Cibinong

2 : Jalur Alternatif Cibubur                 6 : Citeureup                           10 : Bogor

3 : Cileungsi                                        7 : Depok

4 : Jakarta                                            8 : Sentul

Berdasarkan rute diatas, jalur manakah yang optimal untuk dapat meminimalisir biaya operasional PT. Bangkrut Abadi.

          Studi Kasus Knapsack (Forward)

      Perusahaan PT. Bangkrut Abadi ingin mendistribusikan produknya yaitu pakan ternak ke wilayah Bogor. Sebelum melakukan pendistribusian, manager perusahaan tersebut harus mengemas Pakan Tenak yang diproduksi sebelum dilakukan pendistribusian, yaitu dengan memasukkan barang yang sudah diproduksi ke dalam sebuah truk box. Manager tersebut memiliki 5 tipe model pengemasan pakan ternak dengan berat keseluruhan 16 kwintal dengan profit yang berbeda untuk setiap model pengemasan pakan ternak, yang harus dimasukkan ke dalam truk box dengan kapasitas 7 kwintal. Manager tersebut harus mencari solusi optimal agar pendistribusian pakan ternak bisa menghasilkan profit yang maksimal ( n=5 ; M=7 ). Berikut adalah tabel mengenai berat dan profit yang dihasilkan untuk setiap model pengemasan pakan ternak.

Tabel 3.1 Berat dan Profit untuk Pengiriman Produk 

Barang ke-i	wi (Kwintal)	pi (Juta)
1	4	22
2	6	24
3	2	15
4	3	18
5	1	13

  

Berdasarkan tabel diatas, Carilah nilai solusi optimumnya.

Jawaban di postingan selanjutnya ya.

DAFTAR PUSTAKA

Hasan, M. Iqbal. 2002. Penelitian Oprasional. Yogyakarta: Andi Offest.

Subagyo, Pangestu. 2004. Dasar-dasar operation Reserch. Yogyakarta: BFFE