Оптимизация технических систем на основе задач об упаковке и покрытии

Размещено на http://www.allbest.ru/

Иркутский национальный исследовательский технический университет

Оптимизация технических систем на основе задач об упаковке и покрытии

К.М. Ле

А. Л. Казаков

А. А. Лемперт

г. Иркутск, Российская Федерация



Аннотация

Задачи о построении оптимальных покрытий и упаковок кругов на плоскости являются широко известными и популярными математическими проблемами, которые часто применяются в моделировании. Традиционно их использование ограничивается исследованием достаточно простых прикладных постановок: установка датчиков, упаковка изделий и т.п. Целью настоящей работы является распространение указанного модельного аппарата на более сложные технические системы. Представлена общая методика построения математических моделей такого рода, соответствующая классической парадигме «модель-алгоритм-программа», которая апробируется на примере логистических систем. При этом предложено четыре различных типа моделей, каждый из которых соответствует особому классу задач инфраструктурной логистики. Обсуждается также применение данного подхода для изучения энергетических систем, включая вопросы взаимодействия России и Монголии в сфере энергетики.

Ключевые слова: оптимизация, математическое моделирование, техническая система, логистика, энергетика



Annotation

OPTIMIZATION OF ENGINEERING SYSTEMS BASED ON PACKING AND COATING PROBLEMS

К.М. Le

Irkutsk National Research Technical University

Irkutsk, Russian Federation

A. L. Kazakov

Irkutsk National Research Technical University Irkutsk, Russian Federation

A. A. Lempert

Irkutsk National Research Technical University Irkutsk

The problems of constructing optimal coatings and packages of circles on a plane are well-known and popular mathematical problems that are often used in modeling. Traditionally, their use is limited to the study of fairly simple applied settings: installation of sensors, packaging of products, etc. The goal of this research is to extend the specified model apparatus to more complex technical systems. The study presents a general technique for constructing mathematical models of this kind, which corresponds to the classical paradigm «model-algorithm-program», which is tested on the example of logistics systems. We also put forward four different types of models, each of which corresponds to a special class of tasks of infrastructure logistics.The researcj also discussed the application of this approach to the study of energy systems, including the issues of interaction between Russia and Mongolia in the field of energy.

Keywords: optimization, mathematical modeling, technical system, logistics, energy



Введение

Построение оптимальных покрытий и упаковок относится к числу классических задач вычислительной геометрии, интерес к которым сохраняется на протяжении столетий. Суть первой заключается в размещении заданного числа кругов так, чтобы целевое множество лежало внутри их объединения, а радиус был минимальным. Вторая предполагает упаковку в некоторый контейнер заданного числа кругов с максимизацией радиусов последних. В наиболее простой и популярной постановке все круги одинаковы, однако возможны и другие варианты указанных задач.

Задача о покрытии имеет широкое применение в технике и экономике. Сюда можно отнести создание сети искусственных спутников Земли [1]; проблему выбора оптимальной мощности универсальных двигательных установок малой тяги [2]; проектирование энергоэффективной системы мониторинга протяженных объектов беспроводными сенсорными сетями [3; 4]; оптимизацию расположения телевизионных станций [5] и базовых станций сотовой связи [6]; размещения спасательных пунктов [7] и т.д.

Проблема упаковки кругов также встречается в различных областях человеческой деятельности. Примеры использования задачи упаковки кругов в промышленности можно найти в работе [8]: круговая резка материалов, погрузка контейнеров, упаковка труб и цилиндров, размещение производственных мощностей и объектов коммуникационной сети, расположение приборов на панели. Также эта задача возникает в металлообрабатывающей промышленности, в стекольной и целлюлозно-бумажной промышленности [9], при решении проблемы упаковки оптических волокон в трубки, а также при перевозке труб различного размера внутри контейнера [10], измерении солнечной радиации, изучении белковых структур в биологии [11] и др.



Методика исследования технических систем

Предлагаемая методика исследования технических систем на основе задач об оптимальном покрытии и упаковке соответствует общей парадигме математического моделирования «модель-алгоритм-программа» [12]. На первом этапе разрабатываются математические модели исследуемых технических систем. На втором предложенные математические модели сведены к специальным модификациям задач о кратных покрытиях и упаковках кругов. На третьем -- разработаны численные алгоритмы на основе оптико-геометрического подхода и диаграмм Вороного-Дирихле. На последнем (четвертом) этапе предложенные алгоритмы реализованы в виде программного комплекса для проведения вычислительного эксперимента в исследуемых задачах оптимизации и решения прикладных проблем.

Остановимся на отдельных этапах методики более подробно

Построение математической модели состоит из двух шагов. Вначале, в соответствии с общепринятыми принципами математического моделирования, формируется, так называемая, предметная модель, которая представляет собой описание объекта исследования в рамках соответствующей предметной области.

Основной задачей, которую необходимо решить при разработке предметной модели, является выделение наиболее существенных факторов, влияющих на функционирование изучаемого объекта, которые в дальнейшем включатся в рассмотрение, и выявление малозначимых характеристик, которые из рассмотрения исключаются. На этом же этапе определяется цель моделирования. В нашем случае это оптимизация расположения элементов системы.

Далее строится математическое описание предметной модели: производится подбор математического аппарата, с помощью которого выполняется описание предметной модели. В нашем случае это известные задачи непрерывной оптимизации в специальных неклассических формулировках.

Наиболее важной отличительной особенностью рассматриваемых математических моделей является то, что в качестве меры удаленности объектов друг от друга рассматривается обобщенное расстояние, которое учитывает локальные особенности, что приводит к необходимости перехода в метрическое пространство со специальной неевклидовой метрикой, которая, впрочем, может являться классической евклидовой (в случае, когда выраженных локальных особенностей нет).

На втором этапе разработанные математические модели записываются в виде широко известных задач вычислительной геометрии об аппроксимации множеств на плоскости кругами: построение оптимальных покрытий ограниченного множества и упаковок в конечный контейнер (в неклассических формулировках). Помимо уже отмечавшейся выше особенности задач, связанной с заменой обычного евклидова расстояния специальным обобщенным, полученные постановки, вдобавок, либо предполагают использование разнородных объектов (кругов различного радиуса), либо предусматривают построение кратных аппроксимаций -- в зависимости от постановки исходной проблемы из соответствующей предметной области.

Проводить исследование построенных математических моделей аналитическими методами, вообще говоря, не представляется возможным. Отметим, что это затруднительно даже в наиболее простых классических случаях, когда речь идет о равных кругах в евклидовой метрике этой связи на третьем этапе производится разработка алгоритмического аппарата, позволяющего выполнять численное исследование построенных математических моделей. В качестве основы численной методики используется оптико-геометрический подход [14], который в научной школе одного из авторов, профессора А. Л. Казакова, развивается уже около 10 лет.

Главной задачей, которую необходимо решить при построении оптимальных покрытий и упаковок, является разбиение целевой области на зоны (области) Вороного-Дирихле на основе построения диаграммы Вороного-Дирихле. Особенности изучаемых задач приводят к тому, что указанная диаграмма, вообще говоря, уже состоит не из отрезков прямых, как в классическом случае, а зоны не являются многоугольниками (они могут быть даже неодносвязными), что принципиально усложняет построение.

На заключительном (четвертом) этапе работы выполняется реализация разработанных алгоритмов в виде программного комплекса. При этом, поскольку для решения различных задач применяются некоторые общие процедуры (пуск волны из источника и/или с границы многообразия, построение диаграммы Вороного-Дирихле и идентификация обобщенных зон Вороного-Дирихле и т.п.), комплекс имеет модульную архитектуру. Дополнительное расширение возможностей программы, связанное с необходимостью решения прикладных задач, также потребовало доработки программно-алгоритмического инструментария, включая решение проблемы визуализации полученных результатов с привязкой к карте местности.

Применение методики для исследования логистических систем

Пусть имеется некоторый ограниченный полигон обслуживания. Будем предполагать, что количество потребителей, расположенных на территории полигона, настолько велико, что, по аналогии с механикой сплошной среды, можно считать, что они распределены по территории непрерывным образом. Требуется разместить заданное число логистических обслуживающих объектов (ЛО) в данном полигоне с учєтом ограничений различной природы. В роли критерия качества размещения выступает время доставки груза потребителям или достижения потребителями обслуживающего центра. Для удобства рассмотрения выделим и опишем следующие случаи.

Каждый потребитель должен быть обслужен не менее, чем к ЛО; максимальное время доставки груза потребителю должно быть одинаковым для всех ЛО, и указанное время должно быть минимальным.

Такие требования возникают, в первую очередь, при размещении вышек сотовой связи, в задачах обеспечения безопасности охраняемого периметра [5; 15], разработке систем мониторинга распределенных объектов с помощью беспроводных сенсорных сетей, когда необходимо обеспечить корректную работу системы при выходе из строя части обслуживающих устройств (системы с дублированием или резервированием) [16].

Каждый потребитель должен быть обслужен не менее, чем одним ЛО; максимальное время доставки груза потребителю должно быть пропорциональным мощности ЛО, и указанное время должно быть минимальным.

Такие требования возникают в случае, когда требуется разместить объекты, имеющие разные характеристики обслуживания, в частности, площадь складских помещений, погрузочноразгрузочное оборудование и персонал, автопарк и т.п., которые непосредственно влияют на время доставки грузов.

Так, наличие развитой внутренней инфраструктуры позволяет более крупным логистическим центрам осуществлять за заданное время доставку товаров более удаленным потребителям. Если же говорить об устройствах типа сенсоров, то в рамках одной системы может возникнуть необходимость в использовании устройств разных типов.

Каждый потребитель может быть обслужен не более, чем к ЛО; необходимо обслужить максимально возможную долю полигона; максимальное время обслуживания должно быть одинаковым для всех ЛО.

Такие требования возникают в случае, когда избыточное обслуживание недопустимо или приводит к нежелательным последствиям в большей степени, чем отсутствие обслуживания. К примеру, такая ситуация возможна при организации полива растений и обработки ядохимикатами массивов насаждений1 .

Каждый потребитель должен быть обслужен не менее, чем одним ЛО; необходимо обслужить максимально возможную долю рассматриваемой области; зоны обслуживания различных ЛО не должны пересекаться; максимальное время доставки груза потребителю должно быть пропорциональным мощности ЛО.

Такие требования возникают при решении задач размещения различных типов датчиков: тепловых, фотоэлектрических, оптоволоконных, приближения, давления, изображения, влажности и др. К этому классу задач относится проблема построения систем раннего предупреждения лесных пожаров, автоматического управления освещением, идентификации автомобилей и др. При этом диапазоны датчиков не должны пересекаться между собой, поскольку необходимо обеспечить отсутствие интерференции. Для того, чтобы суммарная площадь диапазонов датчиков была максимальной, требуется использовать датчики с разными мощностями [17; 18].

Перейд м к математической формализации представленных постановок.

Пусть М -- заданная ограниченная область c непрерывной границей дМ , в которой потребители распределены непрерывно; n -- количество ЛО; Ot (xt, у) -- координаты центра i -ого ЛО; Sn = {O.} -- множество центров всех ЛО, / = 1,тз; к -кратность обслуживания; f (x,y) > 0 -- непрерывная функция, задающая мгновенную скорость движения (грузов или потребителей) в каждой точке (x, у) є X . 1 СанПиН 1.2.2584-10. Гигиенические требования к безопасности процессов испытаний, хранения, перевозки, реализации, применения, обезвреживания и утилизации пестицидов и агрохимикатов. Введ. 02 марта 2010 г. Москва : Фе- дер. центр гигиены и эпидем. Роспотребнадзора, 2010. 71 с.; СанПиН 1.2.1077 Гигиенические требования к хранению, применению и транспортировке пестицидов и агрохимикатов. Введ. 08 окт. 2001 г. Москва : Роспотребнадзора, 2001. 54 с.

Тогда в качестве меры удаленности двух точек a, b є M друг от друга будем рассматривать выражение



(1)

где G(a,b) -- множество маршрутов, соединяющих а и b Формула (1) определяет минимальное время перемещения между а и b. Далее функцию р(а, b) будем рассматривать в качестве расстояния. В случае, когда f (x, y) = 1, получаем обычное евклидово расстояние.

Случай 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.

21. Астраков С. Н. Сенсорные сети и покрытие полосы эллипсами /

22. С. Н. Астраков, А. И. Ерзин // Вычислительные технологии. - 2013.- Т. 18, 2.- C. 3-11.

23. Галиев Ш. И. Оптимизация многократного покрытия ограниченного множества кругами / Ш. И. Галиев, М. А. Карпова // Журнал вычислительной математики и математической физики. - 2010.- T. 50, 4.- С. 757-769.

