Задачи размещения [1] - частный случай задач оптимизации, где главными параметрами являются координаты точек и расстояния между ними. В общем случае, цель задачи размещения включает в себя определение местоположения одного или нескольких новых объектов на плоскости или в пространстве, где уже имеются некоторые объекты, причем число возможных расположений для нового объекта обычно бесконечно [2]. Такие модели обычно включают евклидовы расстояния или другие соответствующие расстояния и непрерывны по своей природе. Поскольку модели непрерывны, они удобны с точки зрения математического анализа и в некоторых случаях могут быть вычислены точные решения.
В качестве примеров можно привести задачи оптимального размещения складов, размещения оборудования компьютерных и телекоммуникационных сетей, базовых станций беспроводных сетей и др. [3]. Подобные задачи формулируются и в теории аппроксимации, задачах оценивания в статистике [4], обработке сигналов и изображений и др. [5].
В данной работе уделяется внимание выбору функции расстояния. Расстояние - длина кратчайшего пути между двумя точками. Но путь зависит от свойств как пространства, так и способа перемещения в нем. В непрерывных пространствах чаще всего используются метрики: прямоугольная или манхэттенская (l1), евклидова (l2) и чебышевская (l∞).
Постановка задачи Вебера с метриками, основанными на угловом расстоянии
Рассмотрим пример (рис. 1). Подъемный кран или иной манипулятор на неподвижной платформе 1 имеет вращающуюся стрелу 2 с подвижным подъемным механизмом 3, перемещающимся вдоль стрелы. Вся конструкция имеет 3 степени свободы: высота h крюка 4, угол поворота стрелы φ и положение подъемного механизма на стреле r (радиус).
Если механизм переносит груз из некоторой точки A = (ar, aφ, ah) в точку B = (br, bφ, bh), механизм затрачивает некоторую энергию (совершает работу) по изменению высоты Δh = |ah - bh|, угла Δφ = δφ(aφ,bφ), и положения подъемного механизма (радиуса) Δr = |ar - br|. Здесь
?
Рис. 1. Схема механизма
В некоторой области, доступной манипулятору (h < H, r < R, где H - высота крана, R - полезная длина стрелы), имеется множество {Ai} из m точек (потребителей). В каждую i-ю точку Ai = (air, aiφ, aih) требуется доставить wi поддонов некоторого груза (стройматериалов, например). Задача состоит в нахождении некоторой точки X = (xr, xφ, xh), в которой должен быть размещен полный объем грузов таким образом, чтобы затраты на перемещение грузов манипулятором были минимальны. В общем случае, задача формулируется как
(1)
Здесь wi - неотрицательный весовой коэффициент, L(X,Ai) - функция расстояния, определяющая затраты на перемещение груза из точки X в точку Ai. Если данная функция пропорциональна евклидову расстоянию (L(X, Ai) = ||X, Ai||), то мы имеем классическую задачу Вебера с евклидовой метрикой. Но затраты (энергии, времени и т.д.) механизма не пропорциональны евклидову расстоянию. В зависимости от способа вычисления этих затрат сформулируем 2 стратегии управления манипулятором и 2 соответствующие задачи.
Стратегия 1. Минимизировать стоимость движения механизмов. Пусть стоимость вертикального перемещения крюка на 1 м составляет Ch, стоимость вращения стрелы - Cφ за 1 радиан, стоимость движения подъемного механизма вдоль стрелы (изменения радиуса) - Cr за 1 м. Тогда функция расстояния равна
(2)
и целевая функция
(3)
Стратегия 2. Минимизировать длину пути, совершаемого грузом, при условии, что одновременно осуществляется только один вид движения (вертикальное, поворот стрелы, изменение радиуса). В этом случае
(4)
Вертикальная составляющая пути |xh - aih| не зависит от других составляющих. Длина горизонтальной составляющей - это расстояние в метрике Карлсруэ (Москвы) [6].
Планировка городов Москва, Карлсруэ включает улицы 2 типов: «лучи» из центра и непересекающиеся «кольца» вокруг центра. Из точки A можно попасть в B двумя путями:
-
двигаясь по «лучу» к центру, затем по другому «лучу» из центра к B (как в случае метрики French metro [7]);
-
двигаясь вдоль «луча» из точки A, затем двигаясь по кольцевой улице.
Алгоритм на основе процедуры для метрики l1
В метрике l1 функция расстояния между точками Ai = (ai1, ai2) и X = (x1, x2) на плоскости в прямоугольных координатах задана выражением
(5)
В этом случае задача оптимизации (1) разбивается на 2 независимые задачи с целевыми функциями
(6)
(7)
Обе задачи сводятся к обобщенной задаче с целевой функцией
(8)
Данная задача решается известным алгоритмом (см., например, [1]).
В случае Стратегии 1 (см. предыдущий раздел) целевая функция задачи Вебера (1) является суммой 3 независимых функций
(9)
(10)
(11)
(12)
Решение задачи (9) - точка 
, где 
, 
и 
- решения (точки минимума) задач (9), (10) и (11) соответственно, причем задачи (10) и (12) соответствуют обобщенной задаче (8) и могут быть решены соответствующим алгоритмом ([1], [8]).
Лемма 1. Обозначим через XS множество точек минимума задачи (11). Существует индекс 
, для которого 
или 
.
Доказательство. Пусть 
- одна из точек минимума функции (11) и
.
Перейдем к полярной системе координат, такой, что (рис. 2) и условимся, что значения всех углов выражены так, что 
(случай 
исключен, т.к. 
). Такой переход возможен, т.к., независимо от выбора , можно вычесть величину из величин всех углов 
и из самого угла , получив требуемую систему координат. В новой системе координат значения
останутся прежними, следовательно, не изменится и значение целевой функции (11).
Рис. 2. Иллюстрация к Лемме 1
Разобьем множество индексов координат точек-потребителей 
на 2 подмножества:
и 
Тогда
?
?
Если 
, то
?
Поскольку 
и
?
?
Поскольку
, 
т. е.
и, поскольку 
то, если 
то 
Если 
то
и 
Таким образом, если 
, то не является точкой минимума целевой функции, если только все значения не являются таковыми.
Аналогично доказывается, что, если , то не является точкой минимума целевой функции, если только все значения не являются таковыми.
Таким образом, если - точка минимума целевой функции и все значения не являются таковыми, то оба подмножества Q- и Q+ не пусты.
Выберем 4 индекса, 2 для каждого из подмножеств (индексы могут совпадать, если подмножество содержит индекс единственной точки):
?
?
?
?
Выберем произвольное значение 
, такое, что
В этом случае
и
При этом значение целевой функции равно
Здесь
?
?
Для 
: 
Если ΔW > 0, то для
,
т.е. значение не является точкой минимума целевой функции.
Аналогично, если ΔW < 0, то для
?
?
Если ΔW = 0, то для
?
?
Таким образом, в этом случае является точкой минимума, но таковыми являются все точки интервала, включая граничные точки 
и 
.
Значение выбрано произвольно. Таким образом, если
,
то не является точкой минимума целевой функции, за исключением случая ΔW = 0. Но и в этом случае значения
и
являются точками минимума. Значения 
, 
, 
и 
выбраны из множества 
. Соответственно точкой минимума всегда является значение из множества , либо из множества 
, либо из множества 
, причем углы 
и 
равнозначны, дают равные значения целевой функции. Лемма доказана.
Таким образом, если требуется найти любую из точек минимума 
, достаточно произвести поиск в 2 множествах 
и 
. Предлагается следующий алгоритм.
1. Решить задачу (10), используя алгоритм для (8). Сохранить результат в 
.
2. Решить задачу (12) алгоритмом для задачи (8). Сохранить результат как 
.
3. Если 
, то
, иначе 
.
4. 
.
5. Для каждого 
цикл
5.1. Если 
, то
5.2. Если 
, то
.
5.3. Конец цикла 5.
6. Вывод результата 
Останов.
Оценим вычислительную сложность алгоритма. Пусть m - число точек-потребителей. Алгоритм для метрики l1 ([1], [8]) включает в себя этап сортировки координат по возрастанию с асимптотической сложностью O(m log m) и этап суммирования значений координат с линейной сложностью. Таким образом, общая вычислительная сложность этапов 1 и 2 описывается асимптотической формулой O(m log m). Шаги 5 - 5,3 содержат цикл, в котором вычисляются значения целевой функции для каждого из m - 1 значений координат 
и 
. С учетом шагов 3 и 4 значение целевой функции оценивается 2m раз. Целевая функция - линейна (асимптотическая сложность O(m)), следовательно, сложность шагов 3?5.3 алгоритма определяется как O(m2), и асимптотическая сложность всего алгоритма также находится в множестве O(m2).
Пример решения задачи
Полярные координаты точек-потребителей и соответствующие весовые коэффициенты заданы в табл. 1.
Таблица 1 Исходные данные задачи
|
i |
|
|
|
wi |
|
1 |
10 |
5 |
0 |
3 |
|
2 |
20 |
3 |
0 |
2 |
|
3 |
10 |
5 |
π/4 |
4 |
|
4 |
20 |
5 |
π/4 |
3 |
|
5 |
30 |
3 |
π/4 |
4 |
Решение. Шаг 1.
Шаг 2.
Шаг 3.
?
?
Условие 
не выполняется, 
.
Шаг 4.
Шаг 5. Для каждого i от 2 до 5 цикл. Результаты шагов 5.1-5.3 сведены в табл. 2.
Шаг 6.
Таблица 2 Решение (шаги 5.1-5.3 алгоритма)
|
i |
Шаг 5.1. значение
|
Шаг 5.1. условие
|
Шаг 5.1. значение f* |
Шаг 5.1. значение
|
Шаг 5.2. значение
|
Шаг 5.2. условие
|
Шаг 5.2. значение f* |
Шаг 5.2. значение
|
|
2 |
1,25π |
Не выполн. |
1,25π |
0 |
3,75π |
Не выполн. |
1,25π |
0 |
|
3 |
π |
выполняется |
π |
0,25π |
5π |
Не выполн. |
π |
0,25π |
|
4 |
1,25π |
Не выполн. |
π |
0,25π |
6π |
Не выполн. |
π |
0,25π |
|
5 |
1,25π |
Не выполн. |
π |
0,25π |
6π |
Не выполн. |
π |
0,25π |
Выводы
Задачи оптимального размещения формулируются в виде задачи Вебера с метрикой, основанной на измерении углового расстояния в том случае, если для транспортировки предполагается использование механизмов с телескопической стрелой. Решение задач Вебера с рассмотренной метрикой, основанной на измерении углового расстояния, сводится к решению задач с прямоугольной метрикой (l1) и выполняется за полиномиальное время. Эффективность алгоритма доказана аналитически, приведен пример решения задачи.
Рецензенты:
-
Антамошкин А.Н., д.т.н., проф., зав. кафедрой математического моделирования и информатики ФГОУ ВПО «Красноярский государственный аграрный университет», г. Красноярск;
-
Ступина А.А., д.т.н., проф., зав. кафедрой «Экономика и информационные технологии менеджмента» института управления бизнес-процессами и экономики Сибирского федерального университета.
Работа поступила в редакцию 06.09.2012.