Реферат: Теория игр и принятие решений

Теория игр и принятие решений

В зависимости от условий внешней среды и степени информативности лица принимающего решение (ЛПР) производится следующая классификация задач принятия решений:

а) в условиях риска;

б) в условиях неопределённости;

в) в условиях конфликта или противодействия (активного противника).

Теория полезности и принятия решений.

Принятие решений в условиях риска.

Критерий ожидаемого значения.

Использование критерия ожидаемого значения обусловлено стремлением максимизировать ожидаемую прибыль (или минимизировать ожидаемые затраты). Использование ожидаемых величин предполагает возможность многократного решения одной и той же задачи, пока не будут получены достаточно точные расчётные формулы. Математически это выглядит так: пустьХ–случайнаявеличина с математическим ожиданием MXи дисперсией DX. Если x1,x2,...,xn–значения случайной величины(с.в.) X, то среднее арифметическое их(выборочное среднее) значений/>имеет дисперсию />. Таким образом, когдаn®¥

/>®0 и/>®MX.

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

Пример 1. Требуется принять решение о том, когда необходимо проводить профилактический ремонт ПЭВМ, чтобы минимизировать потери из-за неисправности. В случае если ремонт будет производится слишком часто, затраты на обслуживание будут большими при малых потерях из-за случайных поломок.

Так как невозможно предсказать заранее, когда возникнет неисправность, необходимо найти вероятность того, что ПЭВМ выйдет из строя в период времени t. В этом и состоит элемент ”риска”.

Математически это выглядит так: ПЭВМ ремонтируется индивидуально, если она остановилась из-за поломки. Через Tинтервалов времени выполняется профилактический ремонт всех nПЭВМ. Необходимо определить оптимальное значение Т, при котором минимизируются общие затратына ремонт неисправныхПЭВМ и проведение профилактического ремонта в расчёте на один интервал времени.

Пусть рt–вероятность выхода из строя одной ПЭВМ в момент t, а nt–случайная величина, равная числу всех вышедших из строя ПЭВМв тот же момент. Пусть далееС1–затраты на ремонт неисправнойПЭВМи С2–затраты на профилактический ремонт одной машины.

Применение критерия ожидаемого значения в данном случае оправдано, если ПЭВМ работают в течение большого периода времени. При этом ожидаемые затраты на один интервал составят

ОЗ= />,

где M(nt) –математическое ожидание числа вышедших из строя ПЭВМ в моментt. Так как ntимеет биномиальное распределение с параметрами (n, pt), то M(nt) = npt. Таким образом

ОЗ = />

Необходимые условия оптимальностиT*имеют вид:

ОЗ (T*-1) ³ОЗ (T*),

ОЗ (T*+1) ³ОЗ (T*).

Следовательно, начиная с малого значения T, вычисляют ОЗ(T),пока не будут удовлетворены необходимые условия оптимальности.

Пусть С1 = 100; С2 = 10; n = 50. Значения ptимеют вид:

T

рt

/>

ОЗ(Т)

1

0.05

/>

2

0.07

0.05

375

3

0.10

0.12

366.7

4

0.13

0.22

400

5

0.18

0.35

450

T*® 3, ОЗ(Т*) ® 366.7

Следовательно профилактический ремонт необходимо делать через T*=3интервала времени.

--PAGE_BREAK--Критерий “ожидаемое значение –дисперсия”

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

Еслих–с. в.с дисперсией DX, то среднее арифметическое />имеет дисперсию />, гдеn–число слогаемых в />. Следовательно, если DXуменьшается, и вероятность того, что />близко кMX, увеличивается. Следовательно, целесообразно ввести критерий, в котором максимизация ожидаемого значения прибыли сочетается с минимизацией её дисперсии.

Пример 2. Применим критерий “ожидаемое значение –дисперсия”для примера 1. Для этого необходимо найти дисперсию затрат за один интервал времени, т.е. дисперсию

зТ=/>

Т.к. nt, t=/>–с.в., тозТтакже с.в.С.в. ntимеет биномиальное распределение с M(nt) = nptиD(nt) = npt(1–pt).Следовательно,

D(зТ) = D(/>)=/>D(/>) =

= />/>= />/>= n/>{/>–/>},

где С2n = const.

Из примера 1 следует, что

М(зТ) = М(з(Т)).

Следовательно искомым критерием будет минимум выражения

М(з(Т)) + к D(зТ).

Замечание. Константу “к”можно рассматривать как уровень не склонности к риску, т.к. “к” определяет “степень возможности”дисперсии Д(зТ)по отношению к математическому ожиданию. Например, если предприниматель, особенно остро реагирует на большие отрицательные отклонения прибыли вниз от М(з(Т)), то он может выбрать “к”много больше 1. Это придаёт больший вес дисперсии и приводит к решению, уменьшающему вероятность больших потерь прибыли.

