1.2.6. Задача математического программирования

Задача (1.1) называется задачей математического программирования, если ее допустимое множество имеет вид

,

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

f(x)  min,

g_i(x)  0, i = 1, …, k, (1.21)

g_i(x)= 0, i = k+1, …, т, x  P.

При этом условия типа g_i(x)  0 называются ограничениями-нера­венствами, типа g_i(x)= 0 – ограничениями-равенствами, оба этих типа условий — функциональными ограничениями; условие x  P носит название прямого ограничения.

Классическая задача на условный экстремум является частным случаем задачи математического программирова­ния, когда ограничения-неравенства и прямое ограничение отсут­ствуют.

Деление ограничений задачи математического про­граммирования на функциональные и прямые условно. Например, в задаче (1.21) можно исключить ограничения-равенства путем вве­дения их в прямое ограничение, т.е. перейти к задаче вида

f(x)  min,

g_i(x)  0, i = 1, …, k, x  P',

где . Исключение всех функциональных ограничений лишь возвращает нас к задаче вида (1.1). То или иное представление задачи определяется целями исследова­ния. Однако, как правило, чем подробнее описаны функциональные ограничения задачи, тем детальнее удается изучить ее свойства. Обычно в качестве Р берется множество «простой» структуры, напри­мер координатный параллелепипед

,

причем здесь не исключается, что a_j = - или b_j = + (координаты могут уходить в бесконечность) при тех или иных j.

При геометрической интерпретации задач математического про­граммирования используются те же приемы, о которых шла речь выше. В дополнение к этому следует лишь отметить, что при изобра­жении области, определяемой ограничением-неравенством g_i(x)  0, указывается линия уровня g_i(x) = 0 и может ставиться знак «–» с той ее стороны, где g_i(x)  0, и знак «+» - с противоположной.

Пример 1.5. Пусть дана задача

f(x) = x₂  min,

, , .

Ее геометрической интерпретацией служит рис.1.8. Отсюда видно, что решением задачи является «нижняя» точка пересечения окруж­ности g₁(x) = 0 и прямой g₃(x) = 0, т.е. .

1.2.7. Задачи выпуклого программирования

Укажем важный под­класс задач математического программирования. Задача (1.21) назы­вается задачей выпуклого программирования, если множество Р выпукло, функции f, g₁, ..., g_k выпуклы на Р, функции g_k+1, ..., g_m линейны (см. (1.19)).

Легко проверить, что задача из примера 1.5 является задачей выпуклого программирования. Приведем два содержательных при­мера задач этого типа.

Пример 1.6 (задача поиска). Объект, подлежащий обнаруже­нию, находится в одном из п районов с вероятностями р₁, ..., р_п соответственно. Для поиска объекта имеется общий ресурс вре­мени Т. Известно, что при поиске в i-м районе в течение времени t_i, вероятность обнаружения объекта (при условии, что он там нахо­дится) равна , где _i > 0 – заданное число. Требуется так распределить время наблюде­ния по районам, чтобы максимизировать вероятность обнаружения объекта. Соответствующая задача оптимизации имеет вид

,

,

t_i  0, i = 1, …, n.

Нетрудно проверить, что целевая функция задачи вогнута по t = (t₁, …, t_n). Переходя к минимизации этой функции, взятой с обратным знаком, получаем задачу выпуклого программирования.