Решение минимаксной задачи размещения в трехмерном пространстве с прямоугольной метрикой
Аннотация
Рассматривается минимаксная задача размещения точечного объекта в трехмерном пространстве с прямоугольной метрикой ($l_1$- метрикой) и предлагается ее прямое аналитическое решение при помощи методов тропической (идемпотентной) математики. Сначала задача записывается в терминах тропической математики как задача тропической оптимизации, вводится параметр для обозначения минимума целевой функции и задача сводится к решению параметризованной системы неравенств. Эта система решается относительно одной из переменных, а условия существования решений используются для нахождения оптимальных значений второй переменной с помощью вспомогательной задачи оптимизации. Затем вспомогательная задача решается аналогичным образом и находится значение третьей переменной. Полученное общее решение преобразуется в набор прямых решений, записанных в компактной форме для различных случаев соотношений между исходными параметрами задачи.
Литература
Sule D. R. Logistics of Facility Location and Allocation / New York: Marcel Dekker, 2001.
Farahani R. Z., Hekmatfar M. Facility Location / Contributions to Management Science. Heidelberg: Physica-Verlag, 2009.
Eiselt H. A., Marianov V. Foundations of Location Analysis / New York: Springer, 2011. Vol. 155 of International Series in Operations Research and Management Science.
Krivulin N. Using tropical optimization to solve constrained minimax single-facility location problems with rectilinear distance // Computational Management Science, 2017. Vol. 1, № 4. P. 493–518.
Francis R. L. A geometrical solution procedure for a rectilinear distance minimax location problem // AIIE Transactions, 1972. Vol. 4. № 4. P. 328–332.
Hansen P., Peeters D., Thisse J. F. Constrained location and the Weber-Rawls problem // North-Holland Mathematics Studies, 1981. Vol. 59. P. 147–166.
Zabudskii G. G. A minimax planar location problem with forbidden zones: its solution algorithm // Automation and Remote Control, 2004. Vol. 65. № 2. P. 241–247.
Nobakhtian S., Dehkordi A. R. A fast algorithm for the rectilinear distance location problem // Mathematical Methods of Operations Research, 2018. Vol. 87. № 1. P. 1–18.
Cuninghame-Green R. A. Minimax algebra / Berlin: Springer-Verlag, 1979.
Baccelli F., Cohen G., Olsder G. J., Quadrat J. P. Synchronization and Linearity. Wiley Series in Probability and Statistics / Chichester: Wiley, 1993.
Маслов В. П., Колокольцов В. Н. Идемпотентный анализ и его применение в оптимальном управлении / М.: Физматлит, 1994.
Cuninghame-Green R. A. Minimax algebra and applications // Advances in Imaging and Electron Physics, Vol. 90 / Ed. by P. W. Hawkes. San Diego: Academic Press, 1994. P. 1–121.
Golan J. S. Semirings and Affine Equations Over Them / New York: Springer, 2003. Vol. 556 of Mathematics and Its Applications.
Heidergott B, Olsder G. J., van der Woude J. Max Plus at Work / Princeton Series in Applied Mathematics. Princeton: Princeton Univ. Press, 2006.
McEneaney W. M. Max-Plus Methods for Nonlinear Control and Estimation / Systems and Control: Foundations and Applications. Boston: Birkhauser, 2006.
Itenberg I., Mikhalkin G., Shustin E. I. Tropical Algebraic Geometry / Basel: Birkhauser, 2007. Vol. 35 of Oberwolfach Seminars. doi: 10.1007/978-3-7643-8310-7.
Gondran M., Minoux M. Graphs, Dioids and Semirings / New York: Springer, 2008. Vol. 41 of Operations Research/ Computer Science Interfaces.
Кривулин Н. К. Методы идемпотентной алгебры в задачах моделирования и анализа сложных систем / СПб.: Издательство Санкт-Петербургского государственного университета, 2009. 255 с.
Butkovic P. Max-linear Systems. Springer Monographs in Mathematics / London: Springer, 2010.
Кривулин Н. К., Агеев В. А., Гладких И. В. Применение методов тропической математики для оценки альтернатив на основе парных сравнений // Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления, 2017. № 1. С. 27–41.
Krivulin N. K. Tropical optimization problems in time-constrained project scheduling // Optimization, 2017. Vol. 66. № 2. P. 205–224.
Krivulin N. K. An extremal property of the eigenvalue of irreducible matrices in idempotent algebra and solution of the Rawls location problem // Vestnik St. Petersburg Univ. Math, 2011. Vol. 44. № 4. P. 272–281.
Krivulin N. K. A new algebraic solution to multidimensional minimax location problems with Chebyshev distance // WSEAS Transactions on Mathematics, 2012. Vol. 11. № 7. P. 605–614.
Krivulin N. K. Complete solution of a constrained tropical optimization problem with application to location analysis // Relational and Algebraic Methods in Computer Science / Cham: Springer, 2014. Vol. 8428 of Lecture Notes in Computer Science. P. 362–378.
Krivulin N. K., Plotnikov P. V. On an algebraic solution of the Rawls location problem in the plane with rectilinear metric // Vestnik St. Petersburg University: Mathematics, 2015. Vol. 48. № 2. P. 75—81.
Krivulin N.K., Plotnikov P.V. Using tropical optimization to solve minimax location problems with a rectilinear metric on the line // Vestnik St. Petersburg University: Mathematics, 2016. Vol. 49. № 4. P. 340–349.
Krivulin N. A multidimensional tropical optimization problem with nonlinear objective function and linear constraints // Optimization, 2015. Vol. 64. № 5. P. 1107–1129.
Krivulin N. Extremal properties of tropical eigenvalues and solutions to tropical optimization problems // Linear Algebra and its Applications, 2015. Vol. 468. P. 211–232.
Krivulin N. Direct solution to constrained tropical optimization problems with application to project scheduling // Computational Management Science, 2017. Vol. 14. № 1. P. 91–113.
Материал публикуется под лицензией:
