ОПТИМИЗАЦИЯ И ЗОНА ПАРЕТО В ЗАДАЧЕ О ТРЕХ ГОРОДАХ


Условие на минимизацию
n =
Положение городов
x1:
y1:
x2:
y2:
x3:
y3:
Область ограничений по х
xmin
xmax
Область ограничений по y
ymin
ymax
Приоритет
k1
k2
k3
Константы
c1
c2
c3
Точность вычислений
nx
ny
Оптимизировать вычисления
1 - да, 0 - нет

F = -??-
при x = -??-
y = -??-
f1 = -??-
f2 = -??-
f3 = -??-
ЦФ направить в систему Вектор:

Оптимизация и зона Парето в задаче о трех городах. Положения городов задается в начале текста скрипта. Константы - расстояния на котором должен находится завод в условиях 2-5. Паритет того или иного города задается соответствующими коэффициентами. "Оптимизировать вычисления" означает перебор точек происходит в треугольнике р1-р2-р3. Для условия 3 "Оптимизировать вычисления" значение 0 - не оптимизировать вычисления, 1 - оптимизировать вычисления.

Условие 1.
Пусть все три города (p1,p2,p3) стремятся построить завод (opt) как можно ближе.
f1 = Math.sqrt((x1-x)*(x1-x)+(y1-y)*(y1-y) -> min
f2 = Math.sqrt((x2-x)*(x2-x)+(y2-y)*(y2-y)) -> min
f3 = Math.sqrt((x3-x)*(x3-x)+(y3-y)*(y3-y)) -> min
где р1, p2, p3 - местоположение городов
x1=10; y1=10;
x2=85; y2=50;
x3=50; y3=70;
Решением задачи будет поиск общего минимума
F = f1+f2+f3 -> min
Геометрически решением задачи является точка Ферма или точка Торичелли

Для тупого треугольника точка Ферма находится в вершине тупого угла (более подробно читайте об этом здесь).

Условие 2 (поставьте приоритет k1, равный 2. Почему? читайте ниже).
Город p1 поставил условие: расстояние до завода д.б. величина постоянная. Геометрически это будет окружность (r=c), проведенная из точки местоположения 1-го города. Два других же города хотят построить завод как можно ближе. Условие первого города можно также свести к условию на минимум.
f1 = |p1-p|-c -> 0 -> min
f2 = |p2-p| -> min
f3 = |p3-p| -> min
Таким образом, общая проблема сводится к поиску общего глобального минимума, как и в первой случае:
F = f1+f2+f3 -> min
Однако, если искать просто глобальный минимум, то условие первого города все равно не будут удовлетворены, местонахождение завода окажется в точке минимума суммы расстояний - фактически в том же положении, что и при первом условии см. рис. слева.
На практике такая задача решается через построения поверхностей отклика (изолиний). Однако можно обойти эти громоздкие построения: для 1-го города можно ввести приоритет, например, k1 = 2 (задается в диалоге):
F = 2*f1+f2+f3 -> min
В этом случае, как видно на втором рис. в центре условие для 1-го города с некоторой степенью точности выполнено.

Увеличение приоритета больше, чем в два раза, уже не желательно (точка на окружности начинает скатываться по окружности в сторону увеличения суммы расстояний).
Зоной Парето (рис. справа) будет область между частными целевыми функциями (ЦФ). Для первого города частной ЦФ будет окружность, то она и будет участвовать в определении зоны Парето.
"Изобразить в Векторе" означает посмотреть ЦФ и проанализировать, правильно ли строится ЦФ, сколько минимумов/максимумов на ЦФ существует и, соответственно, оценить правильно ли минимум/максимум выбран. На рисунках ниже показаны как выглядят в системе "Вектор" Цф для условия 1: без приоритета (на проекциях xy и Fx) и с приоритетом (рис. справа).


Условие 3.
Пусть расстояния до завода д.б. одинаковыми f1 = |p1-p|-c -> 0 -> min;
f2 = |p2-p|-с -> 0 -> min;
f3 = |p3-p|-с -> 0 -> min,
которое также можно свести к поиску общего глобального минимума:
F = f1+f2+f3 -> min,
который при своем минимуме даст оптимальные параметры ЦФ и местоположения завода. Геометрически решение находится в центре окружности, проведенной через три точки (местоположения трех городов)
.
Приоритет здесь не играет никакой роли. В задаче на компромисс и заранее определить зону Парето сложно, которая может выходить за пределы треугольника и поэтому вычисления происходят не в ообласти треугольника, в прямоугольной области, поэтому команду "Оптимизировать вычисления" не применять. На рис. справа показано, как выглядит условия на компромисс (ЦФ) в системе"Вектор" на прпоекциях xy и Fx.

Условие 4.
Два города p2 и p3 хотят построить завод на заданном расстояния друг от друга. Третий город пусть будет не в счет. Данные условия также можно свести к условию, стремящиеся к минимуму: f2 = |p2-p|-c2 -> 0 -> min;
f3 = |p3-p|-с3 -> 0 -> min;
Глобальный минимум также сводится к поиску минимума F = |f1+f2| -> min
Известно, что решений будет два - две точки пересечения двух окружностей.

Поэтому, при численном подходе, надо смотреть, какое из решений выпало; если оно не удовлетворяет, надо сужать зону ограничений. В нашем случае все нормально. Зоной Парето будет площадь, ограниченная двумя окружностямя (r = c2,c3), которые являются частными ЦФ.

Условие 5.
Два города p2 и р3 хотят построить завод на заданном расстояния, а первый стремится к минимуму. Данные условия также можно сделать однородными: f1 = p1-p -> min;
f2 = |p2-p|-с1 -> min;
f3 = |p3-p|-с3 -> min,
Глобальный минимум также сводится к поиску минимума. Здесь введем и коэффициенты паритета. F = k1*f1 + |k2*f2-c2| + |k3*f3-c3| -> min
Решение. Надо найти компромисс (точку пересечения) между вторым и третьим городами, а затем минимум ЦФ между этим решением условием для первого города. Паритет второго города (k2 = 1.25), дает результат условия 4, а изменяя паритет первого города, можно искать местоположение завода на прямой между компромиссом (второго и третьего городов) и первым городом. На рис. паритет 1-го города задан 1.75.

Зоной Парето будет площадь, ограниченная двумя окружностямя (r = c2,c3) и точкой местоположения 1-го города, которые являются частными ЦФ.

Условие 6.
Первый город стремится построить завод как можно дальше, два других как можно ближе. Поменяв у ЦФ первого города знак, получим что все три ЦФ опять будут стремится к минимуму.
f1 = -(p1-p) -> min;
f2 = p2-p -> min;
f3 = p3-p -> min,
Глобальный минимум (как утверждает [1]) сводится к поиску минимума
F = -f1 + f2 + f3 -> min,
который (как и искомое решение) находиться в зоне Парето (между частными ЦФ) - на отрезке прямой линии между вторым и третьим городами. Так как мы ищем минимум суммы расстояний, то искомое местоположение должно лежать в точке пересечения перпендикуляра, опущенного из р1 на отрезок p2-p3 (фактически это в т. р3). Однако решить задачу, поменяв знак, не удалось. Есть другой решение, знак не менять, а искать общий минимум в зоне Парето, т.е на отрезке p2-p3. Что и сделано в скрипте (точка скатилась к р3, т.к. перпендикуляр от р1 к р2-р3 оказался там).

Условие 7.
Пусть третий город стремится построить завод как можно дальше, два других как можно ближе. Здесь глобальный минимум
F = f1 + f2 + f3 -> min,
будем искать в зоне Парето между частными ЦФ - на отрезке p1-p2 между первым и вторым городами. Так как мы ищем минимум суммы расстояний, то искомое решение должно быть в точке пересечения перпендикуляра, опущенного из р3 на отрезок p1-p2. Вводя же приоритет для города р2, картину можно изменить.



Условие 8.
Первый и второй город стремятся построить завод как можно дальше, третий как можно ближе. Глобальный минимум также сводится к поиску минимума:
F = -f1 - f2 + f3 -> min,
который (как и искомое решение) находится в зоне Парето (между частными ЦФ), которые находитя в точке местоположения 3-го города. Замена знака на противоположный здесь прошла и потверждается в системе Вектор даже на прямоугольной сетке перебора. Для условий 6-9 команда, там, где используется область Парето, команда "Оптимизировать вычисления" никакой роли не играет.

Условие 9.
Первый город стремятся построить завод на заданном расстоянии с, а два других как можно дальше. Решение будет на изолинии сечения первой ЦФ (зоне Парето для всех ЦФ). Поэтому перебирая точки на изолинии, как в нашем случае, или группе изолиний, в случае размерности ЦФ более трех, можно однозначно решить задачу. Более детально этот случай рассмотрен в скриптах Здесь же сначала попробуем решить задачу по принципу общей оптимизации. f1 = |p-c1| -> min; f2 = |p2-p| -> max; f3 = |p3-p| -> max. Как утверждают некоторые исследователи, сменив знак у 2-й и 3-й ЦФ на противоположный, общую цель можно свести к поиску общего минимума: F = f1 - f2 - f3 -> min,
Однако замена знака на противоположный положительного результата не дает. Поэтому решение классическое - в области Парето на изолинии 1-й частной ЦФ: f1=c1, Известно, что это окружность радиуса с1 с центром в точке р1.

В более общем случае изолинии строятся через систему "Вектор" - мощнейшего инструмента этой системы.

Примечание. Рассматриваемый скрипт 3-х ЦФ является инвариантным, т.е., задавая в тексте скрипта свои формулы для ЦФ и диапазон ограничений по координатам x и y, можно моделировать и решать новые задачи. Точность вычислений зависит от количества перебираемых точек на ЦФ, которое можно (nx,ny < 200) изменять по своему усмотрению.

ЛИТЕРАТУРА и ИСТОЧНИКИ

1. Мащунин Ю.К. Исследования и разработка методов решения многокритериальных задач оптимизации в приложении к сложным иерархическим системам. Владивосток: ИАПУ, 1984. - 24 с. Афтореферат диссертации на соискание к.т.н.

2. Мащунин Ю.К. Методы и модели векторной оптимизации. М.: Наука 1986. 141 с.

3. Седых В.И., Болотов В.П., Машунин Ю.К. Справочник. Парето-оптимальное моделирование и анализ инженерных задач. Владивосток: ДВГМА, 1994. - 71 с.

4. Седых В.И., Болотов В.П., Машунин Ю.К., Сатаев А.Г. ПАРЕТО-ОПТИМАЛЬНОЕ МОДЕЛИРОВАНИЕ ИНЖЕНЕРНЫХ ЗАДАЧ. Статья в формаде pdf на странице http://vm.msun.ru/Cbornik.htm здесь.

5. Вильфредо ПАРЕТО - основоположник парето-оптимального моделирования.

6. Подборка о Парето из Интернета здесь