Если функция f(x) достаточно гладкая, то условия выпуклости (вогнутости) можно выразить через ее вторую производную.
Действительно, согласно теореме Лагранжа в некоторой точке Е (рис. 11.5) касательная к графику функции АВ лежит ниже этого графика. Уравнение этой касательной Y = f() + f\'’()(x-), следовательно, f(x)- f() – f’()(x-) 0, откуда в силу формулы Тейлора

где 0<<1.
Деля последнее неравенство на (х-)2 и далее переходя к пределу при х → , получаем, что
f”() 0.



(11.10)
В силу произвольности точки  это неравенство справедливо на всем отрезке [у, z] и является условием выпуклости (в случае вогнутости справедливо обратное неравенство). Для иллюстрации рассмотрим два простых примера.
Пример 1. f(x) =ex, x (-,+), f(“) = eх > 0, следовательно, показательная функция выпукла на всей оси.
Пример 2. f(x) = sin x, x[0,2], f”(x) = - sin x, следовательно, функция sin x вогнута на отрезке [0, π] и выпукла на отрезке [π, 2 π].
Прежде чем сформулировать задачу поиска, отметим, что оптимизационная задача
f(x) → min, х  Р (f(x) → max, х  Р),



(11.11)
где в случае max целевая функция f (х) выпукла, в случае min – вогнута и Р – полиэдр, называется задачей выпуклого программирования. Ясно, что задача линейного программирования является ее частным случаем.
Задача поиска. Объект, подлежащий обнаружению, находится в одном из п районов с вероятностями р1,..., рп соответственно. Для поиска объекта имеется общий ресурс времени Т (т. е. при t>T поиск считается нецелесообразным). Известно, что при поиске в i-м районе в течение времени ti, вероятность обнаружения объекта (при условии, что он там находится) выражается через функцию Бернулли 1- , где i>0 – заданное число (формула показывает, что за бесконечное время ti объект был бы найден). Требуется распределить по районам время наблюдения (поиска) так, чтобы максимизировать вероятность обнаружения объекта. Соответствующая задача оптимизации имеет вид




(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.