Ограничения вида неравенств

(3.3)
Задача выпуклого программирования в случае ограничений в виде равенств имеет вид

Z = f (x1 ,x2 ,…, xn ) max,

(3.4)
Ограничения вида неравенств - student2.ru 1(x1 ,x2 ,…, xn ) = Ограничения вида неравенств - student2.ru 1,

Ограничения вида неравенств - student2.ru 2(x1 ,x2 ,…, xn ) = Ограничения вида неравенств - student2.ru 2,

- - - - - - - - - - - - - - -

Ограничения вида неравенств - student2.ru m(x1 ,x2 ,…, xn ) = Ограничения вида неравенств - student2.ru m,

Для ее решения будем использовать метод множителей Лагранжа. Пусть λ1, λ2,…, λm - некоторые числа. Составим функцию Лагранжа Ограничения вида неравенств - student2.ru :

Ограничения вида неравенств - student2.ru (x1 ,x2 ,…, xn, λ1, λ2,…, λm ) = f (x1 ,x2 ,…, xn ) + Ограничения вида неравенств - student2.ru i [b1 - Ограничения вида неравенств - student2.ru 1(x1 ,x2 ,…, xn )].

Задача на нахождение условного экстремума функции f сводится к задаче нахождения безусловного экстремума функции Лагранжа Ограничения вида неравенств - student2.ru .

Необходимым условием экстремума функции Лагранжа является равенство нулю ее частных производных:

Ограничения вида неравенств - student2.ru = Ограничения вида неравенств - student2.ru - Ограничения вида неравенств - student2.ru i Ограничения вида неравенств - student2.ru = 0,

(3.5)

Ограничения вида неравенств - student2.ru = Ограничения вида неравенств - student2.ru - Ограничения вида неравенств - student2.ru i Ограничения вида неравенств - student2.ru = 0,

- - - - - - - - - - - - - - - - - - - - - - - - -

Ограничения вида неравенств - student2.ru = Ограничения вида неравенств - student2.ru - Ограничения вида неравенств - student2.ru i Ограничения вида неравенств - student2.ru = 0,

Ограничения вида неравенств - student2.ru = b1 - Ограничения вида неравенств - student2.ru 1(x1 ,x2 ,…, xn ) = 0,

Ограничения вида неравенств - student2.ru = b2 - Ограничения вида неравенств - student2.ru 2(x1 ,x2 ,…, xn ) = 0,

- - - - - - - - - - - - - - - - - - - - - - - - - - -- - - - - - -

Ограничения вида неравенств - student2.ru = bm - Ограничения вида неравенств - student2.ru m(x1 ,x2 ,…, xn ) =0.

Получили систему n + m уравнений с n + m неизвестными x1 ,x2 ,…, xn ; λ1, λ2,…, λm. Для выпуклых (вогнутых) функций решение системы уравнений единственное (если конечно, оно вообще существует). Пусть решением системы является следующая совокупность значений переменных: xo 1, xo2,…, xon ; λo1, λo2,…, λom. Это решение, дающее экстремум функции Лагранжа, состоит из двух частей:

оптимальное решение задачи xo=(xo 1,xo2,…, xon) и оптимальный вектор множителей Лагранжа λo=(λo1, λo2,…, λom).

Вообще-то нам необходимо было найти оптимальное решение задачи (3.3), (3.4), то ест решение xo. Но, как увидим далее, значения множителей Лагранжа, соответствующие оптимальному плану xo, не являются излишними. Напротив, с их помощью можно получить дополнительную ценную информацию об оптимальном xo. Остановимся на значении множителей Лагранжа в плановой практике.

Пусть условия (3.3), (3.4) отражают следующую задачу производства x1 ,x2 ,…, xn для некоторого предприятия, который обеспечивал бы ему максимум прибыли f (x1 ,x2 ,…, xn )

и соответствовал бы балансу потребности и лимита по всем видам производственных ресурсов. Если потребность в ресурсе на предприятии составляет Ограничения вида неравенств - student2.ru i(x1 ,x2 ,…, xn ) единиц, лимит этого ресурса составляет bi единиц, то можно утверждать, что план производства должен удовлетворять равенствам

Ограничения вида неравенств - student2.ru i (x1 ,x2 ,…, xn ) = bi , i=1,2,…,m.

Очевидно, что оптимальное решение задачи (3.3) и (3.4) зависит от правых частей ограничений (3.4). Это значит, что компоненты оптимального плана xo 1,xo2,…, xon зависят от лимитов ресурсов b1, b2,…, bm. Понятно, что и оптимальное значение целевой функции

Zo= f (xo1,xo2,…, xon) также будет зависеть от b1, b2,…, bm. Найдем числовое выражение зависимости оптимального значения целевой функции Z от лимитов ресурсов b1, b2,…, bm.

Для измерения чувствительности оптимального значения целевой функции Zo от изменения лимитов ресурсов bi воспользуемся частной производной Ограничения вида неравенств - student2.ru .

Докажем, что Ограничения вида неравенств - student2.ru = λoi , i=1,2,…,m.

Компоненты оптимального плана xoj есть некоторые функции от bi , i=1,2,…,m:

xoj = xoj (b1, b2,…, bm) , j=1,2,…,n.

Поэтому Zo есть сложная функция вида

Zo= Zo(b1, b2,…, bm)= Zo[xo1(b1, b2,…, bm),…, xon(b1, b2,…, bm)].

Используя правило дифференцирования сложной функции, получим

(3.6)
Ограничения вида неравенств - student2.ru = Ограничения вида неравенств - student2.ruОграничения вида неравенств - student2.ru .

Продифференцируем левую и правую части равенства fk (xo1,xo2,…, xon)=bk по bi, получим

(3.7)
Ограничения вида неравенств - student2.ru = Ограничения вида неравенств - student2.ruОграничения вида неравенств - student2.ru = Ограничения вида неравенств - student2.ru = 1, 2, если k = i если k ≠ i.

Умножим на λok и просуммируем по k, получим

λoi - Ограничения вида неравенств - student2.ru ok Ограничения вида неравенств - student2.ruОграничения вида неравенств - student2.ru = Ограничения вида неравенств - student2.ru ok Ограничения вида неравенств - student2.ru .

Отсюда имеем

(3.8)
λoi - Ограничения вида неравенств - student2.ru ok Ограничения вида неравенств - student2.ruОграничения вида неравенств - student2.ru = 0.

Сложив(3.6) и (3.8), получим

(3.9)
Ограничения вида неравенств - student2.ru = λoi + Ограничения вида неравенств - student2.ruОграничения вида неравенств - student2.ru - Ограничения вида неравенств - student2.ru ok Ограничения вида неравенств - student2.ruОграничения вида неравенств - student2.ru .

Два последних слагаемых в первой части (3.9) вместе равны нулю. Покажем это:

Ограничения вида неравенств - student2.ruОграничения вида неравенств - student2.ru - Ограничения вида неравенств - student2.ru ok Ограничения вида неравенств - student2.ruОграничения вида неравенств - student2.ru = Ограничения вида неравенств - student2.ruОграничения вида неравенств - student2.ru - Ограничения вида неравенств - student2.ruОграничения вида неравенств - student2.ru ok Ограничения вида неравенств - student2.ru =

= Ограничения вида неравенств - student2.ru ( Ограничения вида неравенств - student2.ru - Ограничения вида неравенств - student2.ru ok Ограничения вида неравенств - student2.ru ).

Но согласно необходимому условию экстремума функции Лагранжа

(3.10)
Ограничения вида неравенств - student2.ru - Ограничения вида неравенств - student2.ru ok Ограничения вида неравенств - student2.ru = 0,

(3.11)
поэтому два последних слагаемых в правой части равенства (3.9) в сумме дают ноль. Отсюда следует равенство Ограничения вида неравенств - student2.ru = λoi , i=1,2,…,m.

Таким образом, метод множителей Лагранжа, помимо того, что дает решение задачи ВП с ограничениями в виде равенств, позволяет также проанализировать, насколько оптимальное значение целевой функции чувствительно к изменениям констант ограничений. Например, если какой-то множитель Лагранжа равен нулю, то небольшие изменения соответствующей константы ограничений не окажут никакого влияния на оптимальное значение целевой функции. Если некоторая константа bi увеличится на одну единицу, то при λoi >0 множитель Лагранжа λoi показывает, что оптимальное значение целевой функции Zo увеличится на λoi единицу (в задаче на максимум). Обратим внимание на то, что при этом нет необходимости решать новую задачу ВП, у которой правая часть ограничения i равна bi + 1.

В целом можно сделать вывод, что практическое значение равенства (3.11) в том, что мы легко можем оценить, как изменится оптимальное значение целевой функции при малом изменении лимитов ресурсов. По-другому говоря, множители Лагранжа λoi являются оценками ресурсов b1, b2,…, bm.

Рассмотрим теперь способ решения задачи выпуклого программирования в случае ограничений неотрицательности и ограничений в виде равенств .

(3.12)
Задача имеет вид

Z = f (x1 ,x2 ,…, xn ) max,

(3.13)
Ограничения вида неравенств - student2.ru 1(x1 ,x2 ,…, xn ) = Ограничения вида неравенств - student2.ru 1,

Ограничения вида неравенств - student2.ru 2(x1 ,x2 ,…, xn ) = Ограничения вида неравенств - student2.ru 2,

- - - - - - - - - - - - - - -

(3.14)
Ограничения вида неравенств - student2.ru m(x1 ,x2 ,…, xn ) = Ограничения вида неравенств - student2.ru m,

xj ≥ 0, j=1,2,…,n.

Вновь для решения задачи применим метод множителей Лагранжа.

Составим функцию Лагранжа

Ограничения вида неравенств - student2.ru (x1 ,x2 ,…, xn, λ1, λ2,…, λm ) = f (x1 ,x2 ,…, xn ) + Ограничения вида неравенств - student2.ru 1 [b1 - Ограничения вида неравенств - student2.ru 1(x1 ,x2 ,…, xn )].

(3.15)
Нахождение экстремума функции (3.12) при условии (3.13) и (3.14) сводится к нахождению экстремума функции Лагранжа при ограничениях неотрицательности, то есть к решению задачи ВП при ограничениях неотрицательности. Такие задачи мы уже рассматривали. Необходимое условие экстремума функции Ограничения вида неравенств - student2.ru будет записываться так:

(3.16)
xj Ограничения вида неравенств - student2.ru = 0, j=1,2,…,n,

λi Ограничения вида неравенств - student2.ru =0, i=1,2,…,m.

Запишем условие (3.15) в развернутом виде (случай задачи на максимум):

(3.17)
если xj Ограничения вида неравенств - student2.ru 0, то Ограничения вида неравенств - student2.ru = 0; если xj Ограничения вида неравенств - student2.ru 0,то Ограничения вида неравенств - student2.ru ≤ 0;

или, если xj Ограничения вида неравенств - student2.ru 0, то Ограничения вида неравенств - student2.ru - Ограничения вида неравенств - student2.ru i Ограничения вида неравенств - student2.ru = 0; если xj Ограничения вида неравенств - student2.ru 0, то Ограничения вида неравенств - student2.ru - Ограничения вида неравенств - student2.ru i Ограничения вида неравенств - student2.ru ≤ 0.

Что касается условия (3.16), то относительно λi оно является тождеством. Действительно

λi Ограничения вида неравенств - student2.ru = λi ( bi - Ограничения вида неравенств - student2.ru i(x1 ,x2 ,…, xn )) = 0.

Согласно условию задачи Ограничения вида неравенств - student2.ru 1(x1 ,x2 ,…, xn )=bi ,поэтому λi ( bi - Ограничения вида неравенств - student2.ru i(x1 ,x2 ,…, xn )) = 0

Условия bi - Ограничения вида неравенств - student2.ru i(x1 ,x2 ,…, xn ) добавляются к условиям (3.17). Получившаяся система n+m неизвестными позволит решить задачу (3.12)-(3.14).

Наши рекомендации