Engineering Journal: Science and InnovationELECTRONIC SCIENCE AND ENGINEERING PUBLICATION
Certificate of Registration Media number Эл #ФС77-53688 of 17 April 2013. ISSN 2308-6033. DOI 10.18698/2308-6033
  • Русский
  • Английский
Article

Computational tests on the decomposition algorithm for the transportation problem

Published: 14.10.2014

Authors: Gurchenkov A.A., Tizik A.P., Torchinskaya E.V.

Published in issue: #5(29)/2014

DOI: 10.18698/2308-6033-2014-5-1293

Category: Information technology

The article presents numerical tests of iterative method for solving transportation problem based on successive recalculations of functional coefficient. Optimal solution is achieved in three iterations and degeneration is not involved. This solution matches those obtained by standard program using method of potentials. Standard optimization methods are used. Algorithm constructs a sequence of solutions for intermediate one-dimensional problems, which are not permissible for the original problem. Monotonous functional growth at pseudosolutions takes place. Formulas of solutions of intermediate two-dimensional problems with hooked variables are composed. Coefficients of functional are successively recalculated. Finally permissible solution is searched in a set of equations. If there is no such solution the problem of maximum flow with transportation limitations is solved. Corresponding indices pairs are formed by certain rule.


References
[1] Mironov A.A., Tsurkov V.I. Approximation and Decomposition by Extremal Graphs. Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki - Computational Mathematics and Mathematical Physics, 1993, vol.. 33, no. 2, pp. 34-39.
[2] Mironov A.A., Tsurkov V.I. Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki - Computational Mathematics and Mathematical Physics, 1995, vol. 35, no. 1, pp. 141-147.
[3] Mironov A.A., Tsurkov V.I. Izvestiya RAN.Teoriya i Sistemy Upravleniya - Proceedings of the Russian Academy of Sciences. Theory and Control Systems, 1998, no. 6, pp. 67-73.
[4] Mironov A.A., Tsurkov V.I. Transport-type Problems With a Criterion. Avtomatika i Telemekhanika - Automation and Remote Control, 1995, no. 12, pp. 109-118.
[5] Mironov A.A., Tsurkov V.I. Izvestiya RAN. Teoriya i sistemy upravleniya - Proceedings of the Russian Academy of Sciences. Theory and Control Systems, 1998, no. 6, pp. 89-96.
[6] Mironov A.A., Tsurkov V.I. Doklady RAN - RAS Reports, 1996, vol. 346, no. 2, pp. 342-347.
[7] Mironov A.A., Tsurkov V.I. Network Models With Fixed Parameters in Coupling Nodes. 2. Izvestiya RAN. Teoriya i Sistemy Upravleniya - Proceedings of the Russian Academy of Sciences. Theory and Control Systems, 1993, no. 6, pp. 3-14.
[8] Mironov A.A., Levkina T.A., Tsurkov V.I. Minimax Estimations of Expectates of Arc Weights in Integer Networks With Fixed Node Degrees. Applied and Computational Mathematics, 2009, vol. 8, no. 2, pp. 216-226.
[9] Cheburakhin I.F., Tsurkov V.I. On the Complexity of Realization of Symmetric Zhegalkin Polynomials. Applied and Computational Mathematics, 2010, vol. 9, no. 2, pp. 198-219.
[10] Averbakh I., Lebedev V., Tsurkov V. Nash Equilibria Solutions in The Competitive Salesmen Problem on a Network. Applied and Computational Mathematics, 2008, vol. 7, no. 1, pp. 54-65.
[11] Mironov A.A., Tsurkov V.I. Open Transportation Models With a Minimax Criterion. DokladyMathematics, 2001, vol. 64, no. 3, pp. 374-377.
[12] Mironov A.A., Tsurkov V.I. A Triplanar Transportation Problem with a Minimax Criterion. Doklady Mathematics, 1996, vol. 54, no. 3, pp. 972-975.
[13] Cheburakhin I.F., Tsurkov V.I. Mekhatronika, Avtomatizatsiya, Upravlenie - Mechatronics, Automation, Control, 2009, no 7, pp. 19-29.
[14] Cheburakhin I.F.,Tsurkov V.I. Mekhatronika, Avtomatizatsiya, Upravlenie - Mechatronics, Automation, Control, 2010, no. 9, pp. 7-13.
[15] Cheburakhin I.F., Tsurkov V.I. Mekhatronika, Avtomatizatsiya, Upravlenie - Mechatronics, Automation, Control, 2011, no. 3, pp. 27-34.
[16] Tsurkov V. Aggregation in a Branch Manufacturing Problem and its Extension. Proc. 13th IFAC Symp. Information Control Problems in Manufacturing, Moscow, 2009, pp. 310-312.
[17] Tizik A.P., Tsurkov V.I. Avtomatika i Telemekhanika - Automation and Remote Control, 2012, no. 1, pp. 148-158.
[18] Sokolov A.A., Tizik A.P., Tsurkov V.I. Izvestiya RAN. Teoriya i sistemy upravleniya - Proceedings of the Russian Academy of Sciences. Theory and Control Systems, 2013, no. 4, pp. 88-98.
[19] http://math.semestr.ru/transp/index.php