Pemrograman Dinamis dan Contoh Studi Kasus (3) Knapsack (Forward)

Perusahaan PT. Bangkrut Abadi ingin mendistribusikan produknya yaitu pakan ternak ke wilayah Bogor. Sebelum melakukan pendistribusian, manager perusahaan tersebut harus mengemas Pakan Tenak yang diproduksi sebelum dilakukan pendistribusian, yaitu dengan memasukkan barang yang sudah diproduksi ke dalam sebuah truk box. Manager tersebut memiliki 5 tipe model pengemasan pakan ternak dengan berat keseluruhan 16 kwintal dengan profit yang berbeda untuk setiap model pengemasan pakan ternak, yang harus dimasukkan ke dalam truk box dengan kapasitas 7 kwintal. Manager tersebut harus mencari solusi optimal agar pendistribusian pakan ternak bisa menghasilkan profit yang maksimal ( n=5 ; M=7 ). Berikut adalah tabel mengenai berat dan profit yang dihasilkan untuk setiap model pengemasan pakan ternak. 
   
      Tabel Berat dan Profit untuk Pengiriman Produk

Barang ke-i	wi (Kwintal)	pi (Juta)
1	4	22
2	6	24
3	2	15
4	3	18
5	1	13

Berdasarkan tabel diatas, Carilah nilai solusi optimumnya.

Studi kasus yang ada didapatkan data yaitu  n (banyaknya tipe produk) = 5, M (kapasitas kendaraan) = 7. Dilakukan olah data manual sebagai berikut :        

                 Tabel Knapsack

Barang ke-i	wi (Kwintal)	pi (Juta)
1	4	22
2	6	24
3	2	15
4	3	18
5	1	13

Tahap 1:  f₁(y) = max{f₀(y), p₁ + f₀(y – w₁)} = max{f₀(y), 22 + f₀(y – 4)}

Langkah pertama pada studi kasus knapsack, yaitu memulai dari tahap 1. Tahap 1 dengan proses seperti pada tabel 4.6.

                                                         Tabel 4.6 Tabel Knapsack

Solusi Optimum
y	f0(y)	22+f0(y-4)	f1(y)	(x1*, x2*, x3*, x4*, x5*)
0	0	22 + ( ∞ ) =  ∞	0	(0,0,0,0,0)
1	0	22 + (∞ ) =  ∞	0	(0,0,0,0,0)
2	0	22 + (∞ ) =  ∞	0	(0,0,0,0,0)
3	0	22 + (∞ ) =  ∞	0	(0,0,0,0,0)
4	0	22 + 0 = 22	22	(1,0,0,0,0)
5	0	22 + 0 = 22	22	(1,0,0,0,0)
6	0	22 + 0 = 22	22	(1,0,0,0,0)
7	0	22 + 0 = 22	22	(1,0,0,0,0)

Nilai di kolom ini pada tahap pertama adalah 0. Variabel keputusan terdapat di tahap ke-1 dengan besarnya solusi optimum adalah 22.

 Tahap 2:  f₂(y) = max{f₁(y), p₂ + f₁(y – w₂)} = max{f₁(y), 24 + f₁(y – 6)}

Langkah kedua pada studi kasus knapsack, yaitu memulai dari tahap 2. Tahap 2 dengan proses seperti pada tabel 4.7.

                                                 Tabel 4.7 Tabel Knapsack

Solusi Optimum
y	f1(y)	24+f1(y-6)	f2(y)	(x1*, x2*, x3*, x4*, x5*)
0	0	24 + ( ∞ ) =  ∞	0	(0,0,0,0,0)
1	0	24 + (∞ ) =  ∞	0	(0,0,0,0,0)
2	0	24 + (∞ ) =  ∞	0	(1,0,0,0,0)
3	0	24 + (∞ ) =  ∞	0	(1,0,0,0,0)
4	22	24 + (∞ ) =  ∞	22	(1,0,0,0,0)
5	22	24 + (∞ ) =  ∞	22	(1,0,0,0,0)
6	22	24 + 0 = 24	24	(0,1,0,0,0)
7	22	24 + 0 = 24	24	(0,1,0,0,0)

Nilai pada kolom ini merupakan nilai salinan dari f1(y) dari tabel sebelumnya. Variabel keputusan terdapat di tahap ke-1 dan ke-2 dengan besarnya solusi optimum masing-masing adalah 22 dan 24.

Tahap 3: f₃(y) = max{f₂(y), p₃ + f₂(y – w₃)} = max{f₂(y), 15 + f₂(y – 2)}

Langkah ketiga pada studi kasus pendekatan mundur, yaitu memulai dari tahap 3. Tahap 3 dengan proses seperti pada tabel 4.8.     

                                          Tabel 4.8 Tabel Knapsack

Solusi Optimum
y	f2(y)	15+f2(y-2)	f3(y)	(x1*, x2*, x3*, x4*, x5*)
0	0	15 + ( ∞ ) =  ∞	0	(0,0,0,0,0)
1	0	15 + (∞ ) =  ∞	0	(0,0,0,0,0)
2	0	15 + (0 ) =  15	15	(0,0,1,0,0)
3	0	15 + (0 ) = 15	15	(0,0,1,0,0)
4	22	15 + (0 ) =  15	22	(1,0,0,0,0)
5	22	15 + (0 ) =  15	22	(1,0,0,0,0)
6	24	15 + 22 = 37	37	(1,0,1,0,0)
7	24	15 + 22 = 37	37	(1,0,1,0,0)

Nilai pada kolom ini merupakan nilai salinan dari f2(y) dari tabel sebelumnya. Variabel keputusan terdapat di tahap ke-3 ini solusi optimum adalah 15.

Tahap 4:  f₄(y) = max{f₄(y), p₄ + f₃(y – w₄)} = max{f₃(y), 18 + f₃(y – 3)}   

Langkah keempat pada studi kasus pendekatan mundur, yaitu memulai dari tahap 4. Tahap 4 dengan proses seperti pada tabel 4.9.        

                                     Tabel 4.9 Tabel Knapsack

Solusi Optimum
y	f3(y)	18+f3(y-3)	f4(y)	(x1*, x2*, x3*, x4*, x5*)
0	0	18 + ( ∞ ) = ∞	0	(0,0,0,0,0)
1	0	18 + ( ∞ ) = ∞	0	(0,0,0,0,0)
2	15	18 + ( ∞ ) = ∞	0	(0,0,0,0,0)
3	15	18 + 0 = 18	18	(0,0,0,1,0)
4	22	18 + 0 = 18	22	(1,0,0,0,0)
5	22	18 + 15 = 33	33	(0,0,1,1,0)
6	37	18 + 15 = 33	37	(1,0,1,0,0)
7	37	18 + 22 = 40	40	(1,0,0,1,0)

Nilai pada kolom ini merupakan nilai salinan dari f3(y) dari tabel sebelumnya. Variabel keputusan terdapat di tahap ke-4 ini solusi optimum adalah 18.

Tahap 5:  f₅(y) = max{f₅(y), p₅ + f₄(y – w₅)} = max{f₄(y), 13 + f₄(y – 1)}   

Langkah kelima pada studi kasus pendekatan mundur, yaitu memulai dari tahap 5. Tahap 5 dengan proses seperti pada tabel 4.10.

                                  Tabel 4.10 Tabel Knapsack

Solusi Optimum
y	f4(y)	18+f4(y-1)	f5(y)	(x1*, x2*, x3*, x4*, x5*)
0	0	13 + ( ∞ ) = ∞	0	(0,0,0,0,0)
1	0	13 + ( ∞ ) = ∞	0	(0,0,0,0,0)
2	0	13 + (0) = 13	13	(0,0,0,0,1)
3	18	13 + (0) = 13	13	(0,0,0,0,1)
4	22	13 + 18 = 31	31	(0,0,0,1,1)
5	33	13 + 22 = 35	35	(1,0,0,0,1)
6	37	13 + 33 = 46	46	(0,0,1,1,1)
7	40	13 + 37 = 50	50	(1,0,1,0,1)

