Линейного программирования

Рассмотрим игру, платежная матрица которой имеет размерность

A=

Матрица не содержит седловой точки, поэтому решение игры представлено в смешанных стратегиях:

(7.15)

(7.16)

При оптимальной стратегии игрока А выполняется условие:

(7.17)

(7.18)

Можно рассмотреть задачу оптимальной стратегии игрока А, для которой имеют место следующие ограничения:

(7.19)

Величина V (цена игры) неизвестна, но можно считать V > 0 имея в виду, что элементы матрицы А неотрицательны. Этого всегда можно добиться, прибавив ко всем элементам матрицы некоторое положительное число. Преобразуем систему ограничений, разделив все члены неравенства на величину V. В результате получим:

(7.20)

Из условия

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

(7.21)

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

(7.22)

при ограничениях типа (7.20) и условиях неотрицательности:

(7.23)

Решая ее, находим значение t_i и величину 1/V, затем определяем значения

(7.24)

Для определения стратегии игрока В запишем следующие условия:

(7.25)

Разделив все члены неравенства на V, получим:

(7.26)

где

Переменные U_j должны быть определены таким образом, чтобы выполнялось условие (7.26) и достигался максимум функции

(7.27)

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

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

Заказчик (игрок А) имеет 4 возможных метода получения целевого эффекта (4 чистых стратегии):

1.Снижение стоимости реализации проекта;

2. Повышение научно-технического уровня проекта;

3. Приглашение к участию в проекте других инвесторов;

4. Поэтапная реализация проекта.

У подрядчика (игрок В) две чистые стратегии:

5- Привлечение субподрядчиков к работе над проектом;

6- Получение кредитов под модернизацию и расширение производства.

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

Представим условия игры в виде матрицы игры (платежной матрицы), записанной в таблице 7.11.

Таблица 7.11 – Матрица игры

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

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

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

Оптимальной для подрядчика будет 5-я стратегия.

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

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

Таблица 7.12 - Платежная матрица

Максиминная стратегия заказчика:

.

Минимаксная стратегия подрядчика:

.

Отсюда 10< 15, и, следовательно, решение игры не определяется в чистых стратегиях. Для решения игры в смешанных стратегиях необходимо определить вероятности, с которыми игроки А и В должны применять свои чистые стратегии. В этом случае возможно сведение игры к задаче линейного программирования (7.20, 7.22).

В нашем примере целевая функция имеет вид (7.22):

t₁+ t₂+ t₃ + t₄ ® min

при ограничениях (7.20):

-20× t₁ -10× t₂+ 10× t₃+15× t₄ ³ 1,

20× t₁+30× t₂+ 20× t₃+8× t₄ ³ 1.

Cимплекс-матрица для решения задачи на ЭВМ имеет вид, представленный в таблице 7.13.

Таблица 7.13 - Симплекс - матрица

В результате решения задачи значение целевой функции: 0.077.

Значение искомых переменных:

t₁=0; t₂=0; t₃=0.028; t₄=0.049.

Поскольку значение целевой функции

F=1/V=0.077, цена игры V=1/0.077=13.

x₃=V× t₃=0.028 × 13=0.36;

x₄=V× t₄=0.049 × 13=0.64;

x₃+x₄=0.36+0.64=1.

Таким образом, игрок А с вероятностью 0.36 применяет свою 3-ю стратегию, и с вероятностью 0.64 - 4-ю стратегию, рекомендующую повышение научно-технического уровня проекта. Стратегия 1 и 2 являются пассивными (вероятность их применения равна нулю).

Для определения оптимальных смешанных стратегий подрядчика сформулируем следующую задачу линейного программирования (7.27, 7.26):

U₁ + U₂ ® max:

-20 + 20 £ 1,

-10 + 30 £ 1,

10 + 20 £ 1,

15 + 8 £ 1.

Получим симплекс-матрицу, записанную в таблице 7.14.

Таблица 7.14 – Симплекс-матрица

В решении задачи получим значение целевой функции: 0.077 (так же, как и для двойственной задачи).

Значения искомых переменных:

U₁=0.053, U₂=0.024 4.

Значение целевой функции W=1/V=13

y₁=V× U₁=0.053× 13=0.69

y₂=V× U₂=0.024× 13=0.31

y₁+y₂=0.69+0.31=1

Подрядчик с вероятностью 0.69 применяет свою 1-ю стратегию, т.е. привлекает субподрядчиков к работе над проектом; и с вероятностью 0.31 - 2-ю стратегию, рекомендующую ему получение кредитов под модернизацию и расширение производства.

Вопросы для самопроверки:

1. Классифицируйте игры.

2. Каким образом определяется, решается ли матричная игра в чистых стратегиях?

3. Покажите алгоритм решения матричной игры в смешанных стратегиях.

4. В чем особенность игр с природой?

5. Что такое игра n лиц, кооперативная игра?

6. Приведите примеры применения теории игр для решения экономических задач.