PEMROGRAMAN DINAMIS

BAB IV

PEMROGRAMAN DINAMIS

1. Tujuan Praktikum Pemrograman Dinamis
   
   1. Praktikan dapat memahami permasalahan-permasalahan dalam pemrograman dinamis.
      
   2. Praktikan dapat mencari solusi/ menyelesaikan permasalahan menggunakan metode
      penyelesaian masalah pemrograman dinamis yang ada.
      
2. Landasan Teori
   

    Pemrograman dinamis ini pertama kali dikembangkan oleh seorang ilmuwan benama Richard Bellman pada tahun 1957. Apabila dalam riset operasional yang lain, memiliki formulasi standar untuk memecahkan masalah, maka dalam pemrograman dinamis ini tidak ada formulasi yang standar, artinya setiap masalah dalam pemrograman dinamis memerlukan pola pendekatan atau penyelesaian yang berbeda satu dengan lainnya. Oleh karena itu perlu berlatih soal sebanyak mungkin untuk mendapatkan banyak bentuk penyelesaian kasus yang berbeda-beda.

Pemrograman dinamis adalah teknik matematik yang dapat diterapkan pada berbagai jenis persoalan. Ia dapat digunakan untuk menyelesaikan pesoalan dalam area seperti alokasi, pemuatan kargo, penggantian, pembuatan jadwal, dan inventory. Meskipun demikian, program dinamik adalah 'pendekatan' untuk penyelesaian persoalan dan bukan algoritma tunggal yang dapat digunakan untuk menyelesaikan semua jenis persoalan. Jadi, diperlukan algoritma terpisah untuk menyelesaikan setiap jenis persoalan.

Pendekatan program dinamik meliputi optimisasi proses keputusan multi tahap, yaitu membagi suatu persoalan ke dalam tahap-tahap atau sub problem dan kemudian menyelesaikan sub problem itu secara berurutan sampai persoalan awal akhirnya dapat diselesaikan. Jantung pendekatan program dinamik adalah asas optimalitas Bellman yang mengatakan bahwa suatu kebijaksanaan optimal mempunyai sifat bahwa apapun keadaan awal atau keputusan awal,keputusan tersisa harus merupakan kebijaksanaan optimal terhadap keadaan yang dihasilkan keputusan pertama.

Karakteristik Persoalan Program Dinamis

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
   

B.1 Model Pemrogram Dinamis

Persoalan Stagecoach

Jenis persoalan yang agak berbeda yang dapat diselesaikan menggunakan pemrograman dinamik adalah persoalan stagecoach. Dalam beberapa hal ia menyerupai persoalan alokasi, tetapi cukup berbeda untuk disajikan. Dalam realitanya, ini adalah pesoalan menentukan rute optimal melalui jaringan.

    Pada jaman dahulu, seorang pedagang yang bertempat tinggal di Pantai Timur Amerika Serikat akan melakukan perjalanan ke Pantai Barat dengan kereta tingkat. Harga asuransi perjalanan akan mencerminkan rute yang paling aman. Yaitu makin murah polis, makin aman rutenya. Gambar 13 mengilustrasikan berbagai rute dan harga polis untuk bepergian dari suatu negara ke negara bagian yang lain. Tujuan kita adalah mencari rute yang paling aman dari state 1dalam tahap 1 sampai state 10 dalam tahap 5. Nomer dalam lingkaran menyajikan state mana yang dapat ia lalui. Bilangan pada anak panah dari satu state ke state lainnya bersesuaian dengan harga polis. Bila Cij menyatakan harga polis dari state –i ke state-j maka :

C₁₂ = 2     C₂₅ = 8     C₅₈ = 4     C₈₁₀ = 6

C₁₃ = 3     C₂₆ = 7     C₅₉ = 6     C₉₁₀ = 5

C₁₄ = 5     C₂₇ = 4     C₆₈ = 11

C₃₅ = 6     C₆₉ = 9

C₃₆ = 9        C₇₈ = 15

C₃₇ = 8     C₇₉ = 13

C₄₅ = 9

C₄₆ = 7

C₄₇ = 3

    
 

 

 

 

 

 

 

Gambar 13. Contoh persoalan jaringan rute.

Masalahnya adalah menentukan rute yang paling aman dari state 1 sampai state 10. Ini sama saja dengan menentukan rute yang meminimumkan harga polis. Alasan yang diperlukan untuk mendapatkan penyelesaian program dinamik disajikan dalam langkah-langkah berikut.

 

 

