Многокритериальные задачи принятия решения: понятия, проблемы, постановка и примеры

1. Многокритериальные задачи принятия решения: понятия, проблемы, постановка и примеры

Цехан О.Б., зав.каф. МИОЭС, ГрГУ

2. Следует повторить

Общая постановка ЗПР
Понятие отображения
Отношение порядка
Графический метод решения ЗЛП

3. Входной контроль

1. Общая постановка задачи критериального
выбора
2. Графическая интерпретация элементов задачи
линейного программирования
3. Задано множество альтернатив: X={a=1,b=3}.
Какая их двух альтернатив предпочтительнее
• по позитивному критерию f(x)=2*x?
• По двум позитивным критериям f1(x)=2*x и f2=3*x?

4. Самопроверка

f ( x ) max
x X
f x 2 x 1 3 x 2 max
x R2 :
2
x
x
10
2
1
X 2 x 1 3 x 2 6
2 x 4 x 8
2
1
x 1 , x 2 0

5. План лекции

Понятие о многокритериальной задаче.
Источники и проблемы многокритериальности.
Множество целей
Множество объектов
Постановка многокритериальной ЗПР.
Примеры многокритериальных ЗПР. Роль ЛПР.
Основные понятия многокритериальной оптимизации
– Частный (скалярный) критерий, векторный критерий
– Позитивный, негативный критерий
– Идеальное и компромиссное решение
– Достижимые векторные оценки
– Сравнимые и несравнимые альтернативы
• Резюме

6. Понятие о многокритериальной задаче

Если альтернативы оцениваются по нескольким критериям,
то такая ЗПР называется многокритериальной ЗПР
(задачей векторной оптимизации)
Источники и проблемы многокритериальности
Источники: В экономических задачах основными критериями служат
эффективность и стоимость, при этом каждый из критериев, в свою очередь,
может быть подразделен на более частные критерии.
В технических: максимизация надежности при минимизации затрат на
производство
Проблемы:
•В многокритериальных задачах строгого порядка нет (В
однокритериальных задачах целевая функция позволяет ранжировать
альтернативы : чем больше значение целевой функции на альтернативе,
тем она предпочтительнее ).
•Конфликт критериев (нет идеального решения)
•…

7. Множество целей

Задачи оптимизации на множестве целей, каждая из
которых должна быть учтена при выборе оптимального
решения.
Пример - составление плана работы предприятия, в
которой критериями служит ряд экономических
показателей
Множество объектов
Пример: распределение дефицитного ресурса между
несколькими предприятиями.
Для каждого предприятия критерием оптимальности
является:
• степень удовлетворения потребности в ресурсах
• величина прибыли
Для планирующего органа критерием выступает:
• вектор локальных приоритетов предприятий;

8.

Постановка многокритериальных ЗПР
Пусть Х – произвольное множество, а f1, …,fm – числовые функции
(целевые функции, критерии), заданные на множестве X.
Требуется найти оптимальное решение из множества X,
максимизирующее функции на множестве X:
f ( x ) (f1( x ),..., fm ( x )) max
x X
n
Здесь f(x) –- m-вектор-функция аргумента x X, X R.
Элементы x отражают возможные варианты принятия решения,
эффективность которых оценивается по m различным показателям,
имеющим математическое выражение в виде f1( x ),..., fm .( x )
Ограничение x X отражает технические, технологические, ресурсные,
институциональные и иные возможности реализации тех или иных
значений x . Кроме того, часть ограничений может формироваться на
основе имеющейся априорной информации, позволяющей исключить из
рассмотрения заведомо неудачные варианты xi .
Критерий называется позитивным, если ЛПР стремится к его
увеличению, и негативным, если ЛПР стремится к его уменьшению.

9. Пример многокритериальной задачи

Векторная целевая функция f(x) и 4
ограничения :
f1 210 x 1 480 x 2 600 x 3
f ( x )
extr
f2 x1 x 2 x 3
10 x 1 23 x 2 26 x 3 400,
5 x 1 13 x 2 22 x 3 500,
7 x 9 x 11x 400,
2
3
1
x 1, x 2 , x 3 0.

10.

f1 x 2 x 1 3 x 2
f x
max
f2 x 4 x 1 x 2
x R2 :
2
x
x
10
2
1
X 2 x 1 3 x 2 6
2 x 4 x 8
2
1
x 1 , x 2 0

11. Основные понятия

