Техника программной реализации потоковых алгоритмов

Рассмотрены способы реализации ведущего преобразования в схеме симплекс-алгоритма для задач транспортного типа, позволяющие осуществлять перестройку базисного дерева за время линейное от числа вершин сети, существенно сократив при этом число проверок условия оптимальности. Техника программной реализации указанных процедур проиллюстрирована в исходном тексте абстрактного класса t transport и классов t Transshipment и t Transportation, предназначенных для решения и постоптимизационного анализа транспортных задач соответственно в сетевой и матричной постановках.

Ключевые слова

транспортная задача, задача об оптимальном потоке, алгоритмы. структуры данных, объектно-ориентированное программирование, техника программной реализации

Литература

1. Dantzig, G. Application of the Simplex Method to a Transportation Problem / G. Dantzig // Activity Analysis of Production and Allocation. - 1951. - P. 196 - 218.
2. Glickman, S. Coding in Transportation Problem / S. Glickman, J. Jonson, L. Eselson // Naval Research Logistics Quar. - 1960. - V. 7, № 2. - P. 169.
3. 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.
4. Форд, Л. Потоки в сетях / Л. Форд, Д. Фалкерсон. - М.: Мир, 1962. - 276 с.
5. Dantzig, G. Linear Programming and Extensions / G. Dantzig. - Princeton: University, 1963. - 215 p.
6. Гольштейн, Е.Г. Новые направления в линейном программировании / Е.Г. Гольштейн, Д.Б. Юдин. - М.: Сов. радио, 1966. - 524 с.
7. Jonson, J. Networks and Basic Solutions / J. Jonson // Operations. Res. - 1966. - V.14. - P. 619 - 623.
8. 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.
9. 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.
10. 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.
11. 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.
12. Ahrens, J.H. Primal Transportation and Transshipment Algorithms / J.H. Ahrens, G. Finke // Z. Oper. Res. - 1980. - V.24, № 1. - P. 1 - 32.
13. 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.
14. Панюков, А.В. Алгоритм локальной оптимизации для задачи размещения прямоугольных объектов с минимальной длиной связывающей их сети / А.В. Панюков // Изв. АН СССР. Техн. кибернетика. - 1981. - № 6. - C. 180 - 184.
15. Панюков, А.В. Метод решения возмущенной транспортной задачи на сети / А.В. Панюков // Методы и программы решения оптимизационных задач на графах и сетях. Часть 2: Теория, алгоритмы: тез. докл. П Всеc. совещания;. Улан-Удэ, август, 1982. - Новосибирск, 1982. - C. 113 - 114.
16. Гловер, Ф. Последние достижения в технике реализации сетевых потоковых алгоритмов / Ф. Гловер, Д. Клингман // Экономико-оптимизационные задачи большой размерности: труды сов.-американ. семинара. США, 1980. - М., 1983. - C. 180 - 209.
17. Панюков, А.В. Повышение эффективности прямых алгоритмов построения потока минимальной стоимости в насыщенной сети / А.В. Панюков // Системы программного обеспечения задач оптимального планирования: VШ Всес. симп: тез. докл. Нарва-Йыесуу, апрель, 1984. - М., 1984. - C. 153 - 154.
18. Йенсен, П. Потоковое программирование / П. Йенсен, Д. Барнес - М.: Радио и связь, 1984. - 391 с.
19. 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.
20. 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.
21. 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.
22. 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.
23. Kleinschmidt, P. A Strongly Polynomial Algorithm for the Transportation Problem / P. Kleinschmidt, H. Schannath // Mathematical Programming. - 1995. - Vol. 68, № 1. - P. 1 - 13.
24. Панюков, А.В. Упорядоченное изучение базисного дерева в прямых алгоритмах для транспортной задачи / А.В. Панюков // Международная Сибирская конференция по исследованию операций: материалы конф. - Новосибирск, 1998. - С. 44.
25. Панюков, А.В. Задача размещения прямоугольных объектов с минимальной стоимостью связывающей сети / А.В. Панюков // Дискретный анализ и исследование операций. Серия 2. - Том 8, № 1. - 2001. - С. 70 - 87.
26. Панюков, А.В. Способ генерации должностных инструкций и положений о подразделениях // А.В. Панюков, В.А. Телегин // III Всероссийская конференция 'Проблемы оптимизации и экономические приложения': материалы конф. (Омск, 11 - 15 июля 2006 г.) / Омский филиал Ин-та математики им. С.Л. Соболева СО РАН. - Омск, 2006. - С. 185.