TY  - THES
N1  - Noor Saif Muhammad Mussafi, M.Sc
ID  - digilib23106
UR  - https://digilib.uin-suka.ac.id/id/eprint/23106/
A1  - FITRIATUL MALAIKHAH, NIM. 12610023
Y1  - 2016/12/06/
N2  - 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.
PB  - UIN SUNAN KALIJAGA YOGYAKARTA
KW  - optimasi
KW  -  masalah knapsack
KW  -  algoritma Branch and Bound
KW  -  MATLAB
M1  - skripsi
TI  - OPTIMASI MASALAH KNAPSACK MENGGUNAKAN ALGORITMA
BRANCH AND BOUND
AV  - restricted
EP  - 165
ER  -