– Частный (скалярный) критерий f1, , векторный
критерий
f1( x )
f ( x ) ...
f (x)
m
– Позитивный fi ( x ) max , негативный fi ( x ) min
критерий
– Идеальное и компромиссное решение
– Множество векторных оценок многокритериальной
ЗМР. Критериальное пространство и достижимые
векторные оценки.
– Сравнимые и несравнимые альтернативы.

12.

Идеальное решение
f1 x1 10 x 2
f (x )
extr
f2 x 1 10 x 2
X x 1 x 2 1, x 1 , x 2 0,
f1max f1 0,1 10, argmax f1 0,1
X
X
f2 max f2 0,1 10, argmax f2 0,1
Рис. Идеальная точка (0,1)
X
Если функции f1,…,fm достигают максимума в одной
*
x
X
и той же точке
arg max fi x x , i 1, m
*
x X
то говорят, что задача (1) имеет идеальное решение
x* X

13.

В случае отсутствия «идеального решения» в
задаче (1) ищется компромиссное решение
Компромиссное решение
f1 x 1 10 x 2
f (x )
extr
f2 10 x 1 x 2
X x 1 x 2 1, x 1 , x 2 0,
X
Рис. Компромиссное решение
f1max f1 0,1 10, argmax f1 0,1
X
f2 max f2 1,0 10, argmax f2 1,0
X

14.

Идеальное решение
f1 x1 10 x 2
f (x )
extr
f2 x 1 10 x 2
X x 1 x 2 1, x 1 , x 2 0,
X
Рис. Идеальная точка (0,1)
f1max f1 0,1 10, argmax f1 0,1
X
f2 max f2 0,1 10, argmax f2 0,1
X
Компромиссное решение
f1 x 1 10 x 2
f (x )
extr
f2 10 x 1 x 2
X x 1 x 2 1, x 1 , x 2 0,
X
Рис. Компромиссное решение
f1max f1 0,1 10, argmax f1 0,1
X
f2 max f2 1,0 10, argmax f2 1,0
X

15.

Множество достижимых целей
max f1 x x1 2 x 2
max f2 x 2 x1 x 2
x1 x 2 1
x , x 0
1 2
(*1)
(*2)
•альтернативе (0,0) соответствует точка (0,0) в пространстве критериев
(векторная оценка (0;0));
•альтернативе (0,1) соответствует точка (2,1) в пространстве критериев
(векторная оценка (2;1));
•альтернативе (1,0) соответствует точка (1,2) в пространстве критериев
(векторная оценка (1,2)).

16. Сравнимые и несравнимые альтернативы

x1 X
x X
2
X
f1 x
f2 x
Сравнимы, если
f x , i 1, m
fi x
1
i
x1
x2
x3
2
4
3
5
1
6
2 И3
2
M2 и М1

17.

18. Резюме

Постановка многокритериальных ЗПР
Критерий
1. Скалярный
• Векторный
• Позитивный
• Негативный
1. Решение многокритериальной задачи
• Идеальное
• Компромиссное
2. Пространство альтернатив
3. Пространство векторных оценок (критериальное пространство)
4. Векторная оценка альтернативы
5. Множество векторных оценок
6. Альтернативы
• Сравнимые
• Несравнимые
• Доминирующие
• Доминируемые

19. Многокритериальные задачи принятия решения Парето оптимальные оценки и альтернативы

20. Следует повторить

Постановка многокритериальных ЗПР
– Критерий
Скалярный
Векторный
Позитивный
Негативный
– Решение многокритериальной задачи
Идеальное
Компромиссное
– Пространство альтернатив
– Пространство векторных оценок
– Альтернативы
Сравнимые
Несравнимые
Доминирующие
Доминируемые

21. Входной контроль

22. Самопроверка

23. План лекции

• Парето оптимальные альтернативы и Парето
оптимальные оценки.
• Общая технологическая схема принятия решений при
многих критериях.

24.

15.07.1848-20.08.1923
Впервые задачей многокритериальной (векторной) оптимизации
занялся итальянский экономист В. Парето при математическом
исследовании товарного объекта. В 1896 В.Парето предложил в
экономике концепцию, получившую название принципа Паретооптимальности.

25. Парето оптимальность

