Назад в библиотеку

Исходный URL : http://www.omsu.omskreg.ru/vestnik/articles/y1999-i2/a017/article.html

РЕШЕНИЕ ЗАДАЧИ РАЗМЕЩЕНИЯ В ЕВКЛИДОВОМ ПРОСТРАНСТВЕ С ЗАПРЕЩЕННОЙ ОБЛАСТЬЮ

Г.Г. Забудский, И.В. Нежинский

Институт информационных технологий и прикладной математики СО РАН,
644099 Омск , ул. Певцова 13

1. Постановка задачи

Задачи размещения объектов часто возникают на практике и издавна привлекают к себе внимание специалистов [1-3,5,7,8]. Впервые одну из таких задач поставил Ферма в XVII веке. Она заключалась в поиске такой точки на плоскости, сумма расстояний от которой до трех заданных точек была минимальна. В дальнейшем рассматривались задачи размещения в произвольном конечномерном пространстве.

Требовалось разместить несколько объектов относительно некоторого числа фиксированных объектов с произвольными положительными удельными стоимостями связей. Такой класс задач часто называют задачами Вебера или Штейнера-Вебера [5]. Алгоритмы решения этих задач зависят от метрики, выбираемой для определения расстояний между объектами. Если метрика прямоугольная, то задача сводится к специальной задаче линейного программирования, в частности, к решению серии задач отыскания максимального потока [5, 7]. В случае евклидовой метрики задача относится к классу задач выпуклого программирования. Мы будем рассматривать задачу размещения одного объекта в евклидовом пространстве вне некоторой запрещенной области. Объект имеет произвольные положительные стоимости связей с фиксированными объектами.

Пусть в евклидовом пространстве Rⁿ зафиксированно m объектов, координаты которых обозначим через . Задана также запрещенная область - сфера с центром в точке B, радиуса r. Через c_i обозначим удельные стоимости связей между размещаемым и фиксированными объектами. Необходимо так разместить объект в допустимой области, чтобы суммарная стоимость связей была минимальной. Математическая модель задачи имеет вид.

где  

Решению многоэкстремальных задач, в частности, специальных классов, в последнее время уделяется много внимания [6, 9, 10]. Алгоритм решения задач, в которых целевая функция выпукла, а допустимая область является дополнением выпуклого множества, приведен в работах А.С. Стрекаловского [6, 10]. Нами реализован алгоритм решения задачи (1) - (2), основанный на указанном подходе с учетом специфики задачи. Проведены вычислительные эксперименты, которые показали его эффективность.

2. Алгоритм решения задачи

В дальнейшем будем предполагать, что все фиксированные объекты не лежат на одной прямой. В этом случае целевая функция строго выпукла[8]. Будем также считать, что выполнено следующее предположение: оптимальное решение задачи (1) не совпадает с оптимальным решением задачи (1) - (2). Это условие будем обозначать (*).

Класс задач со свойством (*), у которых целевая функция выпукла, а допустимая область является дополнением выпуклого множества, получил название обратно-выпуклых задач [6, 10]. Сложность решения этих задач состоит в том, что они являются многоэкстремальными. Поэтому после нахождении какого-либо экстремума необходимо иметь способ определения: является ли полученная точка локальным или глобальным экстремумом. В случае локального экстремума необходимо найти способ перехода в другой локальный минимум с лучшим значением целевой функции. Существует несколько методов решения многоэкстремальных задач. Практически все они не гарантируют нахождение глобального экстремума. К таким методам относятся: метод "тяжелого шарика", перебор локальных экстремумов с помощью рассмотрения различных начальных точек , метод "спуск-подъем-перевал", методы покрытий и др. Проблема состоит в том, что нет достаточных условий глобального экстремума. Вероятно, одним из первых, кто предложил такие достаточные условия для специального класса задач, был А.С. Стрекаловский. В его работе [6] рассматривалась следующая задача

Теорема [6]. Для того чтобы точка z являлась решением задачи (P), необходимо и достаточно, чтобы выполнялись условия

Таким образом, чтобы проверить является ли z глобальным экстремумом, необходимо решить следующую задачу:

Опишем по шагам алгоритм решения задачи (1) -(2), основанный на изложенной выше схеме с учетом специфики задачи.

Алгоритм решения задачи (1) - (2):

Шаг 1. Методом проекции градиента, начиная с , находим локальный минимум задачи. Пусть z^k точка, найденная на этом шаге.

Шаг 2. Строим R-множество следующим образом:

Шаг 3. Для каждого решаем задачу методом возможных направлений [4]

Шаг 4. Пусть , решение задачи на шаге 3. Для каждого x^j решаем задачу

Шаг 5. Найдем . Предположим, что максимум достигается в точке x^t.

Шаг 6. Если , тогда полагаем u^k+1:=x^t и возвращаемся на Шаг 1.

Шаг 7. Если , тогда Стоп. Точка z^k - глобальный оптимум.

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

Замечание 2. На шаге 1 проблема "особых" точек решалась способом, предложенным в работе [8].

3. Результаты экспериментов

Вычислительные эксперименты проводились для решения задач на плоскости и в пространстве размерности до 20. Количество фиксированных объектов варьировалось от 3 до 150. В задачах на плоскости исходные данные подбирались случайно и некоторым специальным образом. Начальная точка выбиралась в окрестности локального экстремума, не являющегося глобальным. Разрешающее множество в задачах размерности не более 10 выбиралось, как и описано в алгоритме. В задачах большей размерности, с учетом большого количества точек, брались не все симметричные точки, а лишь те, для которых выполнено неравество .

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

Замечание 3. Пусть допустимая область задачи состоит из дополнения к k непересекающимся сферам, с центрами и радиусами соответственно. Тогда решение такой задачи сводится к решению задачи (1) - (2). Действительно, пусть минимум функции (1) на всем пространствеRⁿ. Если для всех , то, очевидно, оптимальное решение исходной задачи. Если существует номер j (не более одного по условию), такой что , то решение исходной задачи находится на сфере j. Полагая B=B^j, r=r_j, решаем задачу (1) - (2) и получаем решение исходной задачи.

Аналогично рассматривается случай, когда размещается несколько объектов (более одного), не связанных между собой. Исходная задача декомпозируется на независимые подзадачи, т. е. для каждого объекта поочередно решается задача (1) - (2).

Работа выполнена при финансовой поддержке РФФИ (код проекта 97-01-00771).

Литература