BAB 2 Studi Literatur

BAB II

STUDI LITERATUR

2.1.    Pemrograman Dinamis      

          Program dinamis adalah suatu teknik dalam metoda kuantitatif yang sering kali beruna dalam menentukan urutan keputusan-keputusan yang saling berhubungan. Program dinamis merupakan suatu pendekatan yang sifatnya umum dan memecahkan persoalan yang ada, dan persamaan-persamaan khusus yang digunakan harus dikembangkan sesuai dengan permasalahannya. Oleh karena itu, perlu diketahui struktur umum dari persoalan program dinamis untuk dapat mengenali apakah suatu persoalan dapat diselesaikan dengan prosedur program dinamis serta bagaimana pemecahannya (Dimyati, 2006). 

2.1.1  Pengertian Pemrograman Dinamis

Program dinamis adalah suatu teknik matematis yang biasanya digunakan untuk membuat suatu keputusan dari serangkaian keputusan yang saling berkaitan. Tujuan utama model ini yaitu untuk mempermudah penyelesaian persoalan optimasi yang mempunyai karakteristik tertentu. Program dinamis berbeda dengan program linier, pada persoalan program dinamis tidak ada formulasi matematis yang standar. Persamaan-persamaan yang terpilih untuk digunakan harus dikembangkan agar dapat memenuhi masing-masing situasi yang dihadapi (Dimyati, 2006).

Program dinamis dapat juga disebut multi stage programming yang berciri memecah persoalan menjadi bagian yang lebih kecil (sub problem atau stage) dimana keputusan dibuat secara berurutan. Multi stage programming memperlakukan persoalan dimana keputusan pada suatu tahap dapat mempengaruhi keputusan pada tahap berikutnya. Penemu dan orang yang bertanggung jawab atas kepopuleran program dinamis adalah Richard Bellman. Sebagai suatu konsep, program dinamis  lebih luwes dibanding kebanyakn model dan metode matematika dalam OR. Penerapan pendekatan program dinamis telah dikabarkan mampu untuk menyelesaikan berbagai masalah seperti alokasi, muatan (knapsack), capital budgeting, pengawasan persediaan dan sebagainya (Mulyono, 2007).

2.1.2  Karakteristik Persoalan Program Dinamis

          Persoalan program dinamis memiliki beberapa karakteristik. Berikut ini diberikan beberapa gambaran dasar yang menandai persoalan program dinamis (Dimyati, 2006):

1.        Persoalan dapat dibagi menjadi beberapa tahap (stage), yang pada masing-masing tahap diperlukan adanya satu keputusan.

2.        Masing-masing stage terdiri atas sejumlah state yang berhubungan dengan stage  yang bersangkutan. Jumlah state ini bisa terbatas, bisa pula tidak terbatas.

3.        Hasil dari keputusan yang diambil pada setiap stage ditransformasikan dari state yang bersangkutan ke state yang berikutnya  pada satge yang berikutnya pula.

4.        Keputusan terbaik pada suatu stage bersifat independen terhadap keputusan yang dilakukan pada stage sebelumnya.

5.        Prosedur pemecahan persoalan dimulai dengan mendapatkan cara atau keputusan terbaik untuk setiap state dari stage terakhir.

6.        Ada suatu hubungan timbal balik yang mengidentifikasi keputusan terbaik untuk setiap state pada stage (n+1). Oleh karena itu, untuk mendapat keputusan terbaik jikan akan bergerak dari state s pada stage n, terlebih dahulu harus didapatkan nilai terbaik dari x_n pada stage (n+1).

Dalam hal ini ditetapkanlah:

a.         Variabel x_n sebagai variabel keputusan pada stage n (n = 1,2, ..., N).

b.         f_n (s, x_n) sebagai nilai fungsi tujuan yang akan dimaksimumkan atau diminimumkan, dengan catatan bahwa sistem akan berawal dari state s pada stage n dan x_n telah terpilih sehingga f_n (s, x_n) = Csx_n + f_n+1 (x_n).

c.          fn(s) sebagai nilai maksimum atau minimum dari  f_n (s, x_n) untuk seluruh nilai x_n yang mungkin.

7.        Dengan menggunakan hubungan timbal balik, prosedur penyelesaian persoalan bergerak mundur stage demi stage, pada setiap stage berusaha diperoleh keputusan optimum untuk masing-masing state hingga akhirnya diperoleh keputusan optimum yang menyeluruh, mulai dari stage awal.

2.1.3  Ciri-Ciri Pokok Masalah Program dinamis

          Program dinamis adalah suatu pendekatan matematika tentang optimasi proses banyak tahap. Konsep dasarnya diungkapkan dalam Principle of Optimality oleh Bellman. Ciri-ciri dasar suatu masalah program dinamis adalah (Mulyono, 2007):

