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




страница1/3
Дата05.05.2016
Размер0.59 Mb.
  1   2   3

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

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

Критерии Fi(X), i=1,2, . . . , m, образуют векторный критерий F(X)=(F1, F2, . . . , Fm). Поэтому в литературе также используют термин "векторная оптимизация".
Сформулируем задачу многокритериальной оптимизации. Она имеет вид:

min F(X) min F(X)

XD или - параметрические ограничения

hk(X)=0, k=1,2, . . . , K; -функц.ограничения равенства

gj(X)  0, j= 1,2, . . . , J. - функц.ограничения неравенства

Задача многокритериальной оптимизации может быть сформулирована следующим образом, например:

в квадрате D={-1x1 1, -1x2 1} заданы два критерия


которые желательно минимизировать.

Замечание. Символ minF(X) понимается как набор символов minFi(X), i=1,2, . . . , m. Будем предполагать, что все критерии нужно минимизировать, т.к. всегда можно перейти от maxFi(X) к min[-Fi(X)], i=1,2, . . . , m, т.е. сменой знака перед частным критерием.

Процесс решения задачи (4), как правило, состоит из двух этапов:



  1. Найти такое множество P  D, для которого F(P)=minF(X), XD;

  2. Определить вектор D, являющийся наиболее предпочтительным из всех векторов множества P и набор технических характеристик объекта Fi(X0), i=1,2, . . . , m.

Таким образом, в результате решения задачи (4) мы получим вектор оптимальных параметров объекта и набор технических характеристик объекта Fi(X0), i=1,2, . . . , m.

Основная сложность логического анализа многокритериальных задач состоит в том, что в них, в отличие от "обычных" (однокритериальных) задач появляется эффект несравнимости вариантов (исходов). Например, если исходы оцениваются по двум критериям (критерии минимизируются) и имеем два вектора оценок (F1(X1), F2(X1))=(2, 5) и (F1(X2), F2(X2))=(3, 2). Вариант X1 лучше по первому критерию, а вариант X2 лучше по второму критерию, то варианты X1 и X2 несравнимы между собой. Несравнимость исходов является формой неопределённости, которая, в отличие от неопределённости, вызванной воздействием среды, связана со стремлением лица принимающего решение “достичь противоречивых целей” и может быть названа ценностной неопределённостью. Выбор между несравнимыми исходами является сложной концептуальной проблемой и составляет основное содержание многокритериальной оптимизации.




  1. Критерий Вальда

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

α= (3)

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

Таблица 10. Пример вариантов решения без учёта риска



B

X


В1

В2

В3

аir



X1

1

10

1

1




X2

1.1

1.1

1.2

1.1

1.1

Выбирая вариант X2, предписываемый критерием Вальда, мы избегаем неудачного значения 1, реализующего в варианте X1 при внешнем состоянии B1, получая вместо него при этом состоянии немного лучший результат 1.1, зато в состоянии В2 теряем выигрыш 10, получая всего только 1.1. Это пример показывает, что в многочисленных практических ситуациях пессимизм минимаксного критерия может оказаться невыгодным

Применение критерия Вальда бывает оправдано, если ситуация, в которой принимается решение, характеризуется следующими обстоятельствами:



  • о возможности появления внешних состояний Вj ничего не известно;

  • приходится считаться с появлением различных внешних состояний Вj;

  • решение реализуется лишь один раз;

  • необходимо исключить какой бы то ни было риск, т.е. ни при каких условиях Вj не допускается получать результат, меньший, чем ZMM.




  1. Ограничения. Допустимая область

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

Проектировщики могут указать разумные пределы изменения каждого из внутренних параметров, которые мы будем называть параметрическими

(2)

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

hk(X)=0, k=1,2, . . . , K; ограничения равенства (3)

gj(X)  0, j= 1,2, . . . , J. ограничения неравенства (4)

Очевидно, ограничения (2) выделяют в n – мерном пространстве параметров параллелепипед П. Ограничения (3) выделяют в параллелепипеде П некоторое подмножество G. Пример. Пусть n=2.

Рис 1. Область работоспособности

Множество D - допустимая область (область работоспособности) - это множество векторов X, для которых одновременно выполняются условия (2), (3) и (4).


  1. Понятие риска


Риском игрока rij при выборе стратегии i в условиях (состояниях) природы j называется разность между максимальным выигрышем, который можно получить в этих условиях и выигрышем, который получит игрок в тех же условиях, применяя стратегию i. Принятие решений в условиях риска характеризуется тем, что поведение природы (среды) имеет случайный характер. Это проявляется в том, что существует некоторая вероятностная мера, в соответствии с которой возникают (наступают) те или иные состояния природы. При этом лицо принимающее решение имеет определённую информацию о вероятностях появления состояний среды, которая по своему характеру может быть весьма разнообразна. Например, имеется три состояния среды B1, B2 и B3, то дополнительная информация о появлении этих состояний может заключаться в том, что состояние B1 наименее вероятно, а состояние B3 более вероятно.

Следовательно, принятие решений в условиях риска предполагает, кроме задания функции реализации, задание некоторой дополнительной информации о вероятностях состояния среды. Если множество состояний природы B конечно (число состояний равно m), то вероятностная мера на нём может быть задана вероятностным вектором q=(q1, q2, …, qm), где qj≥0 и .

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

Таблица 1. Платёжная матрица с вероятностным вектором состояния среды



Решения

Состояния среды

q1



qj



qm

B1



Bj




Bm

X1

a11




a1j




a1m


















Xi

ai1




aij




aim


















Xn

an1




anj




anm

Выбирая решение Xi, игрок знает, что получит один из выигрышей a11, …, a1m с вероятностями q1, …, qm соответственно. Следовательно, исходом для принимающего решение при выборе им решения Xi является случайная величина

.

Итак, сравнение двух решений X1 и X2 сводится к сравнению соответствующих им случайных величин ..

Выбор оптимального решения обычно основывается на одном из следующих критериев:

1) критерий Байеса-Лапласа – ожидаемого значения (прибыли или расходов);

2) комбинации ожидаемого значения и дисперсии;

3) критерий произведения;

4) наиболее вероятного события в будущем и другие.


  1. Множество Р. Компромиссная кривая (аналитически)

Особый интерес для практики — m=2. В этом случае множество паретовских точек представляет собой одномерное многообразие на плоскости и допускает удобное графическое представление.

Опр. Множество паретовских точек в двухмерном пространстве критериев называют компромиссной кривой.

Она может состоять из несвязных кусков и содержать изолированные точки (см. рис. 5). Компромиссная кривая (КК) строго монотонно убывает в следующем смысле. Пусть Y1 и Y2 произвольные точки, принадлежащие КК. Обозначим их координаты Y1(y1,y2) и Y2(y3,y4), если y1y4. Таким образом, КК не содержит ни горизонтальных, ни вертикальных отрезков и её уравнение может быть представлено в форме F2=u(F1) и F1=v(F2).



Рис. 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 (PD).




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

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

ZHW =, (5)

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

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

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

ZHW =, (6)

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

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

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



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

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

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

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




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

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

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

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

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

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


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

Игру будем обозначать буквой 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

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







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

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

Критерии 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.




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

Определить коэффициенты i по методу присваивания баллов, используя шкалу [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

1=0,28, 2=0,34, 3=0,24, 4=0,14

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


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

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



, получим

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

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



(1)

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



.

XD XD
Замечание. Частные критерии имеют различную размерность. Поэтому при образовании обобщённого критерия нужно работать не с натуральными критериями, а с их нормированными значениями. Нормированный критерий представляет собой отношение “натурального” частного критерия к некоторой нормирующей величине. Возможно несколько подходов к выбору нормирующего делителя:



  • в качестве нормирующего делителя берут директивные значения параметров, заданные заказчиком.

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

  • берут лучшие мировые достижения в данной области;

  • в качестве нормирующего берут разность между max и min значениями критерия в области D

Замечание. Пусть имеется два решения X1 и X2. Тогда в соответствии с изложенным принципом следует вычислить сумму абсолютных изменений всех частных критериев, обусловленных этим переходом (переход от X1 к X2)

В случае f<0 решение X2 признаётся лучшим, чем X1, если f>0, то лучше X1. Тогда оптимальным решением будет такое, для которого f0 при переходе от него к любому другому решению, т.е.



где Xopt – точка min, X любая точка из D.

Замечание. Если решается задача выпуклого программирования, то полученное решение (с использованием аддитивного критерия) является оптимальным по Парето, т.е. оптимальное решение, полученное с использованием метода линейной свёртки, лежит в области эффективных решений. Решение, полученное с использованием аддитивного критерия оптимальности — это точка, которая в наибольшей мере удалена от начала координат, однако не вышла за пределы области допустимых значений


  1. Деревья решений

Руководитель поисковой группы должен принять решение: бурить нефтяную скважину или нет. Скважина может оказаться "сухой" (С), т.е. без нефти, "маломощной" (М), т.е. с малым содержанием нефти, и "богатой" (Б), т.е. с большим содержанием нефти. Альтернативами руководителя группы являются: x1 – бурить и x2 – не бурить. Чистая прибыль при выборе одной из альтернатив в зависимости от возможного типа скважины приведена в таблице прибылей (см. табл. 1)

Таблица 1. Платёжная матрица


Тип скважины

Решения


С

М

Б

x1

-70

50

200

x2

0

0

0

Кроме того, руководителю поисковой группы известно, что в данной местности вероятности сухой, маломощной или богатой скважины таковы: P(C)=0.5, P(M)=0.3, P(Б)=0.2.

Руководитель поисковой группы может провести эксперимент с целью уточнения структуры грунта (состояния среды). Этот эксперимент представляет собой сейсморазведку, результатом которой будет ответ – какова структура грунта в данной местности (но не ответ на вопрос о типе скважины!). В принципе структура грунта может быть либо открытой (О), либо замкнутой (З). Руководитель группы имеет таблицу результатов экспериментов, приведённой в этой местности (см. табл. 2).

Таблица 2. Таблица экспериментальных данных


Тип скважины

Структура грунта

Всего

открытая (О)

замкнутая (З)

С (сухая)

n11=45

n12=5

50

М (маломощная)

n21=11

n22=19

30

Б (богатая)

n31=4

n32=16

20

Всего

60

40

n=100

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

Проведём анализ экспериментальных данных полученной таблицы. Предположим, что произведено n экспериментов, результаты которых являются значениями дискретных случайных величин X (тип скважины) и Y (структура грунта), которые принимают соответственно значения С, М, Б и О, З. Обозначим через n11 число экспериментов, в которых X=С и Y=О, через n12 число экспериментов, в которых X=С и Y=З, через n21 число экспериментов, в которых X=М и Y=О и т.д. В нашем случае n=100, n11=45, n12=5, n21=11. Разделив значения таблицы 2 на 100 (число проведённых экспериментов), мы получим закон распределения двумерной случайной величины (X, Y) заданной в табличной форме (см. табл. 3).

Таблица 3. Статистический ряд распределения двумерной с.в. (X, Y)


X,
тип скважины

Y,
структура грунта



открытая (О)

замкнутая (З)

С (сухая)

p11=0.45

p12=0.05

0.50

М (маломощная)

p21=0.11

p22=0.19

0.30

Б (богатая)

p31=0.04

p32=0.16

0.20



0.60

0.40

1

Из таблицы 3 следует, что Р(X=C)=P(C)=0.5, Р(X=M)=P(M)=0.3, Р(X=Б)=P(Б)=0.2; Р(Y=O)=P(O)=0.6, Р(Y=З)=P(З)=0.4,

Итак, руководитель группы должен принять решение:



  • проводить ли эксперимент (его стоимость составляет 10 единиц);

  • если проводить, то, как поступать в дальнейшем в зависимости от результатов эксперимента.

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

Шаг 1. Построим дерево (рис. 1), на котором указаны все этапы процесса принятия решений – дерево решений. Ветви дерева соответствуют возможным альтернативам, а вершины – возникающим ситуациям. Альтернативами руководителя поисковой группы являются : α – отказ от эксперимента, β – проведение эксперимента, x1 – бурить, x2 – не бурить. Состояния природы: выбор типа скважины (С, М, Б), а также выбор структуры грунта (О, З).

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

Игра протекает следующим образом. В начальной позиции ход делает руководитель группы. Он должен принять решение – отказаться от эксперимента (выбрать решение α) или проводить эксперимент (выбрать решение β). Если он отказался от эксперимента, то игра переходит в следующую позицию, в которой руководитель группы должен принять решение: бурить (выбрать альтернативу x1) или не бурить (выбрать альтернативу x2). Если же он решает проводить эксперимент, то игра переходит в позицию, в которой ход делает природа, выбирая одно из состояний О или З, соответствующих возможным результатам эксперимента, и т. д. Игра заканчивается тогда, когда она переходит в окончательную позицию (т.е. вершину дерева, для которой нет исходящих из неё ветвей)

Шаг 2. Для каждого решения, которое является ходом природы (т.е. исходит из позиции, изображённой кружком), надо найти вероятность этого хода. Для этого поступаем следующим образом. Для каждой позиции дерева существует единственный путь, соединяющий эту позицию с начальной позицией. Если это для позиции природы, путь, соединяющий её с с начальной позицией, не проходит через позицию (Э), означающую проведение эксперимента, то вероятности состояний Р(С), Р(М) и Р(Б) являются безусловными (доопытными) и находятся из табл. 3:

Р(С)=50/100, Р(М)=30/100, Р(Б)=20/100.

Если же для позиции природы путь, соединяющий её с начальной позицией, проходит через позицию (Э), то вероятности состояний среды становятся условными вероятностями и находятся по формулам (1), используя данные табл. 3:

=45/60; =5/40; 

 =1/15; .

В позиции (Э) вероятности ходов, приводящих к позициям (О) и (З), находятся из таблицы 3: Р(О)=0.6, Р(З)=0.4.



Шаг 3. Произведём оценку всех позиций дерева игры, "спускаясь" от конечных позиций к начальной. Оценкой позиции служит ожидаемый выигрыш в этой позиции. Оценки конечных позиций находим из таблицы 2. Укажем теперь способ нахождения оценки произвольной позиции дерева игры в предположении, что уже найдены оценки всех следующих за ней позиций.

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

1 – ветвь: =20

2 – ветвь: 0


3
С проведением эксперимента.
Выбираем максимальное значение из
(-30, 0, 95, 0). Оно равно 95.
– ветвь:= -30

4 – ветвь: 0

5 – ветвь: =95

6 – ветвь: 0


Как следует из условия задачи, значение в 95 единиц мы можем получить с вероятностью 0.4. Следовательно, ожидаемый выигрыш будет равен 0.4*95=38 единицам. Вычитаем расходы на проведение эксперимента равное 10 единицам. В итоге получим 28 единиц.

  1. Мультипликативный критерий

В ряде задач проектирования более целесообразным является оперирование с относительными изменениями значений частных критериев.

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

В математической формулировке условие оптимальности на основе принципа справедливой относительной компенсации имеет вид



(3)

где ΔFi(X) – приращение величины i – го критерия, Fi(X) – первоначальная величина i – го критерия.

Полагая , можно представить (3) как дифференциал натурального логарифма

(4)

Из выражения (4) следует, что принцип относительной компенсации приводит к мультипликативному обобщённому критерию оптимальности



(5)

Мультипликативный критерий образуется путём простого перемножения частных критериев в том случае, когда они имеют одинаковую важность. В случае неравноценности частных критериев вводятся весовые коэффициенты i и мультипликативный критерий примет вид



(6)

Мультипликативный критерий иногда представляется в виде отношения произведений частных критериев (выходных параметров)



m1+m2=m; (7)

где в числителе перемножаются все выходные параметры, требующие максимизации и имеющие ограничения а в знаменателе – все выходные параметры, требующие минимизации и имеющие ограничения , где TTi – значение технического требования, предъявленного к i– му критерию. Целевая функция (7) в дальнейшем подвергается максимизации.

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



  1. Критерий Сэвиджа


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

При выборе решения по этому критерию сначала матрице полезности сопоставляется матрица сожалений D - для нашего примера, вычитанием (616,5) из первого столбца матрицы полезности, 1233 из второго столбца, 1849,5 и 2466 из третьего и четвертого столбцов соответственно, получим матрицу рисков:



B

X


B1=2

B2=4

B3=6

B4=8

air

X1=1

0

616,5

1233

1849,5

1849,5

X2=2

83,5

0

616,5

1233

1233

X3=3

167

83,5

0

616,5

616,5

X4=4

250,5

167

83,5

0

250,5

Наименьшее значение среди максимальных элементов строк (выделенные в таблице значения) равно:



ZS=min(1849,5; 1233; 616,5; 250,5)=250,5

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

ZS=. (6)


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

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

При решении задач методом последовательных уступок вначале нужно определить важность частных критериев, т.е. расположить частные критерии в порядке убывания важности. Таким образом, главным считается критерий F1 , менее важным F2, . . . , Fm. Минимизируется первый по важности критерий и определяется его наименьшее значение F1min . Затем назначается величина допустимого снижения уступки 10 критерия F1 и ищется наименьшее значение критерия F2 при условии, что значение F1 должно быть не больше, чем F1min+1. Снова назначается уступка 20, но уже по второму критерию, которая вместе с первой используется при нахождении условного минимума F3 и т.д. Наконец, минимизируется последний по важности критерий Fm при условии, что значения каждого критерия Fi из m-1 предыдущих должны быть не больше соответствующей величины Fimin+i .Получаемое в итоге решение считается оптимальным.

Таким образом, оптимальным считается всякое решение, являющимся решением последней задачи из следующей последовательности задач

Величины уступок выбирают в пределах инженерной точности, т.е. 5-10% от наименьшего значения критерия.

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



  1. Классификация задач выбора

1. Вид отображения F детерминированное, вероятностное или неопределённое, что позволяет выделить соответственно:

задачи Принятия Решений в условиях определенности (детерминированные);

задачи ПР в условиях риска;

задачи ПР в условиях в условиях неопределённости.

2. Мощность множества критериев - одноэлементное или состоящее из нескольких критериев:

задачи ПР со скалярным критерием;

задачи ПР с векторным критерием (многокритериальные задачи).

3. Тип системы - отображает предпочтения одного лица или коллектива, поэтому

задачи индивидуального ПР;

задачи группового ПР.


  1. Способы сужения Парето-оптимального множества


Первый подход. Для заданной многокритериальной задачи оптимизации находится множество её Парето-оптимальных решений, а выбор конкретного оптимального варианта из множества Парето-оптимальных предоставляется ЛПР.

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

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



Указание верхних границ критериев. Дополнительная информация об оптимальном исходе XoptD в этом случае имеет вид

()

Число Ci рассматривается здесь как верхняя граница по i – му критерию.

Отметим, что указание верхних границ по критериям не может быть "извлечено" из математической модели задачи принятия решения; набор ограничений (C1, C2, , Cm) представляет собой дополнительную информацию, полученную от ЛПР.

Рассмотрим теперь второй подход, который приводит к сужению Парето-оптимального множества на основе дополнительной информации, получаемой от ЛПР.

а) Указание нижних границ критериев. Наложим, например, следующие ограничения на оптимальное решение:

зарплата — не менее 600 рублей;

длительность отпуска — не менее 30 дней;

время поездки — не более 40 минут.

Варианты, удовлетворяющие этим дополнительным ограничения: {3, 6, 9}; из них оптимальными по Парето являются варианты 3 и 6. Остаётся сделать окончательный выбор между вариантами 3 и 6.

б) Субоптимизация. Пусть в качестве выделенного (главного, важнейшего) критерия выступает критерий зарплата; ограничения длительность отпуска — не менее 30 дней, время поездки — не более 40 минут. Отбросим варианты, которые не удовлетворяют данным ограничениям; остаются варианты: {2, 3, 5, 6, 9}. Из них максимальную зарплату имеет вариант 3. Этот вариант и будет оптимальным.

в) Лексикографическая оптимизация. Упорядочим критерии по относительной важности. Например, следующим образом: (т.е. важнейший критерий — зарплата, следующий за ним по важности время поездки, наименее важный критерий длительность отпуска). Максимальное значение по критерию З имеют варианты 1 и 7. Далее сравниваем эти варианты по второму по важности критерию В. Так как время поездки для этих вариантов одинакова, переходим к третьему критерию Д; по критерию длительность отпуска лучшим является вариант 7, который и является здесь оптимальным.





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

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

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

Выпуск продукции фирмы существенно зависит от скоропортящегося материала, например, молока или ягод, поставляемого партиями стоимостью 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 единиц. Это критерий абсолютного оптимизма.




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

Опр. Стратегия X1D называется эффективной (оптимальной по Парето), если не существует стратегии X2D такой, что Fi(X2) Fi(X1), i=1, . . ., m, F(X2)F(X1), или
Опр. Если решение не доминируемо никаким другим решением, то оно называется недоминируемым или оптимальным в смысле Парето.
Очевидно, тогда в составе множества D нет смысла сохранять решение X2, оно вытесняется (или, как говорят, “доминируется”) решением X1. Ладно, выбросим, решение X2 как неконкурентоспособное и перейдём к сравнению других решений по всем критериям. В результате такой процедуры отбрасывания заведомо непригодных, невыгодных решений множество D обычно сильно уменьшается: в нём сохраняются только так называемые эффективные (иначе “паретовские”) решения, характерные тем, что ни для одного из них не существует доминирующего решения. Множество таких точек и называется множеством точек оптимальных по Парето. Множество точек оптимальных по Парето лежат между точками оптимумов, полученных при решении задачи математического программирования для каждого частного критерия. В литературе множество точек оптимальных по Парето, как правило, обозначают буквой P (PD).

Опр. Множество векторных оценок, соответствующих множеству эффективных точек, называют областью компромиссов (переговорным множеством) или множеством Парето в области критериев. Будем обозначать 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]

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


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

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

Опр. Антагонистической игрой называется система G=, где 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 нам известен. Тогда в принципе можно составить прямоугольную таблицу (матрицу), в которой перечислены стратегии игроков и соответствующие выигрыши (см. таблицу).

Величина  называется нижней ценой игры. Величина 




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




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

таблица 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 - й критерий. Тогда результаты опроса экспертов можно свести в таблицу

, i=1,2, …,m.

В (L+1) - строке стоят суммы оценок, полученных критериями от экспертов. Тогда весовые коэффициенты определяются следующим образом



- (i=1,2, . . . , m) - формула для вычисления весовых коэффициентов i по методу ранжирования.


  1. Методы последовательной оптимизации


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

Существует один, часто применяемый способ свести многокритериальную задачу к однокритериальной – это выделить один (главный, основной) критерий F1 и стремиться его обратить в максимум (минимум), а на остальные F2, F3 , . . Fm частные критерии наложить только некоторые ограничения, потребовав, чтобы они были не меньше (больше) каких-то заданных величин.



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

Вначале нужно определить важность частных критериев, т.е. расположить частные критерии в порядке убывания важности. Таким образом, главным считается критерий F1 , менее важным F2, . . . , Fm. Минимизируется первый по важности критерий и определяется его наименьшее значение F1min . Затем назначается величина допустимого снижения уступки 10 критерия F1 и ищется наименьшее значение критерия F2 при условии, что значение F1 должно быть не больше, чем F1min+1. Снова назначается уступка 20, но уже по второму критерию, которая вместе с первой используется при нахождении условного минимума F3 и т.д. Наконец, минимизируется последний по важности критерий Fm при условии, что значения каждого критерия Fi из m-1 предыдущих должны быть не больше соответствующей величины Fimin+i .Получаемое в итоге решение считается оптимальным.


  1   2   3


База данных защищена авторским правом ©ekonoom.ru 2016
обратиться к администрации

    Главная страница