Problem plecakowy - porównanie algorytmów rozwiązujących binarne zagadnienie plecakowe

Abstract

Opracowanie dotyczy binarnego zagadnienia plecakowego. Autorzy przedstawiają własny komputerowy system eksperymentowania, będący programową implementacją dwóch algorytmów służących do jego rozwiązywania. Opisane są także przykładowe badania wpływu parametrów problemu na jakość rozwiązania oraz czas jego rozwiązywania.
Autorzy: Karol GĘGA, Marcin JAŚKóW

1. WPROWADZENIE

Procedury załadunkowe stanowią niezbędną część każdego procesu transportowego, czy to na wielką skalę – w przemyśle, gospodarce, czy na skalę mniejszą np. pakowanie plecaka na wycieczkę. Zagadnienia załadunkowe [4],[5], zwane problemami plecakowymi (ang. KP – knapsack problems), zajmują się właśnie tymi procedurami: pozwalają optymalnie obliczyć ilości towaru, przedmiotów, minimalizując koszty transportu lub maksymalizując zyski. W poniższej pracy zajmujemy się binarnym zagadnieniem plecakowym (0-1 KP). Dany jest zbiór n przedmiotów, z których każdy ma określoną objętość oraz zysk z jego zabrania. Należy tak wybrać przedmioty, aby zmieściły się do plecaka, a zysk był jak największy. Używając symboli matematycznych problem można sformułować następująco: Dla danych: b – pojemność plecaka, a¬j – objętość j-tego przedmiotu, cj – zysk z zabrania j-tego przedmiotu, n – ilość przedmiotów należy przyporządkować wartości zmiennych decyzyjnym: