Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Реализация в Excel критериев принятия решений в условиях неопределенности.
Шаблон Excel chl4UncertainlyDecision.xls можно использовать для вычисления всех критериев, описанных выше. Основой вычислений служит матрица затрат (диапазон В9:К19). Если надо использовать матрицу выигрышей, то все элементы этой матрицы надо умножить на -1. Максимальный размер матриц 10x10. На рис. 14.8 показано применение этого шаблона к данным примера 14.3.1.
УПРАЖНЕНИЯ 14.3
1. Хенк — прилежный студент, который обычно получает хорошие отметки благодаря, в частности, тому, что имеет возможность повторить материал в ночь перед экзаменом. Перед завтрашним экзаменом Хенк столкнулся с небольшой проблемой. Его сокурсники организовали на всю ночь вечеринку, в которой он хочет участвовать. Хенк имеет три альтернативы:
а1 — участвовать в вечеринке всю ночь,
а2 — половину ночи участвовать в вечеринке, а половину — учиться, а3 — учиться всю ночь.
14.3. Принятие решений в условиях неопределенности
А | В | D E | L | M | N | Q | ||
Decision Under Uncertainty | ||||||||
Enter x to select method: | Output Results | |||||||
Laplace | X | |||||||
Minimax | X | |||||||
Savage | X | |||||||
Hurwicz | X | Alpha= 10.5 | Optimum strategies | |||||
Input (cost) Matrix: Maximum size = (10x10) | a2 | a3 | a2 | a2 | ||||
s2 | s3 s4 | Laplace | Minimax | Savage | Hurwicz | |||
a1 | 18 25 | 14 5 | ||||||
a2 | 12 23 | 12 5 | ||||||
И | a3 | 12 21 | ||||||
a4 | 19 15 | 21 5 | 22 5 | |||||
Рис. 14.8. Решение в Excel примера 14.3.1
Профессор, принимающий завтрашний экзамен, непредсказуем, и экзамен может быть легким (sj, средним (s2) или трудным (s3). В зависимости от сложности экзамена и времени, затраченного Хенком на повторение, можно ожидать следующие экзаменационные баллы.
Si S2 s3
ai | |||
а2 | |||
а3 |
a) Порекомендуйте Хенку, какой выбор он должен сделать (основываясь на каждом из четырех критериев принятия решений в условиях неопределенности).
b) Предположим, что Хенк более заинтересован в оценке (в буквенном выражении), которую он получит на экзамене. Буквенным оценкам от А до D, означающим сдачу экзамена, соответствует 90, 80, 70 и 60 баллов. Иначе при числе баллов ниже 60 студент получает оценку F, которая свидетельствует о том, что экзамен не сдан. Изменит ли такое отношение к оценкам выбор Хенка?
2. В приближении посевного сезона фермер Мак-Кой имеет четыре альтернативы:
а, — выращивать кукурузу,
а2 — выращивать пшеницу,
as — выращивать соевые бобы,
а4 — использовать землю под пастбища.
Платежи, связанные с указанными возможностями, зависят от количества осадков, которые условно можно разделить на четыре категории:
Sj — сильные осадки,
s2 — умеренные осадки,
ss — незначительные осадки,
s4 — засушливый сезон.
Платежная матрица (в тыс. долл.) оценивается следующим образом.
Глава 14. Теория игр и принятия решений
S1 | s2 | S3 | S4 | |
-20 | -5 | |||
32 | ||||
-50 | -10 | |||
ад |
Что должен посеять Мак-Кой?
3. Один из N станков должен быть выбран для изготовления Q единиц определенной продукции. Минимальная и максимальная потребность в продукции равна Q* и Q соответственно. Производственные затраты ТС, на изготовление Q единиц продукции на станке i включают фиксированные затраты К1 и удельные затраты с, на производство единицы продукции и выражаются формулой ТС: = К, + c/Q.
a) Решите задачу с помощью каждого из четырех критериев принятия решений в условиях неопределенности.
b) Решите задачу при следующих данных, предполагая, что 1000 < Q < 4000.
Станок /' | К, (долл.) | с, (долл.) |
14.4. ТЕОРИЯ ИГР
В теории игр рассматриваются ситуации, связанные с принятием решений, в которых два разумных противника имеют конфликтующие цели. К числу типичных примеров относится рекламирование конкурирующих товаров и планирование военных стратегий противоборствующих армий. Эти ситуации принятия решений отличаются от рассмотренных ранее, где природа не рассматривается в роли недоброжелателя.
В игровом конфликте участвуют два противника, именуемые игроками, каждый из которых имеет некоторое множество (конечное или бесконечное) возможных выборов, которые называются стратегиями. С каждой парой стратегий связан платеж, который один из игроков выплачивает другому. Такие игры известны как игры двух лиц с нулевой суммой, так как выигрыш одного игрока равен проигрышу другого. В такой игре достаточно задать результаты в виде платежей для одного из игроков. При обозначении игроков через А и В с числом стратегий тип соответственно игру обычно представляют в виде матрицы платежей игроку А:
в, | Вг | Вп | |
А, | Зщ | ||
Аг | S22 | 32л | |
Am | Зт1 | Sm2 | Зтл |
Такое представление матричной игры означает, что если игрок А использует стратегию /, а игрок В — стратегию j, то платеж игроку А составляет atj и, следовательно, игроку В--ац.
14.4. Теория игр
14.4.1. Оптимальное решение игры двух лиц с нулевой суммой
Поскольку игры берут свое начало в конфликте интересов, оптимальным решением игры является одна или несколько таких стратегий для каждого из игроков, при этом любое отклонение от данных стратегий не улучшает плату тому или другому игроку. Эти решения могут быть в виде единственной чистой стратегии или нескольких стратегий, которые являются смешанными в соответствии с заданными вероятностями. Рассматриваемые ниже примеры демонстрируют перечисленные ситуации.
Пример 14.4.1
Две компании А и В продают два вида лекарств против гриппа. Компания А рекламирует продукцию на радио (АЛ, телевидении (А2) и в газетах (АЛ. Компания В, в дополнение к использованию радио (ВЛ, телевидения (ВЛ и газет (В,), рассылает также по почте брошюры (54). В зависимости от умения и интенсивности проведения рекламной кампании, каждая из компаний может привлечь на свою сторону часть клиентов конкурирующей компании. Приведенная ниже матрица характеризует процент клиентов, привлеченных или потерянных компанией А.
Максимумы столбцов
в. | Вг | Вз | в4 | Минимумы строк | |
А, | -2 | -3 | -3 | ||
Аг | 5 максимин | ||||
Аз | -2 | -9 | -9 | ||
минимакс
Решение игры основано на обеспечении наилучшего результата из наихудших для каждого игрока. Если компания А выбирает стратегию Ах, то, независимо от того, что предпринимает компания В, наихудшим результатом является потеря компанией А 3 % рынка в пользу компании В. Это определяется минимумом элементов первой строки матрицы платежей. Аналогично при выборе стратегии А2 наихудшим исходом для компании А является увеличение рынка на 5 % за счет компании В. Наконец, наихудшим исходом при выборе стратегии А3 является потеря компанией А 9 % рынка в пользу компании В. Эти результаты содержатся в столбце "Минимумы строк". Чтобы достичь наилучшего результата из наихудших, компания А выбирает стратегию А2, так как она соответствует наибольшему элементу столбца "Минимумы строк".
Рассмотрим теперь стратегии компании В. Так как элементы матрицы являются платежами компании А, критерий наилучшего результата из наихудших для компании В соответствует выбору минимаксного значения. В результате приходим к выводу, что выбором компании В является стратегия В2.
Оптимальным решением в игре является выбор стратегий А2 и В2, т.е. обеим компаниям следует проводить рекламу на телевидении. При этом выигрыш будет в пользу компании А, так как ее рынок увеличится на 5 %. В этом случае говорят, что цена игры равна 5 % и что компании А и В используют стратегии, соответствующие седловой точке.
Глава 14. Теория игр и принятия решений
Решение, соответствующее седловой точке, гарантирует, что ни одной компании нет смысла пытаться выбрать другую стратегию. Действительно, если компания В переходит к другой стратегии (/?,, В% или Bt), то компания А может сохранить свой выбор стратегии Аг, что приведет к большей потере рынка компанией В (6 или 8 %). По тем же причинам компании А нет резона использовать другую стратегию, ибо если она применит, например, стратегию А3, то компания В может использовать свою стратегию В3 и увеличить свой рынок на 9 %. Аналогичные выводы имеют место, если компания А будет использовать стратегию Ах.
Оптимальное решение игры, соответствующее седловой точке, не обязательно должно характеризоваться чистыми стратегиями. Вместо этого оптимальное решение может требовать смешивания случайным образом двух или более стратегий, как это сделано в следующем примере.
Пример 14.4.2
Два игрока А и В играют в игру, основанную на подбрасывании монеты. Игроки одновременно и независимо друг от друга выбирают герб (Г) или решку (Р). Если результаты двух подбрасываний монеты совпадают (т.е. ГГ или РР), то игрок А получает один доллар от игрока В. Иначе игрок А платит один доллар игроку В.
Следующая матрица платежей игроку А показывает величины минимальных элементов строк и максимальных элементов столбцов, соответствующих стратегиям обоих игроков.
Вг | ВР | Минимумы строк | |
Аг | -1 | -1 | |
Ар | -1 | -1 | |
Максимумы столбцов |
Максиминная и минимаксная величины (цены) для этой игры равны -1 долл. и 1 долл. соответственно. Так как эти величины не равны между собой, игра не имеет решения в чистых стратегиях. В частности, если игрок А использует стратегию Аг, игрок В выберет стратегию Вр, чтобы получить от игрока А один доллар. Если это случится, игрок А может перейти к стратегии Ар, чтобы изменить исход игры и получить один доллар от игрока В. Постоянное искушение каждого игрока перейти к другой стратегии указывает на то, что решение в виде чистой стратегии неприемлемо. Вместо этого оба игрока должны использовать надлежащую случайную комбинацию своих стратегий. В рассматриваемом примере оптимальное значение цены игры находится где-то между максиминной и минимаксной ценами для этой игры:
максиминная (нижняя) цена < цена игры < минимаксная (верхняя) цена.
Следовательно, в данном случае цена игры должна лежать в интервале [-1,1], измеряемом в долларах.
14.4. Теория игр
УПРАЖНЕНИЯ 14.4.1
1. Определите решение, определяемое седловой точкой, соответствующие чистые стратегии и цену игры для следующих игр, в которых платежи заданы для игрока А.
а)
е, | е2 | Вз | е4 | |
Аг | ||||
Аз |
Ь)
Bi | Bi | Вз | е4 | |
Ау | -4 | -5 | ||
Аг | -3 | -4 | -9 | -2 |
Аз | -8 | -9 | ||
Ал | -9 |
2. В следующих играх заданы платежи игроку А. Укажите область значений для параметров р и q, при которых пара (2, 2) будет седловой точкой в каждой игре.
а)
Bi Вг е3
4i | Я | ||
А> | Р | ||
е, | е2 | е3 | |
А\ | |||
Аг | Я | ||
Аз | Р |
3. Укажите область, которой принадлежит цена игры в каждом из следующих случаев, предполагая, что платежи заданы для игрока А.
а)
В, | бз | е4 | ||
-4.1 | ||||
Аг | ||||
Аз | -5 | -2 | -3 | |
Ал | -2 | -5 |
Глава 14. Теория игр и принятия решений
Ь)
с)
е. | е3 | е4 | ||
-1 | ||||
Аг | -2 | |||
Аз | ||||
А* | -2 |
d)
е. | Вз | е4 | ||
-6 | ||||
-9 | -2 |
4. Две фирмы производят два конкурирующих товара. Каждый товар в настоящее время контролирует 50 % рынка. Улучшив качество товаров, обе фирмы собираются развернуть рекламные кампании. Если они не будут этого делать, то существующее состояние рынка не изменится. Однако если какая-либо фирма будет более активно рекламировать свои товары, то другая фирма потеряет соответствующий процент своих потребителей. Исследование рынка показывает, что 50 % потенциальных потребителей получают информацию посредством телевидения, 30 % — через газеты и 20 % — по радио.
a) Сформулируйте задачу в виде игры двух лиц с нулевой суммой и выберите подходящие средства рекламы для каждой фирмы.
b) Укажите интервал значений, которому принадлежит цена игры. Может ли каждая фирма действовать с единственной чистой стратегией?
5. Пусть atj — (г, /)-й элемент платежной матрицы с т стратегиями игрока А и л стратегиями игрока В. Элементы платежной матрицы представляют собой платежи игроку А. Докажите, что
max min а,, < min max а,,.
14.4.2. Решение матричных игр в смешанных стратегиях
Решение матричных игр в смешанных стратегиях может быть найдено либо графически, либо методами линейного программирования. Графический метод применим для решения игр, в которых хоть один игрок имеет две чистые стратегии. Этот метод интересен в том плане, что графически объясняет понятие седловой точки. Методами линейного программирования может быть решена любая игра двух лиц с нулевой суммой.
Графическое решение игр. Рассмотрим игру 2 х п, в которой игрок А имеет две стратегии.
14.4. Теория игр
У1 | у2 | У" | |
е. | Вг | Вп | |
Хъ Ау | an | Зщ | |
1 - хь А2 | 32л |
Игра предполагает, что игрок А смешивает стратегии А1 и А2 с соответствующими вероятностями я, и 1 - я,, 0 < 1. Игрок В смешивает стратегии Blt В2, Вп с вероятностями (/,, уг, (/„, где i/.>0,;= 1, 2, п, и у, + j/2 +... + (/„ = 1. В этом случае ожидаемый выигрыш игрока А, соответствующий j-й чистой стратегии игрока В, вычисляется в виде
(аи ~ а2,) xi ~ агг J=1<2.....п-
Следовательно, игрок А ищет величину хх, которая максимизирует минимум ожидаемых выигрышей
maxmin j(a,y -a2j}xl -а2,У
Пример 14.4.3
Рассмотрим следующую игру 2x4, в которой платежи выплачиваются игроку Л.
В\ Вг Вз 64
А '
Аг
2 2 3 -1
4 3 2 6
Игра не имеет решения в чистых стратегиях, и, следовательно, стратегии должны быть смешанными. Ожидаемые выигрыши игрока А, соответствующие чистым стратегиям игрока В, приведены в следующей таблице.
Чистые стратегии игрока В | Ожидаемые выигрыши игрока А |
-2xi + 4 | |
-*1 + 3 | |
* +2 | |
-7*1 + 6 |
На рис. 14.9 изображены четыре прямые линии, соответствующие чистым стратегиям игрока В. Чтобы определить наилучший результат из наихудших, построена нижняя огибающая четырех указанных прямых (изображенная на рисунке толстыми линейными сегментами), которая представляет минимальный (наихудший) выигрыш для игрока А независимо от того, что делает игрок В. Максимум (наилучшее) нижней огибающей соответствует максиминному решению в точке х\ - 0,5. Эта точка
определяется пересечением прямых 3 и 4. Следовательно, оптимальным решением для игрока А является смешивание стратегий Ах и А2 с вероятностями 0,5 и 0,5 соответственно. Соответствующая цена игры v определяется подстановкой х, = 0,5 в уравнение либо прямой 3, либо 4, что приводит к следующему.
Глава 14. Теория игр и принятия решений
-^ + 2 = -^ из уравнения прямой 3, -7^| + 6 = -|- из уравнения прямой 4.
Рис. 14.9. Графическое решение игры двух лиц с нулевой суммой из примера 14.4.3
Оптимальная смешанная стратегия игрока В определяется двумя стратегиями, которые формируют нижнюю огибающую графика. Это значит, что игрок В может смешивать стратегии В3 и В4, в этом случае у, =у2 = О и у4 = 1 - у3. Следовательно, ожидаемые платежи игрока В, соответствующие чистым стратегиям игрока А, имеют такой вид.
Чистые стратегии игрока А Ожидаемые платежи игрока В
1 4у3 - 1
2 -4у3 + 6
Наилучшее решение из наихудших для игрока В представляет собой точку минимума верхней огибающей заданных двух прямых (построение прямых и определение верхней огибающей будет для вас поучительным). Эта процедура эквивалентна решению уравнения
4>3-1 = -4у3 + 6.
Его решением будету3 = 7/8, что определяет цену игры v = 4 х (7/8) - 1 = 5/2.
Таким образом, решением игры для игрока А является смешивание стратегий А, иА2с равными вероятностями 0,5 и 0,5, а для игрока В — смешивание стратегий Вг и В4 с вероятностями 7/8 и 1/8. (В действительности игра имеет альтернативное решение для игрока В, так как максиминная точка на рис. 14.9 определяется более чем двумя прямыми. Любая выпуклая линейная комбинация этих альтернативных решений также является решением задачи.)
14.4. Теория игр
Для игры, в которой игрок Л имеет т стратегий, а игрок В — только две, решение находится аналогично. Главное отличие состоит в том, что здесь строятся графики функций, представляющих ожидаемые платежи второго игрока, соответствующие чистым стратегиям игрока А. В результате ведется поиск минимаксной точки верхней огибающей построенных прямых.
УПРАЖНЕНИЯ 14.4.2
1. Решите графически игру с подбрасыванием монет из примера 14.4.2.
2. Робин часто ездит между двумя городами. При этом есть возможность выбрать один из двух маршрутов: маршрут А представляет собой скоростное шоссе в четыре полосы, маршрут В — длинную обдуваемую ветром дорогу. Патрулирование дорог осуществляется ограниченным числом полицейских. Если все полицейские расположены на одном маршруте, Робин с ее страстным желанием ездить очень быстро, несомненно, получит штраф в 100 долл. за превышение скорости. Если полицейские патрулируют на двух маршрутах в соотношении 50 на 50, то имеется 50 % -ная вероятность, что Робин получит штраф в 100 долл. на маршруте А и 30 % -ная вероятность, что она получит такой же штраф на маршруте В. Кроме того, маршрут В длиннее, поэтому бензина расходуется на 15 долл. больше, чем на маршруте А. Определите стратегию как для Робин, так и для полиции.
3. Решите графически следующие игры, в которых платежи выплачиваются игрокуА.
а)
в.
Вг
Ау Аг -3 4
ъ)
By | Вг | |
Ау | ||
Аг | ||
Аз |
4. Дана следующая игра двух лиц с нулевой суммой.
By | Вг | Вз | |
5,0 | 50,0 | 50,0 | |
Аг | 1,0 | 1,0 | 0,1 |
Аз | 10,0 | 1,0 | 10,0 |
a) Проверьте, что смешанные стратегии с вероятностями (1/6,0,5/6) для игрока А и с вероятностями (49/54, 5/54, 0) для игрока В являются оптимальными, и определите цену игры.
b) Покажите, что цена игры равна
3 3
Глава 14. Теория игр и принятия решений
Решение матричных игр методами линейного программирования. Теория игр находится в тесной связи с линейным программированием, так как любую конечную игру двух лиц с нулевой суммой можно представить в виде задачи линейного программирования и наоборот. Дж. Данциг [3] отмечает, что, когда в 1947 году создатель теории игр Дж. фон Нейман впервые ознакомился с симплекс-методом, он сразу установил эту взаимосвязь и обратил особое внимание на концепцию двойственности в линейном программировании. Этот раздел иллюстрирует решение матричных игр методами линейного программирования.
Оптимальные значения вероятностей xt, i = 1, 2, т, игрока А могут быть определены путем решения следующей максиминной задачи.
тт т
/=1 (=1 1=1
хх + х2 +... + хт = 1, х. > О, i = 1, 2.....т.
Чтобы сформулировать эту задачу в виде задачи линейного программирования, положим
v = min X^-Z^^/'-'Zv.
Отсюда вытекает, что
Za*.-v- у=1.2,..-, л.
Следовательно, задача игрока А может быть записана в виде
максимизировать z = v
при ограничениях
v-^Vi-°- 7 = 1-2,...,/!,
i=i
xt + хг +... + хт = 1,
х, > О, i = l, 2, т,
v не ограничена в знаке. Отметим последнее условие, что цена игры v может быть как положительной, так и отрицательной.
Оптимальные стратегии yv у2, уп игрока В определяются путем решения задачи
limax Z^y-IX^.....1ХЛ
Vj = 1 j=1 у = 1,
mm j max
Уг + Уг+ ■■■+У„ = 1> y>0, /-1,2.....re.
Используя процедуру, аналогичную приведенной выше для игрока А, приходим к выводу, что задача для игрока В сводится к следующему.
Минимизировать w — v
при ограничениях
V -
7 = 1
ZV,^0' ' = 1.2...., п
-л
у,+уг+... +(/„ =!,
14.4. Теория игр
i/.>0,; = 1, 2, п,
v не ограничена в знаке.
Две полученные задачи оптимизируют одну и ту же (не ограниченную в знаке) переменную и, которая является ценой игры. Причиной этого служит то, что задача игрока В является двойственной к задаче игрока А (вам предлагается доказать это утверждение в упражнении 14.4.3.5, используя определение двойственности из главы 4). Это означает, что оптимальное решение одной из задач автоматически определяет оптимальное решение другой.
Пример 14.4.4
Решим следующую матричную игру методами линейного программирования.
В, | Вг | Вз | Минимумы строк | |
Ау | -1 | -3 | -3 | |
А2 | -2 | -1 | -2 | |
Аз | -5 | -6 | -6 | |
Максимумы столбцов |
Значение цены игры v находится между -2 и 2. Задача линейного программирования для игрока А
Максимизировать z = v
при ограничениях
v - За-j + 2х2 + 5лг3 < О, v + л-j - 4х2 + 6х3 < О, v + 3x1+x2-2x3<0,
xv х2, х3 > О,
v не ограничена в знаке. Оптимальным решением является хг = 0,39, х2 = 0,31, х3 = 0,29 и v = -0,91. Задача линейного программирования для игрока В
Минимизировать z = v
при ограничениях
о-3у,+у2 + 3у3>0, и + 2У1-4у2+у3>0, v + 5yi + 6y2-2y3>0,
v не ограничена в знаке. Оптимальным решением является у, = 0,32, у2 = 0,08, у3 = 0,60 и v = -0,91.
Глава 14. Теория игр и принятия решений
В программе TORA для решения игр двух игроков с нулевой суммой надо выбрать команду Zero-sum GamesOSolve^LP-based (Игры с нулевой суммой^Решить^Как задачу ЛП). На рис. 14.10 показан результат решения задачи примера 14.4.4 (файл ch 14ToraGamesEx 14-4-4).
Дата публикования: 2014-11-18; Прочитано: 1677 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!