Файл: В. А.МАТВЕЕВ.pdf

(2β−1, 1−2β).

Обозначим

f1 (β) = 2β −1,

f2 (β) =1− 2β.

Найдём

min max ( f1(β), f2 (β)) =

0≤β≤1 i {1,2}

min (max (2β−1, 1−2β)).

0≤β≤1 i {1,2}

Для нахождения минимакса приведём геометрическую иллюстрацию на рис.6.6.

f

−1

f2 (β)

Рис. 6.6.

Вначаледля каждого β [0,1] найдём

min (2β−1, 1−2β).

i {1,2}

51

На рис.6.6 такие минимумы для каждого β [0,1] образуют ломаную – верхнюю огибающую RST. Затем на огибающей находим наименьшее значение, которое достигается в точке S.

Эта точка появляется при β [0,1] , которое является решением

уравнения f1 = f2 , т.е. 2 β - 1 = 1 - 2 β. Здесь β = 12. Вторая

координата точки S будет 2 12 −1 = 0. Итак S( 12 ,0). В смешанном расширении данной игры

min (max (2β−1, 1−2β)) = 0.

0≤β≤1 i {1,2}

Минимаксная стратегия второго игрока yB = (b, 1- b) = (1/2, 1/2). В примере выполнены условия утверждения 4.2. В самом деле, минимакс и максимин существуют и выполнено равенство

νB = νН = 0.

Значит цена игры ν * = 0 и седловая точка (x*, y*) = ((1/2, 1/2), (1/2, 1/2)).

Витоговой проверке следует продемонстрировать

выполнение равенства (x*)T A( y*) =v *. В данном примере получаем

( 12 , 12) 1 −1 12 = 0.−1 1 12

Это верное равенство.

Ответ : (x*, y*) = ((1/2, 1/2), (1/2, 1/2)), ν * = 0 .

В последнем примере в силу симметрии матрицы выигрыша игроки находятся в равных условиях. Поэтому следует ожидать равные выигрыши в этой антагонистической игре. Но в такой игре выигрыши отличаются знаком. Поэтому для цены игры может быть только одна возможность - ν * = 0. Такой же результат получен графоаналитическим методом. Имеется

52

симметрия и в оптимальных стратегиях игроков. Проведённое исследование рекомендует следующее поведение в игре Орлянка.

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

– орёл или решка будут видны на столе. Орёл или решка выбираются случайно с равными вероятностями. При таком поведении игроков в достаточно большом числе партий средний выигрыш каждого игрока будет приближаться к нулю.

Задачидлясамостоятельногорешения

Задача 6.1. Найти решение матричной игры, используя графоаналитический метод

Задача 6.2. Первый игрок выбирает одно из двух чисел: 1 или 2. Второй игрок выбирает одно из трёх чисел: 1 или 2 или 3. Если оба числа одинаковой чётности, то первый игрок выигрывает у второго сумму выбранных чисел. Если чётность выбранных чисел не совпадает, то сумму чисел выигрывает второй игрок у первого. Построить соответствующую матричную игру и найти равновесие.

Задача 6.3. Найти решение матричной игры, предварительно

53

§7. Выпуклыемножества

Интуитивное представление о выпуклом множестве формируется в школьном курсе математики. Так многоугольник называется выпуклым, если целиком расположен по одну сторону от прямых, на которых лежат его стороны. Например, на рисунке 7.1а) пятиугольник АВСДЕ – выпуклый, а на рисунке 7.1б) пятиугольник MNPQR – не является выпуклым. Он расположен по обе стороны от прямой PQ.

Определяющим свойством, которое отличает выпуклое множество от невыпуклого, является то, что если взять две любые его точки и соединить их отрезком, то весь отрезок будет принадлежать этому множеству. Согласно этому свойству пятиугольник ABCDE – выпуклый, а MNPQR таковым не является, ибо отрезок XY между двумя его точками не полностью принадлежим многоугольнику.

Определение 7.1. Множество точек называется выпуклым, если вместе с любыми двумя своими точками содержит весь отрезок, соединяющий эти точки.

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

54

Теорема. (о пересечении выпуклых множеств). Пересечение (общая часть) любого числа выпуклых множеств является выпуклым множеством.

Доказательство следует непосредственно из определения пересечения множеств.

Будем рассматривать множества в конечномерном евклидовом пространстве Rn , n ≥1. Среди точек выпуклого

множества можно выделить внутренние, граничные и угловые

точки. Точка множества называется внутренней, если найдётся окрестность этой точки, содержащая только точки этого множества. Под произвольной окрестностью точки в евклидовом пространстве понимают круг (шар) с центром в этой точке и произвольного радиуса.

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

Выделяются ограниченные и неограниченные множества в евклидовом пространстве. Множество в пространстве Rn

называется ограниченным, если найдётся окрестность точки этого множества (достаточно большого радиуса), содержащая всё данное множество. В противном случае множество называется неограниченным.

Определение 7.2. Множество точек евклидового пространства называется компактным, если оно является ограниченным и замкнутым.

Точка множества называется угловой (или крайней), если она не является внутренней ни для какого отрезка, целиком принадлежащего данному множеству. На рисунке 7.1 а) каждая точка ломаной замкнутой линии ABCDE является граничной точкой для пятиугольника. У этого множества имеется ровно пять угловых точек. Их множество U1 = {A, B, C, D, E}. У

55

невыпуклого пятиугольника MNPQR границу составляют точки замкнутой ломаной MNPQR. У этого множества четыре угловых точек U2 = {M, N, Q, R}. Точка P является вершиной пятиугольника, но не является угловой точкой. У круга (шара) соответствующая окружность (сфера) состоит из всех граничных точек этого множества. Здесь каждая точка окружности (сферы) является угловой точкой.

Выпуклые множества и угловые точки рассматриваются в

i=1

Если в (7.2) используется две точки (k = 2), то получается определение отрезка (7.1). С применением выпуклой линейной комбинации точек, можно дать ещё одно, эквивалентное

определение выпуклости. Множество V Rn является выпуклым, если вместе с любой системой из k точек содержит и их выпуклую линейную комбинацию (7.2).

Рассмотрим отрезок (7.1) в векторном пространстве. У него две угловые точки: x1 , x2 Rn . Выпуклая линейная комбинация этих точек образует весь отрезок. Рассмотрим три точки

56