Решение задачи о размещении двух объектов в пространстве с метрикой Чебышёва
DOI:
https://doi.org/10.21638/spbu01.2022.405Аннотация
Рассматривается минимаксная задача о размещении двух объектов в многомерном пространстве с метрикой Чебышёва при наличии интервальных ограничений на допустимую область размещения. В задаче имеются две группы объектов с заданными координатами и требуется найти координаты оптимального размещения двух новых объектов с учетом заданных ограничений. Размещение новых объектов считается оптимальным, если оно минимизирует максимум следующих величин: расстояние от первого объекта до самого удаленного от него объекта из первой группы имеющихся объектов, расстояние от второго объекта до самого удаленного объекта из второй группы, а также расстояние между первым и вторым новыми объектами. Задача размещения формулируется как задача многомерной оптимизации в терминах тропической математики, которая изучает теорию и приложения алгебраических систем с идемпотентными операциями. На основе использования методов и результатов тропической оптимизации найдено прямое аналитическое решение задачи. Получен результат, который описывает область оптимального размещения новых объектов в параметрической форме, удобной для формального анализа решения и непосредственных вычислений.Ключевые слова:
тропическая оптимизация, идемпотентное полуполе, минимаксная задача оптимизации, задача о размещении двух объектов
Скачивания
Данные скачивания пока недоступны.
Библиографические ссылки
Литература
1. Eiselt H.A., Marianov V. Pioneering developments in location analysis. In: Foundations of Location Analysis. International Series in Operations Research and Management Science, vol. 155, 3-22. New York, Springer (2011). https://doi.org/10.1007/978-1-4419-7572-0-1
2. Moradi E., Bidkhori M. Single facility location problem. In: Facility Location. Contributions to Management Science, 3-22. Heidelberg, Physica-Verlag (2009). https://doi.org/10.1007/978-3-7908- 2151-2-3
3. Drezner Z. Continuous center problems. In: Foundations of Location Analysis. International Series in Operations Research and Management Science, vol. 155, 63-78. New York, Springer (2011). https://doi.org/10.1007/978-1-4419-7572-0-4
4. Kolokoltsov V.N., Maslov V.P. Idempotent Analysis and Its Applications. In Ser.: Mathematics and Its Applications, vol. 401. Dordrecht, Springer (1997). https://doi.org/10.1007/978-94-015-8901-7
5. Golan J.S. Semirings and Affine Equations Over Them. In Ser.: Mathematics and Its Applications, vol. 556. New York, Springer (2003). https://doi.org/10.1007/978-94-017-0383-3
6. Heidergott B., Olsder G.J., van der Woude J. Max Plus at Work. In Ser.: Princeton Series in Applied Mathematics. Princeton, Princeton University Press (2006).
7. Maclagan D., Sturmfels B. Introduction to Tropical Geometry. In Ser.: Graduate Studies in Mathematics, vol. 161. Providence, AMS (2015). https://doi.org/10.1090/gsm/161
8. Krivulin N. Complete solution of a constrained tropical optimization problem with application to location analysis. In: Relational and Algebraic Methods in Computer Science. Lecture Notes in Computer Science, vol. 8428, 362-378. Cham, Springer (2014). https://doi.org/10.1007/978-3-319-06251-8-22
9. Krivulin N. Using tropical optimization to solve constrained minimax single-facility location problems with rectilinear distance. Comput. Manag. Sci. 14 (4), 493-518 (2017). https://doi.org/10.1007/s10287-017-0289-2
10. Krivulin N. Algebraic solution of minimax single-facility constrained location problems with Chebyshev and rectilinear distances. J. Log. Algebr. Methods Program. 115, 100578 (2020). https://doi.org/10.1016/j.jlamp.2020.100578
11. Krivulin N. Algebraic solutions of tropical optimization problems. Lobachevskii J. Math. 36 (4), 363-374 (2015). https://doi.org/10.1134/S199508021504006X
12. Krivulin N. Direct solution to constrained tropical optimization problems with application to project scheduling. Comput. Manag. Sci. 14 (1), 91-113 (2017). https://doi.org/10.1007/s10287-016- 0259-0
13. Krivulin N. Extremal properties of tropical eigenvalues and solutions to tropical optimization problems. Linear Algebra Appl. 468, 211-232 (2015). https://doi.org/10.1016/j.laa.2014.06.044
References
1. Eiselt H.A., Marianov V. Pioneering developments in location analysis. In: Foundations of Location Analysis. International Series in Operations Research and Management Science, vol. 155, 3-22. New York, Springer (2011). https://doi.org/10.1007/978-1-4419-7572-0-1
2. Moradi E., Bidkhori M. Single facility location problem. In: Facility Location. Contributions to Management Science, 3-22. Heidelberg, Physica-Verlag (2009). https://doi.org/10.1007/978-3-7908- 2151-2-3
3. Drezner Z. Continuous center problems. In: Foundations of Location Analysis. International Series in Operations Research and Management Science, vol. 155, 63-78. New York, Springer (2011). https://doi.org/10.1007/978-1-4419-7572-0-4
4. Kolokoltsov V.N., Maslov V.P. Idempotent Analysis and Its Applications. In Ser.: Mathematics and Its Applications, vol. 401. Dordrecht, Springer (1997). https://doi.org/10.1007/978-94-015-8901-7
5. Golan J.S. Semirings and Affine Equations Over Them. In Ser.: Mathematics and Its Applications, vol. 556. New York, Springer (2003). https://doi.org/10.1007/978-94-017-0383-3
6. Heidergott B., Olsder G.J., van der Woude J. Max Plus at Work. In Ser.: Princeton Series in Applied Mathematics. Princeton, Princeton University Press (2006).
7. Maclagan D., Sturmfels B. Introduction to Tropical Geometry. In Ser.: Graduate Studies in Mathematics, vol. 161. Providence, AMS (2015). https://doi.org/10.1090/gsm/161
8. Krivulin N. Complete solution of a constrained tropical optimization problem with application to location analysis. In: Relational and Algebraic Methods in Computer Science. Lecture Notes in Computer Science, vol. 8428, 362-378. Cham, Springer (2014). https://doi.org/10.1007/978-3-319-06251-8-22
9. Krivulin N. Using tropical optimization to solve constrained minimax single-facility location problems with rectilinear distance. Comput. Manag. Sci. 14 (4), 493-518 (2017). https://doi.org/10.1007/s10287-017-0289-2
10. Krivulin N. Algebraic solution of minimax single-facility constrained location problems with Chebyshev and rectilinear distances. J. Log. Algebr. Methods Program. 115, 100578 (2020). https://doi.org/10.1016/j.jlamp.2020.100578
11. Krivulin N. Algebraic solutions of tropical optimization problems. Lobachevskii J. Math. 36 (4), 363-374 (2015). https://doi.org/10.1134/S199508021504006X
12. Krivulin N. Direct solution to constrained tropical optimization problems with application to project scheduling. Comput. Manag. Sci. 14 (1), 91-113 (2017). https://doi.org/10.1007/s10287-016- 0259-0
13. Krivulin N. Extremal properties of tropical eigenvalues and solutions to tropical optimization problems. Linear Algebra Appl. 468, 211-232 (2015). https://doi.org/10.1016/j.laa.2014.06.044
Загрузки
Опубликован
26.12.2022
Как цитировать
Кривулин, Н. К., & Брюшинин, М. А. (2022). Решение задачи о размещении двух объектов в пространстве с метрикой Чебышёва. Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия, 9(4), 625–635. https://doi.org/10.21638/spbu01.2022.405
Выпуск
Раздел
Математика
Лицензия
Статьи журнала «Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия» находятся в открытом доступе и распространяются в соответствии с условиями Лицензионного Договора с Санкт-Петербургским государственным университетом, который бесплатно предоставляет авторам неограниченное распространение и самостоятельное архивирование.
