semopt2 (1013525)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Занятие 2.НЕОБХОДИМЫЕ И ДОСТАТОЧНЫЕ УСЛОВИЯ УСЛОВНОГОЭКСТРЕМУМАА. ОГРАНИЧЕНИЯ ТИПА РАВЕНСТВПостановка задачиДаны дважды непрерывно дифференцируемые целевая функция f ( x) = f ( x1 ,… , x n )и функции ограничений g j ( x) = g j ( x1 ,… , x n ) = 0, j = 1,… , m , определяющие множестводопустимых решений X .Требуется исследовать функцию f ( x) на экстремум, т.е. определить точки x ∗ ∈ X еелокальных минимумов и максимумов на множестве X :f ( x ∗ ) = min f ( x) ,x∈X{f ( x ∗ ) = max f ( x) ,x∈X}где X = x g j ( x) = 0, j = 1,… , m; m < n .Алгоритм решения задачиШаг 1.

Составить обобщенную функцию Лагранжа:mL ( x, λ 0 , λ ) = λ 0 f ( x ) + ∑ λ j g j ( x ) .j =1Шаг 2. Записать необходимые условия экстремума первого порядка:∂ L( x ∗ , λ ∗0 , λ ∗ )= 0,а)∂ xiб) g j ( x ∗ ) = 0 ,i = 1, … , n ;j = 1, … , m .Шаг 3.

Решить систему для двух случаев.Первый случай: λ∗0 = 0 .Второй случай: λ∗0 ≠ 0 (при этом поделить условие «а» на λ∗0 и заменитьλ∗jλ∗0наλ∗j ).В результате решения найти условно-стационарные точки x ∗ , выделив из нихполученные при λ∗0 ≠ 0 (они могут быть регулярными точками экстремума).Шаг 4. Для выделенных на шаге 3 точек проверить выполнение достаточных условийэкстремума:а) записать выражение для второго дифференциала классической функции Лагранжав точке ( x ∗ , λ ∗ ) :152nnd L( x , λ ) = ∑ ∑∗2∗i =1 j =1∂ 2 L( x ∗ , λ ∗ )dx i dx j ;∂x i ∂x jб) записать систему в точке x ∗ :n∂ g j (x∗ )i =1∂ xidg j ( x ) = ∑∗dx i = 0 ,j = 1, … , m ;в) из предыдущей системы выразить любые m дифференциалов dxi через остальные( n − m ) и подставить в d 2 L( x ∗ , λ ∗ ) ;г) если d 2 L( x ∗ , λ ∗ ) > 0 при ненулевых dx , то в точке x ∗ – условный локальныйминимум. Если d 2 L( x ∗ , λ ∗ ) < 0 при ненулевых dx , то в точке x ∗ – условныйлокальный максимум.

Если достаточные условия экстремума не выполняются,следует проверить выполнение необходимых условий второго порядка, следуяаналогичной процедуре. Если они выполняются, то требуется дополнительноеисследование, а если не выполняются, то в точке x ∗ нет условного экстремума.Шаг 5. Вычислить значения функции в точках условного экстремума.З а м е ч а н и я.1. Иногда удается проверить условие линейной независимости градиентовограничений на множестве X . Если оно выполняется, то на шаге 1 следует записатьклассическую функцию Лагранжа, на шаге 2 можно записывать сразу систему при λ 0 = 1 , ана шаге 3 отсутствует случай λ∗0 = 0 .2.

Для графического решения задачи (при n = 2, m = 1 ) следует:а) построить множество допустимых решений X;б) построить семейство линий уровня целевой функции и найти точки их касания скривыми, описывающими ограничения. Эти точки являются «подозрительными» наусловный экстремум;в) исследовать поведение целевой функции при движении вдоль ограничения кисследуемой точке и от нее. Классифицировать точки, используя определение экстремума(cм.

определения 1.1 и 1.2 – лекция 1).f ( x) = C 2f ( x) = C 4C 4 > C 3 > C 2 > C141325f ( x) = C 36f ( x) = C1g ( x) = 0Рис. 1153На рис. 1 в точках 1 – 2, 4 – 6 линии уровня касаются ограничения. Исследованиеповедения функции в этих точках при движении по стрелкам показывает, что в точках 1,4, 6 – локальный максимум, так как при приближении к ним функция возрастает, а затемубывает; в точках 2, 5 – локальный минимум, так как при приближении к ним функцияубывает, а затем возрастает; в точке 3 нет условного экстремума, поскольку приприближении к ней и удалении дальше от нее функция возрастает.3.

При решении примеров для упрощения записи на шагах 2 и 3 алгоритма будемопускать знак « ∗ », оставляя его только для значений x и λ , соответствующих условностационарным точкам.Пример 1. Найти условный экстремум в задачеf ( x) = x1 + x 2 → extr ,g1 ( x) = x12 + x 22 − 2 = 0 .T† Проверим условие регулярности. Так как ∇g1 ( x) = ( 2 x1 , 2 x 2 ) ≠ 0 для всехx ∈ X , то условие выполняется (см. определение 3.6 – лекция 2). Поэтому будемпользоваться классической функцией Лагранжа.1. Составим функцию Лагранжа:()L ( x , λ1 ) = x1 + x 2 + λ1 x12 + x 22 − 2 .2. Выпишем необходимые условия экстремума первого порядка:а)∂ L (x , λ 1 )∂ x1∂ L (x , λ 1 )∂ x2= 1 + 2λ1 x1 = 0 ⇒ x1 = −1,2λ1= 1 + 2λ1 x 2 = 0 ⇒ x 2 = −1;2λ1б) g1 ( x) = x12 + x 22 − 2 = 0 .3. Решением системы являются две условно-стационарные точки:A: x1∗ = 1, x 2∗ = 1, λ∗1 = −1;2B: x1∗ = −1, x 2∗ = −1, λ∗1 =1.24.

Проверим выполнение достаточных условий экстремума:∂ 2 L (x , λ 1 ) ∂ 2 L (x , λ 1 )а) d 2 L( x ∗ , λ 1∗ ) = 2λ 1∗ dx12 + 2λ 1∗ dx 22 , так как== 2λ∗1 ,22∂x1∂x 2∂ 2 L (x , λ 1 )∂x1∂x 2∂ 2 L (x , λ 1 )== 0;∂x 2 ∂x1∂ g1 ( x)∂ g1 ( x)= 2x2 ;= 2 x1 ,∂ x1∂ x2в) исследуем точку A. Получаем dg1 ( A ) = 2dx1 + 2dx 2 = 0 , откуда dx1 = − dx 2 .б) dg1 ( x ∗ ) = 2 x1∗ dx1 + 2 x 2∗ dx 2 = 0 , так какС учетом полученного соотношения d 2 L ( A ) = − dx12 − dx 22 = −2dx 22 < 0 при dx 2 ≠ 0 .Поэтому в точке x ∗ = (1,1) – регулярный условный локальный максимум.T154Исследуем точку B. Получаем dg1 (B ) = −2dx1 − 2dx 2 = 0 , откуда dx1 = − dx 2 .С учетом полученного соотношения d 2 L (B ) = dx12 + dx 22 = 2dx 22 > 0 при dx 2 ≠ 0 .Поэтому в точке x ∗ = ( −1, − 1) – регулярный условный локальный минимум.T5.

Подсчитаем значения функции в точках экстремума: f ( A ) = 2, f (B ) = −2 .Графическое решение задачи изображено на рис. 2. „x222A1g 1 ( x ) = x1 2 + x 2 2 − 2 = 0−121−22f (x ) = 2−1Bx1f (x ) = 0−2f (x ) = −2Рис. 2Б. ОГРАНИЧЕНИЯ ТИПА НЕРАВЕНСТВПостановка задачиДаны дважды непрерывно дифференцируемые целевая функция f ( x) = f ( x1,…, xn )и функции ограничений g j ( x) = g j ( x1 ,… , x n ) ≤ 0 , j = 1,… , m , определяющие множестводопустимых решений X .Требуется исследовать функцию f ( x ) на экстремум, т.е. определить точки x ∗ ∈ Xее локальных минимумов и максимумов на множестве X :f ( x ∗ ) = min f ( x) ;{}x∈Xf ( x ∗ ) = max f ( x) ,x∈Xгде X = x g j ( x) ≤ 0, j = 1,… , m .Алгоритм решения задачиШаг 1.

