Промышленный лизинг Промышленный лизинг  Методички 

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 91 92

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

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

Второе утверждение вместе со следствием из него показывает, что для поиска значения игры существуют достаточно простые формулы.

Третье устанавливает еще более жесткую связь между искомым решением и чистыми стратегиями игроков.

ТЕОРЕМА 1. Для того чтобы набор (Р*, Q*, v) был решением матричной игры в смешанных стратегиях, необходимо и достаточно, чтобы выполнялось условие

Доказательство начнем с необходимости.

Пусть (Р*, Q*, v) - решение матричной игры в смешанных стратегиях. Тогда для любых наборов Р = {ри рт) и Q = {qb q } выполнены неравенства

справедливые, в частности, и для любых чистых стратегий игроков

(здесь Р = {рь рт} - произвольная стратегия игрока А), которое доказывается совсем просто:

#(! (} )£v£#(P\l,), / = 1,...,/и; * = !,...,л. (*)

Я(Р, (Г)£Я(Р\ Q>v<#(P\ Q),

Я(1 СГ)<#(Р\1,). Достаточность. Предположим выполненным условие #(l Q.)<v£#(P\l,), / = 1,...,/я; * = 1,...,л,

и воспользуемся равенством


т п т I п >

/ 1 Ы\ / 1 \к=\ I

Домножим неравенства

#(l Q.)<v, / = 1,...,/и,

на Pi и, сложив их, получим, что



2>,tf(l Q)Sv5>,=v.

/=1 /=1

Откуда в силу того, что

2>,яо,.Р> %{%*А= \%лрлк = #(p,q),

получаем, что

Я(Р, Q)<v.

Взяв произвольную стратегию Q = {qh qn} игрока В и действуя подобным же образом, домножим неравенства

v<H(P\lk), * = 1,...,и, на qk, сложим их и получим, что

v = v%k<H<r, Q).

Тем самым

Я(Р, Q-)*v<H(P\ Q). Положив здесь Р = Р*, Q = Q*, получим, что

Я(Р\ Q>v

и значит (Р*, Q*, v) - решение в смешанных стратегиях.

ТЕОРЕМА 2. Для любой матричной игры справедливы следующие два соотношения:

штЯ(Р, Q) = mjn#(P,l4), max Я(Р, Q) = max Я(1 Q). Докажем первую серию равенств.

То, что выражение в левой части не превосходит правой,

ramЯ(Р, Q) < min Я(Р, 1к)

легко следует из того, что минимум функции Я(Р, Q) слева ищется на большем множестве (всех стратегий игрока В), а справа на меньшем множестве (только его чистых стратегий). Введем обозначение



и оценим функцию Я(Р, Q) снизу. Имеем

т I я \ т

1 = 1 \ АГ= 1 / 1 = 1

/Я Л Л

* 2Х, Л = 5Х. А 1 = Я(Р, 110) min Я(Р, 1, )

/=1 Аг= 1 /=1

Отсюда

пипЯ(Р, Р)>1ШпЯ(Р, 1.).

Сопоставив первое из доказанных неравенств с последним, убеждаемся в справедливости утверждения.

Справедливость второй серии соотношений доказывается аналогично.

Следствие.

I v = maxmin Я(Р, 1) = пиптахЯ(1/,Р).

ТЕОРЕМА 3. Пусть набор (Р*, Q*, v) является решением матричной игры в смешанных стратегиях. Тогда

из того, что /*,*>(), вытекает равенство HQ.i9Q*) = v9 из того, что q*k>09 вытекает равенство Я(Р\ lk)=v.

Доказательство первого из сформулированных утверждений будем вести от противного.

Вследствие того что набор (Р*, Q*, v) - решение матричной игры в смешанных стратегиях, для любого / выполняются неравенства

H(\i9Q)<v, / = 1,...,/и.

Предположим, что существует номер /., для которого

Pt. >о

и соответствующее неравенство является строгим

Ж1,.,(Г)<

Умножим обе части каждого из неравенств H(lnQ*)<v на р\ и,

сложив (в силу сделанного предположения о том, что одно из них является строгим), получим, что

#(Р\ (Г)=Я(Р\ Q*).



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 91 92