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

Nikolai K.  Krivulin; Joseph V. Romanovsky

Authors

Nikolai K. Krivulin
Joseph V. Romanovsky

Abstract

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

Downloads

Download data is not yet available.

References

1. Pandit S.N.N. A new matrix calculus // J. SIAM. 1961. Vol. 9, N4. 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, N1. P. 95-100. DOI: 10.2307/3007584

3. Giffler B. Scheduling general production systems using schedule algebra // Naval Res. Logist. Quart. 1963. Vol. 10, N1. P. 237-255. DOI: 10.1002/nav.3800100119

4. Hoffman A.J. On abstract dual linear programs // Naval Res. Logist. Quart. 1963. Vol. 10, N1. P. 369-373. DOI: 10.1002/nav.3800100131

5. Воробьев Н.Н. Экстремальная алгебра матриц // Докл. АН СССР. 1963. Т. 152, №1. С. 24-27.

6. Романовский И.В. Асимптотическое поведение процессов динамического программирования с непрерывным множеством состояний // Докл. АН СССР. 1964. T. 159, №6. С. 1224-1227.

7. Корбут А.А. Экстремальные пространства // Докл. АН СССР. 1965. Т. 164, №6. С. 1229-1231.

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

9. Golan J.S. Semirings and Affine Equations Over Them. In Ser. Mathematics and Its Applications. Vol. 556. New York: Springer, 2003. 256 p. DOI: 10.1007/978-94-017-0383-3

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

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

12. Krivulin N. Tropical optimization problems // Advances in Economics and Optimization. Economic Issues, Problems and Perspectives / ed. by L.A. Petrosyan, J.V. Romanovsky, D.W.-K. Yeung. New York: Nova Sci. Publ., 2014. P. 195-214.

13. 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

14. Krivulin N.K., Sorokin V.N. Solution of a tropical optimization problem with linear constraints // Vestnik St. Petersburg Univ. Math. 2015. Vol. 48, N4. P. 224-232. DOI: 10.3103/S1063454115040081

15. Krivulin N. Direct solution to constrained tropical optimization problems with application to project scheduling // Comput. Manag. Sci. 2017. Vol. 14, N1. P. 91-113. DOI: 10.1007/s10287-016-0259-0

16. Романовский И.В. Алгоритмы решения экстремальных задач. М.: Наука, 1977. 352 с.

17. Черников С.Н. Линейные неравенства. М.: Наука, 1968. 488 с.