IMPLEMENTASI ALGORITMA BRANCH AND BOUND PADA 0-1 KNAPSACK PROBLEM UNTUK MENGOPTIMALKAN MUATAN BARANG - Pratiwi, Arum; Mulyono, Mulyono; Rochmad, Rochmad (Universitas Negeri Semarang, 2014)
Pemrogaman bilangan bulat (integer progamming) yang hanya mempunyai satu pembatas dikenal sebagai masalah knapsack (knapsack problem). Metode untuk menyelesaikan permasalahan tersebut adalah algoritma Branch and Bound. Algoritma Branch and Bound secara sistematis mengabaikan sekumpulan kandidat solusi yang tidak potensial menuju solusi optimal menggunakan estimasi batas atas dan bawah (upper and lower estimated bounds) dari kuantitas yang dioptimasi. Alat bantu yang dapat digunakan adalah software Lingo 11.0. Dalam tulisan ini akan dikaji bagaimana cara untuk mengoptimalkan muatan barang agar memperoleh keuntungan yang maksimal. Penyelesaian permasalahan Knapsack 0-1 berdasarkan studi kasus di CV Pangestu Interaksi Semarang dengan menggunakan algoritma Branch and Bound diperoleh solusi optimal x*=(1 ,1 ,1 ,1 ,0,1 ) dan nilai optimal z*=1 1 30000 yang ditemukan pada submasalah 1 , step kesembilan (t=9).