Определение 1. Альтернатива x X доминирует (по Парето) альтернативу
1
1 P 2 если f ( x 1 ) f ( x 2 ), i 1, m
x X x x
i
i
такое, что f ( x 1) f ( x 2 )
i0
i0
2
и
i0 , i0 {1, m}
Определение 2. Альтернатива x X оптимальна по Парето (эффективна)
*
если не существует x X , доминирующей x *
X
x1 x2 x3
f1 x
2
4
3
f2 x
5
1
6
x
3
P
x1
X ý x2, x3
P
x3
P
x1
X ý x4 , x5 , x7 , x8
M1 M 2
X э Q, B

26.

27.

Конус доминирования
f ( x , y ) (f1( x , y ) 2 x y , f2 ( x , y ) 2 x 3y ) max
D {( x , y ) : x 2 y 2 100, x 0, y 0}
y
10
a
grad f1
z=c
b
grad f2
x

28.

В пространстве оценок конус доминирования
имеет направляющие, параллельные осям.

29.

Пример 2. f (x)=(f1=cos x, f2=tg x) max, X=[0,1].
XЭ=[0,1].
f(x)
f2
f1
x
0
x
1

30.

Пример 3. f (x)=(f1=(x-1)2+2, f2=|x-2|) max, X=[0,3].
Xэ={0,3}
f1
y
3
f2
x1
1
x2
2 x3
3
x

31. Методы решения многокритериальных задач

Методы решения многокритериальных
задач
Описание выбора
на языке
бинарных отношений
Критериальный язык описания
выбора
интерактивные
Метод анализа
иерархий
Метод
эффективных
множеств
Лексикографическая оптимизация
Метод
уступок
Аддитивные
Главного
критерия
Мультипликативные
Автоматические (сведение к
однокритериальным)
свертки
Целевого
программирования
Максиминные

32. Резюме

Парето оптимальные альтернативы
Парето оптимальные оценки

33. Многокритериальные задачи принятия решения. Скаляризация

34. Следует повторить

• Графический метод решения ЗЛП
• Критерий
– Скалярный
– Векторный
– Позитивный
– Негативный
• Решение многокритериальной задачи
– Идеальное
– Компромиссное
• Векторная оценка альтернативы
• Множество векторных оценок

35. План лекции

1. Нормирование критериев
2. Метод аддитивной свертки критериев
3. Метод главного критерия
4. Лексикографическая оптимизация
5. Метод последовательных уступок
6. Метод целевого программирования
7. Принцип гарантированного результата (метод
максиминной свертки)
• 8. Метод равных наименьших относительных
отклонений

36.

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

37. Нормирование критериев

Нормирование – приведение критериев к единому
масштабу и безразмерному виду.
f1( x )
f ( x ) ... max
x X
f ( x )
m
g1( x )
g( x ) ... max
x X
g ( x )
m
gi ai fi bi
ai 0, bi
x, y X : x
fi x fi y
- некоторые константы
y
gi x g i y
Решение задачи не изменится при переходе от функций
fi к функциям gi

38.

Некоторые варианты нормирования
Пусть fk* – оптимальное, fk* – гарантированное значение критерия fk
Замена абсолютных значений критериев их:
1)безразмерными относительными величинами:
fk ( x )
fk ( x )
,
fk *
fk * max fk ( x ) 0
x X
2)относительными значениями отклонений
значений критериев f*k
fk ( x ) fk *
fk ( x )
3)относительными оценками:
gk x
fk *
от
оптимальных
,
fk x fk *
fk* fk *
Заметим, что gk(xk*) = 0, gk(xk*) = 1, для остальных x X gk(x) [0; 1].

39. Метод аддитивной свёртки

Пусть критерии соизмеримы (например, нормированы) и
определен вектор весовых коэффициентов критериев
=( 1,…, m), характеризующих важность соответствующего
критерия (если fi f j то i j ):
m
1, 0, i 1, m.
i
i 1
i
Решается задача оптимизации скалярного критерия:
m
F ( x ) i fi ( x ) max, x X
(4)
i 1
! Решение задачи (4) эффективно (т.е. Парето-оптимально) для исходной
многокритериальной задачи

40. Пример решения задачи методом аддитивной свёртки

