Иркутский национальный исследовательский технический университет
Оптимизация технических систем на основе задач об упаковке и покрытии
К.М. Ле
А. Л. Казаков
А. А. Лемперт
г. Иркутск, Российская Федерация
Аннотация
Задачи о построении оптимальных покрытий и упаковок кругов на плоскости являются широко известными и популярными математическими проблемами, которые часто применяются в моделировании. Традиционно их использование ограничивается исследованием достаточно простых прикладных постановок: установка датчиков, упаковка изделий и т.п. Целью настоящей работы является распространение указанного модельного аппарата на более сложные технические системы. Представлена общая методика построения математических моделей такого рода, соответствующая классической парадигме «модель-алгоритм-программа», которая апробируется на примере логистических систем. При этом предложено четыре различных типа моделей, каждый из которых соответствует особому классу задач инфраструктурной логистики. Обсуждается также применение данного подхода для изучения энергетических систем, включая вопросы взаимодействия России и Монголии в сфере энергетики.
Ключевые слова: оптимизация, математическое моделирование, техническая система, логистика, энергетика
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, получаем обычное евклидово расстояние.