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

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

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

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

(3.29)
1(x1 ,x2 ,…, xn ) = 1,

2(x1 ,x2 ,…, xn ) = 2,

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

(3.30)
m(x1 ,x2 ,…, xn ) = m,

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

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

(3.32)
= 0, j=1,2,…,n,

i ≥0, i =0 , ≥0,

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

= f (x1 ,x2 ,…, xn ) + i (b i - i (x1 ,x2 ,…, xn )).

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

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

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

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

- i ≤ 0,

( - i ≤ 0)xj = 0,

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

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

bi - i (x1 ,x2 ,…, xn )≥0,

i ( i (x1 ,x2 ,…, xn ) - b1) = 0,

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

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

Условия дополняющей нежесткости Куна-Таккера.

I'. Если - i < 0, то xj 0,

если xj 0 , то - i = 0.

II'. Если i(x1 ,x2 ,…, xn ) < bi , то i = 0,

если i > 0 , то i(x1 ,x2 ,…, xn ) = bi.

Условия I' и II' называются условиями дополняющей нежесткости.Рассмотрим их экономическую интерпретацию, исходя из прежней экономической постановки задачи ВП: x1 ,x2 ,…, xn - план производства продукции, f (x1 ,x2 ,…, xn ) - прибыль от реализации продукции, i(x1 ,x2 ,…, xn ) - потребность в ресурсе i по данному варианту производственной программы, x1 ,x2 ,…, xn , bi - лимит ресурса i.

Ранее нами было установлено, что i есть оценка ресурса i по его влиянию на оптимальное значение целевой функции. Эта оценка равна производной = λoi. Это справедливо для всех i.

Рассмотрим содержание соотношений II'. Положительность оценки λoi (λoi>0) указывает на то, что ресурс bi в оптимальном плане используется полностью, то есть i(xo1,xo2,…, xon) = = bi . Если ресурс используется не полностью, то есть i(xo1,xo2,…, xon) < bi , то этот ресурс не является дефицитным, его оценка равна нулю: λoi =0.



Аналогичным будет подход при рассмотрении содержания условий I'.

Продукт j целесообразно включить в план производства (xj > 0) только в том случае, когда результатная оценка продукции совпадает с ее затратной оценкой i , то есть когда достигается баланс результата и затрат, связанных с малым выпуском продукции. Если же получаемый результат (оценка продукции) меньше затрат ресурсов i , то включение в план производства продукта целесообразно (xj = 0).

Рассмотрим формулировку условий дополняющей нежесткости применительно к задаче линейного программирования. Для такой задачи

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

i(x1 ,x2 ,…, xn ) = ijxj ≤ bi , i=1,2,…,m,

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

= λoi = yoi ; = cj ; = aij ;

i = oi aij .

Условия дополняющей нежесткости для задачи линейного программирования запишутся следующим образом.

Если ijyoi > cj, то xoj = 0;

если xoj > 0 , то ijyoi = cj ;

если ijxoj < bi, то yoi = 0;

если yoi > 0, то ijxoj = bi.

Полученные соотношения были изучены нами еще в теории линейного программирования.

Теорема Куна-Таккера.

Введем понятие седловой точки функции многих переменных. Дана некоторая функция Q=Q(x1 ,x2 ,…, xn , y1, y2 ,…, ym) двух групп переменных x1 ,x2 ,…, xn и y1, y2 ,…, ym . Пусть по первой группе переменных функцию Q требуется максимизировать, по второй-минимизировать.

Определение. Точка (xo1 ,xo2 ,…, xon , yo1, yo2 ,…, yom ) = (Xo,Yo) называется седловой точкой функции Q, если в ней выполняется следующее неравенство:



Q(X, Yo) ≤ Q (Xo,Yo) ≤ Q(Xo,Y).

(4.1)
Рассмотрим следующую задачу выпуклого программирования:

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

(4.2)
1(x1 ,x2 ,…, xn ) ≤ 1,

2(x1 ,x2 ,…, xn ) ≤ 2,

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

m(x1 ,x2 ,…, xn ) ≤ m,

(4.3)
x1 ≥ 0, x2 ≥ 0, … , xn ≥ 0.

Перейдем от этой задачи на условный экстремум к задаче на безусловный экстремум с помощью функции Лагранжа

(x1 ,x2 ,…, xn, λ1, λ2,…, λm ) = f (x1 ,x2 ,…, xn ) + i (bi – i(x1 ,x2 ,…, xn )).

(4.4)
Предположим, что найдена седловая точка функции Лагранжа

(xo, λo) = (xo 1, xo2,…, xon ; λo1, λo2,…, λom) .

Тогда справедливым будет следующее неравенство:

(x, λo) ≤ (xo, λo) ≤ (xo, λ).

Задача отыскания точки (xo, λo) из области определения функции (x, λ), удовлетворяющей неравенству (4.4), называется задачей о седловой точке.

Теорема. Точка xo будет являться решением задачи ВП (4.1)-(4.3) тогда и только тогда, когда существует такая точка λo ≥ 0, что точка (xo, λo) является седловой точкой функции Лагранжа (x, λ ).


3825905624213210.html
3825952158987838.html
    PR.RU™