Оптимизация местоположения космических станций и пункта дозаправки


Условие минимизации
n =
Область ограничений по х
xmin
xmax
Область ограничений по y
ymin
ymax
Область ограничений по z
zmin
zmax
Приоритет
k1 k2 k3
Константы
c1
c2
c3
Точность вычислений
nx
ny
nz
Оптимизировать вычисления
1 - да, 0 - нет

оптимум F = -??-
полученный при: x = -??-
y = -??-
z = -??-
f1 = -??-
f2 = -??-
f3 = -??-
Cечения ЦФ в т. min в Вектор

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

Условие 1.
Три космические станции p1,p2,p3 стремятся, чтобы пункт дозаправки p был расположена как можно ближе.
f1 = Math.sqrt((x1-x)*(x1-x)*1+(y1-y)*(y1-y)*1+(z1-z)*(z1-z)) -> min
f2 = Math.sqrt((x2-x)*(x2-x)*1+(y2-y)*(y2-y)*1+(z2-z)*(z2-z)) -> min
f3 = Math.sqrt((x3-x)*(x3-x)*1+(y3-y)*(y3-y)*1+(z3-z)*(z3-z)) -> min
где р1, p2, p3 - местоположение станций
x1=10; y1=10; z1=15;
x2=85; y2=50; z2=25;
x3=50; y3=70; z3=60;
Решением задачи будет поиск общего глобального минимума
F = f1+f2+f3 -> min
Геометрическим решением задачи является точка Ферма (Торичелли) зоны Парето. При этом, оперируя коэффициентами приоритета (<=1 k <=2), можно создать более выгодные условия той или иной станции.

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

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

Условие 4.
Две станции p2 и p3 хотят построить пункт дозаправки на заданном расстояния друг от друга. Третья станция не в счет. Данные условия также можно свести к поиску минимума: f2 = |p2-p|-c2 -> 0 -> min;
f3 = |p3-p|-с3 -> 0 -> min;
Глобальный минимум также стремится к минимума F = |f1+f2| -> min
Решений будет множество точек, лежащих на окружности пересечения двух сфер. Можно поставить дополнительное условие, например, чтобы точка из этого множества была выбрана ближайшая к станции 1 (см. решение условия 5). Зоной Парето будет пространство между двумя сферами (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*ff3-c3| -> min
Решение. Надо найти компромисс (окружность пересечения) между второй и третьей станциями, а затем найти минимум ЦФ между окружностью и точкой - условием для первого города. Зоной Парето будет пространство, ограниченная двумя сферами (r = c2,c3) и точкой местоположения 1-го города. Решение данного условия найдено, с той точностью, сколько задано переборов в зоне поиска. Решение можно улучшить: сузив область ограничений, непосредственно в 3-мерном простанстве, или, вообще, перебор выполнять в плоскости треугольника p1-p2-p3, зная (исключая условие 3), что оптимальной решение находится в этой зоне.
"Изобразить в Векторе" означает построить ЦФ по сечениям, проходящим через точку минимума и проанализировать, правильно ли строится ЦФ, сколько минимумов/максимумов на ЦФ существует и, соответственно, оценить правильно ли минимум/максимум выбран. Вот как выглядит в системе "Вектор" Цф (рис.) условие 1 на проекциях: xy, Fx и Fy.
Интересно посмотреть, как выглядит ЦФ в системе "Вектор" см. рис. на проекциях xy и Fx.

Резюме. Режим "Оптимизировать вычисления" значительно повышает точность вычислений и сводит задачу к двумерной.
Как и в задаче о городах добавим условия 6-8.

Условие 6.
Первая станция стремится построить пункт дозаправки как можно дальше, две другие как можно ближе. Общий глобальный минимум находиться в зоне Парето (между частными ЦФ) - на отрезке прямой линии между второй и третьей станциями и будет лежать в точке пересечения перпендикуляра, опущенного из р1 на отрезок p2-p3.

Условие 7.
Пусть третья станция стремится построить пункт дозаправки как можно дальше, две другие как можно ближе. Здесь глобальный минимум будем искать в зоне Парето (между частными ЦФ) - на отрезке p1-p2 между первой и второй станциями. Так как мы ищем минимум суммы расстояний, то искомое решение должно быть в точке пересечения перпендикуляра, опущенного из р3 на отрезок p1-p2.

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

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