Сформулировать задачу многокритериальной (векторной) оптимизации (стр. 5 )

18.  Принятие решений в условиях неопределённости

Если распределение вероятностей будущих состояний природы не известно, вся информация о природе сводится к перечню ее возможных состояний.

Пример. Игра "Поставщик".

Выпуск продукции фирмы существенно зависит от скоропортящегося материала, например, молока или ягод, поставляемого партиями стоимостью 100ед. Если поставка не прибывает в срок, фирма теряет 400 ед. от недовыпуска продукции. Фирма может послать к поставщику свой транспорт (расходы 50 ед.), однако опыт показывает, что в половине случаев транспорт возвращается ни с чем. Можно увеличить вероятность получения материала до 80%, если предварительно послать своего представителя, но расходы увеличатся еще на 50 ед. Существует возможность приобретать более дорогой (на 50%) материал-заменитель у другого, вполне надежного поставщика, однако, кроме расходов на транспорт (50 ед.) возможны дополнительные издержки хранения материала в размере 30 ед., если его количество на складе превысит допустимую норму, равную одной партии.

Какой стратегии должен придерживаться завод в сложившейся ситуации?

Формализация. У природы два состояния: поставщик надежный и поставщик ненадежный. У фирмы - четыре стратегии: 1) не осуществлять никаких дополнительных действий, 2) послать к поставщику свой транспорт, 3) послать к поставщику представителя и транспорт, 4) купить и привезти материал-заменитель от другого поставщика.

Составим таблицу расчетов:

	Затраты и убытки фирмы-изготовителя
Ситуация	Стоимость материала	Недовыпуск продукции	Транспорт	Командировочные расходы	Издержки хранения	Общая сумма
1 1	- 100	0	0	0	0	- 100
1 2	0	- 400	0	0	0	- 400
2 1	- 100	0	- 50	0	0	- 150
2 2	- 50	- 200	- 50	0	0	- 300
3 1	- 100	0	- 50	- 50	0	- 200
3 2	- 80	- 80	- 50	- 50	0	- 260
4 1	- 250	0	- 50	0	- 30	- 330
4 2	- 150	0	- 50	0	0	- 200

Решение. На основе полученных результатов вычислений можно составить платежную матрицу:

		min	max
- 100	- 400	- 400
- 150	- 300	- 300
- 200	- 260	- 260	- 260
- 330	- 200	- 330

Ответ. Нужно придерживаться третьей стратегии и затраты не превысят 260 ед., если послать к поставщику представителя и транспорт.

1. Рассмотренный способ поиска оптимального решения называется критерием Вальда (Максиминный критерий принятия решения). Выбирается решение, гарантирующее получение выигрыша не меньше, чем maxmin:

vW = maxi minj aij = -260 ед.

Применяя этот критерий, мы представляем на месте природы активного и злонамеренного противника. Это пессимистичный подход.

2. Максимаксный критерий. Самый благоприятный случай:

vM = maximaxj aij = -100 ед.

Если фирма ничего не предпримет, то потратит не больше 100 единиц. Это критерий абсолютного оптимизма.

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

Опр. Стратегия X1ÎD называется эффективной (оптимальной по Парето), если не существует стратегии X2ÎD такой, что Fi(X2) £Fi(X1), i=1, . . ., m, F(X2)¹F(X1), или

Опр. Если решение не доминируемо никаким другим решением, то оно называется недоминируемым или оптимальным в смысле Парето.

Очевидно, тогда в составе множества D нет смысла сохранять решение X2, оно вытесняется (или, как говорят, “доминируется”) решением X1. Ладно, выбросим, решение X2 как неконкурентоспособное и перейдём к сравнению других решений по всем критериям. В результате такой процедуры отбрасывания заведомо непригодных, невыгодных решений множество D обычно сильно уменьшается: в нём сохраняются только так называемые эффективные (иначе “паретовские”) решения, характерные тем, что ни для одного из них не существует доминирующего решения. Множество таких точек и называется множеством точек оптимальных по Парето. Множество точек оптимальных по Парето лежат между точками оптимумов, полученных при решении задачи математического программирования для каждого частного критерия. В литературе множество точек оптимальных по Парето, как правило, обозначают буквой P (PÌD).