Весовые коэффициенты:
f ( x ) (f1 x1 3 x 2 , f2 40 x1 10 x 2 ) max
X 2 x1 x2 90, x1 x2 90, x2 50, x1, x 2 0
1 0,3, 2 0,7
Нормировка критериев
Находим f ,f
, решая задачу отдельно по каждому из критериев:
По второму критерию:
По первому критерию:
*
1
*
2
x1* = (10, 50), f1* = 160
x 2* = (45,0), f2* = 1800
Нормированные критерии
f1
f1
f
1
1
( x 1 3 x 2 ), f2 2*
(40 x 1 10 x 2 )
*
f1
160
f2
1800
Линейная свертка критериев:
F ( x ) 0,3f 1 0,7f 2 0,3
1
1
( x1 3 x 2 ) 0,7
(40 x 1 10 x 2 ) (25,1x 1 13,7 x 2 ) / 720
160
1800

41. Недостатки метода аддитивной свертки

1. Значения , как правило, устанавливаются
исходя из неформальных соображений,
связанных с результатами экспертного анализа.
2. Вообще говоря априори не ясно, в каком
соотношении должны находиться весовые
коэффициенты, если известно желательное
отношение значений критериев на оптимальной
точке.
3. Возможны «плохие» значения некоторых
критериев за счет достаточно «хороших»
значений остальных целевых функций.

42. Метод главного критерия

• Один критерий выделяется в качестве главного
• Остальные критерии переводятся в разряд ограничений.
Пусть – ( 2 , 3 ,..., m ) вектор, компоненты которого – это нижние
границы соответствующих критериев.
Решение считается оптимальным, если критерий f1 достигает своего
максимального значения при условии, что по всем остальным
критериям достигнуты значения, не меньше заданных.
Задача будет иметь вид:
F ( x ) f1( x ) max
fi ( x ) i , i 2, m,
x X.
Метод ведущего критерия применяется в таких задачах, как:
• минимизация полных затрат,
•максимизация выпуска комплектных наборов при ограничении на
потребляемые ресурсы

43. Пример

f ( x , y ) (f1 x , f2 y ) max,
X {( x , y } | ( x 2)2 ( y 2)2 4, x 0, y 0}.
2 1
f1 x max
f2 y 1
(x, y ) X
x
a
c
0
1
b
y
Решение задачи – это точка c на рис. ,
множество эффективных точек
Э
X {a, b}, c X Э .
Проблемы принципа:
• Возможно наличие нескольких «главных» критериев, находящихся в
противоречии друг с другом.
• Не всегда ясен алгоритм выбора нижних границ
• Решение может быть слабоэффективно, но не эффективно
i

44. Лексикографические оптимумы.

1. Критерии нумеруются в порядке убывания их важности.
f1
f2
...
fm
2. Определяется значение
.
f1* max f1( x ), X 1* argmax f1( x ), x X
x X
3. Решается задача:
f2 ( x ) max, x X 1*
Пункты 2 и 3 повторяются для критериев
f2,..., .fm
Недостаток метода:
уже на первом шаге множество может состоять из единственного
элемента и остальные функционалы не принимают никакого участия в
построении оптимального решения.
Этот недостаток исправляется следующим методом.

45. Метод последовательных уступок

1. Критерии нумеруются в порядке убывания их важности.
f1 f2 ... fm
f1( x ) . ЛПР
2. Определяется значение f1* max
x X
устанавливает величину уступки Δ1 по этому критерию.
3. Решается задача:
f2 ( x ) max, x X , f1( x ) f1* 1.
Пункты 2 и 3 повторяются для критериев f2,..., f.m
Недостаток
Получаемое решение не всегда является эффективным.

46.

Пример 6. Решить задачу с уступкой по первому критерию 10% от
его оптимального значения
f ( x ) (f1 x1 3 x 2 , f2 40 x1 10 x 2 ) max
X 2 x1 x2 90, x1 x2 90, x2 50, x1, x2 0
Решение. 1 этап.
Решим задачу по критерию
f1
f2
f1* 160 Величина уступки 1 16
*
Дополнительное ограничение: f1 ( x ) f1 1 x1 3x 2 160 16
2 этап: Решаем задачу
f1
Получим
f2 40 x1 10 x 2 max
2 x1 x 2 90x 3 x 160 16
1
2
x1 x 2 90
x 2 50
x1, x 2 0,
Ответ:
x * (18,42), f2 ( x * ) 1440, f1( x * ) 144
(A)

47.

Проблемы метода:
- Произвольный выбор уступок может привести к
тому, что у задачи (А) не будет допустимых планов.
– решение задачи (А) может в общем случае не
быть оптимальным по Парето для задачи (исходной);
– числа i не соизмеряются между собой и обычно
подбираются по принципу: выберем достаточно
маленькие, если задача не будет иметь решения –
немного их увеличим.

48. Пример Решение задачи методом последовательных уступок

f1
Пусть эксперты упорядочили критерии f2
Уступка по главному критерию составляет 3% от его
оптимального значения.
Задача 1-го этапа:
f ( x ) f2 40 x1 10 x 2 max
2 x 1 x 2 90
x1 x 2 60
x 2 50
x1, x 2 0,
Решение задачи первого этапа x 2* (10, 50), f2* 1800
Экспертом назначена уступка по главному критерию:
Δ2 = 0,03 * f2* = 0,03 * 1800 = 54

49.

Дополнительное ограничение
f2 ( x ) f2* 2
40 x1 10 x 2 1800 54 1746
Задача 2-го этапа:
f ( x ) f1 x1 3 x2 max
2 x1 x 2 90
x1 x 2 60
x 2 50
40 x1 10 x 2 1800 54 1746
x1, x 2 0,
Ответ: по методу уступок оптимальной является альтернатива
x * у (42,3; 5,4),
соответствующие значения критериев:
f1( x * у ) 58,5, f2 ( x * у ) 1746
Заметим, что
f1 ( x * у ) 58,5 160 f1* , f2 ( x * у ) 1746 1800 f2*

50. МЕТОД ЦЕЛЕВОГО ПРОГРАММИРОВАНИЯ (идеальной точки)

51. МЕТОД ЦЕЛЕВОГО ПРОГРАММИРОВАНИЯ (идеальной точки)

52.

Пример (метод идеальной точки, евклидова метрика
y * (f1* , f2* ) 2,2
max f1 x x1 2 x 2
max f2 x 2 x1 x 2
x1 x 2 1
x , x 0
1 2
1
2
2
d f x y * x1 2 x 2 2 2 x1 x 2 2 2 min
x1 , x 2
x1 x 2 1
x , x 0
1 2
x1
f1
f2
x2
0,5
1
2
1
d
0,5
2
1
1
0,5 ->
1,5
1,5
1 <=
мин
1

53.

МЕТОД ЦЕЛЕВОГО ПРОГРАММИРОВАНИЯ
(идеальной точки)
* p
d(f(x),y ) = w i fi (x) - y i
i 1
n
1/p
*
min
x X
где y * y 1* ,..., y m* - вектор целевых значений,
*
.
d(f(x),y
) - расстояние (мера отклонения) между f(x)
и y * , 1 p , w i - весовые коэффициенты.
Часто (например, в случае линейного целевого
программирования) полагают p=1.

54. МЕТОД КОМПРОМИССНОГО РЕШЕНИЯ максиминной свертки

Принцип гарантированного результата. Задача
формулируется следующим образом:
fi ( x )
min * max, x X
i
fi
f (x )
fi
f (x )
fi
min i * i * 0
i
Эквивалентная задача:
max,
-задача:
fi ( x )
* 0,
fi
x X.
Получаемое решение эффективно. Оптимальное значение
max , 0 1
Чем меньше
тем противоречивее
критерии

55.

Пример
f ( x ) (f1 8 x1, f2 10 x 2 ) max,
5 x1 3 x 2 450,
2 x1 6 x 2 420,
.
x1, x 2 0.
Решение. Находим решение по каждому из критериев:
f1* 720, x1* (90,0), f2 ( x1* ) 0,
f 700, x (0,70), f1 ( x ) 0,
*
2
*
2
*
2
max,
90 x1 0, 70 x 2 0,
x 1 , x 2 0,
5 x1 3 x 2 450, 2 x1 6 x 2 420.
Ответ
0,6818; x * 61,36; 47,73
f1 8 61,36 546,88, f2 10 47,73 477,3
f1 ( x ) 8 x 1
*
f1
720
f2 ( x ) 10 x 2
*
f2
700
x1 61,36; x 2 47,73

56. МЕТОД ИНТЕРАКТИВНОГО ПРОГРАММИРОВАНИЯ

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

57. Резюме

1. Нормирование критериев
2. Метод аддитивной свертки критериев
3. Метод главного критерия
4. Лексикографическая оптимизация
5. Метод последовательных уступок
6. Метод целевого программирования
7. Принцип гарантированного результата (метод максиминной свертки)
8. Метод равных наименьших относительных отклонений