Автореферат (Решение минимаксных задач размещения на плоскости с прямоугольной метрикой на основе методов идемпотентной алгебры)

На правах рукописиПлотников Павел ВладимировичРЕШЕНИЕ МИНИМАКСНЫХ ЗАДАЧ РАЗМЕЩЕНИЯНА ПЛОСКОСТИ С ПРЯМОУГОЛЬНОЙ МЕТРИКОЙНА ОСНОВЕ МЕТОДОВ ИДЕМПОТЕНТНОЙ АЛГЕБРЫ05.13.17 — Теоретические основы информатики,01.01.09 — Дискретная математика и математическаякибернетикаАВТОРЕФЕРАТдиссертации на соискание учёной степеникандидата физико-математических наукСанкт-Петербург – 2018Работа выполнена на кафедре статистического моделирования Санкт-Петербургского государственного университетаНаучный руководитель:доктор физико-математических наук, доцентКРИВУЛИН Николай КимовичОфициальные оппоненты:СОКОЛОВ Андрей Владимирович,доктор физико-математических наук, профессор,Федеральное государственное бюджетное учреждение науки Федеральный исследовательский центр "Карельскийнаучный центр Российской академии наук", ведущий научный сотрудник Института прикладных математическихисследованийКАЛИНИН Никита Сергеевич,PhD (кандидат физико-математических наук),Федеральное государственное автономное образовательное учреждение высшего образования "Национальный исследовательский университет "Высшая школа экономики", старший научный сотрудник Международной лабораториитеорииигрипринятиярешенийСанкт-Петербургской школы экономики и менеджментаВедущая организация:ФедеральноетельноегосударственноеучреждениеПетербургскийавтономноевысшегообразованиягосударственныйобразова"Санкт-электротехническийуниверситет "ЛЭТИ" им.

В.И. Ульянова (Ленина)"Защита состоится 14 июня 2018 года в 16-00 часов на заседании диссертационного совета Д 212.232.51 на базе Санкт-Петербургского государственного университета по адресу:198504, г. Санкт-Петербург, Старый Петергоф, Университетский пр., д. 28, математикомеханический факультет СПбГУ, ауд. 405.С диссертацией можно ознакомиться в Научной библиотеке им.

М. Горького СанктПетербургскогогосударственногоуниверситетапоадресу:199034,Санкт-Петербург,Университетская наб., 7/9 и на сайте https://disser.spbu.ru/disser/soiskatelyu-uchjonojstepeni/dis-list/details/14/1694.html.Автореферат разослан ""2018 года.Ученый секретарьдиссертационного совета Д 212.232.51доктор физико-математических наук,профессорЮ. К.

ДемьяновичОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫАктуальность темы исследования. Одной из перспективных и быстро развивающихся областей прикладной математики и алгебраической информатики является тропическая математика, которая связана с изучением теории и приложений полуколец сидемпотентным сложением.

В технике, экономике и управлении при автоматизации и информатизации различных процессов достаточно часто можно встретить оптимизационныезадачи, которые могут быть сформулированы и решены в терминах тропической математики (задачи тропической оптимизации).Существует важный с практической точки зрения класс задач оптимизации, возникающих при оптимальном проектировании информационных систем и процессов (оптимизация структуры информационной системы, оптимизация топологии сети передачиданных, оптимизация архитектуры распределенных систем обработки данных и др.), вкоторых требуется найти наилучший способ разместить объект без ограничений или с дополнительными ограничениями на допустимую область размещения. Такую задачу частоназывают задачей1-центра (1-centerproblem), которая представляет важный класс задачоптимизации и находит широкое применение в Data Mining.

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

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

В случае евклидовой метрики, задача, известная также как задача о наименьшей ограничивающей сфере, разрешима за линейное время.Большим прикладным значением обладает решение минимаксной задачи размещения с прямоугольной метрикой (1 -метрика). Такого рода оптимизационную задачу называют задачей Ролса или задачей посыльного. Известно геометрическое решение этойзадачи, а также решение с помощью методов линейного программирования, в частности,с использованием симплекс-метода.Научно-технические задачи. На практике рассматриваемый класс задач можетвстречаться, например, при проектировании размещения центров управления, храненияи обработки данных, собранных с видеокамер системы видеонаблюдения в здании.Система видеонаблюдения такого рода состоит из трех главных компонент: (1) видеокамеры, производящие входной поток видеоинформации, (2) система передачи сигналаот камер до центра управления, хранения и обработки данных и (3) сам этот центр.

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

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

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

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

Алгоритмический подход обычно обеспечиваетчисленное нахождение одного из решений и требует применения специальных программных средств. Такой подход не позволяет получить все решения аналитически в виде явныхформульных зависимостей, удобном для дальнейшего анализа и непосредственных расчетов. Поэтому есть необходимость в разработке новых методов для получения в явномвиде аналитических решений задачи1-центра.Возможностью получать такие решенияобладает подход на основе применения методов тропической математики.Таким образом, актуальной теоретической и практической задачей является разработка методов тропической оптимизации для решения задач1-центрас прямоугольнойметрикой с разного рода ограничениями на допустимую область размещения, которые воз4никают при исследовании принципов создания и функционирования аппаратных средствавтоматизации различных процессов, проектировании и развитии информационных систем различного назначения.Степень разработанности темы.

Диссертационное исследование базируется натеоретических положениях, методологических подходах и концептуальных выводах, обоснованных в трудах отечественных и зарубежных ученых.Значительный вклад в развитие теории и методов тропической математики внеслиН. Н. Воробьев, В. П. Маслов, И. В. Романовский, А. А. Корбут, Р. А.

Кунингхайм-Грин,У. Циммерманн, Г. Л. Литвинов, Г. Б. Михалкин, А. Э. Гутерман, Д. С. Голан, П. Буткович, М. Гондран, Д. Ю. Григорьев, Д. Гунаварден, И. Итенберг, Г. Кохен, Д. Д. Лоусон,У. Макэнини, Я. Н. Шитов и др.При этом учеными разрабатывались не только теоретические положения, но такжерассматривались прикладные задачи, которые формулируются и эффективно решаются в терминах идемпотентной алгебры, составляющей важный раздел тропической математики. Такие задачи изучались в работах Ф.