Введение к работе
Актуальность проблемы Одна из первых и наиболее известных здач оптимизации - задача о размещении центров, т.о. задача гнскания в некотором множестве Хр точек (центров) наименее цаленных в некоторой метрике от множество задагашх точек Y. ри отой в зависимости от значений р (р-1 или р > 1), типа этрического пространства, в котором заданы X и Y, совпадения ли несовпадения X и Y получаем принципиально различные задачи, ак, если X - евклидова плоскость їїя, ^ = 1. Y с Е3, |Y|=3, случаем іслаесаческум задачу поиска точім наименее удаленной от аданных трех, решение которой сало известно еще Торичелли в 640 г. Обобценияілі отой задачи являются классические задачи тейнера о згратчайшеЯ связующей сети в метриках I,, Ъ, L очек на плоскости и задача Ферма о поиске точки метрического ространства, сумма взвезсшшх расстояний от которой до сданной минимальна.
Задачи о ц?і;трах в различной постановка широко
'сследуются, особенно в последнее время, в связи с их :рактическитли значениям! для различных оОлсстей исследования лераций, синтеза сетей, кластеризации, диагностики. [роСлематике задач размещоїшя центров посвящены многие обзорггав ітатьи и монографии. Ввиду трудности задач исследуются, как-гравило, их специальные случаи.
Математическая структура задачи размещения центров шределяется метрикой в пространстве возмемшх точек размещения ї способом оценки качества размещения (критерий оптимальности). 3 следствие отого существует ююго рззнообрпічпіх постановок задач размещения и литература изобилует мегодяг.я иг ресениp. Зграничимсл перечислением основных типов видач ро^'гчдрнил:
- і -
задача Штейнера на плоскости или в пространстве Rn (евклидова метрика Ь2. или сумма квадратов росстояшіп, прямоугольная метрика 1 , чебшаевская метрика L );
задача Штейнера на графо, т.е. в графовой метрике;
задача о медианах графа (графовая метрика, взвешенная суша кратчайших расстоянии, минимизация суммц расстояний);
задача о центрах графа (графовая метрика, максимум крагчаЯіши расстояний, минимизация максимального из кратчайших расстояния).
Актуальной представляется проблема выделения как новых іиіассов полиномиально разрешимых задач о центрах, так и построение алгоритмов Солее эффективных, чем известные хотя Си па частных классах задач.
Диссертационная работа посвящена исследовании следуздш задач размещения центров: задача о р-медианах графа, графовая задача Штейнера, специальная задача о р-модиане плаиарногс графа и динамическая задача Штейнера.
Цель работа :
исследовать связь размещения центров задач і субмодулярной оптимизации;
- изучить структуру оптимальних решений в специальны)
задачах о центрах (динамическая и звездочная задача Штейнера).
Научная новизна работы :
- изложены градиентные методы решения задачи о р-иедианаз
графа, как задачи минимизации специальной супермедулярно;
функции;
- установлена связь задачи Штейнера на графе і
дополнительным усле нем отсутствия смежных точек Штейнера і
задачей мшпшизации супермодулярно!.' функции и изложен
задиенттій алгоритм ее решешія;
для ыаксишзациошшх вариантов указашшх задач найдены ;енхи точности градиентных алгоритмов;
доказана оквивалентность специальной задачи о р-медианах зафа задаче покрытая гранями вершин трехмерного многогранника;
изучена динамическая задача Штейнера на плоскости. Методика исследования. Использована:
теория субмодулярных Функций;
методики оценок точности гради, гпшх алгоритмов;
- основные факти теории графов, дискретной оптимизации и
элиэдральнои комдинаторики.
Практическая значимость. Метода, разработанные в їсоертацин могут применяться при решении шюгих задач ітамизаціш размещения центров в сетях. Задачи размещения гнтров связаны с решением проблем наилучшего расположения в тределенных регионах таїпі.і систем обслуживания, как станции сорей медицинской помоецї, торговые центри, пости покарюй іраїш, фабрики, аеропорти, склади, пункты производства зтребляемого в ото:.» регионе товара я т.д.
Пубдккаїри. Результати диссертации опубликованы в печатных іботах, список которых приведен в автореферате.
Структура и объем работа. Диссертация состоит из введения, эти параграфов, списка литературы Зв (наименования) и изложена з Sf- страницах машинописного текста.