SOFTWARE ENGINEERING OF THE FLOW ALGORITHMS
Keywords:
transportation problem, transhipment problem, algorithms data structures, object-oriented programming, software engineeringAbstract
The authors consider the ways of the software engineering of the pivot procedures in the scheme of the primal simplex algorithm for flow problems, which enable to rearrange the redix tree within the linear time of the vortex of network number, considerably decrease the number of checks of the optimality condition. The technique of the software implementation of these procedures is given in the source text of the abstract class transport and classes Transshipment and Transportation which are destined for solving and post-organizational analysis of the transportation problems in the cross network and matrix definitions respectively.References
Dantzig, G. Application of the Simplex Method to a Transportation Problem / G. Dantzig // Activity Analysis of Production and Allocation. - 1951. - P. 196 - 218.
Glickman, S. Coding in Transportation Problem / S. Glickman, J. Jonson, L. Eselson // Naval Research Logistics Quar. - 1960. - V. 7, № 2. - P. 169.
Fulkerson, D. An Out-of-Kilter Method for Minimal-Cost Flow Problems / D. Fulkerson // SIAM J. of Applied Mathematics - 1961. - V. 9, № 1. - P. 1 - 18.
Форд, Л. Потоки в сетях / Л. Форд, Д. Фалкерсон. - М.: Мир, 1962. - 276 с.
Dantzig, G. Linear Programming and Extensions / G. Dantzig. - Princeton: University, 1963. - 215 p.
Гольштейн, Е.Г. Новые направления в линейном программировании / Е.Г. Гольштейн, Д.Б. Юдин. - М.: Сов. радио, 1966. - 524 с.
Jonson, J. Networks and Basic Solutions / J. Jonson // Operations. Res. - 1966. - V.14. - P. 619 - 623.
Glover, F. Implementation and Computational Comparisions of Primal, Dual and Primal-Dual Computer Codes for Minimum Cost Network Flow Problems/ F. Glover, D. Karney, D. Klingman // Networks. - 1974. - V. 4, № 3. - P. 191 - 212.
A Computational Study on start procedures basis change criteria, and solution algorithms for transportation problems / F. Glover, D. Karney, D. Klingman, A. Napier // Manage. Sci. - 1974. - Vol.20, № 5.- P. 793 - 813.
Bradley, G.H. Design and Implemetation of Large Scale Primal Transshipment Algorithms / G.H. Bradley, G.G. Brown, G.W. Graves // Manage. Sci. - 1977. - Vol.24, № 1. - P. 1 - 34.
Barr, R. Enhancements of Spanning Tree Labeling Procedures for Network 0ptimization / R. Barr, F. Glover , D. Klingman // INFOR. - 1979. - V. 17, № 1. - P. 16 - 34.
Ahrens, J.H. Primal Transportation and Transshipment Algorithms / J.H. Ahrens, G. Finke // Z. Oper. Res. - 1980. - V.24, № 1. - P. 1 - 32.
Armstrong, R. D. Implementation and Analisis of a Variant of Dual Method for the Capacitated transshipment Problem / R.D. Armstrong, D. Klingman, D. Whitman // European J. Oper. Res. - 1980. - V.4, № 6. - P. 403 - 420.
Панюков, А.В. Алгоритм локальной оптимизации для задачи размещения прямоугольных объектов с минимальной длиной связывающей их сети / А.В. Панюков // Изв. АН СССР. Техн. кибернетика. - 1981. - № 6. - C. 180 - 184.
Панюков, А.В. Метод решения возмущенной транспортной задачи на сети / А.В. Панюков // Методы и программы решения оптимизационных задач на графах и сетях. Часть 2: Теория, алгоритмы: тез. докл. П Всеc. совещания;. Улан-Удэ, август, 1982. - Новосибирск, 1982. - C. 113 - 114.
Гловер, Ф. Последние достижения в технике реализации сетевых потоковых алгоритмов / Ф. Гловер, Д. Клингман // Экономико-оптимизационные задачи большой размерности: труды сов.-американ. семинара. США, 1980. - М., 1983. - C. 180 - 209.
Панюков, А.В. Повышение эффективности прямых алгоритмов построения потока минимальной стоимости в насыщенной сети / А.В. Панюков // Системы программного обеспечения задач оптимального планирования: VШ Всес. симп: тез. докл. Нарва-Йыесуу, апрель, 1984. - М., 1984. - C. 153 - 154.
Йенсен, П. Потоковое программирование / П. Йенсен, Д. Барнес - М.: Радио и связь, 1984. - 391 с.
Galil, Z. An $O(n^2(m+nlog n)log n)$ min-cost flow algorithm / Z. Galil, E. Tardos // 27th Annu. Symp. Found. Comput. Sci., Toronto, Oct. 27 - 29, 1986. - P. 1 - 9.
Goldberg, A.V. Combinatorial algorithms for the generalized circulation problem / A.V. Goldberg, , S.A. Plotkin, E. Tardos // Math. Oper. Res. - 1991. - Vol.16, № 2. - P. 351 - 381.
Orlin, J. B. Polynomial dual network simplex algorithms / J.B. Orlin, S.A. Plotkin , E. Tardos // Math. Program. - 1993. Vol. 60A, № 3. P. 255 - 276.
Panyukov, A.V. The Study of Basis Tree for Primal Transshipment Algorithms / A.V. Panyukov // CO94, Amsterdam, the Netherlands, April 5 - 8, 1994. Program&Abstracts.
Kleinschmidt, P. A Strongly Polynomial Algorithm for the Transportation Problem / P. Kleinschmidt, H. Schannath // Mathematical Programming. - 1995. - Vol. 68, № 1. - P. 1 - 13.
Панюков, А.В. Упорядоченное изучение базисного дерева в прямых алгоритмах для транспортной задачи / А.В. Панюков // Международная Сибирская конференция по исследованию операций: материалы конф. - Новосибирск, 1998. - С. 44.
Панюков, А.В. Задача размещения прямоугольных объектов с минимальной стоимостью связывающей сети / А.В. Панюков // Дискретный анализ и исследование операций. Серия 2. - Том 8, № 1. - 2001. - С. 70 - 87.
Панюков, А.В. Способ генерации должностных инструкций и положений о подразделениях // А.В. Панюков, В.А. Телегин // III Всероссийская конференция 'Проблемы оптимизации и экономические приложения': материалы конф. (Омск, 11 - 15 июля 2006 г.) / Омский филиал Ин-та математики им. С.Л. Соболева СО РАН. - Омск, 2006. - С. 185.
