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

(3.3)

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

Z = f (x₁ ,x₂ ,…, x_n ) max,

(3.4)

₁(x₁ ,x₂ ,…, x_n ) = ₁,

₂(x₁ ,x₂ ,…, x_n ) = ₂,

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

_m(x₁ ,x₂ ,…, x_n ) = _m,

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

(x₁ ,x₂ ,…, x_n, λ₁, λ₂,…, λ_m ) = f (x₁ ,x₂ ,…, x_n ) + _i [b₁ - ₁(x₁ ,x₂ ,…, x_n )].

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

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

= - _i = 0,

(3.5)

= - _i = 0,

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

= - _i = 0,

= b₁ - ₁(x₁ ,x₂ ,…, x_n ) = 0,

= b₂ - ₂(x₁ ,x₂ ,…, x_n ) = 0,

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

= b_m - _m(x₁ ,x₂ ,…, x_n ) =0.

Получили систему n + m уравнений с n + m неизвестными x₁ ,x₂ ,…, x_n ; λ₁, λ₂,…, λ_m. Для выпуклых (вогнутых) функций решение системы уравнений единственное (если конечно, оно вообще существует). Пусть решением системы является следующая совокупность значений переменных: x^o ₁, x^o₂,…, x^o_n ; λ^o₁, λ^o₂,…, λ^o_m. Это решение, дающее экстремум функции Лагранжа, состоит из двух частей:

оптимальное решение задачи x_o=(x^o ₁,x^o₂,…, x^o_n) и оптимальный вектор множителей Лагранжа λ_o=(λ^o₁, λ^o₂,…, λ^o_m).

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

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

и соответствовал бы балансу потребности и лимита по всем видам производственных ресурсов. Если потребность в ресурсе на предприятии составляет _i(x₁ ,x₂ ,…, x_n ) единиц, лимит этого ресурса составляет b_i единиц, то можно утверждать, что план производства должен удовлетворять равенствам

_i (x₁ ,x₂ ,…, x_n ) = b_i , i=1,2,…,m.

Очевидно, что оптимальное решение задачи (3.3) и (3.4) зависит от правых частей ограничений (3.4). Это значит, что компоненты оптимального плана x^o ₁,x^o₂,…, x^o_n зависят от лимитов ресурсов b₁, b₂,…, b_m. Понятно, что и оптимальное значение целевой функции

Z_o= f (x^o₁,x^o₂,…, x^o_n) также будет зависеть от b₁, b₂,…, b_m. Найдем числовое выражение зависимости оптимального значения целевой функции Z от лимитов ресурсов b₁, b₂,…, b_m.

Для измерения чувствительности оптимального значения целевой функции Z_o от изменения лимитов ресурсов b_i воспользуемся частной производной .

Докажем, что = λ^o_i , i=1,2,…,m.

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

x^o_j = x^o_j (b₁, b₂,…, b_m) , j=1,2,…,n.

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

Z_o= Z_o(b₁, b₂,…, b_m)= Z_o[x^o₁(b₁, b₂,…, b_m),…, x^o_n(b₁, b₂,…, b_m)].

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

(3.6)

= ∙ .

Продифференцируем левую и правую части равенства f_k (x^o₁,x^o₂,…, x^o_n)=b_k по b_i, получим

(3.7)

= ∙ = = ^1, _2, ^{если k = i} _{если k ≠ i.}

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

λ^o_i - ^o_k ∙ = ^o_k .

Отсюда имеем

(3.8)

λ^o_i - ^o_k ∙ = 0.

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

(3.9)

= λ^o_i + ∙ - ^o_k ∙ .

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

∙ - ^o_k ∙ = ∙ - ∙ ^o_k =

= ( - ^o_k ).

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

(3.10)

- ^o_k = 0,

(3.11)

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

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

В целом можно сделать вывод, что практическое значение равенства (3.11) в том, что мы легко можем оценить, как изменится оптимальное значение целевой функции при малом изменении лимитов ресурсов. По-другому говоря, множители Лагранжа λ^o_i являются оценками ресурсов b₁, b₂,…, b_m.

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

(3.12)

Задача имеет вид

Z = f (x₁ ,x₂ ,…, x_n ) max,

(3.13)

₁(x₁ ,x₂ ,…, x_n ) = ₁,

₂(x₁ ,x₂ ,…, x_n ) = ₂,

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

(3.14)

_m(x₁ ,x₂ ,…, x_n ) = _m,

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

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

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

(x₁ ,x₂ ,…, x_n, λ₁, λ₂,…, λ_m ) = f (x₁ ,x₂ ,…, x_n ) + ₁ [b₁ - ₁(x₁ ,x₂ ,…, x_n )].

(3.15)

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

(3.16)

x_j = 0, j=1,2,…,n,

λ_i =0, i=1,2,…,m.

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

(3.17)

если x_j 0, то = 0; если x_j 0,то ≤ 0;

или, если x_j 0, то - i = 0; если x_j 0, то - i ≤ 0.

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

λ_i = λ_i ( b_i - _i(x₁ ,x₂ ,…, x_n )) = 0.

Согласно условию задачи ₁(x₁ ,x₂ ,…, x_n )=b_i ,поэтому λ_i ( b_i - _i(x₁ ,x₂ ,…, x_n )) = 0

Условия b_i - _i(x₁ ,x₂ ,…, x_n ) добавляются к условиям (3.17). Получившаяся система n+m неизвестными позволит решить задачу (3.12)-(3.14).