An exact iterative algorithm to solve a linear fractional programming problem

Document Type : Research Article

Authors

1 Department of Mathematical Engineering, Yildiz Technical University, Istanbul, Turkey.

2 Department of Business Administration, Yildiz Technical University, Istanbul, Turkey.

3 Department of Mathematics, Yildiz Technical University, Istanbul, Turkey.

10.24200/sci.2022.58352.5685

Abstract

The Linear Fractional Programming (LFP) problem that optimizes the ratio of two linear objective functions under linear constraints has a wide range of application areas. Based on the traditional definition of continuity, we developed an exact iterative algorithm that does not depend on big-M coecients. Removing the nonlinearity in the fractional objective function by converting the objective function into a linear form, an equivalent linear-iterative problem is obtained and a computationally efficient algorithm is proposed. We also analyze the unbounded and asymptotic solution case of the LFP.
To demonstrate the efficiency of the proposed method, illustrative numerical examples are provided for all solution cases. Also, we analyze the validity of our algorithm and compare our results with the existing algorithm from the literature by generating random large-scale test problems.

Keywords

Main Subjects

References

References
1. Chakraborty, M. and Gupta, S. "Fuzzy mathematical programming for multi objective linear fractional programming problem", Fuzzy Sets and Systems, 125(3), pp. 335-342 (2002). https://doi.org/10.1016/S0165-0114(01)00060-4
2. Schaible, S. "Bibliography in fractional programming", Zeitschrift fur Operations Research, 26, pp. 211-241 (1982). https://doi.org/10.1007/BF01917115
3. Schaible, S. "Fractional programming", Zeitschrift fur Operations-Research, 27, pp. 39-54 (1983). https://doi.org/10.1007/BF01916898
4. Schaible, S. "Fractional programming: Applications and algorithms", European Journal of Operational Research, 7(2), pp. 111-120 (1981). https://doi.org/10.1016/0377-2217(81)90272-1
5. Craven, B. "Fractional programming", Sigma Series in Applied Mathematics, Heldermann, Berlin, Germany, 4 (1988). 
6. Bajalinov, E.B. "Linear-fractional programming theory, methods, applications and software", Springer Science and Business Media, 84 (2013). https://doi.org/10.1007/978-1-4419-9174-4
7. Isbell, J. and Marlow, W. "Attrition games", Naval Research Logistics Quarterly, 3(1-2), pp. 71-94 (1956). https://doi.org/10.1002/nav.3800030108
8. Charnes, A. and Cooper, W.W. "Programming with linear fractional functionals", Naval Research Logistics Quarterly, 9(3-4), pp. 181-186 (1962). https://doi.org/10.1002/nav.3800090303
9. Bitran, G.R. and Novaes, A. "Linear programming with a fractional objective function", Operations Research, 21(1), pp. 22-29 (1973). https://doi.org/10.1287/opre.21.1.22
10. Bitran, G.R. and Magnanti, T.L. "Duality and sensitivity analysis for fractional programs", Operations Research, 24(4), pp. 675-699 (1976). https://doi.org/10.1287/opre.24.4.675
11. Swarup, K. "Letter to the editorLinear fractional functionals programming, Operations Research, 13(6), pp. 1029-1036 (1965). https://doi.org/10.1287/opre.13.6.1029
12. Singh, C. "Optimality conditions in fractional programming", Journal of Optimization Theory and Applications, 33(2), pp. 287-294 (1981). https://doi.org/10.1007/BF00935552
13. Bajalinov, E. "Adjusting an objective function to a given optimal solution in linear and linear-fractional programming", In: Constructing and Applying Objective Functions, pp. 233-244 (2002). https://doi.org/10.1007/978-3-642-56038-5
14. Tantawy, S. "A new procedure for solving linear fractional programming problems", Mathematical and Computer Modelling, 48(5-6), pp. 969-973 (2008). https://doi.org/10.1016/j.mcm.2007.12.007
15. Tantawy, S. "An iterative method for solving linear fraction programming problem with sensitivity analysis", Mathematical and Computational applications, 13(3), pp. 147-151 (2008). https://doi.org/10.3390/mca13030147
16. Effati, S. and Pakdaman, M. "Solving the intervalvalued linear fractional programming problem", American Journal of Computational Mathematics, 2(01), 17965 (2012). https://doi.org/10.4236/ajcm.2012.21006
17. Tantawy, S. "A new concept of duality for linear fractional programming problems", International Journal of Engineering and Innovative Technology, 3, pp. 147- 149 (2014). 
18. Simi, F.A. and Talukder, M.S. "A new approach for solving linear fractional programming problems with duality concept", Open Journal of Optimization, 6(1), 74095 (2017). https://doi.org/10.4236/ojop.2017.61001
19. Biswas, A., Verma, S., and Ojha, D. "Optimality and convexity theorems for linear fractional programming problem", International Journal of Computational and Applied Mathematics, 12(3), pp. 911-916 (2017). 
20. Fu, Q., Li, L., Li, M., et al. "A simulation-based linear fractional programming model for adaptable water allocation planning in the main stream of the Songhua River Basin, China", Water, 10(5), 627 (2018). https://doi.org/10.3390/w10050627
21. Ozkok, B.A. "An iterative algorithm to solve a linear fractional programming problem", Computers and Industrial Engineering, 140, 106234 (2020). https://doi.org/10.1016/j.cie.2019.10623
22. Das, S.K., Edalatpanah, S., and Mandal, T. "A new method for solving linear fractional programming problem with absolute value functions", International Journal of Operational Research, 36(4), pp. 455-466 (2019). https://doi.org/10.1504/IJOR.2019.104051
23. Mohammed, N.M. and Lomte, S.S. "Secure and efficient outsourcing of large scale linear fractional programming", In Computing in Engineering and Technology, Iyer, B., Deshpande, P.S., Sharma, S.C., and Shiurkar U. (Eds.), pp. 277-286, Springer, Singapore (2020). https://doi.org/10.1007/978-981-32-9515-5 26
24. Mohammed, N.M., Sultan, L.R., Hamoud, A.A., and Lomte, S.S. "Verifiable secure computation of linear fractional programming using certificate validation", International Journal of Power Electronics and Drive Systems, 11(1): 284, pp. 284-290 (2020). https://doi.org/10.11591/ijpeds.v11.i1.pp284-290
25. Mohammady, S. and Eslahchi, M. "Extension of Tikhonov regularization method using linear fractional programming", Journal of Computational and Applied Mathematics, 371, 112677 (2020). https://doi.org/10.1016/j.cam.2019.112677
26. Toloo, M. "An equivalent linear programming form of general linear fractional programming: A duality approach", Mathematics, 9(14), 1586 (2021). https://doi.org/10.3390/math9141586
Scientia Iranica
Volume 32, Issue 16
Transactions on Industrial Engineering
September and October 2025 Article ID:5685

Files

History

  • Receive Date: 03 June 2021
  • Revise Date: 31 January 2022
  • Accept Date: 29 August 2022

Share

How to cite

Statistics