Общий случай задачи нелинейного программирования

В самом общем виде задача нелинейного программирования имеет следующий вид: найти X'' -(х{', х2,...,х„), для которого

при условиях

Отметим, что отличие данной задачи от классической задачи оптимизации (13.5), (13.6) состоит в том, что здесь имеются ограничения в форме неравенств. Этот, казалось бы, незначительный факт, приводит к столь принципиальным трудностям, что для задачи нелинейного программирования решение в общем случае не найдено. Аналитические методы ее решения разработаны лишь для некоторых частных случаев, например когда и целевая функция, и все функции ограничений являются выпуклыми функциями [1].

Необходимые условия решения задачи нелинейного программирования. Рассмотрим вначале так называемую простейшую задачу нелинейного программирования: найти вектор Хк, такой что выполнено соотношение (13.12), при условиях

и (13.14).

Построим для заданной целевой функции функцию Лагранжа

(13.7). В этом случае исходная задача примет вид

при условиях (13.14).

Очевидно, что в точке оптимального решения задачи X* выполняется соотношение

Это обстоятельство позволяет в окрестности точки Хк вместо функции Лагранжа исследовать целевую функцию W(X), при этом точка оптимального решения задачи (13.15), (13.14) может находиться как внутри области допустимых решений (X > 0), так и на ее границе.

Проанализируем эти два случая.

1. X* — внутренняя точка допустимой области, т.е. Vx^ > 0. Поскольку в X функция L(X, А) имеет минимум, то все ее частные производные равны нулю:

2. X” — граничная точка допустимой области, т.е. Vx, = 0. В этом случае отклонения от оптимальной точки могут приводить только к возрастанию целевой функции (напомним, что в точке X' находится минимум). Следовательно, в таких точках

Обобщая, можно записать необходимые условия решения задачи (13.15), (13.14) в точке X так:

Теперь определим необходимые условия, которые выполняются в точках решения общей задачи нелинейного программирования. Преобразуем исходную общую задачу нелинейного программирования (13.12)—(13.14) с ограничениями-неравенствами в задачу с ограничениями-равенствами путем добавления неотрицательных переменных zf:

Здесь следует отметить, что дополнительные неизвестные z, больше нуля в ограничениях-неравенствах, а в равенствах они равны нулю, т.е.

Теперь общая задача нелинейного программирования сведена к простейшей задаче (13.17) типа (13.12), (13.130, (13.14). Следовательно, можно повторить соответствующие рассуждения о формулировании необходимых условий решения. Функция Лагранжа уже для задачи (13.17) имеет вид

Для переменных z, должны выполняться такие же условия, что и для х,. Поэтому

Из условий (13.18) следует, что в функцию Лагранжа L(X, Z, А) неизвестный вектор Z входить не будет. Данный факт следует из того, что ограничения типа неравенств (только для них z, > 0) в нее не войдут, поскольку им соответствует = 0.

Обобщая вышеизложенное, получаем условия, которым должна удовлетворять точка X* — решение общей задачи нелинейного программирования:

Эти необходимые условия решения общей задачи нелинейного программирования получили названия условия КунаТаккера. Достаточных условий для общей задачи нелинейной оптимизации не получено.

Численное решение задачи нелинейного программирования. На практике задачи нелинейной оптимизации обычно решаются численными (приближенными) методами. Одним из наиболее эффективных является метод штрафных функций. Идея этого метода заключается в переходе от исходной задачи нелинейного программирования к задаче на безусловный экстремум с целевой функцией специального вида

Эта функция строится так, что в области допустимых решений (ОДР) она совпадает с целевой функцией исходной задачи, а при нарушении границ ОДР за счет включения ненулевого значения функции штрафа Н{Х) столь резко меняет свое значение, что на следующем шаге решение вновь оказывается в допустимой области.

Рассмотрим метод штрафных функций несколько подробнее. Пусть задана задача (13.12), (13.13'), (13.14). Построим соответствующую задачу на безусловный экстремум:

где Н(Х) — положительная функция штрафа, строящаяся по схеме причем

Число а должно быть столь велико, чтобы при нарушении границы ОДР оказывать воздействие, достаточное для возвращения в допустимую область. Формально это обстоятельство можно описать условием

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

Для того чтобы начать решение задачи методом штрафных функций, необходимо задать начальное значение искомой точки экстремумах0, а также величин h, е и а„ затем по формуле (13.19) построить ряд уточняющих значений X1, X2,..., Хк+1. Величина X* считается решением задачи, когда выполнится условие достижения заданного порога точности, например такое:

Примечание 13.1. Изложенный метод дает, вообще говоря, возможность поиска лишь локального экстремума, ближайшего к исходной точке. Для выпуклых функций полученное приближение будет близко к глобальному экстремуму.

Примечание 13.2. Если в исходной задаче требуется найти минимум, то при формировании функции F(X) функция штрафа Н(Х) прибавляется, т.е.

Рассмотрим пример.

Пример 13.5

Максимизировать целевую функцию при условиях

Решение. Зададимся величинами= (0, 0), И = 0,2 и Va,= 2. Затем вычислим производные:

Теперь запишем формулу (13.19) для каждой из координат:

Для первого шага координаты X1 вычисляются так:

Следовательно, X1 = (0,2, 0,4), ИДХ1) = 0,88, ограничения задачи выполняются, поэтому о.] (X1) = а21) = 0.

Результаты второго шага:

Отсюда X2 = (0,32, 0,72), ИДХ2) = 1,40. На этом шаге и далее до пятого шага найденные координаты находятся в ОДР, поэтому значения штрафной функции равны нулю. Итак, по аналогии с предыдущими двумя шагами, имеем X? = (0,4, 1,0), ИДХ3) = 1,74 и X4 = = (0,44, 1,2).

После четвертого шага впервые одно из ограничений (второе) не выполняется, поэтому на пятом шаге следует положить а, (X4) = 0 и а24) =2.

Результаты пятого шага:

Полученные решения вновь допустимы. Продолжая данный алгоритм, после десятого шага получаем решение X10 = (0,37, 1,07) и ЩХ10) = 1,8. Описанный процесс может продолжаться до достижения заданной точности.

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

Для решения задач нелинейного программирования с успехом могут применяться методы случайного поиска, построенные по схеме, аналогичной описанной выше. Отличие состоит лишь в том, что на каждом шаге проверяется допустимость в смысле выполнимости условий (13.13'), (13.14).

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >