Open Access
Research Article
A systematic weighted-Hungarian-algorithm for optimization and postoptimal analysis of transportation problem
*Lin Chi-JenCorresponding authorielinchijen@gmail.comDepartment of Industrial Engineering and ManagementMinth University of Science and TechnologyHsinchu, Taiwan (R.O.C.)View full profile → , Lin Wan-Tingtc10031520@gmail.comDepartment of Business ManagementNational Taipei University of TechnologyTaipei, Taiwan (R.O.C.)View full profile →
* Corresponding author · click or hover a name for details
- Received:
- 31 Jul 2021
- Accepted:
- 31 Jan 2022
- Published Online:
- 10 Aug 2023
- Article type:
- Research Article
- Language:
- EN
- Article no.:
- JSMS-936
- Pages:
- 843–866
Abstract
This paper first proposes an easy algorithm for optimizing the transportation problem. Then, optimization procedures of the algorithm are applied for sensitivity analysis and the parametric analysis. The efficient algorithm can be proceeded systematically and smoothly. Some numerical examples are given to demonstrate these procedures. The attractive features of the new algorithms include: (1) The algorithm for solving the optimal solution of the transportation problem is an easy weighted Hungarian algorithm that can be applied to transportation problem and assignment problem; (2) The algorithm conquer the obstacles, e.g. cycling and stalling etc., caused by degeneracy; (3) The algorithm is capable of solving the large scale transportation problem; (4) The algorithm is easily expended to identify the Type I, Type II and Type III sensitivity range perturbing one cost coefficient; (5) The algorithm can reoptimize by using the original optimal table when variation exceeding sensitivity range, needless to resolve from scratch; (6)The algorithm can perform the parametric analysis and determine the optimal value function perturbing one or multiple cost coefficients.
Keywords
Subject Classifications
90C08
References
[1]A. G. Hadigheh & T. Terlaky (2006). Sensitivity analysis in linear optimization: invariant support set intervals. European Journal of Operational Research, 169, 1158-1175.
[2]A. K. Das, Deepmala & R. Jana (2020). Some aspects on solving transportation problem. Yugoslav Journal of Operations Research, 30(1), 45-57.
[3]F. L. Hitchcock (1941). The distribution of a product from several sources to numerous localities. Journal of Mathematics and Physics, 20, 224-230.
[4]F. S. Hillier & G. J. Lieberman (2015). Introduction to Operations Research (10th ed.). McGraw-Hill (Chapter 8).
[5]G. Hadley (1965). Linear Programming (1st ed.). Addison Wesley (Chapter 10).
[6]J. I. Ping & K. F. Chu (2002). A dual matrix approach to the transportation problem. Asia-Pacific Journal of Operational Research, 19, 35-45.
[7]J. Sadeghi (2018). A method for solving the transportation problem. Journal of Statistics & Management Systems, 21(5), 817-837.
[8]Lin Chi-Jen (2010). Computing shadow prices/costs of degenerate LP problems with reduced simplex tables. Expert Systems with Applications, 37, 5848-5855.
[9]L. R. Ford & D. R. Fulkerson (1957). A simple algorithm for finding maximal network flows and an application to the Hitchcock problem. Canadian Journal of Mathematics, 9(2), 210-218.
[10] M. Kang-Ting, Lin Chi-Jen & W. Ue-Pyng (2013). Type II sensitivity analysis of cost coefficients in the degenerate transportation problem. European Journal of Operational Research, 227, 293-300.
[11] M. S. Bazaraa, J. J. Jarvis & H. O. Sherali (2010). Linear programming and network flowers (4th ed.). Wiley-Interscience (Chapter 10).
[12] P. S. Dwyer (1966). The direct solution of the transportation problem with reduced matrices. Management Science, 13(1), 77-96.
[13] P. Rathi, S. Rathi & K. Gupta (2020). An optimization approach for transportation problem of transplant organ using self-adaptive bear hibernation algorithm, Journal of Information and Optimization Sciences, 41(2), 567-576.
[14] R. Bharath (1982). The Hesse-Woolsey-Stern algorithm for the transportation problem: an explication. Interfaces, 12(4), 67-68.
[15] R. R. K. Sharma & K. D. Sharma (2000). A new dual based procedure for the transportation problem. European Journal of Operational Research, 122, 611-624.
[16] S. Haddadi & O. Slimanl (2012). The transportation problem revisited - preprocessing before using the primal-dual algorithm. Journal of the Operational Research Society, 63, 1006-1009.
[17] S. M. Stefanov (2019). Characterization of the optimal solution of the convex generalized nonlinear transportation problem. Journal of Interdisciplinary Mathematics, 22(5), 745-756.
[18] V. Adlakha & H. Arsham (1998). Managing cost uncertainties in transportation and assignment problem. Journal of Applied Mathematics and Decision Science, 2(1), 6-104.
Views: 260Downloads: 68Citations: 3