Langkah 1

Kita mulai dengan mengandaikan bahwa pedagang telah sampai pada tahap 4. Misalkan untuk sementara ia berada dalam state 8. Manakah jalan termurah untuk mencapai state 10? Karenahanya terdapat satu rute, maka biaya termurah dari state 8 ke state 10 adalah 6 unit. Misalkan f4(8)= 6 menyatakan biaya minimum, dan misalkan d4(8) = 10 menyatakan state berikut di mana iaharus pergi dari state8.

Tetapi misalkan dalam stage4 ia berada dalam state9. Biaya minimum dari state9 ke 10 adalah f4 (9) = 5 dan d4 (9) = 10. Jadi, bila ia sampai pada state 8 atau 9 dalam stage 4,keputusan terbaik adalah pergi ke state 10 karena ini hanyalah satu-satunya rute. Hasil ini memang trivial,tetapi diperlukan untuk menyelesaikan keseluruhan program dinamik. Tabel 19 menyajikan keseluruhan hasil di atas.

 

Tabel 19. Keputusan optimal tahap 4 – 5

 

x	8	9
f4(x) d4(x)	6 10	5 10

 

Langkah 2

Kita mundur satu langkah dan andaikan pegadang sekarang sampai pada state 5,6, atau 7 ingin meminimumkan biaya untuk sampai state 10 melewati salah satu satate dalam tahap 4. Bila ia telah sampai pada state 5, ia perlu menyelediki:

1. Jumlah biaya dari state 5 ke 8 dan biaya optimal dari 8 ke 10
   
2. Jumlah biaya dari state 5 ke 9 dan biaya optimal dari 9 ke 10
   

Untuk harga minimum. Harga-harga ini adalah

1. 4 + f4(8) = 10 dari 5 ke 8 ke 10
   
2. 6 + f4(9) = 11 dari 5 ke 9 ke 10
   

Biaya minimum dari state 5 ke satet 10 melalui salah satu state pada tahap 4 adalah 10 dan ini dinyatakan dengan : f3(5) = 10

Rute optimal dari 5 adalah 8. Misalkan d3(5) = 8 menyatakan rute optimal ini.

Dengan cara yang sama, bila kita sampai pada state 6 dalam tahap 3, biaya minimum dari state 6 ke state 10 dengan melewati salah satu state dalam tahap 4 adalah :

 

F3(6) = min = = 18

d3(7) = 9.

Dalam setiap kasus, f3 (x) menyajikan biaya minimum untuk pergi dari state x ke state 10 ; d3 (x) adalah state optimal untuk pergi dari state x. Kebijaksanaan optimal dari setiap state dalam tahap 3 diberikan dalam Tabel 20

Tabel 20. Kebijaksanaan optimal, tahap 3 – 5

 

x	5	6	7	8	9
f4(x) d4(x) f3(x) d3(x)	10 8	14 9	18 9	6 10	5 10

 

 

 

 

 

Langkah 3

Sekarang kita menuju ke tahap 2 di mana pedagang secara teoritis berada dalam state 2, 3, atau 4.Bila ia berada dalam state 2, ia hanya perlu menyelidiki dua jumlahan untuk menentukan biaya minimum dari state 2 ke state 10 dengan melewati tahap 3 dan 4, karena ia hanya dapat melalui tiga state dalam tahap 3, dan biaya minimum untuk masing-masing darinya telah dihitung dalam langkah 2.

Jadi, ia dapat pergi ke state 10 dengan melalui state 5 dengan biaya minimum 8 + f3(5) = 8 + 10 = 18

atau melalui state 6 dengan biaya minimum

7 + f3(6) = 7 + 14 = 21

atau melalui state 7 dengan biaya minimum

4 + f3(7) = 4 + 18 = 22

Jadi,

 

= min

d₂(2) = 5

dengan cara yang sama

 

d₂(3) = 5

 

dengan cara yang sama

 

d₁(1)= 3

 

Ringkasan lengkap kebijaksanaan optimal dari state 1 ke state 10 diberikan dalam Tabel 21.

Tabel 21. Kebijakan optimal

