Материал: 4539

не принадлежит множеству Х. Введем понятие расстояния между двумя точками (a,b) в пространстве Rm :

И наконец, при s= получим равномерную метрику

ρ (a, b) max ai bi .

i

Теперь решение многокритериальной задачи можно свести к реше-

нию обычной однокритериальной задачи оптимизации

эффективной точкой, то есть множество оптимальных решений задачи (8)

вложено во множество Парето.

Утверждение. Если множество F выпукло, то множество оптимальных решений задачи (8) состоит из одной точки, и эта точка из множества Парето.

Для линейных многокритериальных задач удобнее использовать метри-

m

ку ρ1(a,b) ai bi , так как получаемая при этом однокритериальная зада-

i 1

ча тоже оказывается линейной задачей следующего вида:

35

m

fi (x) min

i 1 x X

Пример. Найти решение следующей двухкритериальной задачи мето-

дом идеальной точки:

f1(x)=7x1 +2x3-x4+x5 max f2(x)=x1-5x2-4x3+x4 max

при ограничениях

5x1+2x2 +x3+x4 +x5=11, xi 0 для i=1,2,...,5.

Если использовать метрику при s=1, то метод идеальной точки требует

решения следующей однокритериальной задачи

(x) = -f1 (x)-f2 (x) = -8x1+3x2+4x3-x5 min

или, что эквивалентно,

при ограничениях

5x1+2x2 +x3+x4 +x5=11, xi 0 для i=1,2,...,5.

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

F= -(w1+w2) max ;

36

Оптимальное решение этой задачи определяется таблицей 3 из примера

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

смысле принятой метрики.

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

найдем решение следующей двухкритериальной задачи (пример 2):

37

Рис.2

Как видно из рисунка, линии уровня функции (f), рассматриваемой лишь

для f1 7, f2 14 , имеют вид угла, вершина которого расположена на пря-

мой f1 f2 7, проходящей через идеальную точку f =(7,14). Интересую-

щая нас точка f удовлетворяет условию f1-7=f2-14 и принадлежит отрезку

(f3,f4) в пространстве критериев, а соответствующая ей в пространстве реше-

ний точка x - отрезку (x3,x4). Исходя из этих условий, находим x =(19/5,3) f =(26/5,61/5).

Задания Задание 1. Построить множество Парето для следующей двухкритери-

альной задачи:

3)методом последовательных уступок считая, что критерии упорядочены по важности в последовательности {f1,f2}, и =4.

4)методом идеальной точки с равномерной метрикой.

38

Задание 2. Построить множество Парето для следующей двухкрите-

риальной задачи:

ны по важности в последовательности {f1,f2}, и =1.

4)методом идеальной точки с равномерной метрикой.

Упражнение 3. Доказать утверждение 1.

Упражнение 4. Построить множество Парето для следующей двухкри-

териальной задачи:

Задание 5. Построить множество Парето для следующей двухкрите-

риальной задачи:

Задание 6. Решить двухкритериальную задачу:

39