Читать реферат по информатике, вычислительной технике, телекоммуникациям: "Нелинейное программирование" Страница 2

(Назад) (Cкачать работу)

min

Метод исключения переменных применим лишь в тех случаях, когда уравнения, представляющие ограничения, можно разрешить относительно некоторого конкретного набора независимых пере­менных. При наличии большого числа ограничений в виде равенств, процесс исключения переменных становится весьма трудоемкой процедурой. Кроме того, возможны ситуации, когда уравнение не удается разрешить относительно переменной. В частности, если в примере 1 ограничениезадать в виде

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

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

Рассмотрим задачу минимизации функции n переменных с уче­том одного ограничения в виде равенства:

Минимизировать(3)

при ограничениях(4)

В соответствии с методом множителей Лагранжа эта задача преобразуется в следующую задачу безусловной оптимизации:

минимизировать L(x,u)=f(x)-u*h(x)(5)

Функция L(х;u) называется функцией Лагранжа, u — неизвест­ная постоянная, которая носит название множителя Лагранжа. На знак u никаких требований не накладывается.

Пусть при заданном значении u=u0 безусловный минимум функ­ции L(x,u) по х достигается в точкеиудовлетворяет урав­нению . Тогда, как нетрудно видеть, x0 минимизирует (1) с учетом (4), поскольку для всех значений х, удовлетворяющих (4),и L(x,u)=min f(x).

Разумеется, необходимо подобрать значение u=u° таким обра­зом, чтобы координата точки безусловного минимума х° удовлетво­ряла равенству (4). Это можно сделать, если, рассматривая u как переменную, найти безусловный минимум функции (5) в виде функции u, а затем выбрать значение u, при котором выполняется равенство (4). Проиллюстрируем это на конкретном примере.

Пример 2

Минимизировать

при ограничении=0

Соответствующая задача безусловной оптимизации записывается в следующем виде:

минимизироватьL(x,u)= -u

Решение. Приравняв две компоненты градиента L к нулю, получим

Для того чтобы проверить, соответствует ли стационарная точка х° минимуму, вычислим элементы матрицы Гессе функции L(х;u), рассматриваемой как функция х,

,

которая оказывается положительно определенной. Это означает, что L(х,,u) — выпуклая функция х. Следовательно, координаты, определяют точку глобального минимума. Оптималь­ное значение u находится путем подстановки значенийив урав­нение =2, откуда 2u+u/2=2 или . Таким образом, условный минимум достигается приии равен min f(x)=4/5.

При решении задачи из примера 2 мы рассматривали L(х;u) как функцию двух переменныхии, кроме того, предполагали, что значение параметра u выбрано так, чтобы выполнялось ограни­чение. Если же решение системы

,j=1,2,3,…,n

в виде явных функций u получить нельзя, то значения х и

Похожие работы