Лекция 6. ВЕКТОРНО-ГРАФИЧЕСКИЙ АНАЛИЗ В МНОГОКРИТЕРИАЛЬНЫХ ЗАДАЧАХ

 

С О Д Е Р Ж А Н И Е
1. Введение в проблему

Постановка 1.                    F(Х) = {f1(p) -> min;
                                                           f2(p) -> min; }-> min.
Постановка 2.                    F(Х) = {f1(p) -> max;
                                                           f2(p) -> max; }-> max.
2. Условия приоритета
Постановка 3.                    F(Х) = {f1(p) -> min;
                                                           2*f2(p) -> min}-> min.
3. Противоречивые условия
Постановка 4.                    F(Х) = { f1(p) -> mах;
                                                            f2(p) -> min}.
4. Условия компромисса
Постановка 5.                    F(Х) = { f1(p) -> f2(p) -> c}.
5. Формализация многокритериальных задач

Ключевые слова и их определения к теме


Введение в проблему

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

Постановка 1. Два города р1 и р2 решили построить завод (т.р) по переработке отходов. Им определили, завод может быть построен между городами р11-р12 (рис.1). Города р1, р2 стремятся расположить завод как можно ближе к себе. Критерии (в данном случае расстояния от города до завода s1 и s2) являются частными, а общий критерий решения (например, суммарное расстояние s3=s1+s2) будет глобальным.

Поиск частных оптимальных критериев с построением частных целевых функций (ЧЦФ) рассматривался ранее и не представляет трудностей. Глобальный критерий (суммы частных критериев) определяется также по схеме графочисленной оптимизации. Трудность заключается в определении области допустимых изминений переменных параметров и их приведению к нормализованным (однородным), когда это необходимо параметрам.

Впервые поставил и решил такие задачи итальянский экономист В.Парето. Он определил границы (область) в которой следует искать глобальную ЦФ (на min/max и компромисс). Оптимальные решения лежат внутри той области границы, которой являются линиями (гиперповерхностями) между точками оптимума, полученных при решении задач оптимизации отдельно по каждому критерию. Вне этой области решение задачи будет заведомо хуже, чем внутри области. Это наглядно прослеживается для поставленной задачи (см. рис. 1).
 
Рис.1. Частные целевые функции s1 -зависимости расстояния первого города и s2 - второго города до трассы р11-р12

Зона компромиссных решений определяется или в точке пересечении ЧЦФ (см. рис. 4) (компромисс найден) или зоной компромисса (когда общий компромисс не найден, однако найдена область, в которой он наилучший).

Рассмотрим эти положения на задаче 2-х городов.

Формализация задачи:
F(Х) = {f1(p)=s1=|p1-p| -> min;
            f2(p)=s2=|p2-p| ->min; }->min.
или

F(Х) = f1(p)+ f2(p)=|p1-p|+|p2-p| ->min,

где f1, f2 - частные целевые функци (ЧЦФ) и F - глобальная ЦФ (ГЦФ)поставленной задачи.
 
 
а)
б)
Рис. 2. а) поиска минимум s1+s2 и б) области Парето при условии, что ЧЦФ стремятся к min

Граница ГЦФ на области Парето определяется из соотношения F=(1-t)f1(X) + tf2(X)  (0 ? t ? 1), где при каждом значении t будет отыскиваться точка границы. В частном случае (рис. 2) это определяется непосредственно из соотношения
  p=(1-t)*р1min+t* р2min
На рис. 3, б на основе определения точек минимумов по каждой ЧЦФ, выделена область Парето, где фактически и необходимо строить график ЦФ и искать min/max глобальной (суммарной) ЦФ.

Постановка 2. Каждый город стремится, чтобы с позиций экологии  завод находился  как можно дальше. ГЦФ также будет стремиться к max.

F(Х) = { f1(Х)=| p1-p| ->max;
               f2(Х)=| p2-p| ->max; }->max.

Область, где может быть построен завод тоже отрезок p11-p12. Область Парето будет между ЧЦФ - для первого города т. р12 (там самое дальнее расстояние) для второго т. р11.

Решение задачи и построение графика исходит из ЦФ

F(Х) = f1(p)+ f2(p)=|p1-p|+|p2-p| ->mах; и представляет собой перевернутый график на min (см. рис. 1).


2. Условия приоритета

 Постановка 3. Иногда та или иная функция (в частности, город) может иметь приоритет, например в том чтобы завод был построен ближе. Для этого необходимо в глобальную ЦФ на веса (1-t) и t наложить условия приоритета (уменьшить или увеличить тот или другой на заданный коэффициент). Так, если город р2 имеет приоритет в два раза большего, значит его расстояние до трассы должно быть на половину меньше. Тогда ГЦФ будет иметь вид:

F(Х) = { f1(Х)=| p1-p| ->min;
               f2(Х)=2*| p2-p| ->min}.
 

F(Х) = f1(p)+ 2*f2(p)

Такая ГЦФ иногда называется еще функцией свертки (суммы) двух локальных функций одна из которых имеет тот или иной приоритет. Зона Парето в случае свертки будет той, что на рис.
 



 

3. Противоречивые условия

В этом случае могут быть различные условия.

Постановка 4. Первый город стремится, чтобы завод был построен как можно дальше, а второй город - как можно ближе.

F(Х) = { f1(Х)=| p1-p| ->mах;
               f2(Х)=| p2-p| ->min}.

Решение данной задачи начнем из определения зоны Парето

Строим ЧЦФ для того и другого города (рис.1)

Для первой города (расстояние до завода было максимальным эта будет точка p12, для второго города (требования город был как можно ближе - точка pminр2). Граница изменения р (область по Парето) будет
pminр1< р < p12
 

Построение графика общей ЦФ сводится к тому, что у второго критерия надо поменять знак (мах на min)и строить как сумму ЧЦФ, подобно тому, как это делалось ранее:

F(Х) = f1(p)+ f2(p)=-|p1-p|+|p2-p| ->min;

Знания же области Парето позволяет существенно сузить область поиска ЦФ.
 
 
а)
б)
 
 

Рис.4. а) определение зоны Парето и компромиссного решения при разнонаправленных критериях (у второго города вдобавок еще приоритет 2.0)


4. Условия компромисса

Постановка 5. В результате решения постановки 2 выяснилось, что решение получилось неравноправное: кто-то оказался ближе к заводу и это неустраивало. И тогда решили, давайте построим завод на одинаковом расстоянии друг от друга.

Вот формализация такой постановки:

F(Х) = { f1(Х)=| p1-p| =с;
               f3(Х)=| p3-p| =с; }-> min.

Величина с - неизвестна. Область в которой необходимо решать задачу та же самая - отрезок между городами.

Можно построить ЦФ первого условия (взяв параметр с=0) и ЦФ второго условия (также с= 0). Эти ЧЦФ пересекаются в точке, которая соответствует точке на прямой искомого решения. Для двух городов нахождение точки на прямой равноудаленных от двух заданных (задача Герона) всегда возможна. Поэтому всегда ЧЦФ будут пересекаться. Однако в случае, когда вместо двух городов будут три или более найти общую точку компромисса не всегда возможно. В этом случае графики трех ЧЦФ определяют зону компромиссного решения в которой пользователь самостоятельно выбирает решение в зависимости от приоритета того или иного города (ЧЦФ).
 
 
а)
б)
 
Рис. 5. Определение компромисса для а) 2-х и б) 3- х городов

Для случая постановки (4) области по Парето нет -. невозможно определить мах/мin ЦФ по каждому критерию. Областью решений будет зона компромисса, в которой точка выбирается все равно пользователем и автоматизировать этот процесс (найти точку лучшего компромисса) не представляется как.

Таким образом, можно заметить, что при решении задач постановок (1-3), область ограничений (область перебора точек) можно выбирать в виде области по Парето. Задача определения области Парето легко решается для первых трех постановок (в первом постановке минимум совпал с расположением городов, а во второй и третьей выбраны оптимума по каждому критерию согласно условию задач). В четвертом постановке все критерии стремятся к своему равенству, т.е. должна быть решена система трех уравнений с тремя неизвестными. В каждом уравнении добавляется неизвестная величина - искомый радиус, который может быть определен или аналитически, например, при совместном решении трех уравнений или с помощью ЦФ минимума суммы отклонений. Таким образом, данная задача не является задачей на максимум/минимум, а является задачей компромиссного решения трех уравнений.


5. Формализация многокритериальных задач

Рассмотрим решение задачи первой постановки.

Формализованная запись  1-й части задачи будет:

  F(Х) = { f1(p)=| p1-p| ->min;
               f2(p)=| p2-p| ->min; }->min.

Область ограничений: отрезок прямой р11-р12. Структуризацию (перебор точек внутри области)  выполним по  формуле:

 p = (1.-u)*p11+ u*p12

где
                           0 > u >  1,

Шаг 1. Определяем минимум по каждому критерию (рис.1):

Определяем область Парето с помощью фиксации линий между парами локальных оптимумов на области ограничений по формуле:

       F(X)=(1-t)*f1min + t*f2min
        0 > t > 1.

Шаг 2. Проводим анализ системы на предмет ее минимизации методом свертки. Т.к. условия приоритета не оговорены, строим общую ЦФ как сумму частных целевых функций.
                             F = f1 + f2
Минимум функции F даст значения вектора (координаты x, y), соответствующего искомой точки p*  т.е. точки сумма расстояний от которой до трех заданных является минимальной.

Ввиду того, что частные критерии определены в единых размерных единицах, то величина функции F даcт и искомое расстояние.

F= f1+f2 =s1+s2

Шаг 3. Определяем вектор (точку), обеспечивающую поставленные условия.  Минимум  графика и определит точку глобальной ЦФ

В случае компромисса между функциями f1 и f2 (f1=f2):  если минимум ЦФ F(X) = | f1-f2| равен нулю, то достигнут полный компромисс (для двух городов это условие выполнимо).  Определение глобального компромисса для трех городов: s1=s2=s3=c, аналитически решается (часто не решается) сложно, поэтому в этом случае можно руководствоваться графическим отображением этих функций - точкой пересечения ЧЦФ или зоной между ними (см. рис. 5,б).

Шаг 5. Окончательное решение за лицом принимающее решение.
 



Обобщение предложенной методике на трехмерное пространством более см. в методическом пособии: Седых В.И., Машунин и др. Парето-оптимальное моделирование.

Исследовать следующую задачу. Три города р1, р2, р3 решили в плоскости треугольника, образованного их расположением  построить завод р по переработке отходов. Определить местоположение завода таким, чтобы сумма расстояний от городов до него был минимальной. Определите зоны Парето при противоречивых условиях.



 

Ключевые слова и их определения к теме

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

Постановка задачи - словесное или математическое описание смысла задачи, содержащее исходные данные, ограничения, критерии, необходимую точность решения, связи с другими задачами системы.

Формализация задачи - описание задачи в принятых формальных обозначениях ( в формальном языке).

Решение задачи - алгоритмизированный выбор последовательности операций, математического аппарата и одной из альтернатив их осуществления.

Цель - желаемый или заданный результат.

Критерий (общий, частный, глобальный) - признак, по которому производится оценка соответствия функционирования системы заданному результату при заданных ограничениях.

Целевая функция (ЦФ), частная целевая функция (ЧЦФ) - функция переменных, от которых зависит достижение критерия оптимальности.

Оптимизация - формирование функциональной системы по принятому критерию оптимальности.

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

Область Парето - область допустимых решений (внутри области ограничений), внутри которой невозможно неухудшение одновременно всех частных критериев, или говорят, что в области Парето найдется заведомо лучшая точка по оптимальности, чем вне этой зоны.

Двойственность - тоже, что максимин в теории игр.

Приоритет критерия - отношение предпочтения между критериями.

Паритет критериев  - отношение эквивалентности критериев, приведенных к сравнимым шкалам измерения.

Мультимодальная ЦФ - функция имеющая два и более экстремумов.

Унимодальность - наличие  у ЦФ одного экстремума.

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

Обозначения векторов используемые в пособии: Х(x1,x2,..... xn), Y(y1,y2, ... yn) и  на языке "Калькулятор" системы "Вектор": рn (xn,yn, zn, tn, sn и т.д (в зависимости от размерности вектора)), где n - любая целая положительная величина и

Расстояние между двумя точками (вектор-функциями) p1-p2 пространства определяется модулем разности векторов-функций начальной и конечной точек s = | p1-p2| = | p2-p1|
или, используя координаты (составляющих) векторов, можно сформулировать следующее определение:
расстояние между двумя точками (векторами-функций точек) пространства равно корню квадратному из квадратов разностей одноименных координат этих точек (векторов-функций точек)
s = sqrt((x1-x2)(x1-x2)+(y1-y2)(y1-y2)+.....(в зависимости от размерности векторов).