<<
>>

УСЛОВНЫЙ ЭКСТРЕМУМ ПРИ ОГРАНИЧЕНИЯХ ТИПА НЕРАВЕНСТВ

Постановка задачи

Даны дважды непрерывно дифференцируемые целевая функция /(*) = /(х,,...,хя) и функции ограничений gj(x) = gj(xlt...txn) lt; 0, 7 = определяющие множество допустимых решений X.

Требуется исследовать функцию /(х) на экстремум, т.е. определить точки

х* € X ее локальных минимумов и максимумов на множестве X:

/И = min /(*); /(**) = max /(*), (3.15)

X pound;Л X €л

где X = {х | pound;/(х)pound; О, j = }.

Стратегия решения задачи

Находятся точки х* локального экстремума с помощью необходимых и достаточных условий минимума и максимума первого и второго порядка при ог­раничениях типа неравенств (порядок условий определяется порядком исполь­зуемых производных). Вычисляются значения /(**) функции в найденных точ­ках локального экстремума.

Утверждение 3.4 (необходимые условия минимума (максимума) первого порядка).

Пусть X*- точка локального минимума (максимума) в задаче (3.15). Тогда

найдется такое число А.*0 gt; 0 и вектор X* = ^1,...,А.*т) , не равные одновременно

нулю и такие, что выполняются следующие условия:

- условие стационарности обобщенной функции Лагранжа по х :

(3.16 а)

- условие допустимости решения:

(3.16 6)

- условие неотрицательности для условного минимума:

(3.16 в)

АГуgt;0, 7 = 1 ,...,т

(условие неположительности для условного максимума: А.^ lt; 0 , у = 1,...,/и); - условие дополняющей нежесткости:

(3.16 г)

Если при этом градиенты активных в точке х* ограничений линейно независимы (выполняется условие регулярности), то А*0 * 0.

Замечания 3.4.

1. Точки х*, удовлетворяющие системе (3.16), называются условно- стационарными.

2. В отличие от случая ограничений типа равенств необходимые условия экстремума первого порядка формулируются отдельно для максимума и мини­мума. Утверждение 3.4 было доказано Ф. Джоном (F. John), а при Х*0 ф 0 Куном и Таккером (H.W. Kuhn, A.W. Tucker).

3. Если в решаемой задаче ограничения записаны в форме gy(x) gt; 0, то их

необходимо переписать в виде, используемом в (3.15): -gj(x) lt;0.

4. Далее будем использовать множество индексов ограничений, активных в точке х*, которое обозначим через Ja.

5. При решении задач поиска условного максимума можно использовать необходимые и достаточные условия минимума, применяя преобразование, опи­санное в п.1 замечаний 1.1.

6. Так как точка х* заранее неизвестна, то проверка условия регулярности затруднена, поэтому рекомендуется следовать алгоритму, описанному в п.З заме­чания 3.1.

7. Точка экстремума, удовлетворяющая системе (3.16) при А*0 ф 0, называ­ется регулярной, а при А,*0 = 0 - нерегулярной. Случай А.*0 = 0 отражает вырожден- ность ограничений.

8. Условие (3.16 а) в регулярной точке экстремума х* отражает факт, что антиградиент целевой функции является неотрицательной (неположительной в случае максимума) линейной комбинацией градиентов функций, образующих ак­тивные ограничения в точке х*. Действительно, условие (3.16 а) с учетом (3.16 г) можно переписать в форме

-У/(х*) = = pound; *1 **;(*•) •

'=1 УеУа

На рис. 3.9 в точке х* достигается минимум и выполняется приведенное равенство, а в точке х нет.

pound;2 (*) = 0

Рис. 3.9

9. При Х*0 * 0 справедливы два важных утверждения:

1) если функции /(*), pound;у(*), У = 1,...,/и, выпуклые, то условия утвержде­ния 3.4 являются одновременно и достаточными условиями глобального мини­мума;

2) если функции “-/(*)”, pound;у(х), У = 1,...,/и, выпуклые, то условия теоре­мы 3.4 являются одновременно и достаточными условиями глобального макси­мума.

В обоих случаях множество допустимых решений X выпукло.

10. Условие допустимости решения, являющееся следствием постановки задачи (3.15), включено в (3.16) для удобства формирования алгоритма решения задачи.

11. Из условия дополняющей нежесткости следует, что если ограничение в точке х* пассивное, т.е. gj(x*)lt; 0 , то А.у=0, а если - активное, т.е.

pound;у(х*) = 0, то pound; 0 (для минимума) и А.*у- pound; 0 (для максимума).

Утверждение 3.5 (достаточные условия минимума (максимума) первого по­рядка).

Пусть имеется точка удовлетворяющая системе (3.16) при А.*0 * 0,

число активных ограничений в точке х* совпадает с числом п переменных (при этом условие регулярности выполняется). Если А.* gt; 0 для всех ] е 1а, то точка х*

- точка условного локального минимума. Если А.* lt; 0 для всех ] € , то х* - точка

условного локального максимума в задаче (3.15).

Утверждение 3.6 (необходимое условие минимума (максимума) второго по­рядка).

Пусть х* - регулярная точка минимума (максимума) в задаче (3.15) и имеет­ся решение А*| системы (3.16). Тогда второй дифференциал классической функ­ции Лагранжа, вычисленный в точке (х*,А,*), неотрицателен (неположителен):

lt;12Цх'Х)* О (3.17)

для всех сЬс е Яп таких, что

lt;amp;/(**) = *7gt;о (*}lt;о);

dgj[x*}lt; 0, у'б/в, А,^ = 0.

Утверждение 3.7 (достаточные условия экстремума второго порядка).

Пусть имеется точка |х*,А.*|, удовлетворяющая системе (3.16) при А.о * 0.

Если в этой точке с12Ь^х*, А,*| gt; 0 [с12ь[х*, А,*) lt; о| для всех ненулевых lt;Ьс еЯп та­ких, что

pound;amp;Дх*) = 0, А.у gt; 0 (А.у lt; 0);

lt;/$,(**)lt;0, ) а, А.* = 0,

то точка х* является точкой локального минимума (максимума) в задаче (3.15).

Замечание 3.5. В рассматриваемой задаче замечания 3.2 и пп.1 и 3 замечаний 3.3 также справедливы с учетом замены (3.9) на (3.16).

Алгоритм решения задачи

Шаг 1. Составить обобщенную функцию Лагранжа:

т

pound;(х,А,0А) = Ч /(*)+ X pound;;(*)•

У=1

Шаг 2.

Записать необходимые условия минимума (максимума) первого по­рядка:

б) pound;;(дс*)lt; 0, у = 1

в) А,* gt; 0, у = 1,...,/и (для минимума), А.*у lt; 0, у = 1 (для максимума);

Шаг 3. Решить систему для двух случаев:

1) А, о = 0;

2) А,*о * 0 (при этом поделить условия, записанные на шаге 2, на Х*0 и за-

К ;

менить — на А.,-).

Jf

В результате найти условно-стационарные точки х*, выделив из них полу­ченные при А.*о * 0 (они могут быть регулярными точками экстремума). В каж­дом из двух случаев следует начинать с рассмотрения 2т вариантов удовлетворе­ния условия “г” дополняющей нежесткости.

Шаг 4. Для выделенных на шаге 3 точек проверить достаточные условия экстремума первого или второго порядка.

Для проверки достаточных условий первого порядка следует:

а) определить число / активных в точке х* ограничений;

б) если I — п и gt; 0 для всех у е /д, то в точке х* - локальный минимум. Если I = п и ^. lt; 0 для всех у е /д, то в точке х* - локальный максимум. Если / lt; п или соответствующие множители Лагранжа не удовлетворяют достаточным условиям первого порядка, проверить достаточные условия второго порядка.

