DYNAMIC PROGRAMMING

DYNAMIC PROGRAMMING

AHMAD SOFIYAN

2TA05

10315366

Definisi System Dynamic Programming

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. Penyelesaian persoalan dengan pemrograman dinamis ini akan menghasilkan sejumlah berhingga pilihan yang mungkin dipilih, lalu solusi pada setiap tahap-tahap yang dibangun dari solusi pada tahap sebelumnya, dan dengan metode ini kita menggunakan persyaratan optimasi dan kendala untuk membatasi sejumlah pilihan yang harus dipertimbangkan pada suatu tahap.

Karakteristik Persoalan yang dimiliki oleh Program Dinamis:

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

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.

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

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

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

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

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

Prinsip optimalitas berlaku pada persoalan tersebut.

Langkah-langkah Pengembangan Algoritma Program Dinamis sebagai berikut:

Karakteristikkan struktur solusi optimal.

Definisikan secara rekursif nilai solusi optimal.

Hitung nilai solusi optimal secara maju atau mundur.

Konstruksi solusi optimal.

Kelebihan dan kekurangan System Dynamic Programming

Kelebihan:

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.

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.

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

Prosedur perhitungan dynamic programming juga memperkenankan bentuk analisissensitivitas terdapat pada setiap variabel status (state) maupun pada variabel yang ada di masing-masing tahap keputusan (stage).

Dynamic programming dapat menyesuaikan sistematika perhitungannya menurut ukuran masalah yang tidak selalu tetap dengan tetap melakukan perhitungan satu persatu secara lengkap dan menyeluruh.

Kelemahan:

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.

Masalah Alokasi Sumber Daya yang Terbatas

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

Masalah Muatan (Cargo-loading)

Cargo handling adalah kegiatan pelayanan terhadap muatan / barang (keluar dan masuk) yang melalui bandar udara, meliputi loading unloading, pemindahan dari pesawat udara ketempat penyimpanan (gudang cargo), menyusun dan menyimpan barang tersebut serta menyerahkan kepada pemiliknya, atau sebaliknya menerima dari si pemilik, disusun didalam tempat penyimpanan (gudang cargo), dipindahkan dari tempat penyimpanan ke pesawat udara dan memuat serta menyusun didalam ruangan compartment pesawat udara, dengan pengertian bahwa melaksanakan semua kegiatan tersebut dengan pengetahuan serta keahlian.

Untuk kegiatan Loading, dilakukan pada saat Pre Flight artinya kegiatan memuat barang (bagasi, kargo dan mail) dilakukan sebelum pesawat melakukan penerbangan oleh petugas-petugas ground handling. Stage dalam persoalan ini adalah jumlah barang yang harus diangkut dengan syarat tanpa melampaui kapasitas serta dapat memaksimumkan pendapatan.

Sumber:

http://www.wikipedia.org/

http://soalparna.blogspot.co.id/2015/03/teori-system-dynamic-programming.html