Промышленный лизинг
Методички
Сведение решения матричной игры к задаче линейного программирования Рассмотрим т х л-игру с матрицей а = <**). Без ограничения общности можно считать, что все элементы матрицы А положительны (этого всегда можно добиться, пользуясь аффинным правилом). Тогда искомое значение игры 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 |