Output Summary 6 страница

20.2. Задачи на экстремум при наличии ограничений

a) Будут ли производные новой целевой функции (выраженные через пере­менную х₃) отличаться от полученных с помощью метода Якоби?

b) В чем основное отличие описанной процедуры решения задачи от ме­тода Якоби?

2. Примените метод Якоби к решению задачи из примера 20.2.1, выбирая Y = (x₂, х₃) и Z = (л:,).

3. С помощью метода Якоби решите следующую задачу.

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

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

П* = с,

где С — положительная константа. Пусть теперь правая часть ограничения равна С + S, где S— малое положительное число. Найдите соответствующее изменение оптимального значения целевой функции /.

4. Решите методом Якоби следующую задачу.

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

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

g(X) = х,х₂ - 10 = 0.

a) Найдите изменение оптимального значения целевой функции /(X), если ограничение задачи примет вид х_ух_г - 9,99 = 0.

b) Найдите изменение значения целевой функции /(X) в окрестности допус­тимой точки (2, 5) при условии, что х₁х₂ = 9,99 и дх₁ = 0,01.

5. Решите следующую задачу.

Максимизировать /(X) = х] + 2х\ + Юх] + 5х^х₂

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

g, (X) = jc, + х\ + Ъх_гх_г -5 = 0,

g₂ (X) = xf + 5х,х₂ + лг₃² - 7 = 0.

Используйте метод Якоби для нахождения df(X) в окрестности допусти­мой точки (1, 1, 1). Пусть указанная окрестность определяется условия­ми dg_l = -0,01, dg₂ = 0,02 и дх₁ = 0,01.

6. Решите следующую задачу.

Минимизировать /(X) = xf + х\ + х] + х\

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

g,(X) = ж, + 2ж₂ + Зх₃ + 5x_t - 10 = 0,

g₂(X) = ж, + 2ж₂ + 5ж₃ + 6ж₄ -15 = 0.

а) Покажите, что при выборе х₃ и x_t в качестве независимых переменных ме­тод Якоби не дает оптимального решения.

Глава 20. Классическая теория оптимизации

b) Решите задачу, выбрав х, и х₃ в качестве независимых переменных, и примените достаточные условия для исследования полученной стацио­нарной точки.

c) Найдите коэффициенты чувствительности для этой задачи. 7. Решите следующую задачу линейного программирования.

Максимизировать /(Х) = ^с_;х_у

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

й(Х) = Е«Л-*,=0. '- = 1,2,..., и,

/=|

х^>0, j=l, 2, п.

Покажите, что если в этой задаче пренебречь условиями неотрицательности переменных, то приведенные производные V_cf(X) совпадают с разностями Ц-cv}, определяемыми условием оптимальности задачи линейного про­граммирования (раздел 7.2), а именно

{Zj - с) = {СвВ^Р, - с) для всех

Можно ли непосредственно применять метод приведенного градиента к реше­нию задачи линейного программирования? Почему можно или почему нельзя?

Метод множителей Лагранжа. Коэффициенты чувствительности метода Якоби можно использовать для решения задач с ограничениями в виде равенств. Пусть

x = v_yj-'=^.

dg

Следовательно,

df-kdg = 0.

Это уравнение соответствует необходимым условиям стационарности точек, так как формула для — получена с учетом того, что V_cf = 0. Представленное уравнение

можно записать в более удобной форме, если перейти к частным производным по всем переменным x_jt что приводит к системе уравнений

т-(/-»в) = о,; = 1,2,...,и.

Полученные уравнения вместе с ограничениями задачи g(X) = 0 формируют систе­му, которая позволяет определить допустимые векторы X и X, удовлетворяющие необходимым условиям стационарности.

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

L(X, k) = f(X)-Xdg(X).

20.2. Задачи на экстремум при наличии ограничений

Функция L называется функцией Лагранжа, а параметры X — множителями Ла-гранжа. Как следует из определения, эти множители имеют тот же смысл, что и коэффициенты чувствительности, фигурирующие в методе Якоби. Уравнения