Прик =1 получаем задачу

/>/>

По данным из примера 1 можно составить следующую таблицу

Т

pt

pt2

/>

/>

М(з(Т))+D(з(Т))

1

0.05

0.0025

500.00

2

0.07

0.0049

0.05

0.0025

6312.50

3

0.10

0.0100

0.12

0.0074

6622.22

4

0.13

0.0169

0.22

0.0174

6731.25

5

0.18

0.0324

0.35

0.0343

6764.00

Из таблицы видно, что профилактический ремонт необходимо делать в течение каждого интервала Т*=1.

    продолжение

--PAGE_BREAK--Критерий предельного уровня.

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

Пример 3. Предположим, что величина спроса xв единицу времени (интенсивность спроса) на некоторый товар задаётся непрерывной функцией распределения f(x).Если запасы в начальный момент невелики, в дальнейшем возможен дефицит товара. В противном случае к концу рассматриваемого периода запасы нереализованного товара могут оказаться очень большими. В обоих случаях возможны потери.

Т.к. определить потери от дефицита очень трудно, ЛПР может установить необходимый уровень запасов таким образом, чтобы величина ожидаемого дефицита не превышала А1единиц, а величина ожидаемых излишков не превышала А2единиц. Иными словами, пусть I–искомый уровень запасов. Тогда

ожидаемый дефицит = />,

ожидаемые излишки =/>.

При произвольном выборе А1и А2указанные условия могут оказаться противоречивыми. В этом случае необходимо ослабить одно из ограничений, чтобы обеспечить допустимость.

Пусть, например,

/>/>

Тогда

/>= />= 20(ln/>+/>–1)

/>= />= 20(ln/>+/>–1)

Применение критерия предельного уровня приводит к неравенствам

ln I –/>³ln 20 –/>–1 = 1.996 –/>

ln I –/>³ln 10 –/>–1 = 1.302 –/>

Предельные значения А1и А2должны быть выбраны так, что бы оба неравенства выполнялись хотя бы для одного значения I.

Например, если А1= 2 и А2= 4, неравенства принимают вид

ln I –/>³1.896

ln I –/>³1.102

Значение Iдолжно находиться между 10 и 20, т.к. именно в этих пределах изменяется спрос. Из таблицы видно, что оба условия выполняются для I, из интервала (13,17)

I

10

11

12

13

14

15

16

17

18

19

20

ln I –/>

1.8

1.84

1.88

1.91

1.94

1.96

1.97

1.98

1.99

1.99

1.99

lnI–/>

1.3

1.29

1.28

1.26

1.24

1.21

1.17

1.13

1.09

1.04

0.99

Любое из этих значений удовлетворяет условиям задачи.

    продолжение

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

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

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

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

Варианты решения таковы:

Е1–выбор размеров из соображений максимальной долговечности ;

Еm–выбор размеров из соображений минимальной долговечности ;

Ei–промежуточные решения.

Условия требующие рассмотрения таковы :

F1 –условия, обеспечивающие максимальной долговечность;

Fn–условия, обеспечивающие minдолговечность;

Fi– промежуточные условия.

Под результатом решения eij =е(Ei; Fj) здесь можно понимать оценку, соответствующую варианту Eiи условиям Fjи характеризующие прибыль, полезность или надёжность. Обычно мы будем называть такой результат полезностью решения.

Тогда семейство (матрица) решений/>имеет вид:


F1

F2

… .

Fn

E1

e11

e12

… .

e1n

E2

e21

e22

… .

e2n

… .

… .

Em

em1

em2

… .

emn

Чтобы прийти к однозначному и по возможности наивыгоднейшему варианту решению необходимо ввести оценочную (целевую) функцию. При этом матрица решений />сводится к одному столбцу. Каждому варианту Eiприписывается, т.о., некоторый результатeir, характеризующий, в целом, все последствия этого решения. Такой результат мы будем в дальнейшем обозначать тем же символомeir.

Классические критерии принятия решений .

1. Минимаксный критерий .

Правило выбора решения в соответствии с минимаксным критерием (ММ-критерием) можно интерпретировать следующим образом:

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

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

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

1o. О возможности появления внешних состояний Fjничего не известно;

2o. Приходится считаться с появлением различных внешних состояний Fj;

3o. Решение реализуется только один раз;

4o. Необходимо исключить какой бы то ни было риск.

2. Критерий Байеса –Лапласа.

Обозначим через qi–вероятность появления внешнего состояния Fj.

Соответствующее правило выбора можно интерпретировать следующим образом:

матрица решений/>дополняется ещё одним столбцомсодержащим математическое ожидание значений каждой из строк. Выбираются те варианты, в строках которых стоит наибольшее значение eirэтого столбца.

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

1о. Вероятности появления состояния Fjизвестны и не зависят от времени.

2о. Решение реализуется (теоретически) бесконечно много раз.

3о. Для малого числа реализаций решения допускается некоторый риск.

При достаточно большом количестве реализаций среднее значение постепенно стабилизируется. Поэтому при полной (бесконечной) реализации какой-либо риск практически исключён.

Т.о. критерий Байеса-Лапласа (B-L-критерий)более оптимистичен, чем минимаксный критерий, однако он предполагает большую информированность и достаточно длительную реализацию.

    продолжение

--PAGE_BREAK--3о. Критерий Сэвиджа.

/>

Величину aijможно трактовать как максимальный дополнительный выигрыш, который достигается, если в состоянии Fjвместо варианта Eiвыбирать другой, оптимальный для этого внешнего состояния вариант. Величину aijможно интерпретировать и как потери (штрафы) возникающие в состоянии Fjпри замене оптимального для него варианта на вариант Ei.В последнем случаеeirпредставляет собой максимально возможные (по всем внешним состояниям Fj, j=/>)потери в случае выбора варианта Ei.

Соответствующее критерию Сэвиджа правило выбора теперь трактуется так:

1). Каждый элемент матрицы решений />вычитается из наибольшего результата maxeijсоответствующего столбца.

2). Разности aijобразуют матрицу остатков/>. Эта матрица пополняется столбцом наибольших разностей eir. Выбирают те варианты, в строках которых стоит наименьшее для этого столбца значение.

Требования, предъявляемые к ситуации, в которой принимается решение, совпадают с требованием кММ-критерию.

4о. Пример и выводы.

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

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

Варианты решения таковы:

Е1–полная проверка;

Е2–минимальная проверка;

Е3–отказ от проверки.

ЭВМ может находиться в следующих состояниях:

F1–вирус отсутствует;

F2–вирус есть, но он не успел повредить информацию;

F3–есть файлы, нуждающиеся в восстановлении.

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

Таблица 1.





ММ-критерий

критерий B-L


F1

F2

F3

eir=/>eij

/>eir

eir=/>

/>eir

E1

-20.0

-22.0

-25.0

-25.0

-25.0

-22.33


E2

-14.0

-23.0

-31.0

-31.0


-22.67


E3

-24.0

-40.0

-40.0


-21.33

-21.33

Согласно ММ-критерию следует проводить полную проверку. Критерий Байеса-Лапласа, в предположении, что все состояния машины равновероятны.

P(Fj) = qj= 0.33,

рекомендуется отказаться от проверки. Матрица остатков для этого примера и их оценка (в тысячах) согласно критерию Сэвиджа имеет вид:





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


F1

F2

F3

eir=/>aij

/>eir

E1

+20.0

+20.0


E2

+14.0

+1.0

+6.0

+14.0

+14.0

E3

+2.0

+15.0

+15.0


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

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

    продолжение

--PAGE_BREAK--Производные критерии.

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

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

/>eir= {C/>eij+ (1- C) />eij},

где С–весовой множитель.

Правило выбора согласно критерию Гурвица, формируется следующим образом:

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

При С=1 критерий Гурвица превращается в ММ-критерий. При С = 0 он превращается в критерий “азартного игрока”

/>eir= />/>eij,

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

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

Критерий Гурвица применяется в случае, когда :

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

с появлением состояния Fjнеобходимо считаться;

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

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

2о. Критерий Ходжа–Лемана.

Этот критерий опирается одновременно на ММ-критерий и критерий Баеса-Лапласа. С помощью параметра nвыражается степень доверия к используемому распределений вероятностей.Если доверие велико, то доминирует критерий Баеса-Лапласа, в противном случае –ММ-критерий, т.е. мы ищем

/>eir= />{n/>+ (1-n) />eir}, 0 £n£1. />

Правило выбора, соответствующее критерию Ходжа-Лемана формируется следующим образом:

матрица решений />дополняется столбцом, составленным из средних взвешенных (с весом nºconst) математическое ожиданиями и наименьшего результата каждой строки (*). Отбираются те варианты решений в строках которого стоит набольшее значение этого столбца.

Приn= 1 критерий Ходжа-Лемана переходит в критерий Байеса-Лапласа, а при n= 0 становится минимаксным.

Выбор nсубъективен т. к. Степень достоверности какой-либо функции распределения –дело тёмное.

Для применения критерия Ходжа-Лемана желательно, чтобы ситуация в которой принимается решение, удовлетворяла свойствам:

вероятности появления состояния Fjнеизвестны, но некоторые предположения о распределении вероятностей возможны;

принятое решение теоретически допускает бесконечно много реализаций;

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

    продолжение

--PAGE_BREAK--3о. Критерий Гермейера.

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

/>eir= />/>eijqj.

Т.к. в хозяйственных задачах преимущественно имеют дело с ценами и затратами, условие eij<0 обычно выполняется. В случае же, когда среди величин eijвстречаются и положительные значения, можно перейти к строго отрицательным значениям с помощью преобразования eij— aпри подходящем образом подобранном a>0. При этом оптимальный вариант решения зависит от а.

Правило выбора согласно критерию Гермейера формулируется следующим образом :

матрица решений />дополняется ещё одним столбцом содержащим в каждой строке наименьшее произведение имеющегося в ней результата на вероятность соответствующего состояния Fj. Выбираются те варианты в строках которых находится наибольшее значение eijэтого столбца.

В каком-то смысле критерий Гермейера обобщает ММ-критерий: в случае равномерного распределения qj= />, j=/>, они становятся идентичными.

Условия его применимости таковы :

вероятности появления состояния Fjнеизвестны;

с появлением тех или иных состояний, отдельно или в комплексе, необходимо считаться;

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

решение может реализоваться один или несколько раз.

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

4о. BL (MM) — критерий.

Стремление получить критерии, которые бы лучше приспосабливались к имеющейся ситуации, чем все до сих пор рассмотренные, привело к построению так называемых составных критериев. В качестве примера рассмотрим критерий, полученный путем объединения критериев Байеса-Лапласа и минимакса.

Правило выбора для этого критерия формулируется следующим образом:

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

/>

и наименьшим значением

/>

соответствующей строки. В третьем столбце помещаются разности между наибольшим значением

/>

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

/>

из второго столбца должно быть или равно некоторому заранее заданному уровню риска />. Значение же из третьего столбца должно быть больше значения из второго столбца.

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

вероятности появления состояний Fjнеизвестны, однако имеется некоторая априорная информация в пользу какого-либо определенного распределения;

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

допускается ограниченный риск;

принятое решение реализуется один раз или многократно.

BL(MM)-критерий хорошо приспособлен для построения практических решений прежде всего в области техники и может считаться достаточно надежным. Однако заданные границы риска />и, соответственно, оценок риска />не учитывает ни число применения решения, ни иную подобную информацию. Влияние субъективного фактора хотя и ослаблено, но не исключено полностью.

Условие

/>

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

    продолжение

--PAGE_BREAK--5о. Критерий произведений.

/>eir:= />/>eij

Правило выбора в этом случае формулируется так :

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

Применение этого критерия обусловлено следующими обстоятельствами :

вероятности появления состояния Fjнеизвестны;

с появлением каждого из состояний Fjпо отдельности необходимо считаться;

критерий применим и при малом числе реализаций решения;

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

Критерий произведений приспособлен в первую очередь для случаев, когда всеeijположительны. Если условие положительности нарушается, то следует выполнять некоторый сдвиг eij+ ас некоторой константой а >ï/>eijï.Результат при этом будет, естественно зависеть от а. На практике чаще всего

а := ï/>eijï+1.

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

Пример.

Рассмотрим тот же пример (табл. 1).

Построение оптимального решения для матрицы решений о проверках по критерию Гурвица имеет вид (при С =0.5, в 103):

х

С/>eij

(1-С)/>eij

eir

/>eir

-20.0

-22.0

-25.0

-12.5

-10.0

-22.5


-14.0

-23.0

-31.0

-15.5

-7.0

-22.5


-24.0

-40.0

-20.0

-20.0

-20.0

В данном примере у решения имеется поворотная точка относительно весового множителя С : до С = 0.57 в качестве оптимального выбирается Е3, а при больших значениях – Е1.

Применение критерия Ходжа-Лемана (q = 0.33, n= 0.5, в 103) :

/>

/>eij

n/>

(1-n)/>eij

    продолжение
--PAGE_BREAK----PAGE_BREAK--

+15.0

+20.0

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

Результаты применения критерия произведения при а= 41×103и а= 200×103имеют вид :


/>

eir=/>eij

/>eir


+21

+19

+16

6384

6384

а=41

+27

+18

+10

4860



+41

+17

+1

697



+180

+178

+175

5607


а=200

+186

+177

+169

5563



+200

+176

+160

5632

5632

Условие eij> 0 для данной матрицы не выполнимо. Поэтому к элементам матрицы добавляется (по внешнему произволу) сначала а = 41×103, а затем а = 200×103.

Для а = 41×103оптимальным оказывается вариант Е1, а для а = 200×103–вариант Е3, так что зависимость оптимального варианта от а очевидна.


еще рефераты
Еще работы по математике