1.        Dalam masalah program dinamis, keputusan tentang suatu masalah ditandai dengan optimasi pada tahap berikutnya, bukan keserentakan. Ini berati jika suatu masalah akan diselesaikan dengan program dinamis ia harus dipisahkan menjadi n sub problem.

2.        Program dinamis berkaitan dengan masalah-masalah dimana pilihan atau keputusan dibuat pada masing-masing tahap. Seluruh kemungkinan pilihan dicerminkan, diatur keduanya, oleh sistem status pada setiap tahap.

3.        Berkaitan dengan setiap keputusan pada setiap tahap adalah return function yang mengevaluasi pilihan yang dibuat dalam arti sumbangan yang diberikan kepada tujuan keseluruhan (maksimasi ayau minimasi).

4.        Setiap tahap proses keputusan dihubungkan dengan tahap berdekatan melalui fungsi transisi. Fungsi ini dapat berupa kuantitas yang diskrit maupun kontinu tergantung pada sifat-sifat masalah.

5.        Suatu hubungan rekursif digunakan untuk menghubungkan kebijaksanaan optimum pada tahap n dengan n-1. Ada dua macam prosedur rekursif yaitu forward atau secara maju dan backward atau secara mundur. Hubungan itu adalah:

a.       Forward recursive equation (perhitungan dari depan kebelakang).

b.      Backward recursive equation (perhitungan dari belakang ke depan).

Perbedaan pokok antara metode forward dan backward adalah terletak dalam cara mendefinisikan state.

6.        Dengan menggunakan hubungan rekursif ini, prosedur penyelesaian bergerak dari tahap ke tahap sampai kebijaksanaan optimum tahap terakhir ditemukan. Sekali kebijaksanaan optimum tahap n telah ditemukan, n komponen keputusan dapat ditemukan kembali dengan melacak balik melalui fungsi transisi tahap n.

2.1.4  Prinsip Optimalitas

          Rangkaian keputusan yang optimal dibuat dengan menggunakan prinsip optimalitas pada program dinamis. Prinsip optimalitas berbunyi jika solusi total optimal, maka bagian solusi sampai tahap ke-k juga optimal, pada program dinamis rangkaian keputusan yang optimal dibuat dengan menggunakan prinsip optimalitas. Prinsip optimalitas berati bahwa jika kita bekerja dari tahap k ke tahap k+1, kita dapat menggunakan hasil optimal dari tahap k tanpa harus kembali ketahap awal.  Ongkos pada tahap k+1 = (ongkos yang dihasilkan pada tahap k) + (ongkos dari tahap k ke tahap k+1).

Prinsip optimalitas ini menjamin bahwa pengambilan keputusan pada suau tahap adalah keputusan yang benar untuk tahap-tahap selanjutnya.  Terdapat dua metode yaitu metode greedy yang mana pada metode ini hanya satu rangkaian keputusan yang pernah dihasilkan, sedangkan pada metode program dinamis lebih dari satu rangkaian keputusan yang dihasilkan. Hanya rangkaian keputusan yang memenuhi prinsip optimalitas yang akan dihasilkan.

            Pengembangan algoritma terdapat dalam program dinamis. Berikut terdapat empat langkah-langkah dalam melakukan pengembangan algoritma pada program dinamis :

1.        Karakteristikkan struktur solusi optimal.

2.        Hitung nilai solusi optimal secara maju atau mundur.

3.        Definisikan secara rekursif nilai solusi optimal.

4.        Konstruksi solusi optimal.

2.1.5  Program Dinamis Deterministik

          Cara untuk mengkategorikan persoalan program dinamis deterministik ini adalah dengan melihat bentuk fungsi tujuannya. Contohnya, fungsi tujuannya mungkin meminimumkan jumlah kontribusi dari masing-masing stage atau dapat pula memaksimumkannya atau meminimumkan hasil perkaliannya. Cara pengkategorian yang lain didasarkan pada keadaan dari kumpulan (set) state pada suatu stage. Artinya, apakah state Sn dapat direpresentasikan sebagai variabel state diskrit atau kontinu, atau mungkin diperlukan suatu vektor state (lebih dari satu variabel). Program dinamis deterministik dapat diterangkan dengan diagram berikut (Dimyati, 2006):

         stage n                                                               stage n+1

       state:       

                                                                 kontribusi dari Xn

                  f_n (Sn, Xn)                                                                     f*n+1 (Sn+1)

Gambar 2.7 Diagram Program Dinamis Deterministik

