Задачи ВП при ограничениях вида неравенств

(3.18)

Перейдем к изучению задач выпуклого программирования в виде неравенств. В простейшем случае это такие задачи:

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

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

(3.19)

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

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

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

Путем добавления в левые части неравенств (3.31) неотрицательных переменных x_n+1,x_n+2,…, x_n+m перейдем от ограничений-неравенств к ограничениям-равенствам

(3.20)

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

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

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

_m(x₁,x₂,…, x_n) + x_n+m= _m.

Задача(3.18)-(3.20) является задачей ВП с ограничениями в виде равенств. Для ее решения, как и ранее, применим метод множителей Лагранжа

(x₁,x₂,…,x_n+1,…, x_n+m,λ₁, λ₂,…, λ_m) = f (x₁,x₂,…, x_n) + _i (b_i– _i(x₁,x₂,…,x_n)- x_n+i).

Вместо задачи (3.18)-(3.20) будем решать задачу на безусловный экстремум функции Лагранжа. Необходимое условие экстремума функции Лагранжа записывается так:

(3.21)

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

(3.22)

=0, i=1,2,…,m,

(3.23)

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

Учитывая вид функции , условия (3.21), (3.23) можно выразить следующим образом:

(3.24)

= - _i = 0,

 

= - _i = 0,

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

= - _i = 0,

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

(3.25)

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

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

 

Условия (3.22) с учетом неотрицательности переменных следует уточнить и записать в виде

(3.26)

∙ x_n+i = 0, i=1,2,…,m.

Если экстремум функции достигается внутри области допустимых решений (x_n+i > 0), то в точке экстремума = 0, на границе области (x_n+i = 0): ≤ 0 в случае выпуклости , < 0 - при вогнутости . Так как = - _i, то условие (3.26) примет вид -λ_i x_n+i = 0. Отсюда λ_i x_n+i = 0, однако x_n+i = b_i– _i(x₁,x₂,…,x_n). Следовательно, получим

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

В связи с тем, что = - _i ≤0, получим _i ≥0. Окончательно условие (3.26) можно записать так:

(3.27)

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

b_i– _i(x₁,x₂,…,x_n) ≥ 0, _i ≥0.

Причем, если _i >0, то b_i– _i(x₁,x₂,…,x_n) = 0, если _i =0, то b_i– _i(x₁,x₂,…,x_n) ≥ или

_i(x₁,x₂,…, x_n) ≤ _i.

Для нахождения решения задачи (3.18)-(3.19) достаточно условий (3.24), (3.27). В них не входят переменные x_n+i. Следовательно, можно и не вводить эти переменные в рассмотрение. Сразу можно было бы дял задачи (3.18)-(3.19) составлять функцию Лагранжа

= f (x₁,x₂,…, x_n) + _i (b _i - _i (x₁,x₂,…, x_n)).

Тогда необходимое условие экстремума этой функции включаю бы, как и прежде, условие (3.24). Условие же (3.27) для этой функции стало бы таким:

≥0, _i =0, _i ≥0, i=1,2,…,m,

где = b₁ - ₁(x₁,x₂,…, x_n).

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

Задача ВП в данном случае имеет вид

(3.28)

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

(3.29)

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

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

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

(3.30)

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

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

(3.31)

Для отыскания точки условного экстремума задачи (3.28)-(3.29) следует исходить из следующих условий

(3.32)

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

_i ≥0, _i =0, ≥0,

где - функция Лагранжа вида

= f (x₁,x₂,…, x_n) + _i (b _i - _i (x₁,x₂,…, x_n)).

Если принять во внимание условие неотрицательности x_j ≥ 0, j=1,2,…,n, то вместо равенств (3.31) следует пользоваться равенствами

x_j = 0, где x_j ≥ 0, ≤ 0.

С учетом вида функции Лагранжа условия нахождения точка условного максимума задачи (3.28)-(3.30) можно будет записать так:

I группа условий:

- i ≤ 0,

( - i ≤ 0)x_j = 0,

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

II группа условий:

b_i - _i (x₁,x₂,…, x_n)≥0,

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

x_j ≥ 0, i=1,2,…,m.

Условия I и II называются условиями Куна -Таккера. Из совокупности этих условий выделим для более глубокого рассмотрения следующие отношения.