OPTIMASI MASALAH KNAPSACK 0-1 DENGAN MENGGUNAKAN PEMROGRAMAN DINAMIS

Zahra Zharifah Anwar, Program Studi Matematika, Universitas Negeri Yogyakarta, Indonesia
Caturiyati Caturiyati, Program Studi Matematika, Universitas Negeri Yogyakarta, Indonesia

 10.21831/jktm.v11i1.22844

Abstract


Optimasi merupakan aspek yang mendasar dalam pengambilan keputusan, di mana tujuannya adalah untuk mengidentifikasi solusi optimal dari sekumpulan alternatif yang kompleks. Contoh masalah sehari-hari yang memerlukan optimasi adalah masalah pemuatan barang (masalah knapsack), yang berdampak langsung pada efisiensi operasi logistik dan pada akhirnya berpengaruh pada biaya operasional. Salah satu variasi utama dalam masalah knapsack adalah masalah knapsack 0-1. Setiap item pada masalah knapsack 0-1 memiliki pilihan untuk dimuat ke dalam knapsack atau tidak. Masalah knapsack 0-1 merupakan masalah optimasi kombinatorial yang paling banyak dipelajari. Sebagai masalah yang tergolong NP-hard, masalah knapsack 0-1 memiliki tingkat kerumitan yang tinggi. Salah satu algoritma penyelesaian masalah knapsack 0-1 adalah pemrograman dinamis.


Full Text:

PDF

References


Angelelli, E., Mansini, R., & Grazia Speranza, M. (2010). Kernel search: A general heuristic for the multi-dimensional knapsack problem. Computers and Operations Research, 37(11), 2017–2026. https://doi.org/10.1016/j.cor.2010.02.002

Bellman, R. (1960). Sequential Machines, Ambiguity, and Dynamic Programming. Journal of the ACM, 7(1), 24–28. https://doi.org/10.1145/321008.321011

Cattaruzza, D., Absi, N., Feillet, D., & González-Feliu, J. (2017). Vehicle routing problems for city logistics. EURO Journal on Transportation and Logistics, 6(1), 51–79. https://doi.org/10.1007/s13676-014-0074-0

Cook, W. J., Lovász, L., & Vygen, J. (2009). Research trends in combinatorial optimization: Bonn 2008. In Research Trends in Combinatorial Optimization: Bonn 2008. Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-540-76796-1

Dantzig, G. B. (1957). Discrete-Variable Extremum Problems. Operations Research, 5(2), 266–288. https://doi.org/10.1287/opre.5.2.266

Della Croce, F., Salassa, F., & Scatamacchia, R. (2017). An exact approach for the 0–1 knapsack problem with setups. Computers & Operations Research, 80, 61–67. https://doi.org/10.1016/j.cor.2016.11.015

Dreyfus, S. (2002). Richard Bellman on the Birth of Dynamic Programming. Operations Research, 50(1), 48–51. https://doi.org/10.1287/opre.50.1.48.17791

Eilon, S., & Christofides, N. (1971). The Loading Problem. Management Science, 17(5), 259–268. https://doi.org/10.1287/mnsc.17.5.259

Jalali Varnamkhasti, M. (2012). Overview of the Algorithms for Solving the Multidimensional Knapsack Problems. In Advanced Studies in Biology (Vol. 4, Issue 1).

Kellerer, H., Pferschy, U., & Pisinger, D. (2004). Knapsack Problems. Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-540-24777-7

Martello, S., & Toth, P. (1990). Knapsack Problem Algorithms and Computer Implementations. John Wiley & Sons.

Pan, X., & Zhang, T. (2018). Comparison and Analysis of Algorithms for the 0/1 Knapsack Problem. Journal of Physics: Conference Series, 1069(1). https://doi.org/10.1088/1742-6596/1069/1/012024

Pisinger, D. (1999). An exact algorithm for large multiple knapsack problems. European Journal of Operational Research, 114(3), 528–541. https://doi.org/10.1016/S0377-2217(98)00120-9

Scheithauer, G. (2018). Knapsack problems. In International Series in Operations Research and Management Science (Vol. 263, pp. 19–45). Springer New York LLC. https://doi.org/10.1007/978-3-319-64403-5_2

Soukaina, L., Mohamed, N., Hassan, E. A., & Boujemâa, A. (2018, May 2). A hybrid genetic algorithm for solving 0/1 knapsack problem. ACM International Conference Proceeding Series. https://doi.org/10.1145/3230905.3230907

Taha, H. A. (2007). Operation Research: An Introduction. New Jersey : Pearson Education Inc., 2007.

Vanderbei, R. J. (2020). Linear Programming (Vol. 285). Springer International Publishing. https://doi.org/10.1007/978-3-030-39415-8

Zhang, L., & Zhang, Y. (1999). Approximation for knapsack problems with multiple constraints. Journal of Computer Science and Technology, 14(4), 289–297. https://doi.org/10.1007/BF02948730

Zhou, Y., Shi, Y., Wei, Y., Luo, Q., & Tang, Z. (2023). Nature-inspired algorithms for 0-1 knapsack problem: A survey. Neurocomputing, 554. https://doi.org/10.1016/j.neucom.2023.126630




DOI: https://doi.org/10.21831/jktm.v11i1.22844

Refbacks

  • There are currently no refbacks.


 

Online ISSN (e-ISSN): 3031-1152

Creative Commons LicenseJurnal Kajian dan Terapan Matematika by https://journal.student.uny.ac.id/index.php/jktm/index is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
 
View My Stats