Tugas Riset Operasi 4

Dynamic programming problems adalah masalah multi tahap(multistage) dimana keputusan dibuat secara berurutan (in sequence).Pemrograman dinamis (dynamic programming) adalah metode pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan langkah (step) atau tahapan (stage) sedemikian rupa sehingga solusi dari permasalahan ini dapat dipandang dari serangkaian keputusan-keputusan kecil yang saling berkaitan satu dengan yang lain

Karakteristik Persoalan Program Dinamis:

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

b.                  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. Jumlahnya bisa berhingga atau tak berhingga.

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

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

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

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

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

h.                  Prinsip optimalitas berlaku pada persoalan tersebut.

Langkah-langkah Pengembangan Algoritma Program Dinamis sebagai berikut:

a.                   Karakteristikkan struktur solusi optimal.

b.                  Definisikan secara rekursif nilai solusi optimal.

c.                   Hitung nilai solusi optimal secara maju atau mundur.

d.                  Konstruksi solusi optimal.

Kelebihan dan kekurangan System Dynamic Programming

a.       Mengoptimalkan penyelesaian suatu masalah tertentu yang diuraikan menjadi sub-submasalah yang lebih kecil yang terkait satu sama lain dengan tetap memperhatikan kondisi dan batasan permasalahan tersebut.

b.      Proses pemecahan suatu masalah yang kompleks menjadi sub-sub masalah yang lebih kecil membuat sumber permasalahan dalam rangkaian proses masalah tersebut menjadi lebih jelas untuk diketahui.

c.       Pendekatan dynamic programming dapat diaplikasikan untuk berbagai macam masalah pemrograman matematik, karena dynamic programming cenderung lebih fleksibel daripada teknik optimasi lain.

KELEMAHAN:

a.       Penggunaan dynamic programming jika tidak dilakukan secara tepat, akan mengakibatkan ketidakefisienan biaya maupun waktu. Karena dalam menggunakan dynamic programming diperlukan keahlian, pengetahuan, dan seni untuk merumuskansuatu masalah yang kompleks, terutama yang berkaitan dengan penetapan fungsi transformasi dari permasalahan tersebut.

Program Dinamis (dynamic programming) 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.

1.            Masalah alokasi

              Model alokasi dalam permasalahan program linear merupakan aplikasi yang paling praktis. Semua model alokasi biasanya mencoba untuk mengalokasi-kan suatu sumber daya yang terbatas supaya mengoptimalkan hasil dari alokasi itu. Sumber daya yang terbatas itu dapat berupa lahan, bahan baku, tenaga kerja, mesin, modal, waktu, dan lain lain. Alokasi ini dilakukan untuk memaksimalkan laba atau memperkecil biaya, atau mengoptimalkan ukuran-ukuran efisiensi lain yang ditetapkan oleh keputusan pembuat.

2.         Masalah Muatan (Cargo – Loading)

Masalah knapsack muncul pada tahun 1957 yang dikemukakan oleh Dantzig. Munculnya permasalahan ini adalah dari seorang tentara yang akan berangkat ke medan tempur. Ia membawa sebuah ransel yang mempunyai kapasitas volume tertentu. Ransel tersebut akan diisi berbagai perlengkapan yaitu senjata, pakaian, makanan, obat-obatan dan lain-lain. Masing-masing perlengkapan memberikan suatu nilai yang berarti baginya. Tentara tersebut akan memilih perlengkapan apa saja yang akan dimasukkan ke dalam ransel tanpa melanggar kapasitas volume tetapi jumlahan nilai yang diberikan maksimum.

Masalah knapsack merupakan masalah pemrograman bilangan bulat yang sederhana, tetapi mempunyai aplikasi yang cukup banyak dalam bidang industri. Contohnya adalah cargo loading, cutting stock, pemilihan proyek (project selection),dan budget control.

Keluarga masalah knapsack menghendaki subset item yang memaksimalkan keuntungan tanpa melanggar kapasitas knapsack. Menurut Pisinger (1995) jenis masalah knapsack dibedakan menurut distribusi item dan knapsack, yaitu:

a.                   Masalah knapsack baku atau knapsack 0-1 (MKB)

b.                  Masalah knapsack terbatas (Bounded Knapsack Problem)

c.                   Masalah knapsack pemilihan ganda (Multiple choice Knapsack Problem)

d.                  Masalah knapsack ganda (Multiple Knapsack Problem)