PENYELESAIAN MASALAH INTEGER KNAPSACK DENGAN ALGORITMA DYNAMIC PROGRAMMING DAN ALGORITMA BRANCH AND BOUND

Abstract

Permasalahan Knapsack merupakan suatu permasalahan dalam menentukan pemilihan obyek yang masing-masing mempunyai bobot atau berat (weight) untuk dimuat dalam sebuah media penyimpanan tanpa melebihi kapasitas media penyimpanan tersebut sehingga diperoleh hasil yang optimal dan keuntungan maksimum (profit). Permasalahan Integer Knapsack adalah menentukan objek mana saja yang harus dimuat atau tidak dimuat sama sekali dalam media penyimpanan. Objek yang dimasukkan kedalam media pengangkutan dalam satu item dimensinya harus dimasukkan semua atau tidak sama sekali. Objek dari permasalahan ini adalah bagaimana memilih objek-objek yang dimasukkan ke dalam media pengangkutan sehingga tidak melebihi kapasitas dari media pengangkutan namun memaksimalkan total keuntungan yang diperoleh. Algoritma yang digunakan untuk menyelesaiakan permasalahan Integer Knapsack tersebut, diantaranya adalah algoritma Dynamic Programming dan algoritma Branch and Bound. Oleh karena itu penulis tertarik untuk menerapkan algoritma tersebut untuk menentukan barang yang akan diangkut serta mencari nilai keuntungan maksimum dengan berat total barang tidak melebihi kapasitas berat media pengangkutan. Kompleksitas waktu dari kedua algoritma tersebut juga akan menjadi bahan pertimbangan ketika menentukan algoritma mana yang lebih baik untuk diterapkan pada masalah Integer Knapsac. Pada penelitian ini dilakukan di toko bangunan UD. Toda yang terletak di Kecamatan Ambulu Kabupaten Jember. Pengambilan data dilakukan dengan metode wawancara dan data yang diambil barupa data harga beli, harga jual, dan banyaknya barang. Data tersebut kemudian diolah menggunakan algoritma Dynamic Programming dan algoritma Branch and Bound dengan bantuan program software matematika yaitu MATLAB. Dari hasil penelitian dengan bantuan program menunjukkan: (1) Keuntungan maksimum dihasilkan menggunakan algoritma Dynamic Programming adalah sebesar Rp. 13.387.500,- dengan berat barang yang diangkut 8.000 kg dan waktu komputasi 11,752 detik. (2) Keuntungan maksimum dihasilkan menggunakan algoritma Branch and Bound adalah sebesar Rp. 10.410.000,- dengan berat barang yang diangkut 7.990 kg dan waktu komputasi 0,035285 detik. Berdasarkan kompleksitas waktu pada pengerjaan mengunakan algoritma Dynamic Programming adalah O(𝑛3) yang berarti kelompok kubik. Sedangkan algoritma Branch and Bound adalah O(𝑛2) yang berarti kuadratik. Sehingga algoritma Branch and Bound lebih efisien dalam penyelesaian masalah Integer knapsack. Dari hasil diatas dapat disimpulkan bahwa algoritma Dynamic Programming lebih optimal untuk mencari keuntungan dari pada algoritma Branch and Bound untuk menyelesaikan masalah Integer Knapsack. Serta waktu komputasi dan kompleksitas waktu yang dibutuhkan lebih efisien. Karena algoritma Dynamic Programming bersifat global untuk melakukan pencarian solusinya berbeda dengan algoritma Branch and Bound pencariannya bersifat lokal.