Оптимизация и зона Парето в задаче о 4-городах


Изобразить
Условие на минимизацию
n =
Положение 4-х городов
x1:
y1:
x2:
y2:
x3:
y3:
x4:
y4:
Приоритет
k1
k2
k3
k4
Точность вычислений
nx
F = -??-
при x = -??-
при y = -??-
s1 = -??-
s2 = -??-
s3 = -??-
s4 = -??-

Оптимизация и зона Парето в задаче о 4-x городах. Положения городов задается в начале текста скрипта. Паритет того или иного города задается коэффициентами: k1,k2,k3,k4. Точность (количество точек перебора) задается для вычислительного процесса и на графику не влияет.

Условие 1.
Завод по переработки мусора решили построить на трассе р11-р12. Все 4 города (p1,p2,p3,p4) стремятся построить завод (точка на р11-р12) как можно ближе. 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
f4 = Math.sqrt((x4-x)*(x4-x)+(y4-y)*(y4-y)) -> min
Или тоже самое общая сумма растояний должна быть минимальной).
F = f1+f2+f3+f4 -> min
где р1, p2, p3, р4 - местоположение городов
x1=10; y1=10;
x2=85; y2=50;
x3=50; y3=70;
x4=50; y4=70;
Геометрического решения этой задачи нет.
Поэтому решаем численным методом: перебирать варианты на прямой и выбрать наилучший. Проверить работу алгоритм можно, совместив попарно координаты 4-х городов. В этом случае задача решается геометрически - способом Герона: угол падения равен углу отражения.

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

Условие 3.
Пусть расстояния до завода д.б. одинаковыми. Для двух городов такая задача решается геометрически - окружность проведенная через две точки касательно к прямой в точке касания дает искомую точку. Найти же точку на прямой, равноудаленную от четырех точек нельзя. Поэтому стоит задача: найти наилучшее решение.
Сформулируем условия на минимум частных ЦФ:
f1 = |p1-p|-c -> 0 -> min;
f2 = |p2-p|-с -> 0 -> min;
f3 = |p3-p|-с -> 0 -> min,
f4 = |p3-p|-с -> 0 -> min,
Зоной Парето будет отрезок между частными ЦФ, где где-то должно быть оптимальное решение. Пусть глобальный минимум также стремится к минимуму:
F = |f1-с1|+|f2-с2|+|f3-с3|+|f4-с4| -> min
Что-то вычисляется и строится график ЦФ. Проверить алгоритм можно совместив попарно координаты 4-х городов. В этом случае рассояния всех 4-х городов будет примерно одинаковыми. рисунок .
Примечание. Посмотреть частные ЦФ: f1,f2,f3,f4, надо задать "Условия минимизации", числами 91,92,93,94 соответственно.
Другие варианты условий на оптимизацию см. скрипты:
1) о трех городах и оптимальном расположении завода на плоскости (2-мерном пространстве),
2) о трех космических станциях и станции дозаправки в 3-мерном простанстве и, наконец,
3) о трех галактических станциях и станции обеспечения в 4-мерном простанстве.