Для проверки достаточных условий второго порядка следует:

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

Лагранжа в точке

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

6x1 lt; 0, у е/д, X) =0;

(3.18)

в) исследовать знак второго дифференциала функции Лагранжа для нену­левых с!х , удовлетворяющих системе (3.18).

Если ё2Ь gt; 0, то в точке х* -

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

__________________________________________________________________________ Таблица 3.2

Необходимые условия первого порядка Достаточные условия первого порядка * 0)

п/п

Ухі(х*Д*оД*);

х) */**).

У = 1,...,/и

*,(*)gt;

] = 1,..., т

*о,

І = I,..., т

Число / активных ограничений *7’

1 Є 1 а

Тип условно-стационарной точки х*
1 0 ‘ а 0 gt; 0 п gt; 0 Условный локальный минимум
2 0 lt;; 0 lt; 0 п . lt;Л Условный локальный максимум

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

_________________________________________________________________________ Таблица 3.3

bgcolor=white>3

п/п

І е -Га’ X) gt; 0 X*. lt; 0 і є Х\ = 0 Тип условно-стационарной точки х*
1 gt; 0 0, amp;х * 0 pound; 0 Условный локальный минимум
2 lt; 0 0, lt;1х ф 0 lt; 0 Условный локальный максимум
gt; 0 0 pound; 0 Может быть условный локальный минимум, требуется дополнительное исследование
4 lt; 0 0 lt; 0 Может быть условный локальный максимум, требуется дополнительное исследование
5 = 0 0 lt; 0 Требуется дополнительное исследование
6 = 0 0 lt; 0 Требуется дополнительное исследование
7 0 lt;; 0 Нет экстремума
8 ^0 0 lt; 0 Нет экстремума

условный локальный минимум.

Если с121^х*Д*)lt;0, то в точке х* - условный

локальный максимум.

Если достаточные условия первого и второго порядка не выполняются, следует проверить выполнение необходимых условий второго порядка (утверждение 3.6), следуя аналогичной процедуре. Если они выполняются, то

требуется дополнительное исследование, а если нет, то в точке х* нет условного экстремума.

Шаг 5. Вычислить значения функции в точках условного экстремума. Условия экстремума в задаче (3.15) приведены в табл. 3.2, 3.3.

Пример 3.12. Найти условный экстремум в задаче /(х) = хI + х2 -#9658; ех1т,

Я,(х) = х, +х2-2й0.

? 1. Составим обобщенную функцию Лагранжа:

+*2) + ^1(*1 +х2 “2).

2. Выпишем необходимые условия первого порядка: а^хДоД,) + =0 а^хДоД^ =0.

дхх дх2

б) хх + х2 - 2 lt; 0;

в) Хх gt; 0 (для минимума), Хх lt; 0 (для максимума);

г) Цх, +х2-2) = 0.

3. Решим систему для двух случаев.

В первом случае Х0 = 0. Тогда из условия “а” следует, что Хх = 0. Это про­тиворечит требованию утверждения 3.4 о существовании ненулевого вектора

(*оД)Г-

Во втором случае А,0 * 0. Поделим систему, приведенную в п.2, на А,0 и

заменим — на Хх. Обобщенная функция Лагранжа при этом заменяется клас­се

сической:

а)pound;Х(хД1}= 0 Э1(хД,) = 2 х =0

1 1 эх2

б) X] + х2 - 2 lt; 0 ;

в) Хх pound; 0 (для минимума), Хх lt; 0 (для максимума);

г) А.,(х, + х2 - 2) = 0.

Из условия “г” дополняющей нежесткости следует:

1) Хх = 0 (фактически решается задача поиска безусловного экстремума). Тогда х,* = х2 = 0, Х\ = 0 и условие “б” выполняется. Выполняются необходимые условия и для минимума, и для максимума (строки 1 и 2 в табл. 3.2).

2) Хх ф 0. Тогда из системы

хх + х2 - 2 = 0, 2х! +Хх =0, 2х2 + Хх = 0

получаем:х{ =*2=1; ^ = -2. Так как Х\ lt; О, то необходимое условие минимума не выполняется (в точке (1,1)Г нет минимума), но выполняется необходимое ус­ловие максимума. Таким образом, имеем две условно-стационарные точки.

4. Проверим выполнение достаточных условий экстремума.

В точке х*=(0,0)г ограничение не является активным, так как ^(х*) = -2lt;0, поэтому достаточные условия первого порядка не удовлетворяют­ся (строки 1 и 2 в табл. 3.2). Проверим условия второго порядка. Так как ё2ь[х*= + 2lt;Ьс\gt;Ъ при Лс*0, то в точке х*=(0,0)г регулярный ло­

кальный условный минимум (строка 1 в табл. 3.3), совпадающий в данной задаче с безусловным (рис. 3.10). С другой стороны, функция /(*) выпуклая (см. при­мер 1.19) и множество X также выпуклое (см. определение 1.7 и пример 1.16). Поэтому в точке х* = (0,0)Т достигается глобальный условный минимум (п. 9

замечаний 3.4), а достаточные условия первого и второго порядка можно было и не проверять.

т

В точке х* -(1,1) ограничение является активным, но / = 1 lt; л = 2, по­этому достаточное условие первого порядка не выполняется. Проверим условие второго порядка. Имеем

lt;/2pound;(х*Д*) = 2 lt;1х1 + 2{1х1, dgl^x*} = dxx + (Ьс2=0 =gt; сamp;1 = -сЬс2.

Следовательно, (12Цх*уХ*} = 4ёх2 gt; 0 при lt;2х2 * 0. Так как в этой точке

Х\ = -2 lt; 0, то достаточное условие максимума не выполняется (строка 2 в табл. 3.3). Проверим необходимое условие максимума второго порядка. Так как (12Цх*,Х*} = 4(Ьс2 gt; 0 при любых (Ьс2у то необходимое условие максимума не вы­полняется (строка 4 в табл. 3.3), поэтому в точке х* = (1,1)^ максимума нет.

5. Вычислим значение функции в точке условного минимума: /(**) = 0. #9632;

Пример 3.13. Найти условный экстремум в задаче /(х) = XI + х2 еЛг,

л(*) = *?+*! -1^0.

? 1. Составим обобщенную функцию Лагранжа:

pound;(дсД0,А,1) = А.о(*1 + х2) + Х^х2 + х2 - 1).

2. Выпишем необходимые условия первого порядка:

а) д1кpound;*gt;Ь)ш\0+2х1\1 =0, [1]^*±$й = Хо+2х2\1 = 0;

б) х2 + х2 -1 lt; 0;

в) X, gt; 0 (для минимума), Х{ lt; 0 (для максимума);

г) Х^х2 + х2 -1) = 0.

3. Решим систему для двух случаев.

В первом случае Х0 = 0. Тогда согласно утверждению 3.4 требуется, чтобы А.] ф 0. При этом х\ = х2 = 0 и не удовлетворяется условие “г” дополняющей не- жесткости.

Во втором случае Х0 * 0. Поделим уравнения системы, приведенной в п.2, на Х0 и заменим на Х\:

а) pound;^А) = 1 + 2х,Х| =0, аХ(х’Ач] = 1 + 2х2Х1 =0;

дх2

б) х2 + х2 -1 lt; 0;

в) Ху gt; 0 (для минимума), lt; 0 (для максимума);

г) Х^х2 + х2 -1) = 0.

Из условия “г” дополняющей нежесткости следуют два варианта:

1) X] =0. Тогда условие “а” не выполняется;

2) X! * 0. Тогда х2 + х2 -1 = 0 и система имеет два решения (рис. 3.11):

Л Л

точка А : х{ = х2 = ——, Х^ = — (в точке А может быть минимум);

Л Л

точка В: х{ = х2 = —, X*] = —— (в точке В может быть максимум).

Рис. 3.11

регулярный локальный условный максимум (строка 2 в табл. 3.3). С другой сто­роны, функции /(х) и -/(*) = -X! -х2 - выпуклые и ограничение выпуклое (см.

определения 1.7, 1.8 и пример 1.16), поэтому в точках А и В достигается глобаль­ный экстремум (п. 9 замечаний 3.4). Достаточные условия первого и второго по­рядка проверялись для демонстрации методики.

5. Вычислим значение целевой функции в точках условного экстремума: /{А) = -Л, /(2?) = л/2. Я

Пример 3.14. Найти условный максимум в задаче

/(х) = X! шах,

pound;,(х) = -Х2 lt; О,

*2(*) = *2-(1-*,)3*0- ? 1. Составим обобщенную функцию Лагранжа:

Ь(х,Х0Д1Л2) = ^0*1 + ^1(_дс2) + ^2^2 “0 “*1)3]*

2. Выпишем необходимые условия максимума первого порядка:

а) д1(Х,Х°’Х) = Х0+3\2(1-х1)2 =0, ?Ах.’Ь’Х1 = -х1+х2 = 0;

дх\ д х2

б) -х2 lt;0, х2 -(1 -х^3 pound; 0;

в) х{ lt;о, х2

г) ^(-Хг) = 0, Х.2|х2 -(1 - Х])^ = 0.

3. Решим систему для двух случаев.

В первом случае Х0 = 0, тогда х\ = 1, а х2 = 0. При этом Х{ = А,2 lt; 0, на­пример, Х\ = Х*2 = -1. Получили условно-стационарную точку х* = (1,0)ГД*0 = 0.

На рис. 3.12 показано, что в точке х* = (1,0)Г достигается нерегулярный локальный и глобальный максимум. В ней условие линейной независимости гра­диентов ?pound;,(*•) = (0,-1)Г, Уpound;2(х*) = (0Д)7' не выполняется (см. пример 3.4), и ан­тиградиент целевой функции не может быть представлен в виде неположитель­ной линейной комбинации градиентов активных ограничений. Условие “а” вы­полняется только при А, о = 0. Покажем это.

Рис. 3.12
л*)-!

/М-1

Во втором случае Х0 * 0. Тогда поделим уравнения системы, приведенной в п.2, на Х0 и заменим — на ^, — на Х2. Имеем:

1 + ЗХ2(1 - ЛГХ)2 = О;

—Х| + Х2 = 0 ;

-х2 pound; 0, х2-(1-ДС[)3 ^0;

А-1 lt; 0, Х2 ^ 0;

^2^2 - (! - *і)3] = 0 •

Рассмотрим четыре варианта выполнения условия дополняющей нежестко-

сти:

1) \{ = Х2 = 0. Из первого уравнения следует, что система несовместна;

2) Хх * 0, Х2 = 0. Из первого уравнения также следует, что система несо­вместна;

3) Х-1 = 0, Х2 * 0. Из второго уравнения получаем, что Хх = Х2 = 0, т.е. име­ется противоречие;

4) Х\ ф 0, Х2 * 0. Тогда х2 - 0, х{ = 1 и первое уравнение не удовлетворя­ется.

Новых условно-стационарных точек не найдено. Поэтому в задаче имеется только одна точка х* = (1,0)Г нерегулярного максимума с /(**) = 1. #9632;

Пример 3.15. Найти условный экстремум в задаче

/(*) = (*1 “ 2)2 + (*2 - 3)2 -#9658; ех*г»

^Г|(дс) = X!2 + х2 ~ 52 lt; 0.

? 1. Составим обобщенную функцию Ла1ранжа:

ДдсДоАО = ^о|(х1 “ 2)2 + (*2 “ 3)2] + + х2 - 52|.

2. Выпишем необходимые условия первого порядка:

а)pound;^(^ДоД^_ 2х0(х,-2)+2Х1х, = 0, дpound;(хgt;хоХ) ж 2Х0{х2 -3)+ 23.,х2 =0; ах, вх2

б) х2 + х2 - 52 lt; 0;

в) Х{ gt; 0 (для минимума), Х{ lt; 0 (для максимума);

г) А^х2 + х22 -52) = 0.

3. Решим систему для двух случаев.

В первом случае Х0 - 0. Тогда Х{ * 0 согласно утверждению 3.4. Поэтому х, = 0, х2 = 0 и не выполняется условие “г” дополняющей нежесткости.

Во втором случае Аlt;о * 0. Поделим уравнения системы, приведенной в п.2,

л ^1

на А,0 и заменим — на А,1:

А-о

а) ~^*Д^ = 2(*1 ~2)+ 2X1X1 =0, д^ = 2(х2 -3) + 23ц х2 = 0;

б) х2 + х2 - 52 pound; 0;

в) Ху gt; 0 (для минимума), А^ lt; 0 (для максимума);

г) А^х2 + х2 -52) = 0.

Рассмотрим два варианта выполнения условия “г” :

1) А.| = 0. Тогда Х| = 2,х2 = 3 и выполняются необходимые условия и для минимума, и для максимума (строки 1 и 2 в табл. 3.2). Имеем условно­стационарную точку А: X!* = 2, х2 = 3, А.} = 0;

2) А,] * 0. Тогда х2 + х2 - 52 = 0 и система имеет решение:

1 3

точка В : = 4, х\ - 6, Х\ = ; точка С : х{ = - 4, х2 = - 6, А.*| = -—.

Так как Х\ lt; 0 в обеих точках, то в них минимума нет, но может быть максимум.

4. Проверим достаточные условия экстремума. В обеих условно­стационарных точках ограничение превращается в равенство, т.е. активно. Так

как число активных ограничений / = 1 lt; 2 = л, то условия первого порядка не

выполняются. Так как функция -/(х) = -{хх - 2)2 - (х2 - З)2 не является выпук­лой (см. определение 1.8), то необходимые условия не являются достаточными (п.9 замечаний 3.4). Проверим условия второго порядка:

lt;/2pound;(х* Х)=(2 + 2Г,) йЬс,2 + (2 + 2Х\) (Ьс%.

В точке А ограничение не является активным. Так как Х\ = 0, то + 2с1х2 gt; 0 при lt;!хф 0. Поэтому в точке А - условный локаль­ный минимум (строка 1 в табл. 3.3). Так как целевая функция /(х) выпуклая и

множество допустимых решений выпукло (рис. 3.13), то можно заключить, что в данном случае необходимое условие минимума является достаточным. В точке А - глобальный минимум (п.9 замечаний 3.4). В точках В и С ограничение активно.

Поэтому dgx[x*^ = 2х\ (Ьс{ + 2*2 сЫ2 =0. В точках В и С выполняется

(1х\ =-*^Лс2. Так как ^2pound;(Я) = |^--^^х^ +lt;**2 gt;0 ПРИ ^х2 *0, а Х\ = lt; 0,

то достаточные условия максимума не выполняются (строка 2 в табл. 3.3). Так как й21\В) gt; 0 при всех с1х2) то и необходимое условие максимума второго по­рядка в точке В не выполняется (строка 4 в табл. 3.3). Поэтому в ней нет экстре-

мума. Так как с12Ь(С)= -

12

-(Ьс2 lt; 0 при йх2 * 0, то достаточные усло­

вия максимума выполняются. В точке С условный локальный максимум (строка 2 в табл. 3.3).

5. Вычислим значения функции в точках экстремума /(А) = 0,/(С) = 117. #9632;

Пример 3.16. Найти условный экстремум в задаче /(х) = (х| - а)2 + х2 -#9658; ех!г,

pound;!(*) = *?+*2 —1*0,

amp;(*) = ~*1 * 0

при а = 2, а = 1, а = ~, а = 0, а = -1.

? 1. Составим обобщенную функцию Лагранжа:

1(х, Х0, X) = х0[(*1 - а)2 + *2] + Ц*? + х\ -1) + Х2(-Х1).

2. Выпишем необходимые условия экстремума второго порядка:

з) —lt;‘*ДоД) = 2Х0(*1 - о)+ 2Х,х, — А-2 = 0, = 2Х0Х2 + 2Х,х2 = 0;

д Ху д х2

б) Ху + х2 -1 lt; 0, -X! lt; 0;

в) Ху gt; О, Х2 gt; 0 (для минимума); Х{ lt; О, Х2 lt; 0 (для максимума);

г) Ху\х} + х\ - 1) = О, Х.2(-*1) = °-

3. Решим систему для двух случаев.

В первом случае А,0 = 0. Тогда из первых двух уравнений следует:

2ХуХу — Х2 — 0,

2,ХуХ2 = 0.

Рассмотрим четыре варианта выполнения условия “г”:

1) Ху = О, Х2 = 0. Этот вариант противоречит утверждению 3.4;

2) А.1 = 0, Х2 ф 0. Из первого соотношения Х2 = 0, т.е. имеется противоре­чие;

3) Ху ф 0, Х2 = 0. Тогда хх = х2 =0 и не выполняется первое из условий дополняющей нежесткости “г”;

4) Ху *0, Х2 *0. Тогда х{ =0, а х2 =±1. При этом не удовлетворяется второе уравнение из условий “а”.

Во втором случае Х0 * 0. Поделим уравнения системы, приведенной в п.2, X X

на Х0 и заменим — на Ху, — на Х2. Получим:

А.0 А,0

з) = 2(х, -а)+2Х,х, -Х2 =0, = 2х2 + 2Х,х2 =0;

д Ху дх2

б) Ху + х2 -1 lt; 0, -Ху lt; 0;

в) Ху pound; 0, Х2 pound; 0 (для минимума); Х{ й 0, Х2 pound; 0 (для максимума);

г) Ху(х? + х\ -1] = 0, Х2(-Ху) = 0.

Рассмотрим четыре варианта удовлетворения условия “г” :

1) Ху = 0, Х2 = 0. Получаем условно-стационарную точку А :

х{ = а, х2 = 0, Х\ = 0, А.*2 = 0;

2) Ху = 0, Х2*0. Тогда ^ = 0,х2 = 0, а Х2 = -2а. Получаем условно-:

стационарную точку В: х\ = 0, х2 = 0, Х\ = О, Х*2 = -2а;

3) Ху ф 0, Х2= 0. Тогда

Ху + х2 -1 = 0, 2{ху - а) + 2ХуХу = 0, 2х2(1 + = 0.

Из третьего соотношения имеем: х2 = 0 или Ху = -1. При х2 = 0 получаем:

^1 = ±1. Ограничению удовлетворяет х1 =1. Тогда Ху =а-1. Найдена условна-:

стационарная точка С : х у = 1, х2 = 0, Х\ = а -1, Х*2 = 0. При Х\ = -1 параметр а

должен быть нулевым. Тогда имеется бесконечное множество условно-стацио­нарных точек В , лежащих на полуокружности (рис. 3.14, г);

4) *0, А.2*0. Тогда ^=0, а х2 = ±1. При этом ^=-1, а А,2 = -2а.

Получаем еще две условно-стационарные точки:

Е Х\ = 0, х2 =1, = —1, А»2 = —2а/*: X] = 0, х2 = —1, = —1, Я.2 = —2а.

Таким образом, имеется шесть условно-стационарных точек.

Рис. 3.14

4. Проверим достаточные условия экстремума для различных значений па­раметра а (рис. 3.14, а - д).

Исследуем точку А : х\ = а, х2 = 0, Х\ = 0, Х\ = 0. При а = 2 точка А не лежит в множестве допустимых решений, так как х{ =2, х2 = 0. При а = 1 име­ем: х,* =1, х\ = 0, Х\ = \*2 = 0. В точке А активно первое ограничение. Так как число активных ограничений / = 1 lt; п = 2, то достаточные условия первого по­рядка не выполняются. Проверим условия второго порядка:

lt;1гЦА) = (2 + 2X1 )lt;*с,2 +(2 + 2Х*,)lt;pound;е| = 2(1х} + 2lt;3х\;

1 И) = 2хГ + 2х2 Лс2 = 2Лс| = 0.

Получаем В2ЦЛ) = 2дх\ gt; 0 при сЬс2 * 0. Поэтому в точке А - условный локаль­ный минимум (строка 1 в табл. 3.3). При а = ^ имеем: х[ = х2 =0,

X] = Я.2 = 0. Активных ограничений нет. Так как (12Ь(А) = 2е!х2 + 2(1x1 gt; 0 при с!хф 0, то в точке А - условный локальный минимум (строка 1 в табл. 3.3). При а = 0 имеем: х\ = 0, х2 = 0, Х\ = Х*2 = 0. В точке А активно второе ограничение:

ё2Ь(А) = 2с1х2 + 2(1х2;

^2{А)^'^Х\ =0.

Так как с12ЦА) = 2(1х2 gt; 0 при lt;Ьс2ф 0, то в точке А - условный локальный ми­нимум. При а = -1 имеем: х\ = -1, х2 = 0, т.е. точка А не лежит в множестве до­пустимых решений. Так как целевая функция выпуклая и множество допустимых

решений X выпукло, то в случаях а = 1; 0 необходимые условия минимума

являются и достаточными, а в точке А достигается глобальный минимум (п. 9 замечаний 3.4).

Исследуем точку В : х* = 0, х2 = 0, Х\ - 0, Х*2 = -2а * 0. Так как в этой точке активно только второе ограничение, то достаточные условия первого по­рядка не выполняются. Проверим условия второго порядка:

lt;12ЦВ) = (2 + 2Х.*)аЬс,2 +(2 + 2Х*,)аЬс| = 2lt;amp;,2 + 2Лх\;

4В2(В) = “amp;С\ =0.

Отсюда (12Ь{В) = 2с1х2 gt; 0 при йх2* 0. Если а = 2,1,-^, то ЯГ2=-2аlt;0 и не

удовлетворяются ни достаточные условия второго порядка, ни необходимые (строки 2 и 4 в табл. 3.3). Поэтому в точке В для этих значений параметра нет

экстремума. Если а = 0, то Х*2 = 0, что противоречит условию Х*2 * 0. Если а = -1, то Х*2 gt; 0, и в точке В удовлетворяются достаточные условия локального минимума (строка 1 в табл. 3.3). Так как /(*) и множество X выпуклые, то в точке В при а = -1 достигается глобальный минимум (п. 9 замечаний 3.4).

Исследуем точку С : х\ = 1, х2 = 0, Х\ = а -1 * 0, Х*2 = 0. При а = 2 получа­ем Х\ = 1 gt; 0. Активно первое ограничение:

lt;/21(С) = (2 + 2Х’х | lt;pound;е2 +(2 + 2Х*,)ййс| =4lt;amp;,2 + 4Лс|;

йВ\{С) = 2*1 + 2*2 = 2^| = 0.

Так как с12Ь{С) = 4^2 gt; 0 при йх2 ф 0, то в точке С - локальный условный ми­нимум (строка 1 в табл. 3.3). Так как /(*) и множество Xвыпуклые, то в точке С - одновременно глобальный минимум (п. 9 замечаний 3.4). При а = 1 получаем

А,*2 = 0. Активно первое ограничение:

lt;12ЦС) = (2 + 2Х\) аЬс? + (2 + 2Х\) lt;pound;е| = аЬс,2 + lt;pound;с|;

~ 2*Г 4*\ + 2x5 4х2 = 2^ = 0.

Так как с12Ь(С) = сЬс2 gt; 0, но X,* =-~lt;0, то не выполняются ни достаточ­

ные, ни необходимые условия второго порядка (строки 2 и 4 в табл. 3.3). В точке С нет экстремума. При а = 0 имеем Х\ = -1 lt; О, Х*2 = 0 и ё2ЦС) = (2 + 2^lt;Ьс2 + ^2 + 2А,* |сЬс2 #9632; 0 для любых дх . Поэтому требуется допол­нительное исследование (строка 6 в табл. 3.3) на наличие максимума, так как не­обходимое условие максимума первого порядка выполняется. Рис. 3.14, г пока­зывает, что в точке С - условный максимум (глобальный и локальный). При а = -1 получаем Х\ = -2 lt; О, Х*2 = 0 и

(12ь(с) = (2 + 2Х\) сЬс? + (2 + 2Х\ lt;1x1;

= 2х\ с6с| + 2*2 amp;сг = 2(Ьс{ = 0.

Так как с12Ь(С) = -amp;х\ lt; 0 при дх2 * 0, то в точке С - условный локальный максимум (строка 2 в табл. 3.3).

Исследуем множество 2) при а = 0. При этом Х\ = -1, Х*2 = 0. Так как с!2Д/)) = (2 + 2Х\)сЬс2 +(2 + 2Х\)с1х2 #9632; 0, то требуется дополнительное исследова­ние на наличие условного максимума (строка 6 в табл. 3.3). Рис. 3.14, г показы­вает, что на множестве В достигается глобальный максимум.

Исследуем точки Ей Е х{ = 0,х2 = ±1, Х\ = -1, Х*2 = -2а * 0. При а = 2,1,^

получаем X.*! = -1 lt; 0, Я,*2 = -4,- 2,-1 lt; 0. В точках Е и Е два активных ограниче­ния: / = 2 = п = 2. Так как lt; 0 и У?2 lt; 0, то выполняются достаточные условия максимума первого порядка (строка 2 в табл. 3.2). В точках Е и Е - локальный условный максимум. При а = 0 получаем Х*2 = 0, что противоречит условию Х*2 ф0. При а = -1 получаем Х\ = -1 lt;0, Х*2 = 2 gt;0. Так как не выполняются необходимые условия минимума и максимума, то в точках Ей Енет экстремума (строки 1 и 2 в табл. 3.2).

5. Вычислим значения функции в точках экстремума при различных а (рис. 3.14):

а = 2: /(С) = 1 ,/(pound;) = /(/#9632;) = 5; а = 1: /(А) = 0,/{Е) = /(/•) = 2;

а = ±: /(Л) = 0,/(pound;)=/(^)Л; а = 0: /(Л) = 0,/(Д) = 1;

а = -1: /(В) = 1,/(С) = 4. #9632;

Пример 3.17. Найти условный минимум в задаче /(х) = х2 + (х2 - 2)2 -* min, ft(x) = x?+x|-IsO,

Ых) = 5 °.

gj(x) = -Xj S 0.

? 1. Составим обобщенную функцию Лагранжа:

pound;(х, Х0,Я.) = А.0|х2 + (х2 “ 2)2J + A.i|x2 + х2 - lj + A.2(-Xi) + X3(-x2) .

2. Выпишем необходимые условия минимума первого порядка:

а) дpound;(*’*оЛ) = 2X()Xi + 2X|Xi _ Х2 = о (

— ^= 2^о(х2 —2)+ 2Xjx2 - Х_з = 0;

б) х2 + х2 -1 pound; 0, -Xi lt; 0, -х2 lt; 0;

в) A-i gt; 0, Х2 ^ 0, А,3 gt; 0;

г) Х^х,2 + xf -1) = 0, Х2(-х,) = 0, Х3(-х2) = 0.

3. Решим систему для двух случаев.

В первом случае Х0 = 0. Тогда условия “а” запишутся в виде

2Х]Х} — А2 = 0 j 2A,jX2 — А.3 =0.

Рассмотрим восемь вариантов выполнения условий “г” дополняющей не- жесткости:

1) Х\ = 0, А.2 = 0, А,3 = 0. При этом не удовлетворяется требование утвер­ждения 3.4;

2) Х{ * 0, Х2 - 0, А.3 = 0. Тогда х* = х2 = 0 из условия “а”, но первое усло­вие дополняющей нежесткости не удовлетворяется;

3) А-1 = 0, Х2 *0, Х3 = 0. Тогда из первого уравнения в условии “а” имеем Х2 = 0, т.е. имеется противоречие;

4) Xi = 0, А,2 = 0, Х3 * 0. Тогда из второго уравнения в условии “а” имеем А,3 = 0, т.е. также имеется противоречие;

5) Xj * 0, Я.2 * 0, А.3 = 0. Тогда Xj = 0 и из первого уравнения в условии “а” имеем А,2 = 0, т.е. имеется противоречие;

6) Х\ * 0, А,2 = 0, А.3 ф 0. Тогда х2 = 0 и из второго уравнения в условии “а” имеем А,3 = 0, т.е. также имеется противоречие;

1) Х\ = 0Д2 * 0 Д3 * 0. Тогда не выполняются оба уравнения в условии “а”;

8) Хх * 0, А.2 * 0, А,3 ф 0. Тогда уравнения *! = х2 = 0, х2 + х2 -1 = 0, сле­дующие из условия “г”, вместе не выполняются.

Условно-стационарных точек пока не найдено.

Во втором случае А.0 * 0. Поделим уравнения системы, приведенной в п.2,

А. А. А»

на А-о и заменим — на А.!, — на Х2, — на А.3. Получаем:

Аlt;о А-о А.©

а) = 2х, + 2Х,х,-Х2 = 0, д1(х’Х) = 2(х2 -2)+2Х1Х2-Хг = 0;

дх\ дХ2

б) х2 + х2 -1 pound; 0, -*1 pound; 0, -х2 ^ 0;

в) А., йО, Х2 pound;0, Х3 pound;0;

г) Х^х,2 + х| -1) = 0, Х2(-Х[) = 0, Х3(-х2) = 0.

Рассмотрим восемь вариантов выполнения условий дополняющей нежесткости:

1) А.] = 0, Х2 - 0gt; А.3 = 0. Тогда х1 = 0, х2 = 2 и не выполняется первое ог­раничение в условии “б”;

2) А,| ф 0, \2 = 0, А,3 = 0. Тогда

х\ +х% -1 = 0,

2^1(1 + А^) = 0,

2(х2 -2) + 2А.1х2 =0.

Если А-1 = -1, то третье уравнение не удовлетворяется. Если х{ = 0, то х2 = ±1. Ограничениям в условии “б” удовлетворяет х2 = 1. При этом А-1 = 1. Получили условно-стационарную точку А: = 0, х2 = 1, А.} = 1, Х*2 = 0, А.3 = 0;

3) А.1 = 0, А.2 ф 0, А.3 = 0. Тогда

*,=0,

2^1 — А2 = 0,

2 (х2 - 2) = 0.

Получаем Х2 = 2х, = 0, что противоречит условию Х2 * 0;

4) X] = 0, Х2 = 0, Х3 * 0. Тогда

*2 = 0.

2х, =0,

2(х2 - 2) - Х3 = 0.

Получаем А.3 = - 4 lt; 0, что противоречит условию “в”;

5) А.1 ф 0, А,2 ф 0, А.3 = 0. Тогда

х2 + х2 -1 = 0,

*1=0,

2x1 + 2А-1Х| — А.2 = 0,

2 (х2 — 2) + 2А.}Х2 = 0.

Из третьего соотношения следует, что А,2 = 0, т.е. имеется противоречие;

6) А.! ф 0, А.2 = 0, А,3 * 0. Тогда

х2 + х2 -1 = 0, х2 = 0,

2x1 2А.|Х| = 0,

2 (х2 — 2) + 2А»1Х2 — А,3 = 0.

7) А,! =0, А.3 * 0. Тогда

XI = х2 = 0,

2х\ — А, 2 = 0,

2{х 2 — 2) — А-з = 0.

Из второго соотношения следует, что Х2 = 0. Это противоречит условию Х2 * 0;

8) А«! ф 0, А,2 * 0, А,3*0. Тогда х2+х2-\ = Ъ. Из условия “г” следует: *1 = 0,х2 =0. Эта система несовместна.

Ы*)=-

pound;г(*) = -*1=0

Рис. 3.15

4. Проверим достаточные условия минимума. В точке А имеются два ак­тивных ограничения, т.е. / = 2 = п = 2 (рис. 3.15). Так как А.} = 1 gt; 0, А.2 = 0, то

достаточные условия минимума первого порядка не выполняются (строка 1 в табл. 3.2) ввиду того, что требуется строгая положительность соответствующих множителей Лагранжа. Проверим условия второго порядка:

lt;12ЦА) = (2 + 2Х’,|Л,2 +(2 + 2 .

Так как в точке два активных ограничения и для одного из них Х\ gt;0, а для другого А.2 = 0, то применим условия (3.18) (строка 1 в табл. 3.3):

(Л) = 2х\ (іх{ + 2х\ іїх2 = 2(іх2 =0, А.^ gt; 0; ^2{А) ~-ёхх lt;0, А*2 = 0.

В результате с!21(А) = 4сіх2 gt; 0 при pound; 0 и (Ьс{ ф 0. Поэтому в точке А - ло­кальный условный минимум (строка 1 в табл. 3.3). С другой стороны, целевая функция и множество допустимых решений выпуклые. Поэтому в точке А дос­тигается глобальный минимум (п. 9 замечаний 3.4).

5. Вычислим значение функции в точке глобального минимума: /(Л) = 1. #9632;

Пример 3.18. Найти условный минимум в задаче /(х) = Ху + х2 + 2х3 тт,

^1(х) = -х1 -х2-х3 +1^0,

pound;2(*) = -*1 “[2]*2 +3^0.

? 1. Составим обобщенную функцию Лагранжа:

pound;(х, А,0 , А.) = А^х? + х2 + 2х31 + ^(-Х! - х2 - х3 +1) + А.2(-Х| - Зх2 + 3).

2. Выпишем необходимые условия первого порядка:

а) = 2Х0Х1 -\1-Х2^0, ^ = 2Х0х2-\1 -ЗХ2 = 0,

а/'(у-йД) = 4Мз-Х1=0;

О х3

б) -X! - х2 - х3 +1 lt; 0, —Х| — Зх2 +3^0;

в) А., gt;0, Х2gt; 0;

г) Ху(-Ху - х2 -х3 +1) = 0, А.2(-Х1 - Зх2 + 3) = 0.

3. Решим систему для двух случаев.

В первом случае А.0 = 0. Тогда Ху = 0 и А,2 = 0, что противоречит утвержде­нию 3.4.

Во втором случае Х0 ф 0. Поделим уравнения системы, приведенные в п.2, X X

на Х0 и заменим — на Ху, — на Х2. Условия “а” запишутся в виде:

А»о А.0

^^=2х,-X,-Х.2 =0, ---(*^ = 2х2 - X, - ЗХ2 = 0, 8^дс’Х) = 4хз-Х| =0. дх{ 1 1 2 дх2 дх3

Рассмотрим четыре варианта удовлетворения условий “г” дополняющей нежесткости:

1) Х{ = 0, А.2 = 0. Тогда из условия “а” следует: X! = х2 = х3 = 0. При этом ограничения “б” не выполняются;

2) А-! ф 0, А.2 = 0. Тогда ^(х) = 0 и справедливы уравнения:

-XI - х2 - х3 +1 = 0,

2x1 ~ А.] = 0 =gt; XI = ,

2х2-Х, =0=gt;х2=^-,

4х3 - Я., =0 =gt;х3 = ^-.

4 2 1

Отсюда Ху = — gt; 0, а ^ = х2 = —,х3 = —. Второе неравенство в условии “б” не

2 6 7

выполняется, так как - —- —+ 3 = — gt; 0;

-X! -Зх2+3 = 0,

2^1 -Я.2 = 0 =gt; х, = -^-,

2х2 - ЗА,2 = 0 =gt; х2

4х3 =0 =gt; х3 = 0.

3 3 9

В результате Х2 = - gt; 0 и XI = —, х2 =—» *з = 0. Первое неравенство в условии

3 9 1

“б” в данной точке выполняется, так как------------------- +1 = — lt;0. Имеем условно^

10 10 5

3 9' 3

стационарную точку А: =—, х\ =—, х3 = 0, Х\ = 0, Х*2 = —;

4) Х{ ф 0, Х2 * 0. Тогда ^(х) = 0, ЯгМ = 0 и справедливы равенства:

—XI - х2 - х3 +1 = 0,

-X! - Зх2 +3 = 0,

2х! - А.1 - Х2 = 0 =gt; XI = -1 ^ 2-,

2х2-Х1-ЗХ2^0=gt; х2=^^-,

4х3 -X, =0 =gt; х3 =

Подставляя в первые два соотношения, получаем:

— 5Аlt;1 — 8Х-2 +4 = 0,

— 2Х\ — 5Х-2 +3 = 0.

4 7

Отсюда Х{ = —-, Х2 = —. Так как Х{ lt; 0, то условие “в” не выполняется.

4. Проверим достаточные условия экстремума. В точке А одно активное ог­раничение, так как g2(A) = 0. Поэтому / = 1 lt; л = 3 и достаточное условие ми­нимума первого порядка не выполняется (строка 1 в табл. 3.2). Поэтому прове­рим достаточные условия второго порядка:

pound;!2ЦА) = 2 (Ьс2 + 2с1х2 + 4 сЬс2, dg2{A) = -с1х{ - Ъдх2 = 0.

Отсюда сЬс1 = -Ъс1х2 и lt;12Ь(А)= 2(- 3с1х2)2 + 2с!х2 + 4Ак2 gt; 0 при йбс * 0. Поэтому в точке А - условный локальный минимум (строка 1 в табл. 3.3). С другой сторо­ны, целевая функция и функции выпуклые, так как ограничения ли­

Н(х) =
0 2 0 0 0 4
gt; 0, потому что А| = 2 gt; О, Д2 = 4 gt; О, Д3 = 16 gt; 0 (см. п. 3 заме-
чаний 1.4). Поэтому в точке А - глобальный минимум (п. 9 замечаний 3.4).

5. Вычислим значение функции в точке условного минимума:

/(Л) = — + — + 0= —. #9632; у / 100 100 10

нейные и для них Н(х) = 0, а для целевой функции матрица Гессе (2 0 (Л

Пример 3.19. Найти условный минимум в задаче

/(х) = JC| —gt; min,

SiM = *2 -•*? g2(x) = -x2-xf uuml;O, ft(*) = x? + x\ -1pound; 0.

? 1. Составим обобщенную функцию Лагранжа:

Z,(x, А.0, A.) = Mi + h(x2 - *i) + - *?) + **(*? + x2 - !)•

2. Выпишем необходимые условия первого порядка:

а) dL(xgt;X0gt;X) ш Х() _ 2Х\Х\ - ЗХ2х,2 + 2Х3х, = 0,

дх1

= х, - х2 + 2х3х2 = о;

дх2

б)x2-Xilt;0, -х2-х*pound;0, х2+х2-1pound;0;

в) X] ^ 0, А.2 0, А,3 pound;0;

г) Х,(х2-Xj3) = 0, Х2(-х2-х,3) = 0, X3(x? + xf-l) = 0.

3. Решим систему для двух случаев.

В первом случае А,0 = 0. Рассмотрим восемь вариантов удовлетворения ус­ловий “г” дополняющей нежесткости:

1) А.| =0, А,2 = 0, А.3 =0. Не удовлетворяется требование утверждения 3.4 о существовании ненулевого вектора (a.*0,A.*J;

2) Х| * 0, А.2 = 0, А,3 = 0. Тогда

х2-х\ =0,

—ЗА^х2 = 0,

^ =0.

Имеется противоречие, так как Х\ * 0;

3) А.! =0, А.2 *0, А,3 =0. Тогда

-х2-х,3 =0,

-ЗХ2х2 = 0,

—А, 2 = 0.

Имеется противоречие, так как А.2 * 0;

4) А.! = 0, А.2 = 0, А,3 * 0. Тогда

2А.3Х) = 0,

2А,3х2 = 0, х22 + х2 -1 = 0.

Отсюда следует, что хх = х2 = 0, но при этом не удовлетворяется третье уравне­ние;

5) A.J ф 0, А.2 ф 0, А,э = 0. Тогда

Х2 — *1 =0,

-х2-х\ =0,

—ЗА-рс^ “ *= 0,

Аlt;1 “ Х2 = 0.

Система удовлетворяется при хх = х2 = 0 и любых Х1 = Х2 gt; 0, например, равных единице. Имеем условно-стационарную точку А: х{ = х\ = 0, Х*0 = 0, ^ = Х*2 = 1;

6) А.! * 0, Х2 = 0, Х3 * 0. Тогда

х2~х\ =0» х2 + х\ -1 = 0,

—ЪХ\Х\ + 2X3X1 = 0,

Х1 + 2X3X2 = 0.

Получаем X! = -2Х3х2 = -2Х3Х?. После подстановки в третье уравнение имеем 6Х3 X!5 + 2Х3 X! = 2Х3 х^Зх4 +1) = 0. Так как Х3 * 0, то X! = 0. Тогда х2 = 0 и не

удовлетворяется второе уравнение;

7) X! = 0, Х2 * 0, Х3 ф 0. Тогда

-х2 -X!3 =0,

X!2 + х2 - 1 = 0,

—ЗХ2х2 +2X3X1 =0,

—Х2 + 2X3X2 = о.

Получаем Х2 = 2Х3х2 =-2Х3Х13. Из третьего уравнения имеем 6Х3 XI5 + 2Х3 XI = 2Х3 х^Зх4 +1) = 0. Так как Х3 ф 0, то Х1 = 0 и х2 = 0. При этом

не удовлетворяется второе уравнение;

8) Х1 ф 0, Х2 * 0, Х3 ф 0. Из условия “г” следует система

х2~х\ =°gt;

-х2 - х3 = 0,

Х\ + х2 -1 = 0,

которая несовместна (рис. 3.16).

Во втором случае Х0 * 0. Поделим уравнения системы, приведенной в п.2,

XXX на Х0, заменяя — на Хь — на Х2, — на Х3. При этом соотношения “б”-“г”

Хо Хо Х0

не изменяются, а условие “а” записывается в форме

1 — ЗХ1Х12 — ЗХ2х2 + 2X3X1 = 0,

Х1 — Х2 + 2X3X2 = 0.

Рассмотрим восемь вариантов удовлетворения условия “г” дополняющей нежесткости:

1) Х1 = 0, Х2 = 0, Х3 = 0. Первое уравнение в условии “а” несовместно;

2) X] ^ 0, Х2 = 0, Х3 = 0. Тогда

х2~х1 =°gt;

1-ЗХ^,2 =0,

X! =0.

Имеется противоречие, так как * 0;

3) = 0, Х2 * 0, Я.3 = Тогда

~х2 ~Х1 = 0,

1-ЗХ2х,2 =0,

-Х2 =0.

Имеется противоречие, так как Х2 * 0;

4) ^1=0, ^2=0, Х3 * 0. Тогда

Х1 + х2 quot; 1 = 0»

1 + 2X3^ = 0,

2X3X2 = о.

Так как Х3 *0, то х2 =0, а ^ =±1. Ограничениям “б” удовлетворяет Х| =1. При этом Х3 = lt; 0, что не удовлетворяет условию “в”;

5) X! ^ 0, Х2 * 0, Х3 = 0. Тогда

х2-х,3 =0,

~х2~х\ =0.

1 — ЗХ|Х2 - ЗХ2х2 — 0,

^1 ~ Х2 =: о.

Первые два уравнения удовлетворяются только при X! =х2 =0 (рис. 3.16), но при этом третье уравнение несовместно;

6) Х.1 ф О, Х2 =0, Х3 *0. Тогда

х2 -х,3 =0,

х,2 +х2 -1 = 0,

1 - ЗЛ,|Хр + 2X3X1 = 0,

+ 2Я.3Х2 = 0.

Отсюда Х1 = -2X3X2 - -2Х3х3 и 1 + 6X3^+2Х3Х! = 0. Так как 2Х3х1(Зх14 +1) =-1

только при Х3 gt; 0, X! lt; 0 (не лежит в множестве X, рис. 3.16) или Х3 lt; 0, X! gt; 0 (не удовлетворяется условие “в”), то система несовместна;

7) Х| = 0, Х2 * 0, Х3 * 0. Тогда

-х2-х\ =0,

Х^+Х2-1 = 0,

1 — ЗХ2Х1 + 2А.3Х1 = о,

—Х2 + 2X3X2 = о.

Отсюда Х2 = 2Х3х2 = -2Х3х3 и 1 + 6Х3Х3 + 2Х3Х| = 0. Так как 2Х3х^Зх4 +1) = -1

только при Х3 gt; 0, X! lt; 0 (не удовлетворяются ограничения “6м) и Х3 lt; 0, хх gt; 0, (не удовлетворяется условие “в”), то система несовместна;

8) Х| * 0, Х2 * 0, Х3 * 0. Из условий “г” следует:

х2-х,3 =0,

-х2 -Х13 =0,

Х1 +х2 -1 = 0.

Система несовместна (рис. 3.16).

Таким образом, найдена единственная условно-стационарная точка А.

4. Так как Х*0 = 0, то достаточные условия не проверяются. Из рис. 3.16 следует, что в точке А достигается глобальный условный минимум. Точка А явля­ется нерегулярной точкой минимума. В этой точке нельзя представить антигра-

диент -У/(у4) = (-1,0)г в виде неотрицательной линейной комбинации градиен­тов активных ограничений: V#! (А) = (0,1)г, У#2(Л) = (0,- 1)Г.

5. Значение функции в точке условного минимума /(Л) = 0. #9632;

Пример 3.20. Найти условный минимум в задаче

/(х) = х1 + х2 пип,

й(*) = х\ + (*2 - I)2 -1 ^ 0 gt;

g2^x) = -X, й 0,

pound;з(х) = -х2 lt;; 0.

? Как следует из рис. 3.17, глобальный минимум достигается в точке А: х\ = х\ = 0.

8г{х) = -х\ = 0

В точке А все три ограничения активны и их градиенты линейно зависимы, так как Vgl(A) = (0,-2)Г, У$2(Л) = (-1,0)Г, Уpound;3(/1) = (0,-1)Г и

(0-1 0) „ ГаПЧ-2 0 -1 ) = 2lt;т = 3

(см. определение 3.6). Условие регулярности в утверждении 3.4 не выполняется. Условие “а* в нем имеет вид

-Х0 У/(А) = Л., У^Л) + Х2 У$2(Л) + Х3 У^з(^) или

Если А,0 = 0, то не существует таких неотрицательных Х{1Х2Лз» чтобы сумма, стоящая справа, равнялась нулю. В этом случае условно-стационарных точек нет.

Если Х0 * 0, можно поделить равенство на Х0, заменяя — на Хх, — на

Х-о Х.о

X» 1

Х-2, — на Х.3. При этом равенство будет справедливо при Х.} = -, Х.*2 = 1, Х.*3 = 0.

Х,0 2

Это свидетельствует о том, что первое и второе ограничения активны: ^(^4) = 0,^2(^) = 0, а третье не является активным. Заметим, что третье ограни­чение в задаче является quot;лишнимquot;, так как его добавление не меняет множества допустимых решений. Хотя условие регулярности в точке А не выполняется, она является точкой регулярного минимума, так как Х,*0 ф 0. #9632;

Пример 3.21. Найти условный экстремум в задаче

/(*) = хх -gt; ехЦ,

8\{х) = х\ +х2-1^0, g2{x) = -Х, lt;0,

*з(*) = -*2 * 0.

? 1. Составим обобщенную функцию Лагранжа:

1,(х,Хд,Х) = ^0*1 + ^1(х1 + х2 “ 1) + ^2(“х1) + ^з(“х2) •

2. Выпишем необходимые условия экстремума первого порядка:

аgt; 5pound;(*’Ч:.х) = я,0 + Х1_Х2 = 0, дЧ*'Ьgt;к) = х,-х}=0; дх{ дх2

б) *1 + х2 -1 pound; 0, —Х| lt; 0, -х2 lt; 0;

в) X.! pound; 0, Х2 pound; 0, Х3 pound; 0 (для минимума), Хх pound; 0, Х2 lt; 0, Х3 lt; 0 (для мак­

симума);

г) +х2-1) = 0, Х2(-.Х1)= б» Х3(-дс2) = б'

3. Решим систему для двух случаев.

В первом случае Х0 = 0. Тогда X.! = Х2 = Х3. Если X.! = 0, то Х2 = Х3 = 0 и

имеется противоречие утверждению 3.4. Если X.! *0, то Х2 *0 и Х3 *0. Тогда

хх +х2 -1 = 0, -хх = 0, -х2 = 0. Последние три уравнения образуют несовмест­ную систему.

Во втором случае Х0 * 0. Поделим систему, приведенную в п.2, на Х0, за­меняя — на Х.|, — на Х2, — на Х3. При этом соотношения “б”-“г” сохра- Хд Хд Хд

няют вид, а условие “а” записывается в форме:

1 н- Х| — Х2 = 0,

Хlt;1 - Х3 =0.

Рассмотрим восемь вариантов удовлетворения условия “г” дополняющей нежесткости:

1) X! = 0, Х2 = 0, Х3 = 0. Первое уравнение в условии “а” не удовлетворя­ется;

2) X! * 0,Х2 = 0, Х3 = 0. Из условия “а” X! = 0, т.е. имеется противоречие;

3) X! = 0, Х2 ф 0, Х3 = 0. Тогда Х2 = 1, хх = 0, хх + х2 -1 lt; 0, - х2 lt; 0. Полу­чили бесконечное множество решений - точки отрезка АВ (см. рис. 1.9): х* =0, 0 lt; х2 lt; 1, X*! =0, X2 = 1 gt; 0, Х3 = 0. Удовлетворяется необходимое усло­вие минимума;

4) X] = 0,Х2 = 0, Х3*0. Из условия “а” Х3 = 0, т.е. имеется противоречие;

5) X] ^ 0, Х2 * 0, Х3 = 0. Тогда X! = 0, т.е. также имеется противоречие;

6) Х^О, Х2=0, Х3*0. Тогда Хх = —1 lt; 0, Х3 = X, = —1, х1+х2-1 = 0, -х2 = 0. Получили условно-стационарную точку С (см. рис. 1.9):

*1=1, х5=0, X*! = Х3 = -1 lt; о, х2 = о.

В ней удовлетворяются необходимые условия максимума;

7) X] = 0,Х2 * 0, Х3 ф 0. Из условия “а” Х3 = 0, т.е. имеется противоречие;

8) А.! ф О, Х2 * О, А-з * 0. Тогда

XI +х2-1 = 0,

-*1 =0,

-х2 = 0.

Последняя система несовместна.

4. Проверим достаточные условия экстремума. На множестве АВ активно одно ограничение, поэтому достаточные условия первого порядка не выполня­ются (строка 1 в табл. 3.2). Кроме того, (12Ь{А) = й2ЦВ) г 0 и поэтому достаточ­ные условия минимума второго порядка также не выполняются (строка 1 в табл. 3.3) и требуется дополнительное исследование (строка 5 в табл. 3.3). С другой стороны, целевая функция и ограничения выпуклые, поэтому на отрезке АВ дос­тигается глобальный минимум (п. 9 замечаний 3.4). В точке С два ограничения активны: / = 2 = п = 2. Так как lt; 0, Х3 lt;0, то выполняется достаточное усло­вие локального максимума первого порядка (строка 2 в табл. 3.2). Так как функ­ция quot;-/(*)quot; = -X! и ограничения выпуклые, то в точке С - глобальный максимум

(п. 9 замечаний 3.4).

5. Вычислим значение функции в точках условного экстремума: /(А)ш/(В)ш 0, /(С) = 1. #9632;

<< | >>
Источник: Пантелеев А. В., Летова Т. А.. Методы оптимизации в примерах и задачах: Учеб. посо- бие/А. В. Пантелеев, Т. А. Летова. — 2-е изд., исправл. — М.: Высш. шк.,— 544 с.: ил.. 2005

Еще по теме УСЛОВНЫЙ ЭКСТРЕМУМ ПРИ ОГРАНИЧЕНИЯХ ТИПА НЕРАВЕНСТВ:

  1. ПОСТАНОВКА ЗАДАЧИ И ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ
  2. УСЛОВНЫЙ ЭКСТРЕМУМ ПРИ ОГРАНИЧЕНИЯХ ТИПА НЕРАВЕНСТВ
  3. УСЛОВНЫЙ ЭКСТРЕМУМ ПРИ СМЕШАННЫХ ОГРАНИЧЕНИЯХ
  4. § 8. ПРИНЦИПЫ ПОСТРОЕНИЯ ЧИСЛЕННЫХ МЕТОДОВ ПОИСКА УСЛОВНОГО ЭКСТРЕМУМА
  5. МЕТОД ШТРАФОВ
  6. КОМБИНИРОВАННЫЙ МЕТОД ШТРАФНЫХ ФУНКЦИЙ
  7. МЕТОД ПРОЕКЦИИ ГРАДИЕНТА
  8. 4.5. Оптимизация портфеля ценных бумаг. Постановка и решение классической задачи оптимизации методом неопределенных множителей Лагранжа