Экономико-математическое моделирование задач теории игр

Решение.

Задача сводится к игровой  модели, в которой игра предприятия А против спроса В задана платежной матрицей, представленной в таблице 5.4.

Определим верхнюю и нижнюю цены игры:   = 3,   = 6. Как видно, седловая точка отсутствует, и решение нужно искать в смешанных стратегиях игроков: U^* = ( ,  ), Z^* = ( ,  ,  ,  ).

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

 

Рисунок 5.5 – Геометрическое решение игры примера 5.6

Точка M – точка максимального  гарантированного выигрыша. Она находится  на пересечении отрезков, соответствующих  состояниям спроса B₁ и B₃.

Найдем координаты точки M.

B₁B^'₁:

=   ,  откуда  y = 6x + 3,

B₃B^'₃:

=   ,  откуда  y = -2x + 6,

6x + 3 = -2x + 6,  8x = 3,  x = 3/8,  y = 21/4.

Таким образом, получим:

= 5/8,   = 3/8, v = 21/4.

Полученное решение интерпретируется следующим образом. Продукция А₁ должна составлять 62,5% (5/8) от общего объема выпущенной продукции, продукция А₂ – 37,5% (3/8). Это гарантирует предприятию среднюю прибыль в размере 5,25 (21/4) при любом характере спроса.

Для полного решения игры осталось отыскать оптимальную стратегию  спроса.

Активными стратегиями игрока B (спроса) являются стратегии B₁ и B₃, следовательно,   = 0,   = 0.

Используя выражение (5.2), вытекающее из теоремы об активных стратегиях, составим систему из двух уравнений  с двумя неизвестными:

3  + 6  = 21/4,   +   = 1.

Второе уравнение умножим  на три и вычтем из первого:

3  = 9/4,   = 3/4,   = 1/4.

Ответ: U^* = (5/8, 3/8); Z^* = (1/4, 0, 3/4, 0); v = 21/4.

 

Еще раз обратим внимание на рисунок 5.5 и платежную матрицу, представленную в таблице 5.4.

Стратегия B₂ заведомо невыгодна для игрока В по сравнению со стратегией B₁. На рисунке 5.5 все точки отрезка B₂B^'₂ лежат выше отрезка B₁B^'₁, следовательно, заранее понятно, что стратегия B₂ не входит в оптимальное решение.

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

 

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

Такими стратегиями для  игрока А являются те, которым соответствуют  строки с элементами, заведомо меньшими по сравнению с элементами како-либо другой строки.

Для игрока В невыгодным стратегиям соответствуют столбцы  с элементами, заведомо бoльшими по сравнению с элементами какого-либо другого столбца.

 

5. Приведение парной  игры к задаче линейного программирования

 

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

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

 

Теорема. Для того чтобы число v было ценой игры, а U* и Z*- оптимальными стратегиями, необходимо и достаточно выполнение неравенств:

aij  ≥ v,    ,  aij  ≤ v,    .

 

Рассмотрим игру mxn, определяемую матрицей:

A =

a11   a12    ...     a1n  a21   a22    ...     a2n       ... am1  am2   ...     amn

.

Как и ранее, игрок A обладает стратегиями A₁, A₂, ..., A_m, игрок В – стратегиями B₁, B₂, …, B_n. Требуется определить оптимальные стратегии игроков U^* и Z^*.

Рассмотрим оптимальную  стратегию U^* игрока A.

Согласно теореме, приведенной  выше, справедливо следующее утверждение.

Если игрок А применяет  смешанную стратегию U^* = ( ,  , ...,  ) против чистой стратегии B_j игрока В, то он получает средний выигрыш илиматематическое ожидание выигрыша a_j = a_1j  + a_2j  + ... + a_mj ,  .

Для оптимальной стратегии U^* все средние выигрыши не меньше цены игры v, поэтому получаем систему неравенств:

a11  + a21  + ... + am1  ≥ v,  a12  + a22  + ... + am2  ≥ v, ... a1n  + a2n  + ... + amn  ≥ v.

(5.3)

Предположим для определенности, что v > 0.

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

Каждое из неравенств разделим на число v (v > 0), а также введем новые переменные: y₁ =   / v,  y₂ =   / v, ..., y_m =   / v.

Тогда система (5.3) примет вид:

a11y1 + a21y2 + ... + am1ym≥ 1,  a12y1 + a22y2 + ... + am2ym ≥ 1, ... a1ny1 + a2ny2 + ... + amnym≥ 1.

(5.4)

При этом y_i ≥ 0,    .

Далее рассмотрим равенство   +   + ... +   = 1.

Разделим неравенство  на число v (v ≠ 0). Получим:

y1 + y2 + ... + ym = 1/v.

(5.5)

Вспомним, что цель игрока А – максимизировать свой гарантированный  выигрыш, т.е. цену игры v. Максимизация цены игры v эквивалентна минимизации величины 1/v, поэтому задача может быть сформулирована следующим образом: определить значения переменных y_i ≥ 0, i = 1, 2, …, m, так, чтобы они удовлетворяли линейным ограничениям (5.4) и при этом линейная функция (5.5) обращалась в минимум.

Перед нами задача линейного  программирования.

Решая задачу (5.4) – (5.5), можно  найти оптимальную стратегию U^*.

 

Аналогичные рассуждения  выполним и для игрока В.

Обозначив x_j =   / v,   , в результате получим:

a11x1 + a12x2 + ... + a1nxn≤ 1,  a21x1 + a22x2 + ... + a2nxn ≤ 1, ... am1x1 + am2x2 + ... + amnxn ≤ 1.

(5.6)

x1 + x2 + ... + xn = 1/v.

(5.7)

Таким образом, задача определения  оптимальной стратегии игрока В  сводится к следующему: определить значения переменных x_j ≥ 0, j = 1, 2, …, n, так, чтобы они удовлетворяли линейным ограничениям (5.6) и при этом линейная функция (5.7) обращалась в максимум.

Решая задачу линейного программирования (5.6) – (5.7), получим оптимальную стратегию Z^*.

 

Вновь приведем формулировки полученных задач линейного программирования.

= y1 + y2 + ... + ym → min;			= x1 + x2 + ... + xn → max;
	a11y1 + a21y2 + ... + am1ym≥ 1,  a12y1 + a22y2 + ... + am2ym ≥ 1, ... a1ny1 + a2ny2 + ... + amnym≥ 1;			a11x1 + a12x2 + ... + a1nxn≤ 1,  a21x1 + a22x2 + ... + a2nxn ≤ 1, ... am1x1 + am2x2 + ... + amnxn ≤ 1;
yi ≥ 0,   .			xj ≥ 0,   .

Очевидно, что задачи (5.4) – (5.5) и (5.6) – (5.7) представляют собой  пару взаимно двойственных задач  линейного программирования. Их решение  позволяет решить соответствующую  игру.

При этом:

;     = v ∙  ,   ;     = v ∙  ,   .

(5.8)

 

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

1. Формулировка пары двойственных  задач линейного программирования, эквивалентных заданной парной  игре.

2. Определение оптимальных  планов двойственных задач.

3. Нахождение решения  игры с использованием соотношений  между оптимальными планами двойственных  задач и оптимальными стратегиями  и ценой игры (формулы (5.8)).

 

Пример 5.7. Предприятие выпускает скоропортящуюся продукцию, которую может сразу отправить потребителю (стратегия В₁), отправить на склад для хранения (стратегия В₂) или подвергнуть дополнительной обработке (стратегия В₃) для длительного хранения.

Потребитель может приобрести продукцию немедленно (стратегия A₁), в течение небольшого времени (стратегия A₂), по истечении длительного периода времени (стратегия A₃).

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

Определите оптимальные  пропорции продукции для применения стратегий B₁, B₂ и B₃, руководствуясь «минимаксным критерием» (гарантированный средний уровень затрат) при матрице затрат, представленной в таблице 5.5.

Таблица 5.5 - Платежная матрица  примера 5.7

	B1	B2	B3
A1	2	5	10
A2	8	6	8
A3	12	8	6

Решение.

Проверим игру на наличие  седловой точки:   = 6,   = 8. Седловая точка отсутствует. Упростить игру, путем исключения заведомо невыгодных стратегий не удается.

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

= y1 + y2 + y3 → min;			= x1 + x2 + x3 → max;
	2y1 + 8y2 + 12y3 ≥ 1,  5y1 + 6y2 + 8y3 ≥ 1,  10y1 + 8y2 + 6y3 ≥ 1;			2x1 + 5x2 + 10x3 ≤ 1,  8x1 + 6x2 + 8x3 ≤ 1,  12x1 + 8x2 + 6x3 ≤ 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) найдем решение игры: