Случай 1. Предлагается, что мощности облуживания всех ЛО одинаковы. Тогда зона обслуживания i -го ЛО, / = 1,n , определяется следующим образом:
где Jk(p) -- множество индексов к ближайших ЛО к потребителю в точке p .
Смысл формулы (2) состоит в том, что Mk есть такая подобласть M , которая обслуживается i -м ЛО и (к -- 1) его ближайшими к нему ЛО.
Максимальное время обслуживания i -го ЛО -- это время, за которое грузы доставляются к наиболее удаленному потребителю. Очевидно, что такие потребители располагаются на границе его зоны обслуживания
где dMi -- множество граничных точек Mi . Тогда целевая функция задачи размещения ЛО запишется следующим образом:
Можно видеть, что точки области M , отстоящие от Ot на расстояние не более т (3), образуют круг, покрывающий область Mk . Поскольку объединение Mk есть множество M , то указанные круги образуют покрытие множества M , которое имеет специальную структуру из-за того, что области Mi пересекаются.
Другими словами, построенная модель имеет вид задачи о к -кратном покрытии ограниченной области равными кругами минимального радиуса [19], с целевой функцией (4) и обобщенной на случай неевклидовой метрики (1): требуется расположить в множестве M заданное число n равных кругов Q(O,,r) , где O, -- центр i -го круга, r -- радиус кругов, i = 1,n, n > к > 1,к є N , чтобы каждая точка множества M принадлежала не менее, чем к кругам, и радиус кругов был минимальным.
где Jk(s) -- множество индексов к центров, отстоящих от точки s не больше, чем n -- к оставшихся центров, a р(s,O¦) -- расстояние от точки s до центра O . Целевая функция (5) минимизирует радиус кругов. Выражение (6) гарантирует, что каждая точка множества M принадлежит не менее, чем к кругам. Выражение (7) показывает, что все центры принадлежат множеству M .
Предложим, что максимальные обслуживающие времени ЛО удовлетворяет ограничению т, = T1ia , i = 1,п , а є Q Тогда зона обслуживания i -го ЛО, і = 1,п , определяется следующим образом:
Случай 2. Согласно постановке задачи, предлагается, что, во-первых, мощности обслуживания ЛО неодинаковы, во-вторых, каждая точка исследуемой области должна быть обслужена хотя бы одним ЛО.
В этом случае целевая функция имеет виде
(9)
где 8Mt -- граница области Mt, i = 1, n .
Нетрудно видеть, что построенная модель имеет вид задачи однократного покрытия ограниченного множества кругами с пропорциональными радиусами и целевой функцией (9), обобщенной на случай метрики (1).
Пусть имеются n кругов = {Oi,r},i = 1,n с центрами
Ot и радиусами r , r = iar1 , а є . Необходимо разместить данные круги так, чтобы замкнутое множество M покрывалось полностью объединением всех кругов, и их радиусы были минимальными.
Целевая функция (10) минимизирует радиус первого круга. Условие (11) фиксирует соотношение между радиусом i -ого круга с радиусом первого круга, а условие (12) обеспечивает полное покрытие множества M объединением кругов.
Случай 3. Требуется расположить n ЛО в области M так, чтобы доля области с кратностью обслуживания k , 1 < k < n была максимальной, при этом все зоны обслуживания должны полностью лежать в рассматриваемой области. Мощности обслуживания всех ЛО одинаковы.
Зона обслуживания Mkt , i = 1,n для i -го ЛО, как и в случае 1, определяется по формуле (2). При этом каждая точка Mk обслуживается также и еще (k -- 1) ближайшими ЛО. Для того чтобы каждый потребитель области M был обслужен не больше, чем k заданными ЛО, время обслуживания из i -го ЛО не должно превосходить времени доставки груза до ближайшего потребителя, расположенного на границе области dMk
Тогда целевая функция задачи размещения ЛО примет вид:
очевидно, что точки области M , время достижения которых из Ot не превосходит n по формуле (13), принадлежат окружности радиуса n c центром в Ot, вписанной в область dMk. Таким образом, построенная модель имеет вид задачи о k -кратной упаковке равных кругов в ограниченное множество с метрикой (1) и целевой функции (14).
Пусть имеются равные круги C (O , г), і = 1, п с центрами O (х., у.), радиусом г и ограниченное множество M . Необходимо найти такое расположение о = (о,...,O ), чтобы каждая точка области M принадлежала не больше, чем k кругам, и радиус кругов был максимальным
Целевая функция (15) максимизирует радиус кругов. Условие (16) гарантирует, что все круги находятся внутри области M , а (17) обеспечивает то, что каждая точка множества M принадлежит не больше, чем к кругам.
Случай 4. Предлагается, что, во-первых, каждый потребитель обслуживается единичным ЛО, т.е. зоны обслуживания ЛО не пересекаются между собой, во-вторых, максимальное время доставки груза потребителям удовлетворяет ограничению з =з iб , i =1,n, б ??.
Аналогично случаю 2, по формуле (8) определяется зона обслуживания Mt относительно каждого ЛO, / = 1,n . Тогда целевая функция задачи размещения ЛО имеет вид
где дМі -- граница области Mt.
Очевидно, что р(p,O.)/ іа = р(p,O1), т.е. смысл целевой функции (18) состоит максимизации времени доставки груза от первого ЛО до ближайших потребителей, расположенных на границе зоны обслуживания. Следовательно, решение данной задачи эквивалентно решению известной задачи однократной упаковки кругов разного радиуса в ограниченное множество с метрикой (1). „
кругов были максимальными
Здесь pmin(Oi, dM) = min p(Ot, p) -- расстояние от точки O до границы дМ. рШ
Пусть имеются n кругов Ni = {Oi, r }, і = 1, n с центрами
O. и радиусами r, при этом r = iar, а є Q . Необходимо разместить данные круги внутри области M так, чтобы, во-первых, все круги не пересекались между собой, во-вторых, радиусы
Целевая функция (19) максимизирует радиус первого круга. Неравенство (20) гарантирует, что все круги не пересекаются между собой. Формулы (21) и (22) гарантируют, что каждый круг полностью лежит внутри области М . Равенство (23) фиксирует отношение между радиусами кругов.
Для решения всех поставленных задач авторами разработаны вычислительные алгоритмы, реализованные в рамках программного комплекса КУПОЛ-M [20]. Его описание выходит за рамки данной статьи.
Применение методики для исследования энергетических систем
В настоящее время наблюдается рост значимости энергетической инфраструктуры восточных регионов России и Монголии в обслуживании международных экономических и энергетических связей в регионе Северо-Восточной Азии (СВА). Кроме традиционной роли экспорта энергоресурсов, развитие энергетического сотрудничества, в том числе рыночных институтов, востребованной становится функция регулирования создаваемого энергообъединения стран СВА [21].
Между СССР и МНР было развито тесное взаимодействие в области энергетики. Фактически, вся топливноэнергетическая система Монголии создавалась с участием советских специалистов. К сожалению, в постсоветский период интенсивность контактов существенно снизилась, хотя и по сей день Россия осуществляет поставки энергетических ресурсов в Монголию. Однако, как в реализуемых, так и в перспективных проектах по осуществлению поставок российских энергоресурсов в Китай, маршруты транспортировки обычно проходят, минуя Монголию, что абсолютно неоправданно, поскольку Монголия может (и должна) стать удобным транспортным коридором для поставки из России в КНР и другие страны СВА электроэнергии, нефтепродуктов и природного газа [22]. Последнее обстоятельство также будет способствовать газификации территории Иркутской области, Республики Бурятии, и Монголии, т.е. будет иметь социальный эффект, способствовать обеспечению связности территории РФ (в соответствии с п. 20 Стратегии научно-технологического развития РФ), усилит авторитет и влияние России в регионе СевероВосточной Азии [23; 24].
Таким образом, совместное развитие энергетической инфраструктуры восточных регионов России и Монголии является на современном этапе настоятельной необходимостью.
При этом начальным этапом разработки соответствующей программы двустороннего сотрудничества, очевидно, должно стать сценарное моделирование и прогнозирование долгосрочного развития топливно-энергетических комплексов России и Монголии.
В этой связи актуальной становится задача совершенствования имеющегося [25; 26] и разработки нового модельноалгоритмического аппарата.
По мнению авторов, предложенная в настоящей статье методика может оказаться полезна для моделирования не только транспортно-логистических, но и энергетических систем с учетом межстранового сотрудничества. Однако адаптация модельного подхода для задач энергетики потребует его существенной модернизации и решения следующих проблем:
Электрическую энергию, в отличие от большинства товаров, практически невозможно накапливать.
Инфраструктурные энергетические объекты, как правило, имеют более высокую стоимость и более жесткие ограничения на размещение, чем логистические.
Границы зон обслуживания энергетических объектов значительно более подвижны, чем соответствующие границы в логистике, вследствие того, что в энергетике выше степень централизации и больше скорость движения материальных потоков (электроэнергии).
Некоторые объекты энергетической инфраструктуры: трубопроводы, ЛЭП и т.п. можно рассматривать как линии коммуникации, однако организация ветвлений здесь связана с большими сложностями (и расходами), чем на обычном (колесном) транспорте.
Тем не менее, аналогия между логистическими и энергетическими системами просматривается, указанные выше трудности выглядят преодолимыми и, соответственно, применение предложенного модельно-алгоритмического подхода в новой области представляется возможным и перспективным. покрытие упаковка логистический математический
Заключение
Подводя итоги, отметим следующее:
Предложена методика исследования некоторых сложных технических систем на основе применения в качестве модельного аппарата задач о покрытии и упаковке в неклассических формулировках. Методика апробирована на примере решения проблем инфраструктурной логистики, причем предложено четыре различных типа моделей. Обоснована целесообразность применения методики в энергетической сфере с учетом развития интегрированного энергетического рынка СевероВосточной Азии.
Дальнейшее развитие исследований по тематике статьи может быть связано с совершенствованием предложенного модельно-алгоритмического и программного аппарата и/или с его применением для решения новых классов прикладных задач. При этом наиболее перспективным направлением представляется исследование систем энергетики, включая вопросы взаимодействия приграничных регионов России и Монголии в энргетической сфере.
Список использованной литературы
1. Можаев Г. В. Задача о непрерывном обзоре поверхности Земли и кинематически правильные спутниковые системы / Г. В. Можаев // Космические исследования,-- 1972,-- Т. 10, 6,-- С. 833-840.
2. Брусов В. С. Двигательная установка малой тяги, универсальная для двумерного диапазона / В. С. Брусов, С. А. Пиявский // Известия Академии наук СССР. Космические исследования. -- 1970.-- 4.-- С. 542-546.
3. Алдыноол Т. А. Покрытие плоской области случайно распределенными сенсорами / Т. А. Алдыноол, А. И. Ерзин, В. В. Залюбовский // Вестник НГУ. Серия: Математика, механика, информатика. -- 2010.-- Т. 10, 4.-- C. 7-25.
4. Cardei M. Improving netwotk lifetime using sensors with adjustible sensing ranges / M. Cardei, J. Wu, M. Lu // Int. Journal of Sensor Networks. -- 2006.-- Vol. 1, no. 1.-- P. 41-49.
5. B6nhelyi B. Optimal circle covering problems and their applications / B. B6nhelyi, E. Palatinus, B. L. Lйvai // Central European Journal of Operations Research. -- 2015.-- Vol. 23, no. 4.-- P. 815-832.
6. Efficient algorithm for placing a given number of base station to cover a convex region / G. K. Das, S. Das, S. C. Nandy, B. S. Shina // Journal of Parallel and Distributed Computing. -- 2006.-- Vol. 66, no. 11.-- P. 1353-1358.
7. Галиев Ш. И. Нахождение глобального экстремума и субоп
8. тимальных решений для задач размещения станций скорой помощи / Ш. И. Галиев, Л. Ю. Емалетдинова, М. А. Разина // Вестник Казанского государственного технического университета им. А. Н. Туполева.-- 2004.-- 3.-- С. 40-45.
9. Castilo I. Solving Circle Packing Problems by Global Optimization: Numerical Results and Industrial Applications / I. Castilo, F. Kampas,
10. J. Pinter // European Journal of Operational Research. -- 2008.-- Vol. 191, no. 3.-- P. 786-802.
11. Birgin E. Optimizing the Packing of Cylinders Into a Rectangular Container: A Nonlinear Approach / E. Birgin, J. Martenez, D. Ronconi // European Journal of Operational Research. -- 2005.-- Vol. 160, no. -- Р. 19-33.
12. An Improved Algorithm for the Packing of Unequal Circles within a Larger Containing Circle / H. Wang, W. Huang, Q. Zhang, D. Xu // European Journal of Operational Research. -- 2002.-- Vol. 141, no. -- P. 440-453.
13. Stoyan Y. G. An Optimization Problem of Packing Identical Circles into a Multiply Connected Region / Y. G. Stoyan, A. M. Chugay // Journal of Mechanical Engineering. -- 2011.-- Vol. 14, no. 1.-- P. 44-51.
14. Самарский А. А. Математическое моделирование. Методы описания и исследования сложных систем / А. А. Самарский, Н. Н. Моисеев, А. А. Петров. -- Москва: Наука, 1989.-- 271 с.
15. Specht E. Packomania / E. Specht // Packomania.com. -- 2019.
16. Казаков А. Л. Об одном подходе к решению задач оптимизации, возникающих в транспортной логистике / А. Л. Казаков, А. А. Лемперт // Автоматика и телемеханика. -- 2011.-- 7.-- С. 50-57.
17. Drezner Z. Facility Location: A Survey of Applications and Methods / Z. Drezner. -- New York: Springer, 1995.-- 571 p.
18. Tabirca T. Smallest Number of Sensors for K-Covering / T. Tabirca, L. T. Yang, S. Tabirca // International Journal of Computers Communications & Control. - 2013.- Vol. 8, no. 2.- P. 312-319.
19. Астраков С. Н. Сенсорные сети и покрытие плоскости кругами
20. / С. Н. Астраков, А. И. Ерзин, В. В. Залюбовский // Дискретный анализ и исследование операций. - 2009.- Т. 16, 3.- C. 3-19.