Решение задачи тропической оптимизации с приложением к оптимальному планированию

Авторы

  • Николай Кимович Кривулин
  • Ульяна Львовна Баско

Аннотация

Рассматривается многомерная задача оптимизации, которая формулируется и решается в терминах тропической математики, изучающей теорию и приложения полуколец с идемпотентным сложением. Для решения задачи, целевая функция которой задается при помощи некоторой матрицы, используются методы и результаты идемпотентной алгебры и тропической оптимизации. Сначала строится точная нижняя оценка для целевой функции задачи, что позволяет определить минимальное значение целевой функции. Затем составляется и решается уравнение для целевой функции и ее минимального значения, откуда находится полное решение в виде множества всех собственных векторов матрицы задачи. В качестве приложения полученного результата приводится решение в явном виде задачи составления оптимального плана проекта, который состоит в выполнении некоторого набора работ при заданных ограничениях на время их начала и завершения. Критерий оптимальности плана определяется как минимум максимального разброса времени рабочего цикла по всем работам, которое задано как интервал между временем начала и завершения работы. Полученный аналитический результат расширяет и дополняет существующие алгоритмические численные решения задач оптимального планирования. Представлен иллюстративный пример применения этого результата к решению задачи планирования проекта, состоящего из трех работ.

Скачивания

Данные скачивания пока недоступны.

Библиографические ссылки

1. Pandit S.N.N. A new matrix calculus // J. SIAM. 1961. Vol. 9, N 4. P. 632-639. DOI: 10.1137/0109052

2. Cuninghame-Green R.A. Describing industrial processes with interference and approximating their steady-state behaviour // Oper. Res. Quart. 1962. Vol. 13, N 1. P. 95-100. DOI: 10.2307/3007584

3. Vorob’ev N.N. The extremal matrix algebra // Soviet Math. Dokl. 1963. Vol. 4, N 5. P. 1220-1223.

4. Romanovski˘ı I.V. Asymptotic behavior of dynamic programming processes with a continuous set of states // Soviet Math. Dokl. 1964. Vol. 5, N 6. P. 1684-1687.

5. Cuninghame-Green R.A. Minimax Algebra. In: Lecture Notes in Economics and Mathematical Systems. Vol. 166. Berlin: Springer, 1979. DOI: 10.1007/978-3-642-48708-8

6. Zimmermann U. Linear and Combinatorial Optimization in Ordered Algebraic Structures. In: Annals of Discrete Mathematics. Vol. 10. Amsterdam: Elsevier, 1981.

7. Маслов В.П., Колокольцов В.Н. Идемпотентный анализ и его применение в оптимальном управлении. М.: Физматлит, 1994.

8. Heidergott B., Olsder G. J., van der Woude J. Max Plus at Work. In: Princeton Series in Applied Mathematics. Princeton, NJ: Princeton Univ. Press, 2006.

9. Кривулин Н.К. Методы идемпотентной алгебры в задачах моделирования и анализа сложных систем. СПб.: Изд-во С.-Петерб. ун-та, 2009.

10. Butkoviˇc P. Max-linear Systems. In: Springer Monographs in Mathematics. London: Springer, 2010. DOI: 10.1007/978-1-84996-299-5

11. Clark W., Polakov W.N., Trabold F.W. The Gantt Chart. In: Ronald Manufacturing Management and Administration Series. New York: Ronald Press Company, 1922.

12. Kelley J. E. Critical-path planning and scheduling: mathematical basis // Oper. Res. 1961. Vol. 9, N 3. P. 296-320. DOI: 10.1287/opre.9.3.296

13. Malcolm D.G., Roseboom J.H., Clark C. E., Fazar W. Application of a technique for research and development program evaluation // Oper. Res. 1959. Vol. 7, N 5. P. 646-669. DOI: 10.1287/opre.7.5.646

14. Krivulin N. Extremal properties of tropical eigenvalues and solutions to tropical optimization problems // Linear Algebra Appl. 2015. Vol. 468. P. 211-232. DOI: 10.1016/j.laa.2014.06.044

15. Krivulin N. A multidimensional tropical Optimization problem with nonlinear objective function and linear constraints // Optimization. 2015. Vol. 64, N 5. P. 1107-1129. DOI: 10.1080/02331934.2013.840624

16. Krivulin N. Tropical optimization problems with application to project scheduling with minimum makespan // Ann. Oper. Res. 2017. Vol. 256, N 1. P. 75-92. DOI: 10.1007/s10479-015-1939-9

17. Krivulin N. Tropical Optimization problems in time-constrained project scheduling // Optimization. 2017. Vol. 66, N 2. P. 205-224. DOI: 10.1080/02331934.2016.1264946

18. Elsner L., van den Driessche P. Max-algebra and pairwise comparison matrices // Linear Algebra Appl. 2004. Vol. 385, N 1. P. 47-62. (03)00476-2 DOI: 10.1016/S0024-3795

19. Elsner L., van den Driessche P. Max-algebra and pairwise comparison matrices, II // Linear Algebra Appl. 2010. Vol. 432, N 4. P. 927-935. DOI: 10.1016/j.laa.2009.10.005

20. Krivulin N.K. Eigenvalues and eigenvectors of matrices in idempotent algebra // Vestnik St. Petersburg Univ.: Math. 2006. Vol. 39, N 2. P. 72-83.

21. Krivulin N. Complete algebraic solution of multidimensional optimization problems in tropical semifield // J. Log. Algebr. Methods Program. 2018. Vol. 99. P. 26-40. DOI: 10.1016/j.jlamp.2018.05.002

22. Demeulemeester E. L., Herroelen W. S. Project Scheduling. New York: Springer, 2002. DOI: 10.1007/b101924

23. Neumann K., Schwindt C., Zimmermann J. Project Scheduling with TimeWindows and Scarce Resources. 2nd ed. Berlin: Springer, 2003. DOI: 10.1007/978-3-540-24800-2

Загрузки

Опубликован

16.08.2020

Как цитировать

Кривулин, Н. К., & Баско, У. Л. (2020). Решение задачи тропической оптимизации с приложением к оптимальному планированию. Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия, 6(3), 440–451. извлечено от https://math-mech-astr-journal.spbu.ru/article/view/8400

Выпуск

Том 6 № 3 (2019)

Раздел

Математика

Лицензия

Статьи журнала «Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия» находятся в открытом доступе и распространяются в соответствии с условиями Лицензионного Договора с Санкт-Петербургским государственным университетом, который бесплатно предоставляет авторам неограниченное распространение и самостоятельное архивирование.

Наиболее читаемые статьи этого автора (авторов)