24. Казаков А. Л. КУПОЛ-М: кратные упаковки и покрытия, оптимизация, логистика: свидетельство о гос. регистрации программы для ЭВМ 2018666830 от 21 нояб. 2018 г. / А. Л. Казаков, А. А. Лемперт, К. М. Ле; правообладатели Федеральное государственное бюджетное учреждение науки Институт динамики систем и теории управления имени

25. М. Матросова Сибирского отделения Российской академии наук, дата регистрации 21 дек. 2018.

26. Восточный вектор энергетической стратегии России: современное состояние, взгляд в будущее / под ред. Н. И. Воропая, Б. Г. Санеева.- Новосибирск: Гео, 2011.- 368 с.

27. Энергетическое сотрудничество Монголии и России: современное состояние и стратегические направления / Н. И. Воропай, Б. Г. Санеев, Батхуяг, Х. Энхжаргал // Пространственная экономика. - 2013. - C. 108-122.

28. Топливно-энергетический комплекс Байкальского региона: современное состояние, перспективы развития / под ред. Б. Г. Санеева.- Новосибирск: Гео, 2015.- 176 с.

29. Методический подход к оценке показателей энергоэффектив ности экономики при изменении структуры топливно-энергетического баланса (на примере Байкальского региона) / Б. Г. Санеев, А. Д. Соколов, С. Ю. Музычук, Р. И. Музычук // Пространственная экономика.- 2013.- 4.- С. 90-106.

30. Макаров А. А. Методы исследования и оптимизации энергетического хозяйства / А. А. Макаров, Л. А. Мелентьев.- Новосибирск: Наука, 1973.- 274 с.

31. Методы и модели разработки региональных энергетических программ / под ред. Б. Г. Санеева. - Новосибирск: Наука, 2003.- 140 с.

References

1. Mozhaev G. V. The Problem of Continuous Review of Earth and Kinematically Correct Satellite System. Kosmicheskie issledovaniya = Cosmic Research, 1972, vol. 10, no. 6, pp. 833-840. (In Russian).

2. Brusov V. S., Piyavskii S. A. Low Thrust Propulsion Installation Universal for Two-Dimensional Band. Izvestiya Akademii nauk SSSR. Kosmicheskie issledovaniya = Herald of the USSR Academy of Sciences. Cosmic Research, 1970, no. 4, pp. 542-546. (In Russian).

3. Aldynool T. A., Erzin A. I., Zalyubovskiy V. V. The Coverage of a Planar Region by Randomly Deployed Sensors. Vestnik NGU. Seriya: Matem- atika, mekhanika, informatika = NSU Vestnik Journal, Series: Mathematics, Mechanics,Computer Science, 2010, vol. 10, no. 4, pp. 7-25. (In Russian).

4. Cardei M., Wu J., Lu M. Improving network lifetime using sensors with adjustable sensing ranges. Int. Journal of Sensor Networks, 2006, vol. 1, no. 1, pp. 41-49.

5. B6nhelyi B., Palatinus E., Lrnvai B. L. Optimal circle covering problems and their applications. Central European Journal of Operations Research, 2015, vol. 23, no. 4, pp. 815-832.

6. Das G. K., Das S., Nandy S. C., Shina B. S. Efficient algorithm for placing a given number of base station to cover a convex region. Journal of Parallel and Distributed Computing, 2006, vol. 66, no. 11, pp. 1353-1358.

7. Galiev Sh.I., Emaletdinova L. Yu., Razina M. A. Finding a global extremum and suboptimal solutions for problems of emergency room placement. Vestnik Kazanskogo gosudarstvennogo tekhnicheskogo universiteta im. A. N. Tupoleva = Bulletin of the Kazan National Research Technical University named after A. N. Tupolev, 2004, no. 3, pp. 40-45. (In Russian).

8. Castilo I., Kampas F., Pinter J. Solving Circle Packing Problems by Global Optimization: Numerical Results and Industrial Applications. European Journal of Operational Research, 2008, vol. 191, no. 3, pp. 786-802.

9. Birgin E., MartHnez J., Ronconi D. Optimizing the Packing of Cylinders Into a Rectangular Container: A Nonlinear Approach. European Journal of Operational Research, 2005, vol. 160, no. 1, pp. 19-33.

