Задачи размещения [1] - частный случай задач оптимизации, где главными параметрами являются координаты точек и расстояния между ними. В общем случае, цель задачи размещения включает в себя определение местоположения одного или нескольких новых объектов на плоскости или в пространстве, где уже имеются некоторые объекты, причем число возможных расположений для нового объекта обычно бесконечно [2]. Такие модели обычно включают евклидовы расстояния или другие соответствующие расстояния и непрерывны по своей природе. Поскольку модели непрерывны, они удобны с точки зрения математического анализа и в некоторых случаях могут быть вычислены точные решения.

В качестве примеров можно привести задачи оптимального размещения складов, размещения оборудования компьютерных и телекоммуникационных сетей, базовых станций беспроводных сетей и др. [3]. Подобные задачи формулируются и в теории аппроксимации, задачах оценивания в статистике [4], обработке сигналов и изображений и др. [5].

В данной работе уделяется внимание выбору функции расстояния. Расстояние - длина кратчайшего пути между двумя точками. Но путь зависит от свойств как пространства, так и способа перемещения в нем. В непрерывных пространствах чаще всего используются метрики: прямоугольная или манхэттенская (l₁), евклидова (l₂) и чебышевская (l_∞).

Рассмотрим пример (рис. 1). Подъемный кран или иной манипулятор на неподвижной платформе 1 имеет вращающуюся стрелу 2 с подвижным подъемным механизмом 3, перемещающимся вдоль стрелы. Вся конструкция имеет 3 степени свободы: высота h крюка 4, угол поворота стрелы φ и положение подъемного механизма на стреле r (радиус).

Если механизм переносит груз из некоторой точки A = (a_r, a_φ, a_h) в точку B = (b_r, b_φ, b_h), механизм затрачивает некоторую энергию (совершает работу) по изменению высоты Δh = |a_h - b_h|, угла Δφ = δ_φ(a_φ,b_φ), и положения подъемного механизма (радиуса) Δr = |a_r - b_r|. Здесь

?

В некоторой области, доступной манипулятору (h < H, r < R, где H - высота крана, R - полезная длина стрелы), имеется множество {A_i} из m точек (потребителей). В каждую i-ю точку A_i = (aⁱ_r, aⁱ_φ, aⁱ_h) требуется доставить w_i поддонов некоторого груза (стройматериалов, например). Задача состоит в нахождении некоторой точки X = (x_r, x_φ, x_h), в которой должен быть размещен полный объем грузов таким образом, чтобы затраты на перемещение грузов манипулятором были минимальны. В общем случае, задача формулируется как

 (1)

Здесь w_i - неотрицательный весовой коэффициент, L(X,A_i) - функция расстояния, определяющая затраты на перемещение груза из точки X в точку A_i. Если данная функция пропорциональна евклидову расстоянию (L(X, A_i) = ||X, A_i||), то мы имеем классическую задачу Вебера с евклидовой метрикой. Но затраты (энергии, времени и т.д.) механизма не пропорциональны евклидову расстоянию. В зависимости от способа вычисления этих затрат сформулируем 2 стратегии управления манипулятором и 2 соответствующие задачи.

Стратегия 1. Минимизировать стоимость движения механизмов. Пусть стоимость вертикального перемещения крюка на 1 м составляет C_h, стоимость вращения стрелы - C_φ за 1 радиан, стоимость движения подъемного механизма вдоль стрелы (изменения радиуса) - C_r за 1 м. Тогда функция расстояния равна

(2)

и целевая функция

(3)

Стратегия 2. Минимизировать длину пути, совершаемого грузом, при условии, что одновременно осуществляется только один вид движения (вертикальное, поворот стрелы, изменение радиуса). В этом случае

(4)

Вертикальная составляющая пути |x_h - aⁱ_h| не зависит от других составляющих. Длина горизонтальной составляющей - это расстояние в метрике Карлсруэ (Москвы) [6].

Планировка городов Москва, Карлсруэ включает улицы 2 типов: «лучи» из центра и непересекающиеся «кольца» вокруг центра. Из точки A можно попасть в B двумя путями:

1. двигаясь по «лучу» к центру, затем по другому «лучу» из центра к B (как в случае метрики French metro [7]);
2. двигаясь вдоль «луча» из точки A, затем двигаясь по кольцевой улице.

В метрике l₁ функция расстояния между точками A_i = (aⁱ₁, aⁱ₂) и X = (x₁, x₂) на плоскости в прямоугольных координатах задана выражением

 (5)

В этом случае задача оптимизации (1) разбивается на 2 независимые задачи с целевыми функциями

 (6)

 (7)

Обе задачи сводятся к обобщенной задаче с целевой функцией

 (8)

Данная задача решается известным алгоритмом (см., например, [1]).

В случае Стратегии 1 (см. предыдущий раздел) целевая функция задачи Вебера (1) является суммой 3 независимых функций

 (9)

 (10)

 (11)

 (12)

Решение задачи (9) - точка , где ,  и - решения (точки минимума) задач (9), (10) и (11) соответственно, причем задачи (10) и (12) соответствуют обобщенной задаче (8) и могут быть решены соответствующим алгоритмом ([1], [8]).

.

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

останутся прежними, следовательно, не изменится и значение целевой функции (11).

Разобьем множество индексов координат точек-потребителей  на 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 - число точек-потребителей. Алгоритм для метрики l₁ ([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(m²), и асимптотическая сложность всего алгоритма также находится в множестве O(m²).

Полярные координаты точек-потребителей и соответствующие весовые коэффициенты заданы в табл. 1.

Решение. Шаг 1.

Шаг 2.

Шаг 3.

?

?

Условие  не выполняется, .

Шаг 4.

Шаг 5. Для каждого i от 2 до 5 цикл. Результаты шагов 5.1-5.3 сведены в табл. 2.

Шаг 6.

Выводы

Задачи оптимального размещения формулируются в виде задачи Вебера с метрикой, основанной на измерении углового расстояния в том случае, если для транспортировки предполагается использование механизмов с телескопической стрелой. Решение задач Вебера с рассмотренной метрикой, основанной на измерении углового расстояния, сводится к решению задач с прямоугольной метрикой (l₁) и выполняется за полиномиальное время. Эффективность алгоритма доказана аналитически, приведен пример решения задачи.

• Антамошкин А.Н., д.т.н., проф., зав. кафедрой математического моделирования и информатики ФГОУ ВПО «Красноярский государственный аграрный университет», г. Красноярск;
• Ступина А.А., д.т.н., проф., зав. кафедрой «Экономика и информационные технологии менеджмента» института управления бизнес-процессами и экономики Сибирского федерального университета.

Работа поступила в редакцию 06.09.2012.