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


[Старт] [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] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [ 190 ] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]


190

Решение матричных игр методами линейного программирования. Теория игр находится в тесной связи с линейным программированием, так как любую конечную игру двух лиц с нулевой суммой можно представить в виде задачи линейного программирования и наоборот. Дж. Данциг [3] отмечает, что, когда в 1947 году создатель теории игр Дж. фон Нейман впервые ознакомился с симплекс-методом, он сразу установил эту взаимосвязь и обратил особое внимание на концепцию двойственности в линейном программировании. Этот раздел иллюстрирует решение матричных игр методами линейного программирования.

Оптимальные значения вероятностей xt, i = 1, 2, т, игрока А могут быть определены путем решения следующей максиминной задачи.

т т т

/=1 (=1 ,=1

х1 + х2 + ... +хт = 1, х. > 0, i=l, 2.....т.

Чтобы сформулировать эту задачу в виде задачи линейного программирования, положим

v = min £Xi-*/.Zai!*-"-Zfll».jr.-

Отсюда вытекает, что

Za*.-v- у=1.2,..-, л.

Следовательно, задача игрока А может быть записана в виде

максимизировать z = v

при ограничениях

v-Vi -0 7 = 1-2,..../!,

х, + х2 + ... + хт = 1,

х, > О, i = l, 2, т,

v не ограничена в знаке. Отметим последнее условие, что цена игры v может быть как положительной, так и отрицательной.

Оптимальные стратегии yv у2, уп игрока В определяются путем решения задачи

limax ZX-IX.....1ХЛ

mm j max

y>0, /-1,2.....re.

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

Минимизировать w - v

при ограничениях

ZV,0 = 1.2...., п

у,+у2+ ... +(/„ = !,

7 = 1



i/.>0, ; = 1, 2, п,

v не ограничена в знаке.

Две полученные задачи оптимизируют одну и ту же (не ограниченную в знаке) переменную и, которая является ценой игры. Причиной этого служит то, что задача игрока В является двойственной к задаче игрока А (вам предлагается доказать это утверждение в упражнении 14.4.3.5, используя определение двойственности из главы 4). Это означает, что оптимальное решение одной из задач автоматически определяет оптимальное решение другой.

Пример 14.4.4

Решим следующую матричную игру методами линейного программирования.

Минимумы строк

Максимумы столбцов

Значение цены игры v находится между -2 и 2. Задача линейного программирования для игрока А

Максимизировать z = v

при ограничениях

v - Зхг + 2х2 + Ъх3 < О, v + - 4х2 + 6х3 < О, v + 3x1+x2-2x3<0,

xv х2, х3 > О,

v не ограничена в знаке. Оптимальным решением является = 0,39, х2 = 0,31, х, = 0,29 и v = -0,91. Задача линейного программирования для игрока В

Минимизировать z = v

при ограничениях

о-3у,+у2 + 3у3>0, v + 2yx-Ayt+yt>0, и + 5у, + 6у2-2у3>0,

v не ограничена в знаке. Оптимальным решением является у, = 0,32, у2 = 0,08, у3 = 0,60 и v = -0,91.



В программе TORA для решения игр двух игроков с нулевой суммой надо выбрать команду Zero-sum GamesOSolveLP-based (Игры с нулевой суммойРешитьКак задачу ЛП). На рис. 14.10 показан результат решения задачи примера 14.4.4 (файл ch 14ToraGamesEx 14-4-4).

TORA D:\Woik\TordFilei\cM4ToraGameifx14 4 4 Itf

DECISION ANALYSIS USING GAMES

Рис. 14.10. Решение программой TORA игры двух игроков с нулевой суммой из примера 14.4.4

УПРАЖНЕНИЯ 14.4.3

1. На загородном пикнике две команды, по два человека в каждой, играют в прятки. Есть четыре места, где можно спрятаться (А, Б, В и Г), и два члена прячущейся команды могут спрятаться каждый отдельно в любых двух из четырех мест. Затем другая команда имеет возможность проверить любые два места. Команда, которая ищет, получает премию, если будут обнаружены оба участника прячущейся команды, если же не обнаружен ни один участник, то она выплачивает премию. Иначе игра заканчивается вничью.

a) Сформулируйте задачу в виде игры двух лиц с нулевой суммой.

b) Определите оптимальные стратегии и цену игры.

2. Университетские команды UA и DU определяют свои стратегии игры в национальном чемпионате по баскетболу для колледжей. Оценивая возможности своих "запасных скамеек", каждый тренер разработал по четыре варианта замены игроков на протяжении игры. Способность каждой команды выполнять двух-, трехочковые и штрафные броски является основным фак-

[Старт] [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] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [ 190 ] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]