назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [ 28 ] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90]


28

25.2.Аналогично, вводя для каждой стратегии Уигрока2 i;y = max,-.F

и полагая y=(l/fy)y, мы приходим к задаче линейного программирования

у4/.У< 1, / = 1,. . . ,т, Jj y->max,

которая двойственна к предыдущей. Следовательно, решения двойственной к (25.3), (25.5) и (25.6) задачи линейного программирования и только они суть оптимальные стратегии игрока 2 в игре с матрицей А.

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

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

ХАВ,(25.7)

X >0,(25.8)

ХС->тах,

ЛГ>С,(25.9)

ГО,(25.10)

где X и С - m-мерные векторы, Y и В - -мерные векторы, а - тХп-матрица.

25.4.Умножая неравенство (25.7) справа почленно на неотрицательный вектор У , мы получаем

ХАУВУ,(25.11) а умножая неравенство (25.8) слева почленно на X, -

ХАУ>ХС,(25.12) Из (25.11) и (25.12) следует, что

ХСйВУ(25.13)

при любых Xи у, удовлетворяющих неравенствам(26.7) -(25.10).Следовательно, если в (25.13) имеет место равенство, ХС = ВУ, то ХС- принимает наибольшее значение, допускаемое неравенствами (25.7) и (25,8), а ВУ - наименьшее значение, допускаемое неравенствами (25.9) и (25.10) . Иными словами, Хц У оказываются в этом случае оптимальными решениями для рассматриваемых задач линейного программирования.

255. В связи с парой задач (25.7) - (25.8) и (25.9) - (25.10) линейного программирования мы будем рассматривать (m + w+ 1) X (m + w+ 1)-мат-



рицу М, записывая ее в следующей блочной (клеточной) форме:

-А О В

-в о

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

Пусть Z = (U, F, 1) - оптимальная стратегия, причем U является т-век-тором, V - -вектором, а Г - скаляром. То обстоятельство, что Z - стратегия, означает, что

Z>0, ZJln-, = h(25.14)

а ее оптимальность - что

ZMZ.Vm = 0.(25.15)

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

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

ХАВ,

Х>0,

ХС -> шах,. . . {прямая задача) AY>C

ВУ min;. .. (двойственная задача)

и описанная выше соответствующая им матрица М. Тогда

1) есш Z = {V, V, t) - оптимальная стратегия, в которой f > О, то

х= - и,

Г= - F t

(25.16)

являются соответственно оптимальными решениями прямой и двойственной задач;

2)если для каждой оптимальной стратегии Z = {U, V, t) оказывается t = О, то обе задачи линейного программирования оптимальных решений не имеют;

3)если X и У - решения прямой и двойственной задач линейного программирования и

Г= ---~;г- ,(25 Л7)

+ 7„Г+1



то (т + п - I) - вектор

Z = (rX, tY,t)(25.18)

есть оптимальная стратегия в игре Гм-

Доказательство. 1) Запишем соотношения (25.14) и (25.15) в блочной форме:

О -А

-С в о

или, выполняя действия над блоками,

и>0, VO, tO,(25.19)

UJl +VJj; + t = h(25.20)

Л F-rC>0,(25.21)

-UA+tBO,(25.22)

UC -BV0.(25.23)

По условию > 0. Следовательно, на t можно делить числа, а также -почленно - соотношения. Деля на t векторы Uu V, мы полчаем (25.16), а деля (25.22), (25.21) и (25.19) - формулировки прямой и двойственной задач из условий теоремы.

Поэтому, согласно сказанному в п. 25.4, должно выполняться (25.13). Но из (25.23) следует, что ХС> ВУ, так что в (25.13) в действительности имеет место равенство. Следовательно, X и У составляют пару оптимальных решений пары двойственных задач.

2) Пусть теперь для каждой оптимальной стратегии Z = (U,V,t) имеет место t = 0. На основании теоремы, следующей из леммы Фаркаша (см. п. 17.5), получаем, что для некоторой оптимальной стратегии Z = (U, V, t) в (25.23) должно возникнуть строгое неравенство: UC -BV>0.

Таким образом, система (25.21) - (25.23) может быть переписана в виде

AVO,(25.24)

UAO,(25.25)

UC>BV.(25.26)

Относительно знака стоящих в (25.26) чисел нам могут представиться две возможности. Предположим сначала, что

С>0.(25.27)

Возьмем произвольное а > О и являющийся допустимым решением прямой задачи вектор X. Рассмотрим вектор Х + аП.Нз. основании (25.25) и нера-

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [ 28 ] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90]