Implementation of Branch and Bound Algorithm and Variable Reduction Algorithm in Production Profit Optimization

Authors

  • Hanny Puspha Jayanti UIN Sunan Kalijaga Yogyakarta
  • Muchammad Abrori

DOI:

https://doi.org/10.26555/jim.v11i1.28535

Keywords:

Branch and Bound Algorithm, Integer Linear Programming, Variable Reduction Algorithm

Abstract

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

2024-08-30

Issue

Section

Articles