Опр. Множество векторных оценок, соответствующих множеству эффективных точек, называют областью компромиссов (переговорным множеством) или множеством Парето в области критериев. Будем обозначать YP (YP ÍYD).

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

В области Yc нет противоречия между частными критериями оптимальности, т. к. каждая точка XÎD может быть изменена таким образом, что будет одновременно улучшены все частные критерии.

Если область критериев YD состоит только из области согласия Yc, то существует единственная точка XoptÎD, в которой все частные критерии согласованны между собой в том смысле, что при движении к точке Xopt все Fi(X) i=1, 2, . . ., m, одновременно улучшаются. Все частные критерии достигают минимума в т. Xopt (см. рис. 1). Такую точку называют оптимальным решение и

Рис. 1. Критерии F1 и F2 непротиворечивы

при этом значения всех частных критериев достигают в ней минимума.

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

Рис. 2. Критерии F1 и F2 противоречивы на отрезке [1; 2]

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

20.  Антагонистические игры. Платёжная матрица Цена игры

Игра называется игрой с нулевой суммой, если сумма выигрышей всех игроков равна нулю, т. е. каждый игрок выигрывает только за счёт других. Самый простой случай – парная игра с нулевой суммой – называется антагонистической.

Опр. Антагонистической игрой называется система G=<A, B,H>, где A, B - непустые множества стратегий соответственно первого и второго игроков; H(a, b) – функция выигрыша игрока A (то есть функция потерь игрока B), aÎA, bÎB.

Для задания такой игры достаточно выписать так называемую платежную матрицу, в которой строки соответствуют стратегиям первого игрока, а столбцы – стратегиям второго игрока. Элементами матрицы служат выигрыши первого игрока.

Игру будем обозначать буквой G. В этой игре участвуют два игрока А и В, имеющих противоположные интересы: выигрыш одного равен проигрыше другого. Так как выигрыш игрока А равен выигрышу игрока В с обратным знаком, мы можем интересоваться только выигрышем а игрока А. Естественно, А хочет максимизировать, а В – минимизировать а. Для простоты отождествим себя с игроком А и будем его называть "мы", а игрока В "противник" (разумеется, никаких реальных преимуществ для игрока А из этого не вытекает). Пусть у нас имеется m возможных стратегий А1, А2, . . . ,Аm, а у противника – n – возможных стратегий В1, В2, . . ., Вn (такая игра называется игрой m´n). Обозначим аij наш выигрыш в случае, если мы пользуемся стратегией Аi, а противник – стратегией Вj. Предположим, что для каждой пары стратегий Аi, Вj выигрыш (или средний выигрыш) аij нам известен. Тогда в принципе можно составить прямоугольную таблицу (матрицу), в которой перечислены стратегии игроков и соответствующие выигрыши (см. таблицу).

Величина a= называется нижней ценой игры. Величина b=

называется верхней ценой игры.

21.  Метод ранжирования

таблица 12

Эксперты	Места
1	2	3	4
1	S	P	R	C
2	P	R	S	C
3	P	S	C	R
4	P	S	R	C
5	P	S	C	R

Пусть экспертиза проводится группой из L экспертов. Метод ранжирования основан на том, что каждого эксперта просят расставить частные критерии проектируемого объекта в порядке их важности. Цифрой 1 обозначают наиболее важный частный критерий, цифрой 2 - следующий по важности частный критерий и т. д. Эти ранги преобразовываются таким образом, что ранг 1 - получает оценку m, ранг 2 - оценку m-1 и т. д. до ранга m, которому присваивается оценка 1. Обозначим полученные оценки rik - где i - i - й эксперт, k - k - й критерий. Тогда результаты опроса экспертов можно свести в таблицу