3 |
= 9/4,
= 1/4.Ответ: U* = (5/8, 3/8); Z* = (1/4, 0, 3/4, 0); v = 21/4.
Еще раз обратим внимание на рисунок 5.5 и платежную матрицу, представленную в таблице 5.4.
Стратегия B2 заведомо невыгодна для игрока В по сравнению со стратегией B1. На рисунке 5.5 все точки отрезка B2B'2 лежат выше отрезка B1B'1, следовательно, заранее понятно, что стратегия B2 не входит в оптимальное решение.
Таким образом, столбец B2 может быть исключен из рассмотрения до начала решения задачи, поскольку соответствующая стратегия заведомо невыгодна для игрока B по сравнению со стратегией B2.
Итак, исходная игра может быть упрощена путем исключения из платежной матрицы строк и столбцов, соответствующих заведомо невыгодным стратегиям.
Такими стратегиями для игрока А являются те, которым соответствуют строки с элементами, заведомо меньшими по сравнению с элементами како-либо другой строки.
Для игрока В невыгодным стратегиям соответствуют столбцы с элементами, заведомо бoльшими по сравнению с элементами какого-либо другого столбца.
5. Приведение парной игры к задаче линейного программирования
Игра размера mxn не имеет наглядной геометрической интерпретации. Ее решение достаточно трудоемко, но принципиальных трудностей не имеет, поскольку может быть сведено к решению задаче линейного программирования.
Наряду с приводимыми выше теоремой Неймана и теоремой об активных стратегиях справедлива следующая терема теории игр.
Теорема. Для того чтобы число v было ценой игры, а U* и Z*- оптимальными стратегиями, необходимо и достаточно выполнение неравенств:
|
aij
≥ v, 
aijРассмотрим игру mxn, определяемую матрицей:
A = |
| a11 a12 ... a1n ... am1 am2 ... amn |
|
.Как и ранее, игрок A обладает стратегиями A1, A2, ..., Am, игрок В – стратегиями B1, B2, …, Bn. Требуется определить оптимальные стратегии игроков U* и Z*.
Рассмотрим оптимальную стратегию U* игрока A.
Согласно теореме, приведенной выше, справедливо следующее утверждение.
Если игрок А применяет смешанную стратегию U* = (
, 
, ..., 
) против чистой стратегии Bj игрока В, то он получает средний выигрыш или математическое ожидание выигрыша aj = a1j + a2j + ... + amj, 
.
Для оптимальной стратегии U* все средние выигрыши не меньше цены игры v, поэтому получаем систему неравенств:
| (5.3) |
Предположим для определенности, что v > 0.
Этого всегда можно достигнуть благодаря тому, что прибавление ко всем элементам матрицы А одного и того же постоянного числа С не приводит к изменению оптимальных стратегий, а только лишь увеличивает цену игры на С.
Каждое из неравенств разделим на число v (v > 0), а также введем новые переменные: y1 = / v, y2 = / v, ..., ym = / v.
Тогда система (5.3) примет вид:
| (5.4) |
При этом yi ≥ 0, 
.
Далее рассмотрим равенство + + ... + = 1.
Разделим неравенство на число v (v ≠ 0). Получим:
y1 + y2 + ... + ym = 1/v. | (5.5) |
Вспомним, что цель игрока А – максимизировать свой гарантированный выигрыш, т. е. цену игры v. Максимизация цены игры v эквивалентна минимизации величины 1/v, поэтому задача может быть сформулирована следующим образом: определить значения переменных yi ≥ 0, i = 1, 2, …, m, так, чтобы они удовлетворяли линейным ограничениям (5.4) и при этом линейная функция (5.5) обращалась в минимум.
Перед нами задача линейного программирования.
Решая задачу (5.4) – (5.5), можно найти оптимальную стратегию U*.
Аналогичные рассуждения выполним и для игрока В.
Обозначив xj = 
/ v, , в результате получим:
| (5.6) |
x1 + x2 + ... + xn = 1/v. | (5.7) |
Таким образом, задача определения оптимальной стратегии игрока В сводится к следующему: определить значения переменных xj ≥ 0, j = 1, 2, …, n, так, чтобы они удовлетворяли линейным ограничениям (5.6) и при этом линейная функция (5.7) обращалась в максимум.
Решая задачу линейного программирования (5.6) – (5.7), получим оптимальную стратегию Z*.
Вновь приведем формулировки полученных задач линейного программирования.
|
| ||||
| a11y1 + a21y2 + ... + am1ym ≥ 1, ... a1ny1 + a2ny2 + ... + amnym ≥ 1; |
| a11x1 + a12x2 + ... + a1nxn ≤ 1, ... am1x1 + am2x2 + ... + amnxn ≤ 1; | ||
yi ≥ 0, | xj ≥ 0, |
= y1 + y2 + ... + ym → min;
= x1 + x2 + ... + xn → max;Очевидно, что задачи (5.4) – (5.5) и (5.6) – (5.7) представляют собой пару взаимно двойственных задач линейного программирования. Их решение позволяет решить соответствующую игру.
При этом:
| (5.8) |
;
, 
, Таким образом, процесс нахождения решения игры с использованием методов линейного программирования включает следующие этапы.
1. Формулировка пары двойственных задач линейного программирования, эквивалентных заданной парной игре.
2. Определение оптимальных планов двойственных задач.
3. Нахождение решения игры с использованием соотношений между оптимальными планами двойственных задач и оптимальными стратегиями и ценой игры (формулы (5.8)).
Пример 5.7. Предприятие выпускает скоропортящуюся продукцию, которую может сразу отправить потребителю (стратегия В1), отправить на склад для хранения (стратегия В2) или подвергнуть дополнительной обработке (стратегия В3) для длительного хранения.
Потребитель может приобрести продукцию немедленно (стратегия A1), в течение небольшого времени (стратегия A2), по истечении длительного периода времени (стратегия A3).
В случае стратегий B2 и B3 предприятие несет дополнительные затраты на хранение и переработку продукции, которые не требуются для B1, однако при B1 следует учесть возможные убытки из-за порчи продукции, если потребитель выберет стратегии А2 или А3.
Определите оптимальные пропорции продукции для применения стратегий B1, B2 и B3, руководствуясь «минимаксным критерием» (гарантированный средний уровень затрат) при матрице затрат, представленной в таблице 5.5.
Таблица 5.5 - Платежная матрица примера 5.7
| B1 | B2 | B3 |
A1 | 2 | 5 | 10 |
A2 | 8 | 6 | 8 |
A3 | 12 | 8 | 6 |
Решение.
Проверим игру на наличие седловой точки: 
= 6, 
= 8. Седловая точка отсутствует. Упростить игру, путем исключения заведомо невыгодных стратегий не удается.
Составим пару двойственных задач линейного программирования.
|
| ||||
| 2y1 + 8y2 + 12y3 ≥ 1, |
| 2x1 + 5x2 + 10x3 ≤ 1, | ||
y1 ≥ 0, y2 ≥ 0, y3 ≥ 0. | x1 ≥ 0, x2 ≥ 0, x3 ≥ 0. |
Методы решения задач линейного программирования обсуждались нами в разделе "Линейное программирование".
Решая первую из задач, получим:
= 0,04; 
= 0; 
= 0,1; 
= 0,14.
Решение второй задачи дает следующие результаты:
= 0; 
= 0,08; 
= 0,06; 
= 0,14.
Используя соотношения (5.8) найдем решение игры:
v = |
= 
≈ 7,14;
= 50/7 ∙ 0,1 = 10/14 ≈ 0,71;
= 50/7 ∙ 0,08 = 8/14 ≈ 0,57;Таким образом, чтобы гарантировать себе среднюю величину затрат на уровне 7,14 независимо от поведения потребителей, предприятию следует около 57% продукции отправлять на склад для хранения и около 43% продукции подвергать дополнительной обработке.
6. Общая схема решения парных игр с нулевой суммой
При решении произвольной конечной игры размера mxn рекомендуется придерживаться следующей схемы.
1. Исключить из платежной матрицы заведомо невыгодные стратегии.
2. Определить верхнюю и нижнюю цены игры и проверить, имеет ли игра седловую точку. Если седловая точка есть, то соответствующие ей стратегии игроков будут оптимальными, а цена игры совпадает с верхней (нижней) ценой.
3. Если седловая точка отсутствует, то решение следует искать в смешанных стратегиях. Игры размера mxn решаются путем сведения к задаче линейного программирования. Для игр размера 2xn или nx2 возможно геометрическое решение.
7. Использование альтернативных критериев определения оптимальных стратегий
В задачах, решаемых на основе использования теории игр, довольно часто в качестве противника выступает так называемая природа. Природа может находиться в одном из множества возможных состояний, которое, в принципе, может быть как конечным, так и бесконечным. Довольно часто в этой ситуации речь идёт о выборе одной (соответственно, чистой) стратегии, т. е. «повторить партию», чтобы вести речь о средних выигрышах, невозможно.
Итак, будем считать, что множество состояний природы Bj ( ) конечно. Все возможные состояния известны, не известно только, какое состояние будет иметь место в условиях, когда планируется реализация принимаемого управленческого решения.
Будем считать, что множество управленческих решений (планов) Ai также конечно и равно m.
Как и ранее, исход игры будем определять платёжной матрицей A. Далее условимся, что в том случае, если элементы aij для игрока представляют собой выигрыш, полезность будем считать, что A – это игрок, B – природа. И наоборот, если aij – затраты, потери, то, как таковой, игрок – это игрок В, природа – игрок А.
Один из критериев, применяемых при решении подобных задач, был рассмотрен в предыдущих разделах – это максиминный/минимаксный критерий (называемый также критерием Вальда).
Рассмотрим некоторые альтернативные критерии.
Критерий Лапласа
Данный критерий опирается на «принцип недостаточного основания», согласно которому все состояния природы Bj полагаются равновероятными, т. е. вероятности того, что природа окажется в одном из n своих состояний, одинаковы и равны:
|
.Если для принимающего решение элементы матрицы aij платёжной матрицы – выигрыши, то оптимальной считается та стратегия Ai, для которой среднее арифметическое возможных выигрышей максимально, т. е. критерий:
| (5.9) |
.Если принимающий решение является игроком B, то критерий становится таким:
| (5.10) |
.Критерий Сэвиджа
Введём понятие матрицы рисков R. Это матрица, имеющая размерность mxn. Её элементы rij определяются по следующей формуле (если A – игрок, В - природа):
rij = | (5.11) |
где 
– максимальный элемент j-ом столбце платёжной матрицы.
Для иллюстрации порядка формирования матрицы рисков используем пример. Пусть задана следующая платёжная матрица:
A = |
| 4 8 3 |
|
.Если решение принимает игрок А, то соответствующая матрица рисков такова:
R = |
| 5 0 5 |
|
Если же человек, принимающий решение, – игрок В, т. е. aij – потери, то элементы матрицы рисков определяются так:
rij = aij - | (5.12) |
где 
– минимальный элемент в i-ой строке платёжной матрицы.
Вернемся к примеру, приведенному выше. В случае, если принимающий решение - игрок B, матрица рисков будет такой:
R = |
| 1 5 0 |
|
Критерий Сэвиджа использует матрицу рисков R и рекомендует в условиях неопределенности выбирать ту стратегию, при которой величина риска принимает наименьшее значение в самой неблагоприятной ситуации, т. е.:
| (5.13) |
.По сути, это тот же минимаксный критерий, только по отношению к матрице рисков, а не к платежной матрице.
Если принимающий решение – игрок B, критерий становится таким:
| (5.14) |
.Критерий Гурвица
Данный критерий основан на использовании так называемого коэффициента доверия. Обозначим его 
и предположим, что природа окажется в самом выгодном состоянии с вероятностью и в самом невыгодном состоянии с вероятностью 1- .
Критерий Гурвица ориентирован на установление баланса между случаями крайнего пессимизма и крайнего оптимизма путем взвешивания обоих исходов.
Если принимающий решение – игрок А, то:
| (5.15) |
.Если принимающий решение – игрок B, то:
| (5.16) |
.Заметим, что, если коэффициент доверия равен нулю, критерий Гурвица превращается в "классический" минимакс, а при =1 получаем правило "максимум из максимумов" - выбор лучшего из лучших исходов.
Пример 5.8. Телефонная компания должна определить уровень своих возможностей по предоставлению услуг так, чтобы удовлетворить спрос своих клиентов на планируемый период.
Для каждого уровня спроса существуют различные уровни возможностей телефонной компании (например, при вводе нового тарифа). Имеются четыре варианта спроса на телефонные услуги, что равнозначно наличию четырёх состояний природы. Известны также четыре варианта предоставления телефонных услуг. Прибыль для каждого сочетания «управленческое решение – состояние природы» приведена в таблице 5.6.
Таблица 5.6 - Платежная матрица примера 5.8
| B1 | B2 | B3 | B4 |
A1 | 23 | 20 | 12 | 8 |
A2 | 21 | 24 | 22 | 5 |
A3 | 5 | 12 | 14 | 9 |
A4 | 18 | 22 | 9 | 10 |
Необходимо определить оптимальную стратегию телефонной компании, используя различные критерии.
Решение.
Максиминный критерий (критерий Вальда).
В данном случае обычным образом определяем нижнюю цену игры: =9.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 |
