Вычислительные тесты по декомпозиционному алгоритму…
7
Computational tests on the decomposition algorithm
for the transportation problem
© A.A. Gurchenkov
1
, A.P. Tizik
2
, E.V. Torchinskaya
3
1
Bauman Moscow State Technical University, Moscow, 105005, Russia
2
Dorodnicyn Computing Centre of RAS, Moscow, 119991, Russia
3
Moscow Institute of Physics and Technology (State University), Dolgoprudny,
Moscow Region, 141700, Russia
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.
Keywords:
transportation problem, decomposition, generalized suppliers and consumers.
REFERENCES
[1] Mironov A.A., Tsurkov V.I. Approximation and Decomposition by Extremal
Graphs.
Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki — Computa-
tional Mathematics and Mathematical Physics
, 1993, vol.. 33, no. 2,
pp. 34–39.
[2] Mironov A.A., Tsurkov V.I.
Zhurnal Vychislitel'noi Matematiki i Matematich-
eskoi 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.
