Задачи с ограничениями-неравенствами

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

Условия Куна-Таккера

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

(1)

где - дважды непрерывно дифференцируемые функции векторного аргумента .

Заметим, что представление задач нелинейного программирования в виде (1) не умаляет общности дальнейших рассуждений. Действительно, максимизация тождественна минимизации . Знак неравенства также совершенно условен, поскольку умножением обеих частей неравенства на его можно развернуть в противоположную сторону. Если случится ограничение-уравнение, то его можно записать в виде двух неравенств, поскольку

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

Задачи с неотрицательными переменными. Для начала рассмотрим задачу нелинейного программирования, в которой ограничения сводятся лишь к требованию неотрицательности переменных:

(2)

Теорема 1. Если - решение задачи (2), то для всех

, если , (3)

, если . (4)

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

Теорема доказана.

Нетрудно видеть, что условия (3) и (4) можно записать в следующей форме:

(5)

где .

Замечание 1. Условия (5) дают признак максимума. В случае минимума, необходимо, чтобы выполнялось условие .

Достаточность проверяется так же, как в задачах безусловной оптимизации, т.е. по критерию Сильвестра. Но учитывать при этом следует лишь те переменные, производные которых в исследуемой точке равны нулю.

Пример 1. Покажем, что - решение задачи

Во-первых, как видим, . Во-вторых, градиент также неотрицателен:

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

Условия Куна-Таккера. Вернемся к задаче (1) и рассмотрим ее, используя результаты, полученные для задачи (2).

Теорема 2. Если есть решение задачи (1), то найдутся множители , такие что для

, если , (6)

, если , (7)

и для

, если , (8)

, если . (9)

Доказательство. Преобразуем ограничения-неравенства в уравнения. Для этого введем в задачу дополнительные неотрицательные переменные . Очевидно, для всех

Далее, используя функцию Лагранжа, сводим задачу (1) к виду (2):

Записывая для этой задачи условия (5) с учетом того, что , получаем так называемые условия Куна-Таккера:

(10)

где

Нетрудно видеть, что (10) есть не что иное, как компактная форма записи условий (6) - (9).

Теорема доказана.

Пример 2. Рассмотрим задачу

Исследуем целевую функцию, вычислив для нее градиент и матрицу Гессе.

; ;

Как видим, матрица Гессе отрицательно определена при любом , значит, целевая функция выпукла вверх. Аналогично можно показать выпуклость допустимого множества. Таким образом, задача в целом выпукла и, следовательно, имеет единственное решение в точке, удовлетворяющей условиям Куна-Таккера.

Функция Лагранжа:

Условия Куна-Таккера:

=+,

Эти условия годятся лишь для того, чтобы проверить экстремальность предлагаемых точек, но не для того, чтобы построить алгоритм их поиска. Поэтому для примера рассмотрим две точки: и . Подстановкой можно убедиться, что обе они удовлетворяют системе ограничений. Одна из них является решением задачи. Определим, какая именно.