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

Рис. 5. Примеры КК (компромиссная кривая выделена красным цветом)

Опр. Решение X2 называется доминируемым, если существует решение X1, не хуже чем X2, т. е. для любой оптимизируемой функции Fi, I=1, 2, …, m,

Fi(X2)£Fi(X1) при максимизации функции Fi,

Fi(X2)³Fi(X1) при минимизации Fi.

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

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

6.  Критерий Гурвица

Представляется логичным, что при выборе решения вместо двух крайностей в оценке ситуации придерживаться некоторой промежуточной позиции, учитывающей возможность как наихудшего, так и наилучшего, благоприятного поведения природы. Согласно этому подходу для каждого решения необходимо определить линейную комбинацию min и max выигрыша и взять ту стратегию, для которой эта величина окажется наибольшей, т. е. стараясь занять уравновешенную позицию, Гурвиц предложил критерий (HW), оценочная функция которого находится где-то между точками предельного оптимизма и крайнего пессимизма. Оценочная функция имеет две формы записи:

ZHW =, (5)

где g — “степень пессимизма” ("коэффициент пессимизма", весовой множитель), 0£ g £1.

Матрица решений дополняется столбцом, содержащим средние взвешенные наименьшего и наибольшего результатов каждой строки. Выбираются те варианты Xi, в строках которых стоят наибольшие элементы air этого столбца.

Замечание. В литературе используется и такая форма критерия Гурвица:

ZHW =, (6)

где g - “степень оптимизма” ("коэффициент оптимизма ", весовой множитель), 0£g£1.

При g=0 критерий Гурвица (6) тождественен критерию Вальда, а при g=1 совпадает с максиминным решением.

Критерий Гурвица предъявляет к ситуации, в которой принимается решение, следующие требования:

v  о вероятностях появления Вj ничего не известно;

v  с появлением состояний Вj необходимо считаться;

v  реализуется лишь малое количество решений;

v  допускается некоторый риск.

7.  Внутренние, выходные и внешние параметры

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

Опр. 3. Параметры элементов объекта называют внутренними параметрами, величины. Следовательно, внутренние параметры характеризуют свойства элементов проектируемого объекта (проектные параметры).

Опр.4. Те внутренние параметры, которые являются независимыми друг от друга и могут изменяться в некоторых пределах, называются управляемыми параметрами (независимыми).

Опр.5. Параметры, характеризующие свойства объекта, называют выходными параметрами.

Опр.6. Параметры, характеризующие свойства внешней по отношению к рассматриваемому объекту среды, называют внешними параметрами.

8.  Платёжная матрица. Цена игры. Седловая точка

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

	В1	В2	. . .	Вn
А1	а11	а12		а1n
А2	а21			а2n
. . .
Аm				аmn

В теории игр седловая точка (седловой элемент) — это наибольший элемент столбца матрицы игры, который одновременно является наименьшим элементом соответствующей строки (в игре двух лиц с нулевой суммой). В этой точке, следовательно, максимин одного игрока равен минимаксу другого; С. т. есть точка равновесия.

9.  Векторный критерий. Критериальное пространство

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

Критерии Fi(X), i=1,2, . . . , m, образуют векторный критерий F(X)=(F1, F2, . . . , Fm).

Пусть X1ÎD, тогда

F1(X1) - локальная оценка решения X1 по 1 - му критерию или критерию F1;

F2(X2) - локальная оценка решения X1 по 2 - му критерию или критерию F2;

.

Fm(Xm) - локальная оценка решения X1 по m - му критерию или критерию Fm;

F(X1) = (F1(X1), F2(X1), Fm(X1)) - векторная оценка для решения X1.

Для пояснения сущности задач используют геометрическую интерпретацию, связанную с введением m – мерного пространства Em пространства параметров проектирования (управляемых параметров) и k – мерного пространства Ek выходных параметров. Каждой точке пространства Em и Ek соответствуют векторы X и Y значений переменных проектирования и выходных параметров соответствующего проектируемого объекта. Следовательно, допустимой области D (образ) можно поставить в соответствие некоторое множество оценок. Это множество будем обозначать YD и его будем называть критериальным пространством или областью критериев (оценок), т. е. YD=F(D) – прообраз множества D.

10.  Метод приписывания баллов

Определить коэффициенты li по методу присваивания баллов, используя шкалу [0;10].

Эксперты	Критерии
S	R	P	C
1	4	6	8	2
2	8	6	2	4
3	6	8	4	2
4	8	6	4	2
5	2	8	6	4
å оценок	r1=1,4	r2=1,7	r3=1,2	r4=0,7

l1=0,28, l2=0,34, l3=0,24, l4=0,14

Этот метод основан на том, что эксперты оценивают важность частного критерия по шкале [0-10]. Обозначим через hik - балл i - го эксперта для k- критерия, тогда

где - сумма i - ой строки.

rik - называют весом, подсчитанным для k - критерия i - м экспертом. Отсюда,

, получим

11.  Аддитивный критерий

Идея этого метода заключается в том, что обобщённый критерий записывается в следующем виде:

(1)

который называют аддитивным критерием. Здесь li³0 являются весовыми коэффициентами, которые задают предпочтение i - го критерия по сравнению с другими критериями. Таким образом, мы получили однокритериальную задачу математического программирования

.