9.2. Метод идеальной точки.

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

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

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

Пусть на множестве W плоскости (х,у), определяемом системой неравенств

заданы две линейные функции:

W=

U = x + N2*y+2,

V = x  N3*y+6.

Требуется найти решение задачи

U —>max, V —»max.

Множество W представляет собой пятиугольник (рис. 9), вершины которого имеют следующие координаты:

A(0,0), B(0,2), C(2,2), D(4,1), F(4,0).

Рис. 9

В силу линейности критериев U и V пятиугольник ABCDE переходит в пятиугольник A*B*C*D*E* (рис. 10), координаты вершин которого вычисляются по формулам (1):

А*(2,6), В*(4,4), С*(6,6), D*(7,9), E*(6,10).

Рис. 10 Рис. 11

Находим границу Парето. Это отрезок D*E*. Точка утопии М*(7,10) считается заданной (ее координаты суть наибольшие значения U и V).

Требуется найти на множестве Парето точку, ближайшую к точке утопии М*. Из рисунка видно, что искомая точка должна лежать на отрезке D*E*. Проведем через точки D* и Е* прямую. Пусть

U + V = 

— ее уравнение (рис. 11). Чтобы отыскать конкретные значения параметров ,  и  подставим в него координаты обеих точек — и D*, и Е*. Получим

Вычитая из первого равенства второе, после простых преобразований придем к соотношению

откуда

Положим  =  = 1. Тогда  = 16 и

U + V=16

— искомое уравнение прямой.

Теперь стоит напомнить, как ищется расстояние между точками, заданными своими координатами.

Рис. 12

Пусть M₁(U1,V1) и M₂(U2,V2) — точки на плоскости (U,V) (рис. 12). Для того чтобы найти расстояние между ними, достаточно вычислить длину гипотенузы построенного прямоугольного треугольника.

Воспользовавшись теоремой Пифагора, получим, что гипотенуза равна

По условию задачи нам нужно определить на прямой

U + V = 16

точку M°(U°, V°), расстояние которой от точки М*(7,10) минимально, т. е. решить экстремальную задачу:

Так как U = 16 — V, то последнее соотношение можно переписать в виде

Возводя в квадрат и приводя подобные, получаем, что

Z = 2V² –38V + 181.

Это уравнение описывает параболу (рис. 13) с вершиной

V0=19/2, z0=1/2

(координата V° находится из условия равенства нулю производной z' = 4V-38). Тогда

U0=16-19/2=13/2.

Рис. 13 Рис. 14.

Идеальная точка

M0(13/2, 19/2)

находится на расстоянии 1/2 от точки утопии М*(7,10) (рис. 14). Соответствующие значения х и у легко находятся из системы линейных уравнений

х + у + 2 = 13/2,

х-у+6= 19/2.

Имеем:

x = 4, у= 1/2.

Замечание. Мы рассмотрели задачу, в которой

Ф(x,у) -> max, (x,у) —> max.

На практике часто встречаются случаи, когда требования выглядят по-иному — так:

Ф(х, у) —> max, Ф(х, у) —» min

или даже так:

Ф(х,у) —> min, Ф(ж,у) —>• min.

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

 = -Ф

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

Ф —> min и  —> max

равносильны. Поэтому, поменяв в случае необходимости знак у критерия на противоположный, мы можем свести любую двухкритериальную задачу к уже рассмотренной:

Ф(х, у) -> max, (х, у) -> max.

Рассмотрим соответствующий пример.

Пример 2, Пусть на множестве

(рис. 15) заданы две линейные функции:

U = 2x и V = x-y-l. (2)

Требуется найти решение задачи

U -»max, V —> min (3)

при условии, что точка утопии М* имеет координаты (2,—2).

Рис. 15 Рис. 16 Рис. 17

Введем новую функцию

W = -V = -x + y+l. (4)

Тогда требование (3) можно записать так:

U —> max, W -> max.

Соответственно изменится и точка утопии — N*(2,2).

Функции

U = 2х и W. = -х + у + 1

линейны и преобразуют единичный квадрат w в параллелограмм  (рис. 16), при этом вершины квадрата

(0,0), (1,0), (1,1), (0,1)

переходят в вершины параллелограмма

(0,1), (2,0), (2,1), (0,2).

Множество Парето образуют точки отрезка с концами А(0,2) и В(2,1) (рис. 17). Проведем через эти точки прямую и найдем коэффициенты её уравнения

U + W = .

Подставляя в него координаты точек А и В, получаем, что

2 = , 2а + = 

Положим  = 2. Тогда  = 4 и  = 1. Тем самым уравнение искомой прямой имеет вид

U + 2W = 4.

Пусть C*(U,W) — точка этой прямой, ближайшая к точке N*(2, 2). Это означает, что должно выполняться условие

z = (U - 2)² + (W - 2)² --> min.

Так как U = 4 - 2W, то оно принимает следующий вид:

z = 5W² - 12W + 8 --> min.

Рис. 18

Чтобы найти минимальное значение функции

z = 5W² - I2W + 8

(рис. 18), приравняем к нулю ее производную. Имеем:

z' = 10W - 12 = 0.

Отсюда

W=6/5, U=4-12/5=8/5.

Соответствующие значения х и у находятся из уравнений (см. (2))

2*x=8/5, -x+y+1=6/5

откуда

х = 4/5, y = 1.

Расстояние от найденной точки

С*(8/5, 6/5]

до точки утопии N*(2,2) равно 2/5.

Ответ: идеальная точка

M0(8/5, 6/5)

находится от заданной точки утопии М*(2, —2) на расстоянии 2/5.

8.4. Задания и ответы.

1. На множестве

заданы две линейные функции:

U = 2х + 1 и V = 2у + 3.

Требуется найти решение задачи

U —> max, У —> max,

при условии, что точка утопии М* имеет координаты (5,7).

Ответ: идеальная точка М°(3,5) находится от заданной точки утопии М*(5,7) на расстоянии 2*2; (1,1) — соответствующая точка плоскости (ж, у).

2. На множестве, определяемом системой неравенств

заданы линейные функции:

U = х + у + 2, V = х — у + 6.

Требуется найти решение задачи

U —> max, V —> max,

при условии, что точка утопии М* имеет координаты (7,8).

Ответ: идеальная точка

M0(11/2,13/2)

находится от заданной точки утопии М*(7,8) на расстоянии З/2;

(2,3/2) — соответствующая точка плоскости (х, у).