—=0 и —=0 дк дХ

дают необходимые условия для определения стационарных точек функции /(X) при ограничениях g(X) = 0. Достаточные условия, используемые в методе множи­телей Лагранжа, будут сформулированы без доказательства. Определим матрицу

0 | Р

где

Р =

a²L(x,x)..

^и Q = —,—\\ д^{дя всех} ' ^и }■

ох ох.

Матрица Н^в называется окаймленной матрицей Гессе.

Пусть имеется стационарная точка (Х₀, Х₀) функции Лагранжа L(X, X), и окайм­ленная матрица Гессе Н⁸ вычислена в точке (Х₀, Х₀). Тогда Х₀ является следующим.

1. Точкой максимума, если, начиная с углового минора порядка 2т + 1, после­дующие п-т угловых миноров окаймленной матрицы Гессе Н^в образуют знакопеременный числовой ряд, в котором знак первого члена определяется множителем (-l)^m+I.

2. Точкой минимума, если, начиная с углового минора порядка 2т + 1, после­дующие п-т угловых миноров матрицы Н^в имеют знаки, определяемые множителем (-1)"¹.

Эти условия являются достаточными для определения экстремальной точки. Другими словами, экстремальной может оказаться стационарная точка, не удовле­творяющая этим условиям.

Существуют другие условия определения экстремальных точек задачи, которые являются как необходимыми, так и достаточными. Однако их практическое ис­пользование часто связано со значительными вычислительными трудностями. Оп­ределим матрицу

0 Р Л,P^r Q-ulJ'

вычисленную в стационарной точке (Х₀, Х₀), где ju — неизвестный параметр. Пусть |Д| — определитель матрицы Д, тогда все п-т действительных корней ju, полинома |Д| = 0 должны быть

1) отрицательными, если Х₀ — точка максимума,

2) положительными, если Х₀ — точка минимума.

Глава 20. Классическая теория оптимизации

Пример 20.2.4

Рассмотрим задачу из примера 20.2.2. Функция Лагранжа имеет вид £(ХД) = xf + х²₂ + х² + х₂ + 3х_ъ - 2)-Х₂(5дг, + 2.v₂ + дг, -5).

Необходимые условия экстремума записываются в виде следующей системы уравнений.

— = 2х,-X,-5Х₂=0, их,

^ = 2х₂-Х₁-2Х₂=0, ох₂

= 2x,-3X_t-X₂ = 0,

дх,

^- = -(х₎₊х₂+Зх,-2) = 0,

DL

= —(5лг, + 2х₂ + х, — 5) = 0.

Решением этой системы являются векторы

Х₀ = (*„ х₂, x_z) = (0,8043, 0,3478, 0,2826),

А. = (Я,, Л₂) = (0,0870, 0,3043).

В этом решении объединены результаты примеров 20.2.2 и 20.2.3. Как видим, значения множителей Лагранжа X совпадают со значениями коэффициентов чувствительности, полученными в примере 20.2.3. Это указывает на то, что эти коэффициенты не зависят от выбора вектора зависимых переменных Y при реализации метода Якоби.

Чтобы показать, что найденная точка является точкой минимума, рассмотрим матрицу

Г0 0 1 13" 0 0 5 2 1 Н" = 1 5 2 0 0 12 0 2 0 ^3 1 0 0 2j

Здесь и = 3,/и = 2ии-/и=1. Следовательно, необходимо проверить только опреде­литель матрицы Н^я, знак которого задается множителем (-1)² в точке минимума. Так как detH* = 460 > 0, то Х₀ является точкой минимума.

20.2. Задачи на экстремум при наличии ограничений

Пример 20.2.5

Рассмотрим задачу при ограничении минимизировать z = х² + xl + х]

4х, +xl +2х,-14 = 0.

Функция Лагранжа имеет вид

ЦХ,\) = х² +х²₁₊х²

-Х(4дг, +xl + 2х, -14).

Отсюда получаем необходимые условия экстремума в виде системы

