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

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

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

Задачи ВП при ограничениях вида неравенств - №1 - открытая онлайн библиотека 1(x1 ,x2 ,…, xn ) ≤ Задачи ВП при ограничениях вида неравенств - №2 - открытая онлайн библиотека 1,

(3.19)
Задачи ВП при ограничениях вида неравенств - №1 - открытая онлайн библиотека 2(x1 ,x2 ,…, xn ) ≤ Задачи ВП при ограничениях вида неравенств - №4 - открытая онлайн библиотека 2,

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

Задачи ВП при ограничениях вида неравенств - №5 - открытая онлайн библиотека m(x1 ,x2 ,…, xn ) ≤ Задачи ВП при ограничениях вида неравенств - №4 - открытая онлайн библиотека m,

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

(3.20)
Задачи ВП при ограничениях вида неравенств - №1 - открытая онлайн библиотека 1(x1 ,x2 ,…, xn ) + xn+1= Задачи ВП при ограничениях вида неравенств - №2 - открытая онлайн библиотека 1,

Задачи ВП при ограничениях вида неравенств - №1 - открытая онлайн библиотека 2(x1 ,x2 ,…, xn ) + xn+2= Задачи ВП при ограничениях вида неравенств - №4 - открытая онлайн библиотека 2,

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

Задачи ВП при ограничениях вида неравенств - №5 - открытая онлайн библиотека m(x1 ,x2 ,…, xn ) + xn+m= Задачи ВП при ограничениях вида неравенств - №4 - открытая онлайн библиотека m.

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

Задачи ВП при ограничениях вида неравенств - №13 - открытая онлайн библиотека (x1 ,x2,…,xn+1,…, xn+m1, λ2,…, λm) = f (x1 ,x2 ,…, xn ) + Задачи ВП при ограничениях вида неравенств - №14 - открытая онлайн библиотека i (biЗадачи ВП при ограничениях вида неравенств - №1 - открытая онлайн библиотека i(x1 ,x2,…,xn)- xn+i).

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

(3.21)
Задачи ВП при ограничениях вида неравенств - №16 - открытая онлайн библиотека = 0, j=1,2,…,n,

(3.22)
Задачи ВП при ограничениях вида неравенств - №17 - открытая онлайн библиотека =0, i=1,2,…,m,

(3.23)
Задачи ВП при ограничениях вида неравенств - №18 - открытая онлайн библиотека =0, i=1,2,…,m.

Учитывая вид функции Задачи ВП при ограничениях вида неравенств - №19 - открытая онлайн библиотека , условия (3.21), (3.23) можно выразить следующим образом:

(3.24)
Задачи ВП при ограничениях вида неравенств - №20 - открытая онлайн библиотека = Задачи ВП при ограничениях вида неравенств - №21 - открытая онлайн библиотека - Задачи ВП при ограничениях вида неравенств - №22 - открытая онлайн библиотека i Задачи ВП при ограничениях вида неравенств - №23 - открытая онлайн библиотека = 0,

Задачи ВП при ограничениях вида неравенств - №24 - открытая онлайн библиотека = Задачи ВП при ограничениях вида неравенств - №25 - открытая онлайн библиотека - Задачи ВП при ограничениях вида неравенств - №22 - открытая онлайн библиотека i Задачи ВП при ограничениях вида неравенств - №27 - открытая онлайн библиотека = 0,

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

Задачи ВП при ограничениях вида неравенств - №28 - открытая онлайн библиотека = Задачи ВП при ограничениях вида неравенств - №29 - открытая онлайн библиотека - Задачи ВП при ограничениях вида неравенств - №22 - открытая онлайн библиотека i Задачи ВП при ограничениях вида неравенств - №31 - открытая онлайн библиотека = 0,

Задачи ВП при ограничениях вида неравенств - №32 - открытая онлайн библиотека = b1 - Задачи ВП при ограничениях вида неравенств - №1 - открытая онлайн библиотека 1(x1 ,x2 ,…, xn ) - xn+1 = 0,

