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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТНа правах рукописиПлотников Павел ВладимировичРЕШЕНИЕ МИНИМАКСНЫХ ЗАДАЧ РАЗМЕЩЕНИЯНА ПЛОСКОСТИ С ПРЯМОУГОЛЬНОЙ МЕТРИКОЙНА ОСНОВЕ МЕТОДОВ ИДЕМПОТЕНТНОЙАЛГЕБРЫ05.13.17 — «Теоретические основы информатики»01.01.09 — «Дискретная математика и математическая кибернетика»Диссертация на соискание учёной степеникандидата физико-математических наукНаучный руководитель:доктор физ.-мат.

наук, доцентКривулин Н.К.Санкт-Петербург20182ОглавлениеВведение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41 Элементы идемпотентной алгебры . . . . . . . . . . . . . . . . . 181.1Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .181.2Идемпотентное полуполе .

. . . . . . . . . . . . . . . . . . . . . .201.3Идемпотентная алгебра векторов и матриц . . . . . . . . . . . . .221.4Предварительные результаты . . . . . . . . . . . . . . . . . . . . .242 Решение некоторых задач тропической оптимизации . . . . . . 262.12.2Задача тропической оптимизации в матричной форме . .

. . . . .262.1.1Анализ и решение задачи . . . . . . . . . . . . . . . . . . .272.1.2Формулировка основного результата . . . . . . . . . . . . .32Решение задач оптимизации в скалярной форме . . . . . . . . . .332.2.1Решение задачи с одной переменной . . . . . .

. . . . . . .332.2.2Решение второй задачи с одной переменной . . . . . . . . .422.2.3Решение задачи с двумя переменными с ограничениями . .442.2.4Решение задачи с двумя переменными . . . . . . . . . . . .562.2.5Решение задачи с тремя переменными . . . . . . . .

. . . .633 Решение задач размещения точечного объекта на плоскостис прямоугольной метрикой и ее приложения . . . . . . . . . . . 713.1История развития задачи . . . . . . . . . . . . . . . . . . . . . . .3.2Постановка задачи размещения центрального сервера управленияв сети локальных коммуникаций . . . . .

. . . . . . . . . . . . . .3.33.47173Постановка задачи размещения центра управления системой видеонаблюдения . . . . . . . . . . . . . . . . . . . . . . . . . . . . .75Постановка задачи размещения на плоскости . . . . . . . . . . . .7733.5Решение задачи размещения на плоскости без ограничений .

. . .783.6Решение задач размещения на плоскости с ограничениями . . . .813.6.1Размещение на отрезке прямой . . . . . . . . . . . . . . . .813.6.2Размещение в прямоугольнике . . . . . . . . . . . . . . . .89Решение задачи размещения в трехмерном пространстве . . . . .933.7Заключение .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104A Программная реализация вычисления оптимальной областиразмещения точечного объекта . .

. . . . . . . . . . . . . . . . . 117A.1 Программная реализация решения минимаксной задачи размещения без ограничений на область размещения на языке R . . . . . 117A.2 Программная реализация решения минимаксной задачи размещения с ограничениями в виде отрезка прямой на языке R. . . . . 119A.3 Программная реализация решения минимаксной задачи размещения с ограничениями в виде прямоугольника на языке R . . .

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

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

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

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

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

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

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

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

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

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