10 марта 2016г.
Хорошо известна задача Штейнера о поиске кратчайшей сети на плоскости, соединяющей заданный набор точек [1, 3, 5, 6, 8 – 9]. Еѐ решение основано на частном случае трѐх точек, который называют задачей Ферма- Торричелли-Штейнера. Задача Штейнера имеет множество приложений, среди которых: проектирование транспортных сетей, сетей линий электропередач, беспроводных сетей. Известно множество обобщений задачи Штейнера, которые получаются путѐм изменения количества точек, метрики (функции расстояния между точками), накладывание дополнительных условий на количество и расположение так называемых узловых точек сети Штейнера, перехода к рассмотрению графов и т.д. [1, 3, 6, 8, 9]. Исследования на эту тему продолжаются и в наши дни [8 – 10].
Однако практически во всех во всех предлагаемых моделях задачи Штейнера объекты, которые соединяются сетями, считаются точками, т.е. их размерами пренебрегают. В работе [5] сделана попытка учесть размеры этих объектов и предложен новый подход к обобщению задачи Ферма-Торричелли-Штейнера для трѐх объектов: предполагается, что эти объекты погружены в некоторые круги на плоскости и ставится следующая задача о поиске кратчайшей сети, соединяющей три заданных круга на плоскости. В работе [10] постановка задач такого типа рассмотрена для систем множеств в банаховых пространствах, но только с аналитической точки зрения (не приведено полного геометрического описания решения).
Поясним смысл формулировки задачи 2. Моделируется ситуация, где рассматриваются две зоны на местности с разной проходимостью. Пусть проходимость (например, в зоне густого
леса равна 1, а обработанного участка леса – k: 0 < k < 1). Внутри некоторых пунктов (шаров) местность обработана и проходимость лучше, а вне этих кругов проходимость хуже. Минимизация суммы расстояний в данном случае означает
минимизацию затрат на доставку чего-либо из некоторого пункта
в заданные три
пункта (ограничены кругами
wA , wB , wC). Следовательно, наше обобщение
задачи Ферма-Торричелли-Штейнера в некотором смысле моделирует задачу оптимизации перемещений на местности
с неоднородным ландшафтом. В качестве
примера можно привести такую задачу: В густом лесу (примем
коэффициент его проходимости за 1) есть три обработанных участка (их коэффициент проходимости k). Где построить
дом леснику, чтобы тратить минимальное количество времени на обслуживание участков?
Или, пусть есть три населѐнных пункта, у жителей которых не хватает денег, чтобы провести полностью асфальтированную
дорогу между пунктами. А хватает
лишь на то, чтобы около каждого города
был проасфальтированный участок
дороги (с коэффициентом 0 < k < 1), а
дальше будет проложена грунтовая
дорога (коэффициент проходимости которой равен
1). Возникает вопрос, где спроектировать перекрѐсток для этих дорог, чтобы затраты на бензин у водителей были минимальными? Кстати, в этой задаче
коэффициент проходимости k в некотором
смысле описывает
действие силы трения.
Исследования первого автора выполнены при частичной финансовой поддержке гранта Президента Российской Федерации для государственной поддержки
молодых российских учѐных-кандидатов наук, код МК- 2915.2015.1
Список литературы
1. Иванов А.О. Плоские взвешенные минимальные бинарные деревья.
// Фундаментальная и прикладная математика, 1996. – №2. – С. 375 – 409.
2.
Кларк Ф. Оптимизация и негладкий анализ.
– М.: Наука, 1988. – 280 с.
3.
Протасов В.Ю. Максимумы
и минимумы в геометрии. – М.МЦНМО, 2005.
– 56с.
4.
Рокафеллар Р. Выпуклый
анализ. – М.: Мир, 1973. – 473 с.
5.
Стонякин Ф.С., Шпилѐв Р.О. Задача Штейнера для кругов на плоскости. // Учѐные записки Таврического национального университета им. В.И. Вернадского. Серия «Физико-математические науки».
– Т. 25(64). – 2012, № 2 – с. 128 – 139.
6. Тихомиров В.М. Рассказы
о максимумах и минимумах.
— М.: МЦНМО, 2006. — 200 с.
7. Щербаков О.С. Угловой метод решения задач и его приложения. // Международный научно-технический конкурс «Шаг в науку»
– Симферополь, 2011.
– 37 с
8.
Brazil Marcus,
Charl J. Ras, Doreen A. Thomas. A Flow-dependent Quadratic Steiner Tree Problem
in the Euclidean Plane.
// arXiv:1111.2109v1 [math.MG].
– 9 Nov 2011.
9.
Isaac Fung,
Konstantinos Georgiou, Jochen Koenemann, Malcolm Sharpe. Efficient
Algorithms for Solving Hypergraphic Steiner
Tree Relaxations in Quasi-Bipartite Instances. // arXiv:1202.5049v1 [cs.DM].
– 22
Feb 2012.
10. Mordukhovich B.S. and Nam N.M. Applications of variational analysis to a generalized Fermat-Torricelli problem. // J. Optim. Theory
Appl., Vol. 148. – 2011. – P. 431 – 454.