Составить обобщенную функцию Лагранжа:mL ( x, λ 0 , λ ) = λ 0 f ( x ) + ∑ λ j g j ( x ) .j =1155Шаг 2. Записать необходимые условия минимума (максимума) первого порядка:∂ L( x ∗ , λ ∗0 , λ ∗ )= 0,i = 1,… , n ;а)∂ xiб) g j ( x ∗ ) ≤ 0 , j = 1, … , m ;в) λ∗j ≥ 0 , j = 1, … , m (для минимума), λ∗j ≤ 0 , j = 1, … , m (для максимума);г) λ ∗j g j ( x ∗ ) = 0 , j = 1, … , m .Шаг 3. Решить систему для двух случаев.Первый случай: λ∗0 = 0 .Второй случай: λ∗0 ≠ 0 (при этом поделить условия, записанные на шаге 2, на λ∗0 изаменитьλ∗jλ∗0на λ∗j ).В результате решения найти условно-стационарные точки x ∗ , выделив из нихполученные при λ∗0 ≠ 0 (они могут быть регулярными точками экстремума). В каждомиз двух случаев следует начинать с рассмотрения 2 m вариантов удовлетворения условия«г» дополняющей нежесткости.Шаг 4.

Для выделенных на шаге 3 точек проверить выполнение достаточныхусловий экстремума первого или второго порядка.Для проверки выполнения достаточных условий первого порядка следует:а) определить число l активных в точке x ∗ ограничений;б) если l = n и λ∗j > 0 для всех j ∈ J a , то в точке x ∗ – условный локальныйминимум. Если l = n и λ∗j < 0 для всех j ∈ J a , то в точке x ∗ – условныйлокальный максимум. Если l < n или соответствующие множители Лагранжане удовлетворяют достаточным условиям первого порядка, проверитьдостаточные условия второго порядка.Для проверки выполнения достаточных условий второго порядка следует:а) записать выражение для второго дифференциала классической функцииЛагранжа в точке ( x ∗ , λ ∗ ) :∂ 2 L( x ∗ , λ ∗ )d L( x , λ ) = ∑ ∑dx i dx j ;∂x i ∂x ji =1 j =1б) записать условия, накладываемые на первые дифференциалы активныхограничений:n ∂ g (x∗ )j∗dg j ( x ) = ∑dx i = 0 , j ∈ J a ; λ∗j > 0 ( λ∗j < 0 );∂ xii =1∗2n∂ g j (x∗ )i =1∂ xidg j ( x ) = ∑∗∗nndx i ≤ 0 , j ∈ J a , λ∗j = 0 ;в) исследовать знак второго дифференциала функции Лагранжа при ненулевыхdx , удовлетворяющих системе, составленной в п.б.

Если d 2 L( x ∗ , λ ∗ ) > 0 , то156в точке x ∗ – условный локальный минимум. Если d 2 L( x ∗ , λ ∗ ) < 0 , то в точкеx ∗ – условный локальный максимум.Если достаточные условия первого и второго порядка не выполняются, следуетпроверить выполнение необходимых условий второго порядка (см. утверждение 3.6 –лекция 2), следуя аналогичной процедуре. Если они выполняются, то требуетсядополнительное исследование, а если нет, то в точке x ∗ нет условного экстремума.Шаг 5. Вычислить значения функции в точках условного экстремума.Пример 2.

