14. Постановка задачи нелинейного программирования. Классические методы ее решения для системы ограничений в виде равенств.

В задаче нелинейного программирования (НЛП) требуется найти значение многомерной переменной x=(x1,x2,…xn), минимизирующее целевую функцию f(x) при условиях, когда на переменную х наложены ограничения типа неравенств: hi(x)<=0, i-1,2,…m (1), а переменные xi, т.е. компоненты вектора х, неотрицательны: xi>=0.

Иногда в формулировке задачи ограничения (1) имеют противоположные знаки неравенств. Учитывая, однако, что если  hi(x)>=0, то -hi(x)<=0, всегда можно свести задачу к неравенствам одного знака. Если некоторые ограничения входят в задачу со знаком равенства, например Ф(х)=0, то их можно представить в виде пары неравенств Ф(х)<=0, -Ф(х)<=0, сохранив тем самым типовую формулировку задачи.

 

Задача оптимизации, содержащую несколь­ко ограничений в виде равенств:

Минимизировать F(x1,x2,…,xn) при ограничениях hk(x1,x2,…,xn)=0, k=1,…,n.

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

 

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

Минимизировать F(x1,x2,…,xn) (3) при ограничениях h1(x1,x2,…,xn)=0 (4).

В соответствии с методом множителей Лагранжа эта задача преобразуется в следующую задачу безусловной оптимизации: минимизировать  L(x,u)=f(x)-u*h(x) (5).

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

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

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