10. Wang H., Huang W., Zhang Q., Xu D. An Improved Algorithm for the Packing of Unequal Circles within a Larger Containing Circle. European Journal of Operational Research, 2002, vol. 141, no. 2, pp. 440-453.

11. Stoyan Y. G., Chugay A. M. Optimization Problem of Packing Identical Circles into a Multiply Connected Region. Journal of Mechanical Engineering, 2011, vol. 14, no. 1, pp. 44-51.

12. 12.Samarskii A. A., Moiseev N. N., Petrov A. A. Matematicheskoe mod- elirovanie. Metody opisaniya i issledovaniya slozhnyi sistem [Mathematical Modeling. Methods of Description and Investigation of Complex Systems]. Moscow, Nauka Publ., 1989. 271 p.

13. Specht E. Packomania. Packomania.com, 2019.

14. Kazakov A. L., Lempert A. A. An Approach to Optimization in Transport Logistics. Avtomatika i telemekhanika = Automation and Remote Control, 2011, no. 7, pp. 50-57.

15. Drezner Z. Facility Location: A Survey of Applications and Methods. New York, Springer, 1995. 571 p.

16. Tabirca T., Yang L. T., Tabirca S. Smallest Number of Sensors for K-Covering. International Journal of Computers Communications & Control, 2013, vol. 8, no. 2, pp. 312-319.

17. Astrakov S. N., Erzin A. I., Zalyubovskiy V. V. Sensor Networks and Covering of Plane by Discs. Diskretnyi analiz i issledovanie operat- sii = Discrete Analysis and Operations Research, 2009, vol. 16, no. 3, pp. 3-19. (In Russian).

18. Astrakov S. N., Erzin A. I. Sensor Networks and Band Coverage with Ellipses. Vychislitel'nye tekhnologii = Computational Technologies, 2013, vol. 18, no. 2, pp. 3-11. (In Russian).

19. Karpova M. A. Optimization of a Multiple Covering of a Bounded Set with Circles. Zhurnal vychislitel'noi matematiki i matematicheskoi fiziki = Computational Mathematics and Mathematical Physics, 2010, vol. 50, no. 4, pp. 757-769. (In Russian).

20. Kazakov A. L., Lempert A. A., Le K. M. KUPOL-M: kratnye upa- kovki i pokrytiya, optimizatsiya, logistika [Dome-M: Multiple packages and coatings, optimization, logistics]. Software state registration certificate No 2018618633. Copyright belongs to Matrosov Institute for System Dynamics and Control Theory of Siberian Branch of Russian Academy of Sciences. Applied 21 November 2018. Published 21 December 2018. (In Russian).

21. Voropai N. I., Saneev B. G. (eds). Vostochnyi vektor energetich- eskoi strategii Rossii: sovremennoe sostoyanie, vzglyad v budushchee [The Eastern Vector of Russia's Energy Strategy: State of the Art and Prospects]. Novosibirsk, Geo Publ., 2011. 368 p.

22. Voropai N. I., Saneev B. G., Batkhuyag S., Enkhjargal K. Energy Cooperation between Mongolia and Russia: Current State and Strategic Directions. Prostranstvennaya ekonomika = Spatial Economics, 2013, no. 3, pp. 108-122. (In Russian).

23. Saneev B. G. (ed.). Toplivno-energeticheskii kompleks Baikal'sk- ogo regiona: sovremennoe sostoyanie, perspektivy razvitiya [Energy Sector of the Baikal Region: Current State, Prospects for Development]. Novosi- birsk,Geo Publ., 2015. 176 p.

24. Saneev B. G., Sokolov A. D., Muzychyuk S. Yu., Muzy- chyuk R. I. Methodical Approach to Estimation of Energy Efficiency Parameters of the Economy Under the Structural Changes in the Fuel And Energy Balance (on the Example of Baikal Region). Prostranstvennaya ekonomika = Spatial Economics, 2013, no. 4, pp. 90-106. (In Russian).

25. Makarov A. A., Melentev L. A. Metody issledovaniya i optimizatsii energeticheskogo khozyaistva [Methods of Energy Economy Research and Optimization]. Novosibirsk,Nauka Publ., 1973. 274 p.

26. Saneev B. G. (ed.). Metody i modeli razrabotki regional'nykh en- ergeticheskikh programm [Methods and Models for the Development of Regional Energy Programs]. Novosibirsk,Nauka Publ., 2003. 140 p.

Размещено на Allbest.ru