PEMECAHAN MASALAH KNAPSACK DENGAN METODE BRANCH AND BOUND

Sulasmina, Merisa (2010) PEMECAHAN MASALAH KNAPSACK DENGAN METODE BRANCH AND BOUND. Other thesis, Fakultas MIPA.

Preview

PDF (PEMECAHAN MASALAH KNAPSACK DENGAN METODE BRANCH AND BOUND) - Supplemental Material Available under License Creative Commons Public Domain Dedication. Download (232Kb) | Preview

Abstract

Pada pemrograman integer ada pemrograman integer khusus yang sering dikenal dengan pemrograman integer nol-satu. Pada pemrograman integer nol- satu variabel-variabel keputusannya diharapkan bernilai nol atau satu. Salah satu masalah yang berhubungan dengan pemrograman integer nol-satu adalah masalah Knapsack. Masalah ini berkaitan dengan bagaimana memuat sejumlah anggota barang atau item ke dalam truk sehingga didapatkan solusi optimal yang diharapkan. Pada masalah Knapsack yang hanya memiliki satu kendala dapat diselesaikan dengan metode Branch and Bound. Rumusan masalah pada penelitian ini adalah Bagaimana menyelesaikan masalah Knapsack dengan menggunakan metode Branch and Bound. Penelitian ini bertujuan untuk menunjukkan bagaimana proses penyelesaian suatu masalah Knapsack dengan menggunakan metode Branch and Bound. Langkah penyelesaian masalah Knapsack dengan metode Branch and Bound adalah : pencabangan, pembatasan, dan penghentian. Iterasi langkah pencabangan dan pembatasan terus dilakukan hingga semua variabel keputusan bernilai integer. Selanjutnya untuk menentukan nilai optimal masalah, dimulai dari submasalah terakhir ke submasalah-submasalah sebelumnya. Penghentian penentuan nilai optimal dilakukan jika penyelesaian program linier submasalah tidak mempunyai penyelesaian layak, jika seluruh variabel keputusan sudah bilangan bulat dan jika nilai Z optimalnya lebih kecil dari nilai batas bawah Z (Lower Bound). Kata Kunci : pemrograman linier, pemrograman integer 0-1, metode Branch and Bound

Actions (login required)

View Item