(3.25)
- - - - - - - - - - - - - - - - - - - - - - - - - - -- - - - - - - - - - - -

Задачи ВП при ограничениях вида неравенств - №34 - открытая онлайн библиотека = bm - Задачи ВП при ограничениях вида неравенств - №1 - открытая онлайн библиотека m(x1 ,x2 ,…, xn ) - xn+m =0.

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

(3.26)
Задачи ВП при ограничениях вида неравенств - №17 - открытая онлайн библиотека ∙ xn+i = 0, i=1,2,…,m.

Если экстремум функции Задачи ВП при ограничениях вида неравенств - №13 - открытая онлайн библиотека достигается внутри области допустимых решений (xn+i > 0), то в точке экстремума Задачи ВП при ограничениях вида неравенств - №17 - открытая онлайн библиотека = 0, на границе области (xn+i = 0): Задачи ВП при ограничениях вида неравенств - №17 - открытая онлайн библиотека ≤ 0 в случае выпуклости Задачи ВП при ограничениях вида неравенств - №19 - открытая онлайн библиотека , Задачи ВП при ограничениях вида неравенств - №17 - открытая онлайн библиотека < 0 - при вогнутости Задачи ВП при ограничениях вида неравенств - №19 - открытая онлайн библиотека . Так как Задачи ВП при ограничениях вида неравенств - №17 - открытая онлайн библиотека = - Задачи ВП при ограничениях вида неравенств - №44 - открытая онлайн библиотека i , то условие (3.26) примет вид -λi xn+i = 0. Отсюда λi xn+i = 0, однако xn+i = biЗадачи ВП при ограничениях вида неравенств - №1 - открытая онлайн библиотека i(x1 ,x2,…,xn). Следовательно, получим

λi (biЗадачи ВП при ограничениях вида неравенств - №1 - открытая онлайн библиотека i(x1 ,x2,…,xn)) = 0.

В связи с тем, что Задачи ВП при ограничениях вида неравенств - №17 - открытая онлайн библиотека = - Задачи ВП при ограничениях вида неравенств - №44 - открытая онлайн библиотека i ≤0, получим Задачи ВП при ограничениях вида неравенств - №49 - открытая онлайн библиотека i ≥0. Окончательно условие (3.26) можно записать так:

(3.27)
λi (biЗадачи ВП при ограничениях вида неравенств - №1 - открытая онлайн библиотека i(x1 ,x2,…,xn)) = 0,

biЗадачи ВП при ограничениях вида неравенств - №1 - открытая онлайн библиотека i(x1 ,x2,…,xn) ≥ 0, Задачи ВП при ограничениях вида неравенств - №49 - открытая онлайн библиотека i ≥0.

Причем, если Задачи ВП при ограничениях вида неравенств - №49 - открытая онлайн библиотека i >0, то biЗадачи ВП при ограничениях вида неравенств - №1 - открытая онлайн библиотека i(x1 ,x2,…,xn) = 0, если Задачи ВП при ограничениях вида неравенств - №44 - открытая онлайн библиотека i =0, то biЗадачи ВП при ограничениях вида неравенств - №1 - открытая онлайн библиотека i(x1 ,x2,…,xn) ≥ или Задачи ВП при ограничениях вида неравенств - №57 - открытая онлайн библиотека

Задачи ВП при ограничениях вида неравенств - №1 - открытая онлайн библиотека i(x1 ,x2 ,…, xn ) ≤ Задачи ВП при ограничениях вида неравенств - №4 - открытая онлайн библиотека i.

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

Задачи ВП при ограничениях вида неравенств - №13 - открытая онлайн библиотека = f (x1 ,x2 ,…, xn ) + Задачи ВП при ограничениях вида неравенств - №14 - открытая онлайн библиотека i (b i - Задачи ВП при ограничениях вида неравенств - №1 - открытая онлайн библиотека i (x1 ,x2 ,…, xn )).

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

