Полученные условия фактически подтверждают предыдущий результат, ибо если Я, > 0, то gt(X) = 0 или S,2 = 0 . Аналогично при gX) < О S2 > 0 и, следовательно, \ = 0.

Теперь для задачи максимизации можно сформулировать условия Куна-Таккера, необходимые для того, чтобы векторы X и X определяли стационарную точку:

Х>0, Vf(X)-XVg(X) = 0, Лд(Х)-0, i = l,2, .... те, g(X)<0.

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

Достаточность условий Куна-Таккера. Если целевая функция и область допустимых решений рассматриваемой задачи обладают определенными свойствами, связанными с выпуклостью и вогнутостью, то необходимые условия Куна-Таккера являются также достаточными. Упомянутые свойства перечислены в табл. 20.1.

Таблица 20.1

Процедура проверки выпуклости или вогнутости некоторой функции является более простой, чем доказательство выпуклости множества допустимых решений экстремальной задачи. Так как выпуклость допустимого множества может быть установлена путем непосредственной проверки выпуклости или вогнутости функций ограничений, по этой причине мы приводим перечень требований, которые легче использовать на практике. Чтобы установить эти требования, рассмотрим задачу нелинейного программирования в общей постановке.

Максимизировать или минимизировать z = f(X)

при ограничениях

g,(X)<0, 1=1,2.....г,

g,(X)>0, i= r+1.....р,

gt(X) = 0, i=p + l.....те.

При этом функция Лагранжа имеет вид

L(X,S,X) = /(X)-±Х,[gl(X) + S?]-±X,[g,(X)-S,2]- £ X,g,(X),

1 = 1 i=r+l / = (,.1

где Я, - множитель Лагранжа, соответствующий i-му ограничению. Требования, которые устанавливают достаточность условий Куна-Таккера, приведены в табл. 20.2.

Таблица 20.2

Требуемые свойства

Тип оптимизации fl[X)

Максимизация

Минимизация

Вогнутая

Выпуклая

Выпуклая Вогнутая Линейная

Выпуклая

Вогнутая

Линейная

>0 (1</<г)

<0 (r + \<i<p)

Нет ограничений (р +1 < i < /и)

<0 (1 <i <г)

> 0 (г +1 < i < р)

Нет ограничений (p + \<i<m)

В табл. 20.2 представлена лишь часть условий, упомянутых в табл. 20.1. Это связано с тем, что область допустимых решений задачи может быть выпуклой, и в то же время функции ограничений, которые ее формируют, могут не соответствовать требованиям, перечисленным в табл. 20.2.

Законность положений табл. 20.2 основана на том, что при сформулированных условиях функция Лагранжа L(X, S, Я) является вогнутой в задаче максимизации и выпуклой - в задаче минимизации. Это подтверждается тем, что если £,(Х) - выпуклая функция, то функция Яд(Х) оказывается выпуклой при Я,>0 и вогнутой- при Я, <0. Аналогичные рассуждения подтверждают все остальные условия. Заметим также, что линейная функция является как выпуклой, так и вогнутой. Наконец, если функция f вогнутая, то функция -/ является выпуклой, и наоборот.

Пример 20.2.7

Рассмотрим следующую задачу.

Минимизировать /(X) = х,2 + х2 + х,

при ограничениях

gl(X) = 2x,+x2-5<0, g2(X) = x,+x3-2<0, g,(X)=l-x,S0, g4(X) = 2-x2<0, g5(X) = -*3<0.

Поскольку рассматривается задача минимизации, то к < 0. Поэтому условия Куна-Таккера записываются в следующем виде.

(Я Я2, Я3, Я4, Я5) < 0,

(2 10)

(2х;2х2,2хз)-(Х,Д2ДзД4Д5)

1 0 1 -10 0 0-10 0 0-1

= 0,

g(X)<0.

Эти условия можно упростить и привести к виду

Я Я2, Я3, Я4, Я6 < О, 2х, - 2Я, - Я2 + Я3 = О, 2х2 - Я, + Я4 = О, 2х3 - Я2 + Я5 = О, Я,(2х, +х2- 5) = О, Я2(х,+х3-2) = 0, Я3(1-х,) = 0, Я4(2-х2) = 0,

2х,+х2<5,

х,+х3<2,

х,>1,х2>2,х3>0.

Отсюда получаем решение: х, = 1, х2 = 2, х3 = 0, Я, = Я2 = Я5 = О, Я3 = -2, Я4 = -4. Поскольку и целевая функция ДХ), и область допустимых решений g(X) < 0 являются выпуклыми, функция L(X, S, X) также должна быть выпуклой, и полученная стационарная точка определяет глобальный минимум задачи. Рассмотренный пример показывает также, что решение системы, порожденной условиями Куна-Таккера, в явной форме может быть затруднительным. Следовательно, для численных расчетов описанная процедура не подходит. Тем не менее условия Куна-Таккера играют основополагающую роль при рассмотрении алгоритмов решения задач нелинейного программирования в главе 21.

УПРАЖНЕНИЯ 20.2.4

1. Покажите, что условия Куна-Таккера для задачи

максимизировать ДХ)

при ограничениях

g(X)>0

совпадают с условиями, сформулированными в разделе 20.2.2, с той лишь разницей, что множители Лагранжа X должны быть неположительными.

2. Дана следующая задача.

Максимизировать /(X)

при ограничениях

g(X) = 0.

Покажите, что условия Куна-Таккера для этой задачи имеют вид

Vf(X)-XVg(X) = 0, g(X) = 0, X по знаку не ограничен.