Analisis algoritma Boudjellaba-Gningue-Shamakhai (BGS) dan algoritma Dynamic Programming dalam menyelesaikan masalah Knapsack (0-1)

Hapidah, Epi (2023) Analisis algoritma Boudjellaba-Gningue-Shamakhai (BGS) dan algoritma Dynamic Programming dalam menyelesaikan masalah Knapsack (0-1). Sarjana thesis, UIN Sunan Gunung Djati Bandung.

Preview	Text (COVER) 1_cover.pdf Download (8MB) | Preview
Preview	Text (ABSTRAK) 2_abstrak.pdf Download (8MB) | Preview
Preview	Text (DAFTAR ISI) 3_daftarisi.pdf Download (8MB) | Preview
Preview	Text (BAB I) 4_bab1.pdf Download (9MB) | Preview
	Text (BAB II) 5_bab2.pdf Restricted to Registered users only Download (9MB) | Request a copy
	Text (BAB III) 6_bab3.pdf Restricted to Registered users only Download (9MB) | Request a copy
	Text (BAB IV) 7_bab4.pdf Restricted to Registered users only Download (9MB) | Request a copy
	Text (BAB V) 8_bab5.pdf Restricted to Registered users only Download (8MB) | Request a copy
	Text (DAFTAR PUSTAKA) 9_daftarpustaka.pdf Restricted to Registered users only Download (8MB) | Request a copy

Abstract

INDONESIA : Masalah knapsack terjadi saat beberapa barang dipilih lalu dimasukkan ke dalam knapsack dengan batas total kapasitas knapsack dalam pesanan untuk memaksimalkan total keuntungan yang didapatkan. Tujuan dari penelitian adalah menganalisis kedua algoritma tersebut dan mencari algoritma yang dapat memberikan solusi optimal yang lebih baik dalam menyelesaikan masalah knapsack (0-1). Pada penelitian ini digunakan integer knapsack problem atau masalah knapsack (0-1) dan masalah knapsack dihubungkan dengan masalah transportasi linear. Analisis hasil perbandingan dari data sekunder diperoleh dari Badan Pusat Statistik (BPS) dengan judul “Ekspor Barang Perhiasan dan Barang Berharga Menurut Negara Tujuan Utama pada tahun 2017-2019” sebanyak 30 data dengan masing-masing data adalah 10 data kasus 1 (2017), 10 data kasus 2 (2018) dan 10 data kasus 3 (2019) yang digunakan sebagai objek penelitian masalah knapsack dengan menggunakan metode Algoritma Boudjellaba-Gningue-Shamakhai (BGS) dan Algoritma Dynamic Programming. Hasil percobaan dengan data tersebut dengan 3 kasus untuk data yang berbeda. Metode Algoritma Boudjellaba-Gningue-Shamakhai (BGS) secara manual, pada kasus 1 (2017) dengan jumlah 10 data dengan maka , dan diperoleh hasil solusi layak awal sama dengan solusi optimal yaitu atau profit sebesar 2.641.421.900 USD dan berat barang yang optimal dimasukkan ke dalam knapsack yaitu sebanyak 397,7 ton, yaitu barang dengan tujuan ke Taiwan, India, Afrika Selatan, Uni Emirat Arab, Swiss, Australia, Hongkong, Singapura dan Amerika Serikat. Pada kasus 2 (2018) dengan jumlah 10 data dengan maka , dan diperoleh hasil solusi layak awal sama dengan solusi optimal yaitu atau profit sebesar 1.781.768.100 USD dan berat barang yang optimal dimasukkan ke dalam knapsack yaitu sebanyak 353,9 ton, yaitu barang dengan tujuan ke Taiwan, Uni Emirat Arab, Afrika Selatan, Swiss, Italia, Australia, India, Hongkong, dan Singapura. Pada kasus 3 (2019) dengan jumlah 10 data dengan maka , dan diperoleh hasil solusi layak awal sama dengan solusi optimal yaitu atau profit sebesar 1.909.797.984 USD dan berat barang yang optimal dimasukkan ke dalam knapsack yaitu sebanyak 414,1 ton, yaitu barang dengan tujuan ke Taiwan, India, Afrika Selatan, Uni Emirat Arab, Swiss, Hongkong, Singapura dan Amerika Serikat. Pada kasus dengan metode Algoritma Dynamic Programming secara manual, yaitu pada kasus 1 (2017) dengan jumlah 10 data diperoleh hasil keputusan bahwa barang yang dimasukkan ke dalam knapsack adalah barang dengan tujuan ke Taiwan, India, Afrika Selatan, Uni Emirat Arab, Swiss, Italia, Hongkong, Singapura, dan Amerika Serikat. Nilai keuntungan optimal atau profit yang diperoleh sebesar 2.641.776.900 USD dengan berat 402,7 ton. Pada kasus 2 (2018) dengan jumlah 10 data diperoleh hasil keputusan bahwa barang yang dimasukkan ke dalam knapsack adalah barang dengan tujuan ke Taiwan, Uni Emirat Arab, Afrika Selatan, Swiss, Italia, Australia, India, Hongkong dan Singapura. Nilai keuntungan optimal yang diperoleh sebesar 1.781.768.100 USD dengan berat 353,9 ton. Pada kasus 3 (2019) dengan jumlah 10 data diperoleh hasil keputusan bahwa barang yang dimasukkan ke dalam knapsack adalah barang dengan tujuan ke Taiwan, India, Afrika Selatan, Uni Emirat Arab, Swiss, Hongkong, Singapura dan Amerika Serikat. Nilai keuntungan optimal yang diperoleh sebesar 1.884.718.200 USD dengan berat 414,1 ton. Berdasarkan analisis yang dilakukan, dapat disimpulkan bahwa untuk menentukan solusi optimal dalam menyelesaikan masalah knapsack dengan menggunakan metode Algoritma Dynamic Programming menghasilkan nilai yang lebih optimal dibandingkan dengan metode Algoritma Boudjellaba-Gningue-Shamakhai (BGS). ENGLISH : The knapsack problem occurs when several items are selected and then put into the knapsack with a limit on the total knapsack capacity in the order to maximize the total profit earned. The purpose of this research is to analyze the two algorithms and find an algorithm that can provide a better optimal solution in solving the knapsack problem (0-1). In this study, the integer knapsack problem or knapsack problem (0-1) is used and the knapsack problem is related to the linear transportation problem. Analysis of comparative results from secondary data obtained from the Central Statistics Agency (BPS) with the title "Export of Jewelry and Valuable Goods by Main Destination Countries in 2017-2019" as many as 30 data with each data being 10 data case 1 (2017), 10 case 2 data (2018) and 10 case 3 data (2019) which are used as objects of research on the knapsack problem using the Boudjellaba-Gningue-Shamakhai (BGS) Algorithm and the Dynamic Programming Algorithm. The results of experiments with these data with 3 cases for different data. Manual Boudjellaba-Gningue-Shamakhai (BGS) Algorithm method, in case 1 (2017) with a total of 10 data with then , and the results obtained the initial feasible solution is the same as the optimal solution, namely or a profit of 2.641.421.900 USD and the optimal weight of goods put into the knapsack is 397,7 tons, namely goods destined for Taiwan, India, South Africa, United Arab Emirates, Switzerland, Australia, Hong Kong, Singapore and the United States. In case 2 (2018) with a total of 10 data with then , and the results of the initial feasible solution are the same as the optimal solution, namely or a profit of 1.781.768.100 USD and the optimal weight of goods to be put into the knapsack is 353,9 tons, namely goods destined for Taiwan, United Arab Emirates, South Africa, Switzerland, Italy, Australia, India, Hong Kong and Singapore. In case 3 (2019) with a total of 10 data with then , and the results of the initial feasible solution are the same as the optimal solution, namely or a profit of 1.909.797.984 USD and the optimal weight of goods to be put into the knapsack is 414,1 tons, namely goods destined for Taiwan, India, South Africa, the United Arab Emirates, Switzerland, Hong Kong, Singapore and the United States. Whereas in the case of the manual Dynamic Programming Algorithm method, namely in case 1 (2017) with a total of 10 data, the decision was obtained that the goods put in the knapsack were goods destined for Taiwan, India, South Africa, the United Arab Emirates, Switzerland, Italy, Hong Kong, Singapore and the United States. The optimal profit value or profit earned is 2.641.776.900 USD with a weight of 402,7 tons. In case 2 (2018) with a total of 10 data, the decision was obtained that the goods put in the knapsack were goods destined for Taiwan, the United Arab Emirates, South Africa, Switzerland, Italy, Australia, India, Hong Kong and Singapore. The optimal profit value obtained is 1.781.768.100 USD with a weight of 353,9 tons. In case 3 (2019) with a total of 10 data, the decision was obtained that the goods put in the knapsack were goods destined for Taiwan, India, South Africa, the United Arab Emirates, Switzerland, Hong Kong, Singapore and the United States. The optimal profit value obtained is 1.884.718.200 USD with a weight of 414,1 tons. Based on the analysis performed, it can be concluded that to determine the optimal solution in solving the knapsack problem using the Dynamic Programming Algorithm produces a more optimal value compared to the Boudjellaba-Gningue-Shamakhai (BGS) Algorithm method.

Actions (login required)

View Item