2.1.6  Program Dinamis Probabilistik

          Berbeda dengan program dinamis deterministik, pada program dinamis probabilistikini stage berikutnya tidak dapat seluruhnya ditentukan oleh state dan keputusan pada stage saat ini, tetapi ada suatu distribusi kemungkinan mengenai apa yang akan terjadi. Namun, distribusi kemungkinan ini masih seluruhnya ditentukan oleh state dan keputusan pada stage saat ini. Struktur program dinamis probabilistik ini dapat digambarkan sebagai berikut (Dimyati, 2006):

                                                                                                  stage n+1

                                                                                                     s_n+1

                                                                                                                 f_n*+ 1 (1)

 

  state:                                                                                                       f_n*+ 1 (2)

 

    f_n ( Sn, Xn)

                                                                                                                                               f_n*+1 (N)

Gambar 2.8 Diagram Program Dinamis Probabilistik

            Gambar diatas apabila diperluas sehingga mencakup seluruh state dan keputusan pada seluruh stage yang mungkin, maka gambar tersebut akan membentuk pohon keputusan. Jika pohon keputusan ini tidak terlalu lebar, maka akan dapat digunakan sehingga cara untuk membuat ikhtisar dari berbagai kemungkinan dapat terjadi. Akibat struktur probabilistik, maka hubungan antara f_n (s_n, x_n) dengan f_n*+1 (s_n + 1) menjadi lebih rumit dari pada untuk program dinamis deterministik. Bentuk yang tepat untuk hubungan ini akan bergantung pada bentuk fungsi tujuan secara keseluruhan (Dimyati, 2006).   

       

2.1.7    Knapsack

Knapsack adalah tas atau karung yang digunakan untuk memasukkan sesuatu, tetapi tidak semua barang bisa ditampung kedalam karung tersebut. Karung tersebut hanya dapat menyimpan beberapa objek dengan total ukurannya (weight) lebih kecil atau sama dengan ukuran kapasitas karung. Knapsack memiliki tiga jenis persoalan-persoalan yang harus diselesaikan, diantaranya Knapsack 0/1 merupakan sesuatu yang dimasukkan kedalam karung dimensinya harus dimasukkan semua atau tidak sama sekali. Knapsack bounded adalah sesuatu yang dimasukkan kedalam karung dimensinya bisa dimasukkan sebagaian atau seluruhnya (Wahab, 2005).

Knapsack problem bisa diselesaikan dengan berbagai cara. Ada beberapa strategi algoritma yang bisa menghasilkan solusi optimal, diantaranya adalah brute force. Strategi ini tidak efisien, jadi knapsack problem pada laporan ini akan diselesaikan dengan greedy algorithm yaitu solusi yang mencari nilai optimum. Algoritma ini memecahkan permasalahan langkah per langkah, pada setiap langkah (Wahab, 2005):

1.    Mengambil pilihan terbaik yang bisa diperoleh saat itu juga tanpa memperatikan konsekuensi kedepan (prinsip “take what you can get now!”).

2.    Berharap bahwa dengan memilih optimum lokal pada setiap langkah akan berakhir dengan optimum global.

Greedy Algorithm memiliki beberapa strategi yang digunakan untuk memilih objek yang akan dimasukkan kedalam knapsack. Berikut adalah strategi-strategi yang digunakan (Wahab, 2005):

1.    Greedy By Profit

Langkah dalam greedy by profit, knapsack diisi dengan objek yang mempunyai keuntungan terbesar. Strategi ini mencoba memaksimumkan keuntungan dengan memilih objek yang paling menguntungkan terlebih dahulu. Pertama kali yang dilakukan adalah mengurutkan secara menurun objek-objek berdasarkan profit-nya.

2.    Greedy by weight

Langkah greedy by weight, knapsack diisi dengan objek yang mempunyai berat paling ringan. Strategi ini mencoba memaksimumkan keuntungan dengan memasukkan sebanyak mungkin objek ke dalam knapsack. Pertama kali yang dilakukan adalah mengurutkan secara menaik objek-objek berdasarkan beratnya, kemudian baru diambil satu-persatu objek yang dapat ditampung oleh knapsack sampai knapsack penuh atau sudah tidak ada objek lagi yang bisa dimasukkan.

3.    Greedy by density

Langkah greedy by density, knapsack diisi dengan objek yang mempunyai densitas terbesar. Strategi ini mencoba memaksimumkan keuntungan dengan memilih objek yang mempunyai keuntungan per unit berat terbesar. Pertama kali yang dilakukan adalah mencari nilai profit per unit (density) dari tiap-tiap objek, kemudian objek-objek tersebut diurutkan berdasarkan densitynya. Objek selanjutnya diambil satu persatu yang dapat ditampung oleh knapsack sampai knapsack penuh atau sudah tidak ada objek lagi yang bisa dimasukkan.

Pemilihan objek berdasarkan salah satu dari ketiga strategi di atas tidak menjamin akan memberikan solusi optimal. Berbeda dengan strategi brute force yang selalu dapat memberikan hasil yang optimal. Tetapi greedy mengurangi jumlah langkah (kompleksitas) pencarian (Wahab, 2005).