OPTIMASI MASALAH KNAPSACK MENGGUNAKAN ALGORITMA BRANCH AND BOUND

FITRIATUL MALAIKHAH, NIM. 12610023 (2016) OPTIMASI MASALAH KNAPSACK MENGGUNAKAN ALGORITMA BRANCH AND BOUND. Skripsi thesis, UIN SUNAN KALIJAGA YOGYAKARTA.

[img]
Preview
Text (OPTIMASI MASALAH KNAPSACK MENGGUNAKAN ALGORITMA BRANCH AND BOUND)
12610023_BAB-I_IV-atau-V_DAFTAR-PUSTAKA.pdf - Published Version

Download (9MB) | Preview
[img] Text (OPTIMASI MASALAH KNAPSACK MENGGUNAKAN ALGORITMA BRANCH AND BOUND)
12610023_BAB-II_sampai_SEBELUM-BAB-TERAKHIR.pdf - Published Version
Restricted to Registered users only

Download (5MB)

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.

Item Type: Thesis (Skripsi)
Additional Information: Noor Saif Muhammad Mussafi, M.Sc
Uncontrolled Keywords: optimasi, masalah knapsack, algoritma Branch and Bound, MATLAB
Subjects: Matematika
Divisions: Fakultas Sains dan Teknologi > Matematika (S1)
Depositing User: Drs. Bambang Heru Nurwoto
Date Deposited: 21 Dec 2016 14:23
Last Modified: 21 Dec 2016 14:23
URI: http://digilib.uin-suka.ac.id/id/eprint/23106

Share this knowledge with your friends :

Actions (login required)

View Item View Item
Chat Kak Imum