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


[Старт] [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]


40

начает, что оптимальная стратегия второго игрока представляет собой совокупность трех стратегий. Любые две прямые, имеющие противоположные наклоны, определяют одно возможное оптимальное решение. Таким образом, из трех комбинаций (2, 3), (2, 4) и (3, 4) комбинация (2, 4) должна быть исключена как неоптимальная.

Комбинация (2, 3) дает у1 =у1=0. Следовательно, Уз=-У2 Ожидаемые проигрьш1и второго игрока, соответствующие чистым стратегиям первого игрока, представлены в табл. 5.12.

Таблица 5.12

Чистые стратегии первого игрока

Ожидаемые проигрыши второго ифока

-У2+3

у,+2

Значение у*2=\/2 (соответствующее минимаксной точке) определяется из равенства

->2+з=>;;+2.

Отметим, что подстановкой у*2=1/2 в выражение для ожидаемого

проигрыша второго игрока можно найти минимаксное значение, равное 5/2, совпадающее, как и должно быть, со значением игры v *.

Аналогично может быть рассмотрена и комбинация (3, 4), дающая другое оптимальное решение. Любое взвешенное среднее комбинаций (2, 3) и (3, 4) также будет давать оптимальное решение, в которое входят стратегии 2, 3 и 4.

Пример. Рассмотрим следующую игру вида 4x2 (табл. 5.13).

Таблица 5.13

Стратегия 1

Стратегия 2

Стратегия 1

Стратегия 2

Стратегия 3

Стратегия 4

Решение.

Эта игра не имеет седловой точки. Пусть Ух и У2=1-У1 - смешанные стратегии второго игрока. Тогда ожидаемые проигрыши второго игрока показаны в табл. 5.14.



Таблица 5.14

Чистые стратегии

Ожидаемые проигрыши

первого игрока

второго ифока

-2л+ 4

У\+2

-8л+6

Эти четыре прямые изображены на рис. 5.2. В данном случае минимаксная точка определяется как самая нижняя точка на огибающей сверху. Значение у1 получается как точка пересечения прямьос 1 и 3. Это дает у; = 2/3 и v* =8/3.

Среднеожидаемый выигрыш у~ первого игрока

Рис. 5.2

Прямые, пересекающиеся в минимаксной точке, соответствуют чистым стратегиям 1 и 3 первого игрока. Это показывает, что х*2=х1=0. Следовательно, xl-x. Ожидаемые выигрыши первого игрока, соответствующие чистым стратегиям второго игрока, приведены в табл. 5.16.

Таблица 5.16

Чистые стратегии второго игрока

Ожидаемые выигрыши первого игрока

2x1+2



Значение Xj =1/3 определяется из уравнения

-X, + 3 = + 2 .

Таким образом, оптимальной стратегией первого игрока будет X* = 1/3, х\ = О, Хз = 2/3, Х4 = О. Это дает, как и прежде, v* = 8/3 .

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

5.2.8. Решение игр вида (тхп) с помощью линейного программирования. Теория игр находится в тесной связи с линейным программированием, так как каждая конечная игра двух лиц с нулевой суммой может быть представлена как задача линейного программирования и, наоборот, каждая задача линейного программирования может быть представлена как игра. Г. Данциг указывает, что создатель теории игр Дж. фон Нейман, который первым ввел симплекс-метод в линейное программирование (1947 г.), установил это соотношение и в дальнейшем обосновал и развил концепцию двойственности в линейном программировании. В этом разделе описывается способ нахождения решения игры методом линейного программирования, который особенно эффективен для игр, описываемых матрицей большой размерности.

Мы показали, что оптимальная смешанная стратегия первого игрока определяется условиями

шах min У а..х,,

X, l<j<n, IJ

(5.8)

Xi > О, /= 1,w, Yui =1.

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

v = minX ..х, =т1п(Хад,Еад. тогда задача принимает вид

maxv

(5.9)

[Старт] [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]