Laporkan Masalah

Penyelesaian masalah integer knapsack dengan konstrain minmax menggunakan dynamic programming

RAHAJOE, Rr. Ani Dijah, Drs. Edi Winarko, M.Sc., Ph.D

2010 | Tesis | S2 Ilmu Komputer

Integer knapsack merupakan permasalahan mencari optimalitas dari pemilihan benda-benda yang akan dimasukkan ke dalam suatu wadah dengan keterbatasan ruang dan daya tampung. Benda-benda yang dimasukkan merupakan benda yang utuh dan mempunyai berat, harga atau nilai. Pada permasalahan sistem pemuatan barang kedalam kontainer, optimalitas pemilihan benda-benda atau barang-barang yang akan dikirim meminimalkan total berat pada saat batasan minimal kapasitas atau volume terpenuhi tanpa melebihi kapasitas maksimal kontainer yang telah ditentukan. Jenis-jenis knapsack yang telah dibahas selama ini hanya menggunakan batasan memaksimalkan dengan tidak melebihi kapasitas yang ditentukan sehingga tidak dapat diterapkan pada permasalahan tersebut. Permasalahan lainnya pada pemilihan komposisi sayuran, buah atau makanan dengan menentukan nilai total minimum kolesterol dimana total kalorinya mempunyai batasan minimal tanpa melebihi batas maksimal kalori yang telah ditentukan. Penelitian ini bertujuan untuk mengembangkan algoritma dynamic programming untuk menyelesaikan integer knapsack dengan konstrain minimalmaksimal (minmax). Hasil penelitian menunjukkan bahwa penerapan integer knapsack dengan konstrain min-max ini digunakan untuk menghasilkan solusi optimal pada permasalahan pemilihan komposisi makanan dan pada permasalahan sistem pemuatan barang kedalam kontainer untuk mengoptimalkan ruang kontainer yang tersedia dibandingkan dengan hasil pemuatan barang oleh PT DFI.

Integer knapsack is a problem which is looking for the optimality of choosing goods that will enter in to a container with limited space and capacity. The goods entered to are the whole things and having weight, cost or level. In stuffing commodity system problem into container, the goods choosing optimality or the goods which will be sent minimize the total weight at capacity minimum constraint or volume fulfilled without over allocation container capacity. The kinds of knapsack have been discussed recently just using maximize limitation without exceeding the maximal capacity of such container, so that cannot be applied in those problems. The other problem is in choosing vegetables composition, fruits or foods by determining minimum total quality of cholesterol that have minimum constraint of calorie total without exceeding the maximum constraint of allocation calorie. The research objective is to develop dynamic programming algorithm for for for minimum-maximum constraint of integer knapsack solution. The research results show that the application of integer knapsack with the minimummaximum constraint is used to produce the optimal solution in choosing problem of food composition and in problem of commodity stuffing system into container to optimize such container space compared with commodity stuffing by DFI company.

Kata Kunci : Integer knapsock,Minimax,Dynamic programming


    Tidak tersedia file untuk ditampilkan ke publik.