СВЯЗЬ МАТРИЧНЫХ ИГР С ЛИНЕЙНЫМ ПРОГРАММИРОВАНИЕМ (ОСНОВНАЯ ТЕОРЕМА ТЕОРИИ ИГР). ПРИМЕР РЕШЕНИЯ ЗАДАЧИ

Первоначально развитие теории стратегических матричных игр осуществлялось параллельно и независимо от линейного программирования. Позже было установлено, что стратегичес­кая матричная игра может быть сведена к паре двойственных задач линейного программирования. Решив одну из них, полу­чаем оптимальные стратегии игрока 1; решив другую, получа­ем оптимальные стратегии игрока 2. Математическое соответ­ствие между стратегическими матричными играми и линейным программированием было установлено Дж. Б. Данцигом, сфор­мулировавшим и доказавшим в 1951 г. основную теорему тео­рии игр [23].

Теорема. Каждая матричная игра с нулевой суммой всегда имеет решение в смешанных стратегиях, т.е. существуют такое число v и такие стратегии U * и W * игроков 1 и 2 соответственно, что выполняются неравенства:

Поясним смысл доказываемых неравенств: если игрок 1 от­клоняется от своей оптимальной стратегии, то его выигрыш не увеличивается по сравнению с ценой игры; если от своей опти­мальной стратегии отклоняется игрок 2, то по сравнению с це­ной игры его проигрыш не уменьшается.

Доказательство. Пусть матрица игры равна A = . Всегда можно считать, что все коэффициенты а ij > 0. Если это не так, то предположим, что наименьший из всех отрицательных коэффициентов есть а 0 < 0. Тогда увеличим все элементы платежной матрицы на произвольное положительное число а > – а 0 . Функция выигрыша при этом окажется равной

Из этого следует, что от увеличения всех элементов матрицы A = на величину a цена игры увеличивается на эту величи­ну, причем оптимальные смешанные стратегии не изменяются.

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

Рассмотрим теперь пару двойственных задач линейного про­граммирования с матрицей условий A = ( aij > 0), совпадаю­щей с платежной матрицей игры. Введем вектор ограничений прямой задачи В = (1, 1, . , 1) T , состоящий из т единиц (это вектор-столбец, для удобства записи представленный в виде транспонированной строки. Т - символ транспонирования мат­рицы), и вектор-строку коэффициентов линейной формы или функционала С = (1, 1. 1), состоящий из п элементов. Тогда в векторно-матричной форме соответствующая задача линей­ного программирования может быть записана следующим образом:

где Х- вектор искомых переменных задачи (П1). То же в скалярной форме:

Двойственная задача к задаче линейного программирования (П1) может быть записана следующим образом:

где Y - вектор искомых переменных задачи (П2).

То же в скалярной форме:

Все элементы матрицы А по предположению положительны, поэтому многогранные множества задач (П1) и (П2) ограниче­ны. Многогранник задачи (П1) не пуст, так как Х = 0 является допустимым планом. Следовательно, задача (П1), а с ней (по первой теореме двойственности) и задача (П2) разрешимы, и их функционалы в оптимальных планах совпадают (вторая теорема двойственности):

(С, X*) = (У* В).

С учетом выбранных единичных векторов С и В получаем следующее соотношение:

Из условия YA ³ С следует, что Y* ¹ 0, поэтому

Положительность значения v обеспечивается положительно­стью всех значений элементов платежной матрицы А.

Обозначим U * = vY *, W * = vX *. Поскольку v, X*, Y* неотри­цательны, то U * ³ 0, W * ³ 0.

Кроме того, , , так как по определению это частоты использования смешанных стратегии, а сумма частот равна единице. По условиям прямой и двойственной задач АХ £ В и YA ³ С. Оптимальные планы этих задач обозначим X* и Y *, причем по предположению X* = W*/v , Y*= U*/v. Поэтому

Умножим обе части неравенства (ПЗ) слева на произвольный w-мерный вектор U ³ 0, для которого справедливо

где В - единичный вектор.

UAM * ³ v ( U , B ) = v ,

т.е. имеет место неравенство

UAM* ³ v . (П5)

Также умножим обе части неравенства (П4) справа на произ­вольный n -мерный вектор W > 0 , для которого справедливо

где С - единичный вектор.

U * AM ³ v ( C , W ) = v ,

т.е. справедливо неравенство

U * AM ³ v . (П6)

Сравнивая неравенства (П5) и (П6), приходим к соотноше­нию

UAW * £ v £ U * AW ,

т.е. U * и W * - оптимальные стратегии, а v - цена игры с платеж­ной матрицей А, что и требовалось доказать.

Следствие (С1). В процессе доказательства основной теоре­мы теории игр с платежной матрицей A = ( aij > 0) игре приведена в соответствие следующая пара задач линейного про­граммирования:

Составляющие оптимальных стратегий и игры связа­ны с компонентами и оптимальных планов двойственных задач линейного программирования (П7) формулами:

Следствие (С2). Вместо приведенной выше пары двойствен­ных задач линейного программирования (П7) иногда удобнее рассматривать другую пару задач, имеющих более ясный содер­жательный экономический смысл:

1. Прямая задача. Игрок 1 стремится увеличить цену игры:

v ® m ах (П8)

т. е. игрок 1 действует так, чтобы его средний выигрыш при использовании его стратегий с частотами ui для любой j -й стра­тегии игрока 2 был не меньше величины v , которую он стремит­ся увеличить;

т. е. сумма частот применения стратегий игрока 1 равна единице.

2. Двойственная задача. Игрок 2 стремится уменьшить свой проигрыш:

v ® min (П9)

т. е. игрок 2 действует так, чтобы его средний проигрыш при использовании его стратегий с частотами wj для любой i -й стра­тегии игрока 1 не превышал величины v, которую он стремится уменьшить;

т. е. сумма частот применения стратегий игрока 2 равна единице.

В такой постановке каждая из задач (П8) и (П9) содержит на одно переменное (v) и на одно ограничение ( или ) больше, т.е. размерности прямой и двойственной задач соответ­ственно увеличиваются, что может сыграть определенную роль при ручном решении задач линейного программирования, но не имеет практического значения при решении задач линейного про­граммирования на ЭВМ.

Пример решения задачи. Решить аналитически (используя мажорирование) игру с платежной матрицей

Решение. Если для первых двух строк матрицы взять ве­совые коэффициенты соответственно 0,25 и 0,75, то получим:

0,25 * 24 + 0,75 * 0 + 6 > 4;

0,25 * 0 + 0,75 * 8 = 6 > 4.

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

В матрице есть два нуля. Для того чтобы все элементы мат­рицы стали больше нуля, прибавим к каждому элементу по еди­нице. Матрица примет вид:

Далее ставим и решаем пару задач (двойственных) линейно­го программирования:

Для первой задачи (игрока 2) из условия угловой точки следует:

откуда получаем оптимальное решение:

Находим оптимальные смешанные стратегии игрока 2:

Для второй задачи (игрока 1) из условия угловой точки следует:

откуда оптимальное решение равно:

Оптимальными смешанными стратегиями игрока 1 будут:

Цена игры рассчитывается с учетом ее поправки на единицу:

v = 1:0,1427-1=6,008.

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