Teori System Dynamic Programming

DAFTAR ISI

BAB I

PENDAHULUAN

1. Latar Belakang
2. Maksud Dan Tujuan
3. Batasan Masalah

BAB II

Landasa Teori System Dynamic Programming

1. 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:

1. Persoalan dapat dibagi menjadi beberapa tahap (stage), yang pada setiap tahap hanya dapat 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. Jumlahnya bisa berhingga atau tak berhingga.
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.

Langkah-langkah Pengembangan Algoritma Program Dinamis sebagai berikut :

1. Karakteristikkan struktur solusi optimal.
2. Definisikan secara rekursif nilai solusi optimal.
3. Hitung nilai solusi optimal secara maju atau mundur.
4. Konstruksi solusi optimal.

2. Kelebihan dan kekurangan System Dynamic Programming

Kelebihan:

1. 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.
2. 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.
3. Pendekatan dynamic programming dapat diaplikasikan untuk berbagai macam masalah pemrograman matematik, karena dynamic programming cenderung lebih fleksibel daripada teknik optimasi lain.
4. 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).
5. Dynamic programming dapat menyesuaikan sistematika perhitungannya menurut ukuran masalah yang tidak selalu tetap dengan tetap melakukan perhitungan satu persatu secara lengkap dan menyeluruh.
   

Kelemahan:

1. 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.

3. Multi Stage Graph Problem

Multistage Graph adalah Graph dengan sifat-sifat khusus :

1. Graph berarah (Directed Graph)
2. Setiap edge-nya memiliki weight (bobot)
3. Hanya terdapat 1 source (disebut s) dan 1 sink (disebut t)
4. Lintasan dari source ke sink terdiri atas beberapa stage V1 sampai Vk
5. Semua edge menghubungkan node di Vi ke sebuah node di Vi + 1 dimana 1 ≤ i ≤ k
6. Terdapat stage sebanyak k, dimana k ≥ 2
7. Setiap path dari s ke t merupakan konsekuensi dari pilihan sebanyak k–2

Multistage Graph merupakan bentuk permodelan yang dapat digunakan untuk menyelesaikan berbagai permasalahan dunia nyata.

Contoh : pemilihan project untuk mendapatkan keuntungan maksimal; serta pemilihan langkah-langkah yang harus dipilih dalam menyelesaikan sebuah tugas.

Multistage Graph Problem

1. Problem mencari lintasan terpendek dari source ke sink pada sebuah Multistage Graph.
2. Problem ini merupakan salah satu contoh penerapan yang bagus dari Dynamic Programming.

Dynamic Programming pada Multistage Graph Problem

Teknik penyelesaian Multistage Graph Problem dengan Dynamic Programming berdasar pada sebuah prinsip bahwa jalur terpendek dari satu node (awal atau akhir) ke node lain di stage tertentu merupakan jalur terpendek dari stage sebelumnya ditambah panjang salah satu edge penghubung stage.

1. Metode Forward

Menghitung jarak ke depan (menuju sink)

2. Metode Backward

Menghitung jarak ke belakang (dari source)

METODE FORWARD

• Prinsip : analisis dilakukan dengan menghitung path (jalur) dari suatu node ke sink
• Rumus : cost (i,j) = min{c (j,k) + cost (i+1,k)}
• Perhitungan dimulai dari node-node di stage k–2
• Cost (i,j) artinya panjang lintasan dari node j di stage i menuju sink (t)
• c (j,l) artinya panjang lintasan dari node j ke node l

METODE BACKWARD

• Prinsip : analisis dilakukan dengan menghitung path (jalur) dari source ke suatu node
• Rumus : bcost (i,j) = min{bcost (i–1,l) + c (l,j)}
• Perhitungan dimulai dari node-node di stage 3
• Bcost (i,j) artinya panjang lintasan backward dari source (s) menuju node j di stage i
• c (j,l) artinya panjang lintasan dari node j ke node l

Rute Terpendek Multistage Graph

4. Studi Kasus
1. Knapsack Problem
2. Coin Change Problem
3. Traveling Salesman Problem

BAB III

Algoritma dan Pemrograman

1. Algoritma Dan Pemrograman Knapsack Problem

2. Algoritma Dan Pemrograman Coin Change Problem

3. Algoritma Dan Pemrograman Traveling Salesman Problem

Kesimpulan

Daftar pustaka

Di unduh 8.50 11/01/2015

Link http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2006-2007/Makalah_2007/MakalahSTMIK2007-032.pdf

https://www.scribd.com/doc/110045673/Metode-Greedy-amp-Dynamic-Programming#download

diunduh 8.43 12/01/2015

link http://aryo.lecture.ub.ac.id/files/2013/05/DAA-VII-Dynamic-Programming.pptx

http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2013-2014/Makalah2013/MakalahIF2211-2013-043.pdf

http://elearning.gunadarma.ac.id/docmodul/pengantar_analisis_algoritma/bab6_pemrograman_dinamis.pdf

knapsack problem bisa kita gambarkan, misalnya kita mempunyai sebuah kantong atau tas dengan kapasitas tertentu sedangkan dihadapan kita terdapat begitu banyak pilihan barang, maka kita harus memilih barang mana saja yang kira-kira akan kita ungkut sesuai kapasitas kantong yang kita miliki supaya kita bisa mendapatkan keuntungan yang sebesar-besarnya atau maksimal.