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

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

Автор: Панюков А.В., Телегин В.А.

Журнал: Вестник Южно-Уральского государственного университета. Серия: Математическое моделирование и программирование @vestnik-susu-mmp

Статья в выпуске: 27 (127), 2008 года.

Бесплатный доступ

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

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

Короткий адрес: https://sciup.org/147159058

IDR: 147159058

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

  • 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. I960. Vol. 7, N 2. P. 169.
  • Fulkerson D. An Out-of-Kilter Method for Minimal-Cost Flow Problems/D. Fulkerson//SIAM J. of Applied Mathematics. 1961. Vol. 9, N 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. Vol. 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. Vol. 4, N 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, N 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, N 1. P. 1-34.
  • Barr R. Enhancements of Spanning Tree Labeling Procedures for Network Optimization/R. Barr, F. Glover, D. Klingman//INFOR. 1979. Vol. 17, N 1. P. 16-34.
  • Ahrens J.H. Primal Transportation and Transshipment Algorithms/J.H. Ahrens, G. Finke//Z. Oper. Res. 1980. Vol. 24, N 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. Vol. 4, N 6. P. 403-420.
  • Панюков А.В. Алгоритм локальной оптимизации для задачи размещения прямоугольных объектов с минимальной длиной связывающей их сети/А.В. Панюков//Изв. АН СССР. Техн. кибернетика. 1981. № 6. С. 180-184.
  • Панюков А.В. Метод решения возмущенной транспортной задачи на сети/А.В. Панюков//Методы и программы решения оптимизационных задач на графах и сетях. Часть 2: Теория, алгоритмы: тез. докл. II Всес. совещания;. Улан-Удэ, август, 1982. Новосибирск, 1982. С. 113-114.
  • Гловер Ф. Последние достижения в технике реализации сетевых потоковых алгоритмов/Ф. Гловер, Д. Клингман//Экономико-оптимизационные задачи большой размерности: труды сов. американ. семинара. США, 1980. М., 1983. С. 180-209.
  • Панюков А.В. Повышение эффективности прямых алгоритмов построения потока минимальной стоимости в насыщенной сети/А.В. Панюков//Системы программного обеспечения задач оптимального планирования: VDI Всес. симп: тез. докл. Нарва-Йыесуу, апрель, 1984. М., 1984. С. 153-154.
  • Йенсен П. Потоковое программирование/П. Йенсен, Д. Барнес. М.: Радио и связь, 1984. 391 с.
  • Galil Z. An 0(n2(m + пlogn) 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, N 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//C094, 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, N 1. P. 1-13.
  • Панюков А.В. Упорядоченное изучение базисного дерева в прямых алгоритмах для транспортной задачи/А.В. Панюков//Международная Сибирская конференция по исследованию операций: материалы конф. Новосибирск, 1998. С. 44.
  • Панюков А.В. Задача размещения прямоугольных объектов с минимальной стоимостью связывающей сети/А.В. Панюков//Дискретный анализ и исследование операций. Сер. 2. Т. 8, № 1. 2001. С. 70-87.
  • Панюков А.В. Способ генерации должностных инструкций и положений о подразделениях // А.В. Панюков, В.А. Телегин // III Всероссийская конференция «Проблемы оптимизации и экономические приложения: »: материалы конф. (Омск, 11-15 июля 2006 г.) / Омский филиал Ин-та математики им. С.Л. Соболева СО РАН. Омск, 2006. С. 185.
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp