Диссертация (1150701), страница 10
Текст из файла (страница 10)
Задачи размещенияобъектов в пространстве образуют широкий класс задач оптимизации. Задачи размещения можно разделить по способу задания ограничений и по выборукритерия оптимальности. Основная цель при решении состоит в определенииоптимального места расположения нового объекта с учетом уже имеющихся.Изучение задач размещения началось, по-видимому, в 1909 году, когда Альфред Вебер [104] предложил решить задачу по определению местонахожденияотдельного склада.
При этом было необходимо минимизировать суммарное расстояние между складом и несколькими клиентами. В середине 1960-х годовтеория размещения объектов продолжила свое развитие. Наряду с большим72количеством работ в этой области стоит отметить статью С. Хакими [105]. Вэтой работе был предложен способ определения местоположения полицейскихучастков в системе шоссе. При описании задачи размещения следует рассматривать два множества: объекты, которые уже расположены в точках или намаршрутах в области исследования, и объекты, для которых оптимальное место расположения следует найти. Также нужно задать параметры пространства, в котором объекты находятся, и выбрать метрику, в которой необходимооценивать и оптимизировать расстояние или время.Среди публикаций, посвященных задачам размещения, можно отметить работу Х.
Эйселта и В. Марианова [106], в которой приведен обзор задач размещения. В работе Р. Френсиса [107] изучены часто встречающиеся типы задачразмещения одного или нескольких объектов на плоскости. Примеры решениязадач размещения на графах предложены в работах П. Мирчандэни и Р. Фрэнсиса [108] и М. Даскина [109]. В работах З. Дрезнера [110], а также С. Никелаи Ж. Пуэрто [111] проведены обзоры задач размещения и варианты их решения.
Традиционно рассматривают два типа задач размещения: минисуммные(минимизируется сумма расстояний) [112, 113] и минимаксные (минимизируется максимальное расстояние) задачи размещения [114, 115].Для описания и решения минимаксных задач размещения с прямоугольнойи чебышевской метрикой достаточно полезным оказывается применение методов тропической оптимизации.
Такие задачи могут быть сформулированы втерминах одного из идемпотентных полуколец – (max ,+)-алгебры. Обзор тропических задач оптимизации приведен в работах В. Н. Колокольцова [116] иН. К. Кривулина [49]. Одномерная задача размещения на графах рассмотрена в работах [20, 21]. При этом задача сводится к минимизации рациональнойфункции в терминах тропической математики.
Однако, полученные решенияне удается записать в многомерном случае, что сужает область применениярезультатов.Решение задач пространственного размещения объектов зависят от метрики, в которой вычисляется расстояние между объектами. Так в работе [71] предложен метод решения различных задач размещения в чебышевской метрике наоснове спектральной теории матриц тропической математики.73В этом разделе будет изучена минимаксная задача размещения на плоскостис прямоугольной метрикой (задача Ролса), которая может быть представленав терминах идемпотентной алгебры. Подход к решению основывается на преобразовании задач размещения к экстремальным задачам, решение которыхописанно в главе 2.В ходе исследования были получены аналитические зависимости, предлагающие на основе известных данных о размещении обслуживаемых объектов(групп населения, камер видеонаблюдения или иных источников потока информации, пожароопасных объектов и др.) найти оптимальные зоны размещения обслуживающих объектов (например, маршрутизаторов, серверов, центровуправления систем видеонаблюдения и т.д.).
При этом требуется разместить новый обслуживающий объект так, чтобы минимизировать расстояние от этогообъекта до самого удаленного из обслуживаемых объектов.Важно подчеркнуть, что полученные результаты позволяют указать не только одну точку, где размещение будет оптимальным, а выбрать зону, поле оптимального размещения.
Это весьма важно с прикладных позиций, т.к. позволяетучесть при проектировании возможность использования, например, земельныхучастков или зданий и сооружений.Кроме того, важным преимуществом исследуемого подхода является простота итоговых формульных зависимостей, что позволяет легко использоватьего на практике при решении задач пространственного планирования при создании и развитии информационных и иных систем.3.2Постановка задачи размещения центрального серверауправления в сети локальных коммуникацийРешение задач размещения точечного объекта на плоскости (задача 1центра) находит применение при оптимизации процесса сбора, обработки и хранения информации. Рассмотрим в качестве примера задачу, появляющуюся приразмещении аппаратного комплекса обработки интернет-трафика (центрального сервера управления сетью локальных коммуникаций), в условиях городскойинфраструктуры.74Пусть необходимо собирать, обрабатывать и хранить информацию, поступающую от клиентов локальной сети.
Координаты этих клиентов задаютсявекторами = (1 ,2 ) ∈ R2 , где = 1, . . . ,. Задача размещения состоит втом, чтобы найти оптимальное местоположение центрального сервера, котороезадано неизвестным вектором = (1 ,2 ) . При этом, необходимо минимизировать расстояние от этого центра до самого дальнего клиента. Основная задачасостоит в снижении величины затухания сигнала, которое прямо пропорционально зависит от расстояния (длины кабеля), что и оправдывает минимакснуюпостановку задачи.Прокладка оптоволоконных и проводных сетей осуществляется вдоль уличной сети. Поэтому для описания и решения задач оптимального размещенияможет быть использована прямоугольная (манхэттенская метрика).
При этом,по различным причинам (градостроительные регламенты, социальные ограничения, требования радиоэлектронной совместимости, соображения информационной безопасности и др.) могут возникать ограничения на допустимую областьразмещения.Пусть на плоскости R2 имеются два вектора = (1 ,2 ) и = (1 ,2 ) .Расстояние между этими векторами в прямоугольной метрике вычисляется поформуле(,) = |1 − 1 | + |2 − 2 |.Тогда задача 1-центра для сети локальных коммуникаций состоит в поискеминимума функции() = max (( ,) + ) = max (|1 − 1 | + |2 − 2 | + ) = (1 ,2 ),1≤≤1≤≤которая определяет максимальное по всем расстояние в прямоугольной метрике от центра управления системой (сервера) до клиентов с учетом дополнительного слагаемого .
Числа могут отражать дополнительные затраты,связанные, например, с важностью объектов или с особенностями их внутренней планировки. В данной постановке задачи, эти числа могут иметь смыслвысоты (вертикальной координаты) объекта.75В общем виде задачи размещения центра управления (сервера) локальнойсетью принимает следующий вид: = min2 ().∈R2HHHH § *HHHH HHHHHHHHHHH HHHHH§ HHHH HHHHH HH HHHHHHH§§ HHHHHHHHHHH HHH HHHHHHHHHHHHHH HH H HHHH HHHHHHHHH HHHHHHHH§§ HHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHHHH HHHHH(1 ,2 )HHHHHHHHHHHHHHHHHH HHHHHHHHH§ HHHHHHHHHHHHHHHHH j 1HРисунок 3.1 - Размещения центрального сервера управления в сети локальныхкоммуникаций3.3Постановка задачи размещения центра управлениясистемой видеонаблюденияРассмотрим задачу размещения центра управления системой видеонаблюдения в здании (задача 1-центра). Пусть необходимо собирать, обрабатыватьи хранить информацию от видеокамер внутреннего и наружного наблюдения.
Координаты этих объектов задаются векторами = (1 ,2 ,3 ) ∈ R3 ,где = 1, . . . ,. Задача размещения состоит в том, чтобы найти оптимальное76положение центра управления, хранения и обработки информации, заданноевектором = (1 ,2 ,3 ) .Необходимо решить задачу минимизации расстояния от этого центра до наиболее удаленной камеры. При этом преследуется цель, состоящая в повышениикачества информационного обмена за счет снижения уровня затухания сигнала,которое находится в прямой пропорциональной зависимости от длины кабеля(расстояния).
Указанные моменты оправдывают минимаксную постановку задачи. В силу того, что кабели внутри одного этажа чаще всего прокладываютвдоль линий разделения пола, стен и потолка, а межэтажные перекрытия проходятся по вентиляционным шахтам, можно считать, что расстояние междулюбыми двумя объектами измеряется в прямоугольной метрике.Пусть в трехмерном пространстве R3 имеются два вектора = (1 ,2 ,3 ) и = (1 ,2 ,3 ) . Расстояние между этими векторами в прямоугольной метрикевычисляется по формуле(,) = |1 − 1 | + |2 − 2 | + |3 − 3 |.Тогда задача 1-центра для системы видеокамер состоит в поиски минимумафункции() = max (( ,)+ ) = max (|1 −1 |+|2 −2 |+|3 −3 |+ ) = (1 ,2 ,3 ),1≤≤1≤≤которая определяет максимальное по всем расстояние в прямоугольной метрике от центра управления системой (сервера) видеонаблюдения до видеокамер с учетом дополнительного слагаемого .
Числа могут отражать дополнительные затраты, связанные с важностью объекта.В общем виде задача размещения центра управления системой видеонаблюдения принимает следующий вид: = min3 ().∈R77HHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH ыйHHHH ЭтH i3 6HHHH HHаHHH HHHHHH жHHHHHHHHi HHHHHHHHHHHH HHHHHHHHHHHH HHHHHHH iHH HHH HHHHiHHHH HHHHHHHHHHHHHHHHHHHHHH HHHHHH* 2HHHHHHHHHHHHHHHHHHHHH ПеHHHHHHрвыHHHHHHHH й этHHHHHаHHHHHHH жHHH HHHHHH HHHH (,,)H1 2 3H HHHHHHHHH HHHHHHH HHHHHHHHHHHH HHHHH HHHHHHj 1Hiii§ Рисунок 3.2 - Размещения центра управления системой видеонаблюдения вздании [1].3.4Постановка задачи размещения на плоскостиРассмотрим минимаксную задачу размещения на плоскости с прямоугольной метрикой и ограничениями на допустимую область размещения.
Предположим, что на множестве R2 задан набор точек и определено некоторое допустимое подмножество ⊂ R2 . Требуется разместить новую точку на множестве так, чтобы минимизировать расстояние от этой точки до самой удаленной отнее из числа заданных точек.Пусть на плоскости R2 имеются два вектора = (1 ,2 ) и = (1 ,2 ) .Расстояние между этими векторами в прямоугольной метрике вычисляется по78формуле(,) = |1 − 1 | + |2 − 2 |.Рассмотрим набор точек = (1 ,2 ) ∈ R2 и чисел ∈ R, заданных длявсех = 1, . . . ,. Для произвольного вектора = (1 ,2 ) введем функцию() = max (( ,) + ) = max (|1 − 1 | + |2 − 2 | + ) = (1 ,2 ),1≤≤1≤≤которая определяет максимальное по всем расстояние в прямоугольной метрике от точки до точки с учетом дополнительного слагаемого .Задача размещения, которую иногда называют задачей Ролса или задачейпосыльного, состоит в том, чтобы найти все векторы , которые обеспечиваютминимумmin ().∈3.5(3.1)Решение задачи размещения на плоскости без ограниченийСуществует геометрическое решение задачи (3.1) без ограничений на множество размещения [62,63], известной как задача Ролса или задача посыльного.Алгебраическое решение в терминах тропической математики было дано в работе [74], однако, оставалось неясным является ли оно полным.Чтобы построить полное решение сначала представим задачу в терминахидемпотентного полуполя Rmax ,+ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