Найти условный минимум в задачеf ( x) = x12 + ( x 2 − 2) 2 → min ,g1 ( x) = x12 + x 22 − 1 ≤ 0 ,g 2 ( x) = − x1 ≤ 0 ,g 3 ( x) = − x 2 ≤ 0 .† 1. Составим обобщенную функцию Лагранжа:L ( x, λ 0 , λ ) = λ 0 ⎡ x12 + ( x 2 − 2) 2 ⎤ + λ 1 ( x12 + x 22 − 1) + λ 2 (− x1 ) + λ 3 (− x 2 ) .⎣⎦2. Выпишем необходимые условия минимума первого порядка:∂ L (x , λ 0 , λ )а)= 2λ 0 x1 + 2λ1 x1 − λ 2 = 0 ,∂ x1∂ L (x , λ 0 , λ )= 2λ 0 (x 2 − 2) + 2λ1 x 2 − λ 3 = 0 ;∂ x2б) x12 + x 22 − 1 ≤ 0 , − x1 ≤ 0 , − x 2 ≤ 0 ;в) λ1 ≥ 0 , λ 2 ≥ 0 , λ 3 ≥ 0 ;г) λ 1 ( x12 + x 22 − 1) = 0 , λ 2 (− x1 ) = 0 , λ 3 (− x 2 ) = 0 .3. Решим систему для двух случаев.Первый случай: λ 0 = 0 , тогда условия “а” запишутся в виде2λ1x1 − λ 2 = 0 ,2λ1x 2 − λ 3 = 0 .Рассмотрим восемь вариантов выполнения условий «г» дополняющейнежесткости:1) λ1 = 0 , λ 2 = 0 , λ 3 = 0 , при этом не удовлетворяется требование утверждения3.4;2) λ1 ≠ 0 , λ 2 = 0 , λ 3 = 0 , тогда x1 = x 2 = 0 из условия «а», но первое условиедополняющей нежесткости не удовлетворяется;3) λ1 = 0 , λ 2 ≠ 0 , λ 3 = 0 , тогда из первого уравнения в условии «а» имеемλ 2 = 0 , т.е.

имеется противоречие;4) λ1 = 0 , λ 2 = 0 , λ 3 ≠ 0 , тогда из второго уравнения в условии «а» имеем λ 3 = 0 ,т.е. также имеется противоречие;5) λ1 ≠ 0 , λ 2 ≠ 0 , λ 3 = 0 , тогда x1 = 0 и из первого уравнения в условии «а»имеем λ 2 = 0 , т.е. имеется противоречие;1576) λ1 ≠ 0 , λ 2 = 0 , λ 3 ≠ 0 , тогда x 2 = 0 и из второго уравнения в условии «а»имеем λ 3 = 0 , т.е. также имеется противоречие;7) λ1 = 0 , λ 2 ≠ 0 , λ 3 ≠ 0 , тогда не выполняются оба уравнения в условии “а”;8) λ1 ≠ 0 , λ 2 ≠ 0 , λ 3 ≠ 0 , тогда уравнения x1 = x 2 = 0 , x12 + x 22 − 1 = 0 ,следующие из условия “г”, вместе не выполняются.Условно-стационарных точек пока не найдено.Второй случай: λ 0 ≠ 0 .

Поделив уравнения приведенной в п.2 системы на λ 0 иλλλзаменив 1 на λ1 , 2 на λ 2 , 3 на λ 3 , получим:λ0λ0λ0∂ L ( x, λ )∂ L (x , λ )= 2 ( x 2 − 2) + 2 λ 1 x 2 − λ 3 = 0 ;а)= 2 x1 + 2λ1 x1 − λ 2 = 0 ,∂ x2∂ x1б) x12 + x 22 − 1 ≤ 0 , − x1 ≤ 0 , − x 2 ≤ 0 ;в) λ1 ≥ 0 , λ 2 ≥ 0 , λ 3 ≥ 0 ;г) λ 1 ( x12 + x 22 − 1) = 0 , λ 2 (− x1 ) = 0 , λ 3 (− x 2 ) = 0 .Рассмотрим восемь вариантов выполнения условий дополняющей нежесткости:1) λ1 = 0 , λ 2 = 0 , λ 3 = 0 , тогда x1 = 0, x 2 = 2 и не выполняется первоеограничение в условии «б»;2) λ1 ≠ 0 , λ 2 = 0 , λ 3 = 0 , тогдаx12 + x 22 − 1 = 0 ,2 x1 (1 + λ1 ) = 0 ,2 (x 2 − 2) + 2λ1 x 2 = 0 .Если λ1 = −1 , то третье уравнение не удовлетворяется. Если x1 = 0 , то x 2 = ±1 .Ограничениям в условии «б» удовлетворяет x 2 = 1 , при этом λ1 = 1 .

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций