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

Пусть имеем игру размерности т?п с матрицей

.

Обозначим через р*=(p1;...;рт), q*=(q1;...;qn) оптимальные смешанные стратегии игроков А и В.

,                                     (13)

где p1+p2+...+рт=1; рi?0 (i=1,…,m).

Аналогично стратегия q* игрока В гарантирует ему проигрыш не больше v, независимо от выбора стратегии Аi игроком А, т.е.

                                        (14)

где q1+q2+…+qп=1; qj?0 (j=1,…,п).

Поскольку элементы платежной матрицы на основании теоремы 5 всегда можно сделать положительными, то и цена игры vgt;0.

Преобразуем системы (13) и (14), разделив обе части каждого неравенства на положительное число v, и введем новые обозначения: pi/v=хi, qj/v=yj (i=1,…,m; j =1,…,п). Получим:

                                  (15)

где

х1+х2+...+хт=1/v; хi?0 (i=1,…,m),                    (16)

и

                                    (17)

где

у1+у2+…+уп=1/v; уj?0 (j=1,…,п).                  (18)

Так как игрок А стремится максимизировать цену игры v, то обратная величина 1/v будет минимизироваться, поэтому оптимальная стратегия игрока А определится из задачи линейного программирования следующего вида: найти минимальное значение функции z=х1+х2+...+хт при ограничениях (17), (18).

Оптимальная смешанная стратегия игрока В определится решением задачи следующего вида: найти максимальное значение функции w=у1+у2+…+уп при ограничениях (17), (18).

v==, pi=, qj= (i=1,…,m; j=1,…,п).

Проиллюстрируем решение матричной игры сведением ее к задаче ЛП.

Пример 8. Два сельскохозяйственных предприятия А и В выделяют денежные средства на строительство трех объектов. С учетом особенностей вкладов и местных условий прибыль предприятия А в зависимости от объема финансирования выражается элементами матрицы . Убыток предприятия В при этом равен прибыли предприятия А. Требуется найти оптимальные стратегии предприятий А и В.

¦ Обозначим чистые стратегии предприятий А и В через А1,А2,А3 и B1,B2,B3 соответственно. Предположим, что предприятие А располагает общей суммой а тыс. ден. ед., отпускаемой на строительство трех объектов. Аналогично и предприятие В имеет сумму в b тыс. ден. ед., отпускаемую на строительство тех же трех объектов. Тогда чистая стратегия А1 – это выделение a1 тыс. ден. ед. предприятием А на строительство первого объекта; A2 – чистая стратегия предприятия А, которое выделяет сумму a2 тыс. ден. ед. на строительство второго объекта; А3 – чистая стратегия предприятия А, которое выделяет сумму a3 тыс. ден. ед. на строительство третьего объекта. Общая сумма средств, выделяемых на строительство трех объектов, a=a1+a2+а3. Аналогично определяются чистые стратегии и для предприятия В.

Проверим игру на наличие седловой точки:

?=aij=4, ?=aij=6, ???,

поэтому решение игры определяем в смешанных стратегиях.

Для игрока А:                                        Для игрока В:

            z=х1+х2+х3?min,                                w=у1+у2+у3?max,

              хi ?0 (i=1,2,3),                                     уj?0 (j=1,2,3).

Вводя балансовые переменные х4?0, х5?0, х6?0 для исходной задачи и у4?0, у5?0, у6?0 для двойственной задачи, модели задач преобразуем к канонической форме. При этом балансовые переменные двойственной задачи станут базисными.

При «ручном» счёте проще решать двойственную задачу, т.к. она не требует введения искусственных переменных. Соответствие

ноническая форма задачи имеет вид:

w=у1+у2+у3?max;

уj?0 (j=1,…,6).

Решая ее симплекс-методом, имеем (итерации 0–2) оптимальный план

Итерация 0                                                    Итерация1

у*=(;…;)=(1/27; 4/27; 0; 0; 2/27; 0).

х*=(;…;)=(2/27; 0; 1/9; 0; 0; 17/27), z*=5/27.

По формулам v==, =хi, =уj (i=1,…,т, j=1,…,п) получим цену игры v=27/5 и вероятности и для оптимальных смешанных стратегий соответственно предприятий А и В:

=27/5?2/27=2/5, =27/5?0=0, =27/5?1/9=3/5,

=27/5?1/27=1/5, =27/5?4/27=4/5, =27/5?0=0.

Таким образом, оптимальными смешанными стратегиями сельскохозяйственных предприятий А и В являются стратегии р*=(2/5;0; 3/5) и q*=(1/5; 4/5;0) соответственно при гарантированном получении предприятием А независимо от стратегий предприятия В прибыли не менее 27/5=5,4 тыс. ден. ед. Убыток предприятия В при этом составит не более 5,4 тыс. ден. ед.

Итак, из общей суммы средств а тыс. ден. ед., выделяемых предприятием А на строительство трех объектов, на долю первого объекта должно выделяться 40%, второго – 0% и третьего – 60% этой суммы. Аналогично распределяются средства b тыс. ден. ед. предприятием В: на долю первого объекта приходится 20%, второго – 80% и третьего – 0 % общей суммы.    ?