-
Метод уступок
Пусть на плоскости (x,y) задано множество M (рис. 4), в каждой точке которого определены две непрерывные функции u = f(x,y) и v = g(x,y).
Нарисуем на плоскости (u, v) множество P всех точек, координаты которых вычисляются по формулам u = f(x,y) и v = g(x,y), (x,y) M (рис.5).
Рассмотрим задачу: во множестве P найти точку (x0, y0), в которой
f(x0, y0) = max и g(x0, y0) = max.
Из рис. 4.5 видно, что точка с координатами (fmax, gmax) (точка утопии) лежит вне множества P. Это означает, что наибольшее значение функции u и наибольшее значение функции v достигаются в разных точках A и B. Поэтому поставленная задача в общем случае решения не имеет.
Метод уступок является одним из наиболее простых методов решения задачи с двумя критериями. Он состоит в том, что ЛПР, работая совместно с аналитиком−специалистом последовательно сужает множество точек на границе Парето и, в конце концов, соглашается остановиться на некоторой компромиссной паре значений критериев.
Снова вернемся к задаче выбора автолюбителем машины. На первом шаге, рассматривая границу Парето, состоящую из четырех вариантов покупки ( 4 жирные точки на рис. 4.3), автолюбитель согласится ослабить свое требование по надежности и откажется покупать сверхнадежную (сн) машину, так как его кошелек почти полностью опустеет. Останется 3 варианта.
На втором шаге автолюбитель согласится ослабить свое требование по стоимости и откажется покупать не очень надежную (нон) машину, хотя она и самая дешевая среди машин, составляющих множество Парето. Остается 2 варианта.
На третьем шаге автолюбитель выбирает один из двух оставшихся вариантов, например, надежную (н), но не очень дорогую машину. Это и будет ответом в задаче выбора машины, полученным методом уступок.
-
Метод идеальной точки
Другой подход, также использующий множество Парето, называется методом идеальной точки. Он состоит в отыскании на границе Парето точки, ближайшей к точке утопии, задаваемой лицом, принимающем решение. ЛПР обычно формулирует цель в виде желаемых значений показателей, и их сочетание можно рассматривать как координаты точки утопии, которая обычно не принадлежит множеству Парето.
Пример. Пусть множество М точек плоскости XOY определено системой неравенств:
(1)
На множестве M заданы две линейные функции
u = 5x − y + 2,
v = − x + 3y +2. (2)
Требуется во множестве M найти точку (x0, y0), в которой функции u и v принимают максимальные значения.
Множество M представляет собой квадрат OABC (рис. 4.6), вершины которого имеют координаты: O(0, 0), A(0, 2), B((2, 2), C(2, 0).
Линейные функции u и v преобразуют квадрат OABC в параллелограмм PQRS, вершины которого, вычисляемые по формулам (2), имеют координаты: P(2, 2), Q(0, 8), R(10, 6), S(12, 0) (легко проверить, что ).
Точка утопии M0(12, 8), координаты которой являются наибольшими значениями функций u и v на множестве M, не принадлежит параллелограмму PQRS.
Граница Парето параллелограмма PQRS состоит из отрезков QR и RS. Точка, ближайшая к точке утопии M0, должна лежать на одном из этих отрезков.
Нетрудно доказать, что этой точкой является точка R. Для этого проведем окружность с центром в точке M0 и радиусом r = M0R. Докажем, что эта окружность касается параллелограмма PQRS в точке R, то есть не имеет других общих точек с отрезками QR и RS, кроме R.
Уравнение прямой, которой принадлежит радиус M0R, имеет вид:
, упростив которое, получаем уравнение y = x − 4.
Угловой коэффициент этой прямой равен: k1 = 1. Проведем касательную EF к окружности в точке R. Ее угловой коэффициент равен: k2 = − 1, следовательно, ее уравнение имеет вид: y − 6 = − (x − 10) или x + y −16 =0.
Найдем угловые коэффициенты k3 и k4 прямых QR и RS:
k3 = , k4 =
Так как k4 < k2 < k3 < 0, то углы , образованные прямыми RS, EF и QR − тупые, и следовательно, отрезки RS и QR лежат ниже прямой EF. Поэтому касательная EF имеет только одну общую точку R c отрезками RS и QR.
Найденная ближайшая к M0 (идеальная) точка R(10, 6) отстоит от точки утопии M0(12, 8) на расстоянии
Соответствующие значения x0 и y0 легко найти из системы уравнений:
(3)
Решив систему (3), получим: x0 = 2, y0 = 2 (можно было не решать систему (3), а вспомнить, что прообразом точки R при отображении (2) была точка B(2, 2)).
Если критерий заключается в минимизации функции, то, поменяв у критерия знак на противоположный, можно свести любую двухкритериальную задачу с двумя переменными к задаче рассмотренного типа.