x	1	2	3	4	5	6	7	8	9
f4(x) d4(x) f3(x) d3(x) f2(x) d2(x) f1(x) d1(x)	19 3	18 5	16 5	19 5	10 8	14 9	18 9	6 10	5 10

 

Dari Tabel 21. kita melihat bahwa biaya minimum dari state 1 ke state 10 adalah 19 dan rute optimalnya adalah :

1® 3 ®5 ®8 ®10

 

1. PERMASALAHAN
   
   1. Soal/ Kode Praktikum : P₄/ B
      

      Perusahaan angkutan omega merupakan jasa tranportasi yang melayani perjalanan dari Yogyakarta ke bandung jalur yang dapat di lalui di tunjukkan dalam diagram berikut :
      

 

 

 

 

 

 

 

Dalam diagram di atas angka dalam lingkran menunjukkan kota yang di lalui dari angka 1 (Yogyakarta) dan berahir di angka 10 (bandung) garis menunjukkan rute antara satu daerah dengan daerah lain dan angka diatas menunjukkan biaya dalam ribu. Karena suatu hal ongkos perjalanan dari kota 2, 3, dan 4 menuju kota 5 dan 6 masing-masing naik 65% dari ongkos biasanya. Analisa permasalahan diatas dengan menentukkan rute yang harus di pilih dengan cost minmal.

1. Penyelesaian Dengan Menggunakan Manual
   

   
    

STAGE 4

S	F 4 * (S)	X4 *
7	8	10
8	9	10
9	6	10

 

STAGE 3

X3   S	F3 (S,X3) = CSX3 + F4 *(X3)			F3*(S)	X3*
	7	8	9
5	14	13		13	8
6		10	11	10	8

 

STAGE 2

X2 S	F2 (S, X2) = CSX2 + F3 *(X2)		F2*(S)	X2*
	5	6
2	19	16	16,65	6
3	14	17	13,65	5
4	15	13	13,65	6

 

 

STAGE 1

X2 S	F1 (S, X2) = CSX2 + F3 *(X2)			F1*(S)	X1*
	2	3	4
1	22,65	22,65	22,65	22,65	4

 

Berdasarkan hasil diatas rute yang dipilih

1® 4 ® 6® 8® 10 degan biaya ongkos biaya :

9 + 3,65 + 6 + 5 + 1 + 9 = Rp 22,65

 

1. Penyelesaian Dengan Menggunakan Software WinQSB
   
   1. Buka program WinQSB dan pilih menu dinamic programming
      

1. Buka file|new problem sampai muncul kotak dialog pada Gambar 13 berikut:
   

 

1. Kemudian isi data sesuai Gambar 13 dan klik OK
   
2. Kemudian akan mucul tabel penginputan data seperti pada Gambar 14 dan ketikkan data yang telah didapatkan pada tabel tersebut (lihat Gambar 14)
   

 

    Gambar 14. Tabel peng-input-an data

1. Setelah penginputan data selesai klik solve and analize|solve the problem sehingga akan muncul solusi yang diperlihatkan oleh Gambar 15
   

    Gambar 15. Solusi optimal

Pada Gambar 15 dapat dilihat bahwa solusi optimal dari permasalahan transportasi di atas adalah dari node 1® 4 ® 6® 8® 10 dengan biaya Rp 22,65

 

 

1. Kesimpulan
   

Pemrograman dinamis adalah teknik matematik yang dapat diterapkan pada berbagai jenis persoalan. Ia dapat digunakan untuk menyelesaikan pesoalan dalam area seperti alokasi, pemuatan kargo, penggantian, pembuatan jadwal, dan inventory. Meskipun demikian, program dinamik adalah 'pendekatan' untuk penyelesaian persoalan dan bukan algoritma tunggal yang dapat digunakan untuk menyelesaikan semua jenis persoalan. Jadi, diperlukan algoritma terpisah untuk menyelesaikan setiap jenis persoalan

Pendekatan program dinamik meliputi optimisasi proses keputusan multitahap, yaitu membagi suatu persoalan ke dalam tahap-tahap atau sub problem dan kemudian menyelesaikan sub problem itu secara berurutan sampai persoalan awal akhirnya dapat diselesaikan.

Dengan menggunakan program WinQSB dan menggunakan hitungan manual tentang Pemrograman dinamis. Untuk mendapatkan ongkos minimal Rp 22,65 maka rute yang harus dipilih yaitu 1® 4 ® 6® 8® 10.