Постановка задачи нелинейного программирования (ЗНЛП) с ограничениями равенствами



Решается задача f(x)→ min (max) (1)

g1(x)=b1

g2(x)=b2   (2)

………

gm(x)=bm

Которая м.б. записана в виде

f(x)→min (max) (3)

g(x)=b   (4) где g(x) – вектор функция ограничения исходной задачи, компонентами кот являются функции gi(x) (i=1,m) стоящие в левой части системы ограничений (2).

В общем случае f(x) и gi(x) являются нелинейными функциями.

Множество точек х, являющихся решением системы ограничений (2) задают область ограничений ДÎRn задач (1)-(2) и (3)-(4).

Сформулируем теорему, дающую достаточные условия существования решения ЗНЛП общего вида:

f(x)→ min (max) (5),

хÎД с Rn  (6)

Теорема Вейерштрасса:

Пусть область ограничений Д, задачи (5)-(6) является не пустым и компактным множеством, тогда непрерывная целевая функция f(x),заданная на этом множестве, достигает глобального условного экстремума на внутренней или граничной точке множества Д.

Данная теорема справедлива для любых ЗНЛП в том числе и для задач с ограничениями-равенствами.

 

32 Назначение и обоснование метода множителей Лагранжа.

В основе метода лежит тот факт, что в точке условного экстремума х*ÎД градиент целевой функции Ñf(x) д.б. ортогонален касательной гиперплоскости к области ограничений Д, определяемый системой ограничений g1(x)=b1 или g(x)=b   

                                    g2(x)=b2 

                                     ………

                                    gm(x)=bm

Это означает, что должны существовать такие числа l1,l2,…lm для кот справедливо:

Ñf(x*) = åj=1nlj * Ñgj(x*)

Т.е. градиент Ñf(x*) представим в виде линейной комбинации градиента функции ограничений, кот в свою очередь ортогональны множествам уравнений mj = {gi(x) = bj} (j=1, m)ф-ии ограничений gi(x)

 

33 Схема реализации метода множителей Лагранжа

Метод реализуется за 3 шага:

Шаг1. Рассматривается ф-ия Лагранжа

L(x,λ) = f(x) + λT(b – g(x)) = f(x) + åi=1n lj (bi – gi(x))

Где xT = (x1, x2, …, xn) – вектор инструментальных переменных множителей Лагранжа,

λT = (λ1, λ2, … , λm) – вектор множителей Лагранжа.

 

Шаг2. Определяются стационарные точки (х*, λ*) функции множителей Лагранжа. Для этого решается система уравнений, представляющая собой необходимые условия существования стационарной точки (все частные производные по аргументам функции Лагранжа равны 0)

∂L(x,λ) / ∂xj = (∂f(x) / ∂xj) - åi=1m λi * (∂gi(x) / ∂ xj) = 0, j = 1, m

∂L / ∂ λi = bi - gi(x) = 0,  i = 1, m

Эта система м.б. представлена в матричной форме:

Ñfх(x) - λT Rg(x) = 0

b – g(x) = 0

где Rg(x) – матрица Якоби вектор-функции g(x)

 

Шаг3. Определяется тип условного экстремума функции f(x) в найденных стационарных для функции Лагранжа точках. Для этого в рассмотрении вводится так называемая окаймленная матрица Гессе QB(x*, y*), имеющая блочную структуру:

QB(x*, y*) = 0mxm     Rg(x*)

              RgT(x*) H(x*, λ*)

Где 0mxm - нулевая матрица размера m на m (где m – число ограничений в задачах f(x)→ min (max)

g1(x)=b1

………

gm(x)=bm

Rg(x*) – матрица Якоби

H(x*, λ*) = (hij)mxn, где hij = ∂2L(x*, λ*) / ∂xi ∂xj – это матрица, эл-ты кот есть частные производные 2ого порядка функции Лагранжа по инструментальным переменным.

Тип экстремума следует из достаточных условий: точка х* есть точка max функции f(x), если начиная с порядка 2m+1 главный и все последующие угловые миноры окаймленной матрицы Гессе образуют знакопеременный числовой ряд, причем знак первого члена этого ряда, т.е. главного минора М2m+1 порядка 2m+1, равен совпадает со знаком (-1)m+1. Точка х* является точкой min функции f(x), если все главные миноры окаймленной матрицы Гессе, начиная с минора порядка 2m+1 имеют одинаковые знаки, определяемые знаком (-1)m.

!!! Каждая стационарная точка обрабатывается отдельно.

 

Интерпретация множителей Лагранжа. Теорема Лагранжа.

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

 Множители Лагранжа измеряют чувствительность оптимального значения f*=f(х*) целевой функции, к изменениям const-компонент в правой части ограничений.Что следуетет из теоремы.

Теорема Лагранжа

Пусть х* - решение задачи f(x)→ min (max)

g1(x)=b1

………

gm(x)=bm

а строки матрицы Якоби в точке х*(Rg(x*)) линейно независимы. Тогда существует единственный вектор множителей Лагранжа λ = (λ1*, λ2*, … , λm*) удовлетворяющий вместе с х* системе условий Ñfх(x) - λT Rg(x) = 0

b – g(x) = 0

и при этом справедливы соотношения:

λi* = ∂f* /∂bi i = 1, m

Во многих экон-их задачах целевая функция имеет размерность стоимости (т.е. цены, умноженной на объем продукции). С помощью ограничений вида g(x)=b устанавливаются определенные величины для затрат ресурсов. Поскольку в таких задачах с помощью множителей Лагранжа измеряют, по сути, чувствительность величины f*=f(х*), имеющей размерность стоимости, к изменениям некот кол-ва затраченного ресурса, то эти множители в этом случае имеют размерность цены. По этой причине множители Лагранжа часто называют теневыми ценами (данного вида ресурсов)

35 Метод подстановки в решении ЗНЛП с ограничениями-равенствами

Метод применяется для решения задач вида:

f(x)®max(min) (1)

xi=ji(xm+1,xm+2,…xn), i=1,m (2)

Для решения задачи (1)-(2) производится подстановка выражений (2) в целевую функцию, после чего возникает задача без ограничений.

f(x)=f(j1(xm+1,…xn), j2(xm+1,…xn),… jm(xm+1,…xn) xm+1,xm+2,…xn)=ψ(xm+1…xn)®max(min) (3)

В итоге задача поиска экстремума функции f(x) с ограничениями свелась к задаче поиска экстремума функции без ограничений. Эту задачу можно решить классическим методом и получить x*m+1, x*m+2, …, x*n

Подстановка этих значений в (2) даёт искомое значение для x1*, x2*, … , xm*


Дата добавления: 2018-02-15; просмотров: 518; Мы поможем в написании вашей работы!

Поделиться с друзьями:






Мы поможем в написании ваших работ!