Задачи ВП при ограничениях вида неравенств - №18 - открытая онлайн библиотека ≥0, Задачи ВП при ограничениях вида неравенств - №49 - открытая онлайн библиотека i Задачи ВП при ограничениях вида неравенств - №18 - открытая онлайн библиотека =0, Задачи ВП при ограничениях вида неравенств - №66 - открытая онлайн библиотека i ≥0, i=1,2,…,m,

где Задачи ВП при ограничениях вида неравенств - №18 - открытая онлайн библиотека = b1 - Задачи ВП при ограничениях вида неравенств - №1 - открытая онлайн библиотека 1(x1 ,x2 ,…, xn ).

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

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

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

(3.29)
Задачи ВП при ограничениях вида неравенств - №1 - открытая онлайн библиотека 1(x1 ,x2 ,…, xn ) = Задачи ВП при ограничениях вида неравенств - №4 - открытая онлайн библиотека 1,

Задачи ВП при ограничениях вида неравенств - №1 - открытая онлайн библиотека 2(x1 ,x2 ,…, xn ) = Задачи ВП при ограничениях вида неравенств - №4 - открытая онлайн библиотека 2,

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

(3.30)
Задачи ВП при ограничениях вида неравенств - №5 - открытая онлайн библиотека m(x1 ,x2 ,…, xn ) = Задачи ВП при ограничениях вида неравенств - №4 - открытая онлайн библиотека m,

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

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

(3.32)
Задачи ВП при ограничениях вида неравенств - №16 - открытая онлайн библиотека = 0, j=1,2,…,n,

Задачи ВП при ограничениях вида неравенств - №49 - открытая онлайн библиотека i ≥0, Задачи ВП при ограничениях вида неравенств - №66 - открытая онлайн библиотека i Задачи ВП при ограничениях вида неравенств - №18 - открытая онлайн библиотека =0 , Задачи ВП при ограничениях вида неравенств - №18 - открытая онлайн библиотека ≥0,

где Задачи ВП при ограничениях вида неравенств - №19 - открытая онлайн библиотека - функция Лагранжа вида

Задачи ВП при ограничениях вида неравенств - №13 - открытая онлайн библиотека = f (x1 ,x2 ,…, xn ) + Задачи ВП при ограничениях вида неравенств - №14 - открытая онлайн библиотека i (b i - Задачи ВП при ограничениях вида неравенств - №1 - открытая онлайн библиотека i (x1 ,x2 ,…, xn )).

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

xj Задачи ВП при ограничениях вида неравенств - №16 - открытая онлайн библиотека = 0, где xj ≥ 0, Задачи ВП при ограничениях вида неравенств - №16 - открытая онлайн библиотека ≤ 0.

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

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

Задачи ВП при ограничениях вида неравенств - №87 - открытая онлайн библиотека - Задачи ВП при ограничениях вида неравенств - №22 - открытая онлайн библиотека i Задачи ВП при ограничениях вида неравенств - №89 - открытая онлайн библиотека ≤ 0,

( Задачи ВП при ограничениях вида неравенств - №87 - открытая онлайн библиотека - Задачи ВП при ограничениях вида неравенств - №22 - открытая онлайн библиотека i Задачи ВП при ограничениях вида неравенств - №89 - открытая онлайн библиотека ≤ 0)xj = 0,

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

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

bi - Задачи ВП при ограничениях вида неравенств - №1 - открытая онлайн библиотека i (x1 ,x2 ,…, xn )≥0,

Задачи ВП при ограничениях вида неравенств - №94 - открытая онлайн библиотека i ( Задачи ВП при ограничениях вида неравенств - №1 - открытая онлайн библиотека i (x1 ,x2 ,…, xn ) - b1) = 0,

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

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