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

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

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

Рассмотрим т х л-игру с матрицей

а = <**).

Без ограничения общности можно считать, что все элементы матрицы А положительны (этого всегда можно добиться, пользуясь аффинным правилом). Тогда искомое значение игры v - положительное число.

Интересы игрока А.

Из утверждений о свойствах оптимальных смешанных стратегий игроков вытекает, что при любой чистой стратегии 1* игрока В, k = 1,л, оптимальная смешанная стратегия Р = {ри ..., рт) игрока Л обеспечивает его средний выигрыш, не меньший v. Иными словами, выполняются соотношения

fc = l, л,

Р; = 1, р. >0, / = 1, т,

которые с учетом обозначений

х{ = -, 1 = 1, , v

можно записать так:

aikxi > 1, к = 1, л, i=i

Ух, = -, х,. >0, / = 1, /и.

/=i v

Поскольку игрок А стремится максимально увеличить свой гарантированный средний выигрыш, задача отыскания решения матричной игры сводится к следующей задаче:

Найти неотрицательные величины хь хт, удовлетворяющие неравенствам



Jaikxi £1, fc = l, л, и такие, что их сумма минимальна

niin.

Интересы игрока В.

Аналогичным образом заключаем, что оптимальная смешанная стратегия Q = {qu qn} игрока В при любой чистой стратегии 1/ игрока А обеспечивает его средний выигрыш, не больший v. Иными словами, выполняются соотношения

\z£v, / = 1, /И,

2=1, Як*0, k = l, л,

которые с учетом обозначений

Ук=-, = 1 л, v

можно записать так

*=i v

Поскольку игрок В стремится сделать гарантированный средний выигрыш игрока А минимально возможным, задача отыскания решения матричной игры сводится к следующей задаче:

Найти неотрицательные величиныуи у , удовлетворяющие неравенствам

Iaikyk £1, / = 1, т, и такие, что их сумма максимальна



ук - max.

Тем самым, мы получаем следующий важный результат.

ТЕОРЕМА. Решение матричной игры с положительной матрицей А = (aik) равносильно решению двойственных задач линейного программирования.

Задача А: найти неотрицательные величины хи хт удовлетворяющие неравенствам

aikxt >1, * = !,..., л,

и такие, что их сумма минимальна,

5>.

Задача В: найти неотрицательные величины уи уп, удовлетворяющие неравенствам

алук<19 / = 1, т,

Аг= 1

и такие, что их сумма максимальна,

2>.-

При этом значение игры

max.

где 0 - величина, обратная общему значению оптимальных сумм

в-2 2*.

а оптимальные значения р] и 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