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

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

МЕТОДЫ РЕШЕНИЯ
МНОГОКРИТЕРИАЛЬНЫХ ЗАДАЧ.
СВЕРТКА КРИТЕРИЕВ
Космачева И.М., Астрахань, АГТУ

2. Проблема оптимальности в многокритериальных задачах

Качество решения оценивается по многим
критериям;
Объективно неизвестно, какое решение
лучше, если критериев много и/или они
«конфликтующие».
Проблема выбора единственного решения:
парето-оптимальных решений может быть
много.

3.

Методы решения
многокритериальных задач
Интерактивные
Метод
анализа
иерархий
Метод
эффективных
множеств
Лексикографическая
оптимизация
Метод
уступок
Аддитивные
Метод
главного
критерия
Сведение к
однокритериальным
Методы
свертки
Мультипликативные
Метод целевого
программиров
ания
Максиминные
3

4. Проблемы задач оптимизации

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

5. Проблемы задач многокритериальной оптимизации

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

6. Общие сведения о многокритериальных задачах

Впервые
проблема
многокритериальной
оптимизации возникла
у
итальянского
экономиста В. Парето
при математическом
исследовании
товарного объёма.
6

7. Принцип Парето

7
В законе. В 80% всех аварий виноваты только 20%
водителей.
В экономике. 20% работающего населения обеспечивает
80% пенсионеров. Остальные не работают, не платят
налоги и т.д.
В науке. Лишь 20% ученых совершают 80% открытий и
создают 80% изобретений.
В
торговле. 80% прибыли компании приносят 20%
клиентов. 80% продаж приходится на 20% продуктов.
Основное следствие закона Парето: факторов, дающих
наибольший вклад в результат, всегда немного.
Принцип Парето позволяет сузить класс возможных
претендентов на решение и исключить из
рассмотрения заведомо неконкурентоспособные
варианты.

8. Принцип Парето

8
Принцип Парето не является универсальным,
пригодным
во
всех
без
исключения
многокритериальных задачах, и иногда может
нарушаться.
Пример 1: Если последовательно применять «принцип
Парето» для отбора клиентов - после избавления от
аутсайдеров предприятие попадет в зависимость от
узкой группы VIP-клиентов.
Пример 2: Попытка уменьшить избыточность речи
путём исключения слов, не имеющих прямого
отношения к сообщению, ведёт к тому, с каждым
сокращением сообщение всё менее понятно адресату и
допускает больше произвольных толкований.

9. Принцип Парето

9
Стратегии
поведения
человека
в
условиях
многокритериальной среды можно разделить на два
класса:
стратегия исключения;
стратегия компенсации.
Результаты
экспериментальных
исследований
показывают, что при решении многокритериальных задач
с более чем двумя возможными решениями, человек
обычно не придерживается лишь одной линии поведения.

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

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

11. Отношение Парето

11

12.

Множество Парето

13. Методы многокритериальной оптимизации:множество Парето

13

14. Методы многокритериальной оптимизации:множество Парето

14
x1
x2
х3
x4
х5
(2,2,3) (1,0,2) (4,2,1) (0,3,5) (2,1,1)
0
0
A(P ) 0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0

15. Множество Парето

16.

Множество Парето
Отношение Парето является отношением строгого порядка
(антирефлексивным,
асимметричным,
транзитивным),
инвариантным относительно сдвига и гомотетии, т.е.
xPy ( x z ) P( y z ) z R ,
xPy ( x) P( y ) 0.
n

17.

Отношение лексикографии

18.

Отношение лексикографии
Отношение лексикографии является отношением строгого
линейного порядка, инвариантным относительно сдвига и
гомотетии, т.е.
xLy ( x z ) L( y z ) z R ,
xLy ( x) L( y ) 0.
n

19. Методы многокритериальной оптимизации

1)методы свертки критериев,
2)методы, основанные на наложении
ограничений на критерии,
3)методы, основанные на отыскании
компромиссного решения,
4)методы целевого программирования и
др.

20. Методы многокритериальной оптимизации: свертки

20
• Линейная
• Мультипликативная
• Максиминная (минимаксная) свертка
fi(x) –оценка альтернативы x по i-му критерию,
pi –коэффициент важности i-го критерия, pi (i=1,2,…,n) –
принимают значения из [0,1] и удовлетворяют условию
нормировки .