Nilai pada kolom ini merupakan nilai salinan dari f2(y) dari tabel sebelumnya. Variabel keputusan terdapat di tahap ke-3 ini solusi optimum adalah 15. Setelah dilakukan penghitungan manual 5 tahap maka ditentukan solusi optimum X = (1,0,1,0,1) dengan åp = f = 50.

Studi kasus knapsack terdapat permasalahan pada packing barang yang akan dikirimkan melalui kurir. Terdapat 5 barang yang akan dikirim, masing masing memiliki bobot dan nilai yang berbeda dengan kapasitas maksimum truk pengantar 7 kwintal. Studi kasus knapsack terdapat permasalahan pada packing barang yang akan dikirimkan melalui kurir. Terdapat 5 barang yang akan dikirim, masing masing memiliki bobot dan nilai yang berbeda dengan kapasitas maksimum truk pengantar 7 kwintal. Solusi optimum X= (1, 0, 1, 0, 1) dengan ∑p = f = 50. Angka ini bermaksud bahwa PT. Bangkrut Abadi mendapat keuntungan maksimal bila barang ke 1, 3 dan 5 digabung pada saat proses packing, sedangkan untuk barang ke 2 dan 4 dapat digabung dengan barang lain.

Perhitungan Software Knapsack

            Langkah pertama dalam melakukan perhitungan software yaitu membuka dahulu software qm.exe. Muncul tampilan seperti yang terlihat pada gambar 4.11.

Gambar 4.11 Tampilan Software Qm

Ketik huruf M untuk menjalankan perhitungan pemrograman dinamis. Muncul tampilan seperti yang terlihat pada gambar 4.12.

 Gambar 4.12 Tampilan Software Qm

            Ketik huruf C untuk masuk ke perhitungan Knapsack. Tekan huruf N untuk membuat data baru. Masukan data untuk problem title, berapa banyak capacity (kapasitas) yang ada pada truk. Masukan data pada setiap number of item (banyaknya varian barang) dan tabel berat, profit (keuntungan) dan ketersediaan (availbe). Muncul tampilan seperti yang terlihat pada gambar 4.13.

Gambar 4.13 Tampilan Software Qm untuk Input Data Knapsack

Tekan tombol escape (esc) lalu tekan huruf R (Run) untuk menjalankan Software. Muncul tampilan seperti yang terlihat pada gambar 4.14.

 
Gambar 4.14 Tampilan Perhitungan Data Software Qm  

              Perhitungan software diatas dapat diketahui didapat hasil. Final solution yang didapat yaitu item nomer 5 dengan nilai 22, item nomer 4 dengan nilai 0, item nomer 3 dengan nilai 15, item nomer 2 dengan nilai 0 dan item nomer 5 dengan nilai 13 dengan total nilai tersebut adalah 50. 

                  

              Studi kasus knapsack terdapat permasalahan pada packing barang yang akan dikirimkan melalui kurir. Terdapat 5 barang yang akan dikirim, masing masing memiliki bobot dan nilai yang berbeda dengan kapasitas maksimum truk pengantar 7 kwintal. Studi kasus knapsack terdapat permasalahan pada packing barang yang akan dikirimkan melalui kurir. Terdapat 5 barang yang akan dikirim, masing masing memiliki bobot dan nilai yang berbeda dengan kapasitas maksimum truk pengantar 7 kwintal. Solusi optimum X= (1, 0, 1, 0, 1) dengan ∑p = f = 50. Angka ini bermaksud bahwa PT. Bangkrut Abadi mendapat keuntungan maksimal bila barang ke 1, 3 dan 5 digabung pada saat proses packing, sedangkan untuk barang ke 2 dan 4 dapat digabung dengan barang lain.