Implementation of Branch and Bound Algorithm and Variable Reduction Algorithm in Production Profit Optimization
DOI:
https://doi.org/10.26555/jim.v11i1.28535Keywords:
Branch and Bound Algorithm, Integer Linear Programming, Variable Reduction AlgorithmAbstract
Linear Programming (LP) cannot answer production problems that require decision variables to be integers. For this reason, Integer Linear Programming (ILP) exists as a special case of LP where the decision variables are integers. This research is intended to determine the difference in output values and the number of iterations used in the Branch and Bound Algorithm and Variable Reduction to solve the problem of maximizing production profits. The Branch and Bound algorithm divides the problem into sub-problems that lead to a solution by forming a search tree structure and applying restrictions to achieve an optimal solution. Meanwhile, the Variable Reduction Algorithm involves moving the decision variables from the left side to the right side of the constraint function. This study uses data from the Rembang Dairy Industry, with the problem of wanting to maximize production profits. Using Maple's assistance, the settlement using the Branch and Bound Algorithm and Variable Reduction yields the same profit, which is IDR 14,786,548. However, the calculation process using the Variable Reduction Algorithm requires more iterations than the Branch and Bound Algorithm.References
Meflinda, Astuti, and Mahyarni, Operations Research (Riset Operasi). Riau: UNRI PRESS, 2011.
Siswanto, Operation Research, Jilid 1. Jakarta: Erlangga, 2007.
S. Mulyono, Operations Research. Jakarta: Fakultas Ekonomi Universitas Indonesia, 1991.
S. S. Supatimah, Farida, and S. Andriani, “Optimasi Keuntungan dengan Metode Branch and Bound,” AKSIOMA J. Mat. dan Pendidik. Mat., vol. 10, no. 1, pp. 13–23, 2019. Available: http://surl.li/fgxeg
P. Pandian and M. Jayalakshmi, “A New Approach For Solving A Class Of Pure Integer Linear Programming Problems,” Int. J. Adv. Eng. Technol., vol. III, no. I, pp. 248–251, 2012. Available: http://surl.li/fgxdt
V. R. Parmono, R. Kristiawan, and H. A. Hutahaean, Riset Operasi, Pertama. Jakarta: Universitas Terbuka, 2007.
L. V. Nuranggraini, A. Pradjaningsih, and A. Riski, “Optimasi Produksi Susu Dengan Algoritma Affine Scaling (Studi Kasus Pada Industri Susu Rembangan Jember),” Pros. Semin. Nas. Integr. Mat. dan Nilai Islam., vol. 4, no. 1, pp. 13–18, 2021. Available: http://surl.li/fgxcw
Downloads
Published
Issue
Section
License
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
This work is licensed under a Creative Commons Attribution-ShareAlike 2.0 Generic License.