eprintid: 23106
rev_number: 10
eprint_status: archive
userid: 111
dir: disk0/00/02/31/06
datestamp: 2016-12-21 07:23:35
lastmod: 2016-12-21 07:23:35
status_changed: 2016-12-21 07:23:35
type: thesis
metadata_visibility: show
creators_name: FITRIATUL MALAIKHAH, NIM. 12610023
title: OPTIMASI MASALAH KNAPSACK MENGGUNAKAN ALGORITMA
BRANCH AND BOUND
ispublished: pub
subjects: Matematika
divisions: jur_mat
full_text_status: restricted
keywords: optimasi, masalah knapsack, algoritma Branch and Bound, MATLAB
note: Noor Saif Muhammad Mussafi, M.Sc
abstract: Sebagian besar masalah perencanaan dalam dunia nyata merupakan
masalah optimasi. Salah satu masalah optimasi yang dihadapi adalah masalah
knapsack yang merupakan masalah pemilihan barang dengan pembatasan
kapasitas maksimum daya tampung. Pemilihan barang didasarkan pada kombinasi
barang yang akan menghasilkan nilai kepentingan tertinggi dan masih memenuhi
batasan kapasitas daya tampung. Masalah yang menarik untuk dibahas adalah
masalah knapsack yang dihadapi oleh para pendaki gunung. Mereka akan
dihadapkan pada masalah pemilhan barang yang akan dibawa saat mendaki. Hal
yang perlu diperhatikan adalah tas ransel mempunyai kapasitas maksimum
sehingga tidak semua barang dapat dimasukkan.
Terdapat beberapa algoritma yang dapat digunakan untuk menyelesaikan
masalah knapsack. Algoritma yang digunakan pada penelitian ini adalah algoritma
Branch and Bound. Proses pencarian solusi pada algoritma ini menggunakan
skema Breadth First Search (pencarian melebar). Langkah kerja algoritma Branch
and Bound dalam optimasi masalah knapsack dimulai dengan merepresentasikan
pencarian solusi ke dalam bentuk pohon berakar. Selanjutnya dilakukan proses
branching dan bounding terhadap pohon berakar. Branching adalah pembagian
permasalahan menjadi beberapa subregion yang mungkin mengarah ke solusi.
Sedangkan bounding merupakan pencarian nilai batas untuk solusi optimal di
dalam subregional yang mengarah ke solusi. Tahapan branching dan bounding
dihubungkan dengan strategi pencarian yang ditentukan berdasarkan kriteria
knapsack. Proses pencarian solusi dilakukan secara manual dan rancang bangun
menggunakan bahasa pemrograman MATLAB.
Berdasarkan hasil penelitian mengenai masalah knapsack yang dihadapi
oleh pendaki gunung dengan kapasitas tas ransel 25 liter, diperoleh hasil optimal
yaitu 15 barang terpilih dari total 21 barang yang tersedia, dengan jumlah volume
23,7813 liter, nilai kepentingan 163, dan hanya menyisakan ruang kosong sebesar
1,2187 liter.
date: 2016-12-06
date_type: published
pages: 165
institution: UIN SUNAN KALIJAGA YOGYAKARTA
department: FAKULTAS SAINS DAN TEKNOLOGI
thesis_type: skripsi
thesis_name: other
citation:   FITRIATUL MALAIKHAH, NIM. 12610023  (2016) OPTIMASI MASALAH KNAPSACK MENGGUNAKAN ALGORITMA BRANCH AND BOUND.  Skripsi thesis, UIN SUNAN KALIJAGA YOGYAKARTA.   
document_url: https://digilib.uin-suka.ac.id/id/eprint/23106/1/12610023_BAB-I_IV-atau-V_DAFTAR-PUSTAKA.pdf
document_url: https://digilib.uin-suka.ac.id/id/eprint/23106/2/12610023_BAB-II_sampai_SEBELUM-BAB-TERAKHIR.pdf