Моделирование рисковых ситуации в экономике и бизнесе (стр. 27 из 29)

Из этого следует, что от увеличения всех элементов матрицы A =

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

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

Рассмотрим теперь пару двойственных задач линейного программирования с матрицей условий A =

(a_ij > 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 =

(a_ij > 0) игре приведена в соответствие следующая пара задач линейного программирования:

Составляющие оптимальных стратегий

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

Цена игры

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

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

v ® mах (П8)

при условиях:

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

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

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

v ® min (П9)

при условиях:

т. е. игрок 2 действует так, чтобы его средний проигрыш при использовании его стратегий с частотами w_j для любой 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) из условия угловой точки следует:

25x₁ + x₂ = 1;

х₁ + 9x₂ = 1,

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

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

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

25y₁ + y₂ = 1;

y₁ + 9 y₂ = 1,

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

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

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

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

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