Экология и безопасность жизнедеятельности (стр. 36 )

(11.12)

(11.13)

(11.14)

Из теории вероятностей хорошо известно, что

(11.15)

Кроме того, очевидно, что задача g(x)→max эквивалентна задаче (-g(x))→ min; также очевидно, что условия (11.13) и (11.14) определяют определенный полиэдр Р (рис. 11.6). Следовательно, вводя целевую функцию получаем следующую оптимизационную задачу:

, (11.16)

где Р– полиэдр, заданный неравенствами (11.13) и (11.14).

Так как причем , то функция f(t) выпуклая и мы имеем задачу выпуклого программирования. Общие методы решения таких задач довольно сложны, однако в нашем конкретном случае можно предложить наглядное геометрическое решение.

Действительно, имеем <0. Значит, функция f(t) убывает по любому переменному ti, i = 1, 2,...,n,

и ее наименьшее значение достигается на гиперплоскости t1 + t2 +…+ tn = T (в случае двух переменных это прямая АВ на рис. 11.6). Однако в отличие от задач линейного программирования это наименьшее значение достигается необязательно в вершинах А, В и т. д., в чем можно убедиться, исследуя на АВ функцию f(t) в случае двух переменных. Тогда f(t1,t2)= Минимум этой функции может достигаться и внутри отрезка [0, T] в зависимости от соотношения параметров р1, р2, α1, α2, в чем можно убедиться непосредственным исследованием функции одного переменного (например, если то минимум достигается в середине Е отрезка АВ).

11.3. Игровые модели

Часто возникают ситуации, в которых различные участники имеют не совпадающие между собой интересы. Математические модели и методы для исследования таких так называемых конфликтных ситуаций получили название теории игр [18].

Приведем простейшие понятия и результаты этой теории. Под словом «игра» понимается совокупность правил, руководствуясь которыми игроки-участники принимают решения. Предположим, что результатом игры является плата, которую в соответствии с правилами проигравший участник платит выигравшим. Для простоты ограничимся сначала так называемыми «играми двух лиц с нулевой суммой». Для того чтобы полностью определить такую игру, нужно задать таблицу платежей – платежную матрицу, например, следующую матрицу размера 3х4:

Эта запись означает, что игрок А выбирает одну из строк этой матрицы, а игрок В, не зная выбора А, выбирает один из столбцов матрицы. Число на пересечении выбранных строки и столбца определяет выигрыш первого игрока (соответственно проигрыш второго). Например, если А выбрал вторую строку, а В – третий столбец, то А выиграл 5 единиц, а В их проиграл. Если же А выбрал третью строку, а В – второй столбец, то А проиграл 2 единицы, а В их выиграл.

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

Прежде чем сформулировать ответ, вернемся к рассматриваемой матрице. Сразу видно, что игроку А выгоднее всего выбрать первую строку, так как все ее элементы больше соответствующих элементов остальных строк. Точно так же игроку В выгоднее всего выбрать второй столбец, так как все элементы этого столбца меньше соответствующих элементов остальных столбцов. Следовательно, в данном примере оптимальными стратегиями будут следующие: для А – выбор первой строки, а для В – выбор второго столбца. Число 4, стоящее на пресечении первой строки и второго столбца, носит название цены игры, т. е. платы, которую получает оптимально играющий игрок. Таким образом, в этом примере гарантированный выигрыш А – не менее 4-х единиц и гарантированный проигрыш В – не более 4-х единиц (он равен 4 единицам, если оба игрока играют оптимально).

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

Однако далеко не каждая матрица имеет седловую точку, например, матрица седловой точки не имеет. Говорить здесь о максимизации наименьшего возможного выигрыша (минимизации наибольшего возможного проигрыша) возможно только при использовании так называемой смешанной стратегии при многократной игре с одной и той же платежной матрицей. Суть этой стратегии заключается в выборе разных стратегий с определенными частотами. Итак, пусть А выбирает первую строку с частотой х, а вторую – с частотой (1 – х). Аналогично для В соответствующие частоты обозначим через у и (1 –у). Тогда средний выигрыш А, обозначаемый через Е (х, у), равен

Е(х, у)=4(1-х)у+х(1-у)=х+4у-5ху. (11.17)

Нас интересует величина max min E(x,y). Имеем

x y

Еу=4-5х, (11.18)

откуда Еу>0 при , Ey=0 при х= и Еу<0 при . Значит,

(график на рис. 11.7). Следовательно,

(11.19)

и оптимальной смешанной стратегией для А будет выбор первой строки с частотой и второй строки – с частотой . Средний проигрыш В, обозначаемый F(x,y), очевидно равен –Е (х, у). Нас интересует величина где

F(x,y)=5xy-x-4y. (11.20)

Имеем Fx=5y-1, откуда Fx< 0 при , Fx = 0 при y = и Fx>0 при < у ≤ 1. Значит,

(график на рис. 11.8). Следовательно,

(11.21)

и оптимальной стратегией для А будет выбор первого столбца с частотой и второго столбца – с частотой .

При оптимальных смешанных стратегиях выигрыш А и соответственно проигрыш В в пять раз меньше максимально возможного при одиночной игре.

Отметим также, что в рассмотренном примере мы показали существование оптимальных стратегий и установили равенство

; (11.22)

при этом величину Е(х, у) можно трактовать как математическое ожидание выигрыша, а величину v = определить как цену игры.

Рассмотрим теперь общий случай прямоугольной матрицы

.

При любой допустимой стратегии игрока A: x1 ≥ 0, ...,хm ≥ 0, x1 +x2+…+xm=1 и любой допустимой стратегии игрока В: y1 ≥ 0, ...,ym ≥ 0, y1 +y2+…+ym=1 математическое ожидание выигрыша равно

(11.23)

Множество допустимых стратегий x = (x1,…,xn) игрока А обозначим через X, а множество допустимых стратегий у=(у1,...,yn) игрока В обозначим через Y.

Рассмотренные выше примеры являются частными случаями общих теорем [18] для игр с прямоугольными матрицами (прямоугольными играми); из них, в частности, вытекает:

1. Величины существуют и равны между собой; при этом величина

(11.24)

является ценой игры.

2. Всякая прямоугольная игра имеет цену; каждый игрок в прямоугольной игре всегда имеет оптимальную стратегию.

3. Пусть Е – математическое ожидание выигрыша в прямоугольной игре с матрицей С, имеющей цену v. Тогда для того, чтобы элемент х* =(х1*,...,х*m)Î Х был оптимальной стратегией для игрока А, необходимо и достаточно, чтобы для всякого j =1, 2,...,n базисного вектора y(j) = имело место неравенство