A general iterative solver for unbalanced inconsistent transportation problems

• Autorzy: Carp D. , Popa C. , Serban C.

Identyfikatory

DOI

10.5604/08669546.1203199

• Języki publikacji: EN

Abstrakty

EN

The transportation problem, as a particular case of a linear programme, has probably the highest relative frequency with which appears in applications. At least in its classical formulation, it involves demands and supplies. When, for practical reasons, the total demand cannot satisfy the total supply, the problem becomes unbalanced and inconsistent, and must be reformulated as e.g. finding a least squares solution of an inconsistent system of linear inequalities. A general iterative solver for this class of problems has been proposed by S. P. Han in his 1980 original paper. The drawback of Han’s algorithm consists in the fact that it uses in each iteration the computation of the Moore-Penrose pseudoinverse numerical solution of a subsystem of the initial one, which for bigger dimensions can cause serious computational troubles. In order to overcome these difficulties we propose in this paper a general projection-based minimal norm solution approximant to be used within Han-type algorithms for approximating least squares solutions of inconsistent systems of linear inequalities. Numerical experiments and comparisons on some inconsistent transport model problems are presented.

Słowa kluczowe

EN

inconsistent linear inequalities; least squares solutions; projection-type algorithm; Kaczmarz Extended; transportation problem; simplex algorithm; Han’s algorithm

PL

problemy transportowe; algorytm simplex; algorytm Hana

• Wydawca: Warsaw University of Technology, Faculty of Transport
• Czasopismo: Archives of Transport
• Rocznik: 2016
• Tom: Vol. 37, iss. 1
• Strony: 7--13
• Opis fizyczny: Bibliogr. 10 poz., tab.

Twórcy

autor

Carp D.

• University Constanta Maritime University, Constanta, Romania

autor

Popa C.

• Ovidius University of Constanta, Faculty of Mathematics and Computer Science, Constanta, Romania

autor

Serban C.

• Ovidius University of Constanta, Faculty of Civil Engineering, Constanta, Romania

Bibliografia

• [1] CARP, D., POPA, C., SERBAN, C., 2014. Modified Han algorithm for maritime containers transportation problem, ROMAI J., 10(1), pp. 11-23.
• [2] CARP, D., POPA, C., SERBAN, C., 2015. Modified Han algorithm for inconsistent linear inequalities, Carpathian J. Math., 31(1), pp. 37- 44.
• [3] HAN, S. P., 1980. Least squares solution of linear inequalities, Tech. Rep. TR-2141, Mathematics Research Center, University of Wisconsin – Madison.
• [4] KOOPMANS T.C., BECKMANN M., 1957. Assignment problems and location of economic activities, Econometrica, 25(1), pp. 53-76
• [5] NICOLA A., POPA C., RUDE U. (2011), Projection algorithms with corrections, Journal of Applied Mathematics and Informatics, 29(3- 4), pp. 697-712.
• [6] POPA,, C., 1998. Extensions of block-projections methods with relaxation parameters to inconsistent and rank-defficient least-squares problems, B I T, 38(1), pp. 151-176.
• [7] POPA, C., 2010. Extended and constrained Diagonal Weighting Algorithm with applications to inverse problems in image reconstruction, Inverse Problems, 26(6), 17 p.
• [8] POPA, C., 2012. Projection algorithms - classical results and developments. Applications to image reconstruction, LAP Lambert Academic Publishing, Saarbrucken 2012.
• [9] POPA, C., CARP, D., SERBAN, C., 2013. Iterative solution of inconsistent systems of linear inequalities, Proceedings of Applied Mathematics and Mechanics (PAMM), 13, pp. 407-408
• [10] VANDERBEI, R.J., 2001. Linear programming. Foundations and extensions, Int. Series in Oper. Res. and Manag. Sciences, 37, Springer US.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.