Постановка задачи нелинейного программирования (ЗНЛП) с ограничениями равенствами
Решается задача 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; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!