дх,

= 2х,-4Х = 0,

= 2х₂ - 2Ъ:₂ = 0,

дх₂

-= 2х,

дх,

dl

■2Х = 0,

— = -(Ах. + xl + 2*з -14) = 0, дХ ^{v 2 3} >

решениями которой являются векторы

(Х„, A₀), = (2, 2,1,1), (Х₀,А₀)₂ = (2,-2, 1, 1), (Х₀,А₀)₃ = (2,8,0, 1,4, 1,4). Используя достаточные условия, вычислим элементы матрицы

'0 4 2х₂ 2Л 4 2 0 0 2х₂ 0 2-2Х 0 {2 0 0

Так как /и = 1 и и = 3, то для того, чтобы стационарная точка была точкой миниму­ма, знак последних 3-1 = 2 угловых миноров должен определяться знаком мно­жителя (-1)"" = -1. Таким образом, в точке (Х^ Л₀)₁ = (2, 2, 1, 1) имеем

0 4 4 4 2 0 4 0 0

-32 < 0

0 4 4 2

4 2 0 0

4 0 0 0

2 0 0 2

= -64<0.

Вточке(Х₀Д₀)₂ = (2, -2, 1, 1)

0 4^ 4 2 0 -4 0 0

= -32<0

0 4-42

4 2 0 0

-4 0 0 0

2 0 0 2

= -64<0.

Глава 20. Классическая теория оптимизации

Наконец, в точке (Х₀, А₀)₃ = (2,8, 0, 1,4, 1,4)

0 4 0 4 2 0 0 0 -0,8 = 12,8 > 0 и

0 4 0 2

4 2 0 0

О 0 -0,8 О

2 0 0 2

= 32>0.

Отсюда следует, что (X,,), и (Х„)₂ — точки минимума. Тот факт, что в точке (Х„)₃ не удовлетворяются достаточные условия максимума или минимума, не означает, что эта точка не является экстремальной. Это следствие того, что используемые усло­вия являются лишь достаточными.

Для иллюстрации схемы проверки достаточных условий экстремума, которая ис­пользует корни полинома, рассмотрим матрицу

'0 4 2х₂ 2 ^

4 2-й 0 0

2х₂ 0 2-2X-U 0

_к2 0 0 2-й,

А =

В точке (Х„, Я₀), = (2, 2, 1,1) имеем

|Д| = V- 26/^+16 = 0,

откуда получаем ju= 2 и //=8/9. Так как все ju> 0, то (Х₀), = (2, 2, 1) — точка мини­мума. В точке (Х₀, Л₀)₂ = (2, -2, 1,1)

|Д| = 9//- 26// + 16 = 0,

что совпадает с рассмотренным выше случаем. Следовательно, (Х₀)₂ = (2,-2, 1) яв­ляется точкой минимума. Наконец, в точке (Х„, Л₀)₃ = (2,8, 0, 1,4, 1,4)

|Д| = 5//-6//-8 = 0,

откуда получаем ju=2 и //=-0,8, что свидетельствует о том, что точка (Х„)₃ = (2,8, 0, 1,4) не является экстремальной.

УПРАЖНЕНИЯ 20.2.3

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

Максимизировать /(X) = 5х, + Зх₂

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

^(Х) = х, + 2х₂ + х₃ - 6 = О, g₂(X) = Зх, + х₂ + х_л - 9 = 0,

^"1* ^"2' ^"3> ^"4 ~

2. Найдите оптимальное решение следующей задачи.

Минимизировать /(X) = х¹ + 2х²₂ + 1 Ох²

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

g,(X) = x_l+x²₂+x,-5 = 0, £₂(Х) = лг, +5дг₂ + х₃-7 = 0.

20.2. Задачи на экстремум при наличии ограничений

Пусть g,(X) = 0,01 и g₂(X) = 0,02. Найдите величину соответствующего изме­нения оптимального значения функции /(X).

3. Решите упражнение 20.2.2.6 методом множителей Лагранжа и проверьте, что полученные значения множителей Лагранжа совпадают со значениями коэффи­циентов чувствительности, полученными ранее при решении этого упражнения.

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

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

Обобщенный метод множителей Лагранжа. Пусть дана задача, в которой требуется

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

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

£(Х)<0, j = 1,2.....т.

Если в рассматриваемой задаче имеются условия неотрицательности переменных X > 0, то предполагается, что они включены в указанные т ограничений.

Основная идея обобщенного метода множителей Лагранжа состоит в том, что если точка безусловного оптимума функции /(X) не удовлетворяет всем ограничениям за­дачи, то оптимальное решение задачи с ограничениями должно достигаться в гра­ничной точке области допустимых решений. Следовательно, одно или несколько из т ограничений задачи должны выполняться как равенства. Поэтому вычислительная процедура обобщенного метода множителей Лагранжа включает следующие шаги.

Шаг 1. Решается задача без учета ограничений

максимизировать 2=/(Х).

Если полученное оптимальное решение удовлетворяет всем огра­ничениям задачи, вычисления заканчиваются, так как все огра­ничения являются избыточными. Иначе следует положить k = 1 и перейти к шагу 2.

Шаг 2. Активизируются любые k ограничений задачи (т.е. преобразовывают­ся в равенства), и оптимизируется функция /(X) при наличии k огра­ничений методом множителей Лагранжа. Если оптимальное решение этой задачи является допустимым по отношению к остальным огра­ничениям исходной задачи, вычисления заканчиваются: полученная точка является локальным оптимумом². Иначе нужно сделать актив­ными другие k ограничений исходной задачи и повторить данный шаг. Если все подмножества, состоящие из k активных ограничений, не приводят к допустимому решению, следует перейти к шагу 3.

Шаг 3. Если k = m, вычисления прекращаются: задача не имеет допустимых решений. Иначе необходимо положить k — k + 1 и перейти к шагу 2.

В описанной вычислительной процедуре часто игнорируется то важное обстоя­тельство, что она не гарантирует получения глобального оптимума даже в тех

Локальный оптимум определяется из множества оптимумов, полученных в результа­те оптимизации целевой функции f(X.) при учете всех комбинаций из k ограничений-равенств, k = 1, 2, т.

Глава 20. Классическая теория оптимизации

случаях, когда задача имеет единственное оптимальное решение. Другим важным моментом является ошибочность интуитивного представления, что если p<q, то оптимальное значение целевой функции /(X) при р ограничениях-равенствах все­гда лучше, чем при q ограничениях-равенствах. В общем случае это имеет место лишь в том случае, когда набор из р ограничений является подмножеством набора из q ог­раничений. Рассматриваемый ниже пример служит иллюстрацией сказанного.

Пример 20.2.6

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

Максимизировать z = - (2х - 5)² - (2дг₂ -1)²

л-, + 2х₂ < 2, x_itx₂>0.

Графическое представление данной задачи (рис. 20.7) призвано помочь в понима­нии аналитических выкладок. Как видим, целевая функция задачи является во­гнутой, а область допустимых решений выпуклой. Отсюда следует, что эффектив­ный алгоритм должен гарантировать определение глобального оптимума. Однако обобщенный метод множителей Лагранжа, как будет показано, позволяет найти лишь точку локального максимума.

Рис. 20.7. Пространство решений для зада­чи примера 20.2.6

Точка безусловного экстремума находится как решение уравнений

— =-4(2*-5) = 0,

дх, ^{У 1} '

—4(2дг₂-1) = 0.

дх₂

Отсюда имеем (x_v х₂) = (5/2, 1/2). Так как это решение не удовлетворяет условию.г, + 2лг₂ < 2, ограничения поочередно активизируются. Рассмотрим ограничение х₁ = 0. Функция Лагранжа в этом случае примет вид

L(x,,x₂,\) = —(2л:, - 5)² -(2дг₂ - if -Хх_{.

20.2. Задачи на экстремум при наличии ограничений

Следовательно,

— = -4(2х.-5)-Х = 0,

дх, ^к '

— = -4(2х₂-1) = 0, дх₂ ^{V 2} '

— = -х,= 0. дХ '

Решением этой системы будет точка (х,,х₂) = (0, 1/2), которая является точкой максимума, в чем можно убедиться, используя достаточное условие. Поскольку эта точка удовлетворяет остальным ограничениям исходной задачи, вычислительная процедура завершается: (х₁,х₂) = (0, 1/2) — точка локального максимума задачи. (Заметим, что если поочередно активизировать оставшиеся ограничения задачи х_г > 0 и х, + 2х₂ < 2, то получаются недопустимые решения.) Оптимальное значение целевой функции z = -25.

Как видно из рис. 20.7, допустимому решению (х,, х₂) = (2, 0) рассматриваемой за­дачи, которое определяется точкой пересечения двух прямых х₂ = 0 и х, + 2х₂ = 2, соответствует значение целевой функции z = -2. Оно лучше значения функции z, которое получено с учетом одного активного ограничения.

Как следует из описанной вычислительной процедуры, при реализации обобщенно­го метода множителей Лагранжа на большее, чем получение приемлемого допустимого решения задачи, не следует рассчитывать. Особенно это проявляется тогда, когда целе­вая функция задачи не является одновершинной. Если в оптимизационной задаче име­ется единственный (глобальный) условный экстремум (как в примере 20.2.6), то, чтобы его найти, можно использовать откорректированный обобщенный метод множителей Лагранжа. Для этого необходимо провести сравнение безусловного оптимума и ус­ловных экстремумов, полученных с учетом всех возможных наборов активных огра­ничений, т.е. когда сначала отдельные ограничения делаются активными поочеред­но, затем рассматриваются пары активных ограничений, и так до тех пор, пока все т ограничений рассматриваемой задачи не станут активными. Наилучший из всех та­ких допустимых экстремумов является глобальным.

Если эту процедуру применить к решению задачи из примера 20.2.6, то для оп­ределения глобального экстремума необходимо решить семь задач. Это свидетель­ствует о том, что возможности использования обобщенного метода множителей Ла­гранжа для решения практических задач ограничены.

Условия Куна-Таккера. Данный раздел посвящен рассмотрению необходимых условий Куна-Таккера, которые позволяют определять стационарные точки в за­даче нелинейного программирования с ограничениями в виде неравенств. В основу изложения положен метод множителей Лагранжа. Эти условия являются также и достаточными, если выполняются определенные правила, которые описаны ниже.

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

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

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

g(X)<0.

Глава 20. Классическая теория оптимизации

Ограничения-неравенства можно преобразовать в равенства с помощью неотрица­тельных дополнительных переменных. Пусть Sf[>Q) — дополнительная перемен­ная, которая прибавляется к левой части t-ro ограничения g_t(X.) < 0 и пусть

S = (S„S₁,...,S\^T и S² =(S₁²,S₂²,...,5')^r,

где т — общее количество ограничений-неравенств. Следовательно, функция Ла­гранжа записывается в виде

ДХ, S,A) = /(X)-X.[g(X) + S²].

При ограничениях g(X) < 0 необходимым условием оптимальности в задаче макси­мизации (минимизации) является неотрицательность (соответственно, неположи­тельность) множителей X. Приведем обоснование этого. Рассмотрим задачу макси­мизации. Так как множители X выражают скорость изменения целевой функции / по отношению к изменениям g, т.е.

то как только правая часть ограничения g(X) < 0 увеличивается и становится боль­ше нуля, область допустимых решений задачи расширяется и, следовательно, оп­тимальное значение целевой функции не может уменьшиться. Это значит, что X > 0. Аналогично в задаче минимизации при увеличении правой части ограниче­ния оптимальное значение функции / не может увеличиться, откуда следует, что X < 0. Если же ограничения задачи имеют вид равенств, т.е. g(X) = 0, то компоненты вектора X по знаку не ограничены (см. упражнение 20.2.4.2).

Указанные выше ограничения на вектор X должны рассматриваться как часть необходимых условий Куна-Таккера. Теперь получим остальные условия.

Вычисляя частные производные функции L по X, S и X и приравнивая их к ну­лю, получаем

J|= V/(X)-XVg(X) = 0,

— = -2XS =0,; = 1,2,...,/и,

dS,

Из второй группы уравнений следуют такие результаты.

1. Если Я, не равняется нулю, то S² = 0. Это означает, что соответствующий это­му ограничению ресурс является дефицитным и, следовательно, полностью исчерпан (ограничение имеет вид равенства).

2. Если S² > 0, то Я, = 0. Это значит, что £-й ресурс дефицитным не является и,

следовательно, не влияет на значение целевой функции/(т.е. А.,. =-^- = 0).

fa

Из второй и третьей групп уравнений следует, что

Яд(Х) = 0, i=l,2,т.

20.2. Задачи на экстремум при наличии ограничений

Полученные условия фактически подтверждают предыдущий результат, ибо если Я, > 0, то g_t(X) = 0 или S,² = 0. Аналогично при g^X) < О S² > 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.....р,

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

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

L(X,S,X) = /(X)-±Х,[_gl(X) ₊ S?]-±X,[g,(X)-S,²]- £ X,g,(X),

1=1 i=r+l i=p.l

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

Глава 20. Классическая теория оптимизации

Таблица 20.2

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

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

9/W

А,

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

Минимизация

Вогнутая

Выпуклая

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

Выпуклая

Вогнутая

Линейная

>0 (1</<г) <0 (r + \<i<p)

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

<0 (1 <i <г)

> 0 (г +1 < i < р)

Нет ограничений + \ < j < _т)

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

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

Пример 20.2.7

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

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

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

_gl(X) = 2x,+x₂-5<0, g₂(X) = x,+x₃-2<0, g₃(X)=l-x,<0, g₄(X) = 2-x₂<0, g₅(X) = -x₃<0.

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

(Я,, Я₂, Я₃, Я₄, Я₅) < 0,

(2 10)

(2х_|,2х₂,2х₃)-(Х,Д₂Д₃Д₄Д₅)

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

= 0,

20.2. Задачи на экстремум при наличии ограничений

g(X)<0.

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

Я,, Я₂, Я₃, Я₄, Я₆ < О, 2х, - 2Я, - Я₂ + Я₃ = О, 2х₂ - Я, + Я₄ = О, 2х₃ - Я₂ + Я₅ = О, A,(2x_t +х₂- 5) = О, Я₂(х₁+х₃-2) = 0, Я₃(1-*,) = 0, Я₄(2-*₂) = 0, Я^ = О, 2х,+х_г<5, x,+x₃<2,

Отсюда получаем решение: х, = 1, х₂ = 2, х₃ = 0, Я, = Я₂ = Я₅ = О, Я₃ = -2, Я₄ = -4. По­скольку и целевая функция ДХ), и область допустимых решений g(X) < 0 являются выпуклыми, функция £(Х, 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 по знаку не ограничен.

Глава 20. Классическая теория оптимизации

3. Запишите необходимые условия Куна-Таккера для следующих задач.

a) Максимизировать /(X) = х³ -х₂ + х,х₃

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

х, + х₂ + х₃ = 5, 5х² - х² - х₃ > 0, х,>0, х₂>0, х₃>0.

b) Минимизировать /(X) = х,⁴+ х²+5х,х₂х₃

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

х,²-х₂+х₃³ <10, х,³+х₂²+4х₃2:20.

4. Дана задача

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

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

g(X) = 0.

Пусть ДХ) — вогнутая функция, а g,(X) (t = 1, 2, т) — линейные функ­ции. Покажите, что в этом случае необходимые условия Куна-Таккера ока­зываются также и достаточными. Верно ли последнее утверждение, если ё'ДХ) является выпуклой нелинейной функцией для всех г? Почему?

5. Дана задача

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

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

^(Х)>0,^₂(Х) = 0,^(Х)<0.