RulTO-2 (Правила выполнения РГР для заочников)

Лунева С.Ю. Методические указания к РГР и КР по ТО ( ТО и ЧМ)стр.1Этап №2Методы решения ЗНП при ограничениях типа равенства22Дано: f (X ) = x1 + 2 x 2 − 2 x1 − 6 x 2 − 12 → extr2 x 1 + x 2 = −1Преобразуем ограничение к виду: ϕ1 ( X) = 02 x1 + x 2 = −1 ⇒ 2 x1 + x 2 + 1 = 0 ⇒ ϕ1 (X ) = 2 x1 + x 2 + 1а) Решить задачу графическиАлгоритм графического решения задачи1. Вычислить точку касания, пользуясь условиями касания:Ккас•точка касания принадлежит ограничению, т.е.

ϕ1 ( X•градиенты функции и ограничения в точке касания являются линейно-зависимыми,т.е. ∇f ( XKac) = 0;) = α ⋅ ∇ϕ1 (X Kac )2. Построить ограничение и определить множество допустимых решений X.3. Вычислить функцию в точке касания, определить конфигурацию и построитьсоответствующую линию уровня.Решение:Решение задачи есть точка касания ограничения и линии уровня функции f = C , гдеC = const . Искомая точка касания обладает следующими свойствами:••КасКасточка касания принадлежит ограничению: 2 x1 + x 2= −1в точке касания градиенты функции и ограничения линейно зависимы:∇f ( XKac) = α ⋅ ∇ϕ1 ( XKac 2 x1Kac − 2  2  2 x1Kac − 2 4 x 2 Kac − 6)⇒= α ⋅   ⇒= 4 x Kac − 6 121 2Воспользовавшись условиямикоординаты решения:касания, 2 x 1 + x 2 = −1 2 x + x 2 = −1⇒ 1 x1 − 1 = 4 x 2 − 6x1 − 4 x 2 = −5*составим⇒(1) − 2⋅(2)системууравненийи*2 x1 + x 2 = −1 x1 = −1⇒ *9x=9x 2 = 1 2ТНайдена точка X = ( −1, 1) - точка касания ограничения и линии уровня функции.Пример выполнения этапа №2, 2010 г.найдемЛунева С.Ю.

Методические указания к РГР и КР по ТО ( ТО и ЧМ)стр.2Построим графическую иллюстрацию решения.Ограничение в задаче - прямая с уравнением 2 x1 + x 2 = −1 , она проходит через точки:x1x20-0.5-10Построим прямую на графике и обозначим ϕ1 ( X) = 0 .*ТНайдём значение функции в найденной точке касания X = ( −1, 1) :f = (−1) 2 + 2 ⋅ 12 − 2 ⋅ (−1) − 6 ⋅ 1 − 12 = −13Определим конфигурацию линии✸) уровня функции, вычислив инвариант:D=1 00 2=2т.к.

D > 0, то искомая линия уровня эллипс.Запишем уравнение линии уровня:x12 + 2 x 22 − 2 x1 − 6x 2 − 12 = −13x12 + 2 x 22 − 2 x1 − 6x 2 = −1Приведем уравнение линии уровня к каноническому виду, выделив полные квадраты:x12 − 2 x1 + 2( x 22 − 3x 2 ) = −1x 2 − 2x1 + 1 − 1 + 2( x 22 − 2 ⋅ 3 x 2 + 9 − 9 ) = −1241 4( x1 − 1) 2 − 1 + 2(( x 2 − 3 ) 2 − 9 ) = −124( x 1 − 1) 2 + 2( x 2 − 3 ) 2 = −1 + 1 + 9223 2( x1 − 1) 2 ( x 2 − 2 )+= 1 - каноническое уравнение эллипса9924Центр эллипса - точка с координатами (1, 3 ) .2Главные диагонали эллипса прямые с уравнениями: x1 = 1 и x 2 = 3 .2✸)см. Приложение к №2Пример выполнения этапа №2, 2010 г.Лунева С.Ю. Методические указания к РГР и КР по ТО ( ТО и ЧМ)стр.3Найдем точки пересечения эллипса с главными диагоналями:x1 = 1 ⇒(x 2 − 3 )22 =1 ⇒94(x 2 − 3 )2 = 924⇒x2 − 3 = ± 322⇒x2 = 3x2 = 0Получены точки с координатами: (1, 0) и (1, 3)x2 = 32⇒( x1 − 1) 2= 1 ⇒ ( x1 − 1) 2 = 9⇒292x1 − 1 = ± 32⇒x 2 = 3.1213x1 = −1.1213Получены точки с координатами: (−1.1213, 3 ) и (3.1213, 3 )22Найдем еще несколько точек для построения эллипса, выразив x1 из каноническогоуравнения эллипса:(x 2 − 3 )22 ⋅ 9 +1x1 = ± 1 −294x2x100.511.522.5312.581133.121332.58111x11-0.5811-1-1.1213-1-0.58111Построим на чертеже линию уровня функции.Пример выполнения этапа №2, 2010 г.x2ϕ(X) = 0f=0f * = -131X*10x1Лунева С.Ю.

Методические указания к РГР и КР по ТО (ТО и ЧМ)стр.4б) Решить задачу методом множителей Лагранжа(аналитически отыскать экстремум функции при ограничениях типа равенства,используя аппарат необходимых и достаточных условий)Алгоритм решения задачи методом множителей Лагранжаm1. Записать классическую функцию Лагранжа: L( X, λ ) = f (X ) + ∑ λ jϕ j ( X)j=12. Записать необходимые условия экстремума ФМП при ограничениях типа равенств: ∂L(X, λ ) ∂f (X) m ∂ϕ j (X )=+ ∑λj= 0,∂x i∂x ij=1 ∂x iϕ (X ) = 0,j = 1..m ji = 1..n3.

Решить полученную систему. Решение системы – условно-стационарные точки(X*, λ*) .4. Проверить достаточные условия экстремума в каждой точке ( X*, λ*) , для этого∂ 2LЗаписать второй дифференциал функции Лагранжа: d L = ∑ ∑dx i dx ji =1 j=1 ∂x i ∂x j2Записать дифференциалы ограничений dϕ j ( X ) =n∂ϕ j (X)i =1∂x i∑n ndx iВ каждой точке ( X*, λ*)24.1. Вычислить второй дифференциал d L( X*, λ*)4.2. Записать условия равенства 0 дифференциалов ограничений в каждой точке X * :n  ∂ϕ j ⋅ dx i = 0,dϕ j (X*) = ∑ i =1  ∂x i  X *j = 1..m4.3.

Используя уравнения из п. 4.2, выразить любые m дифференциалов переменных2через оставшиеся ( n − m) и подставить их в выражение для d L( X*, λ*) .24.4. Определить знак d L( X*, λ*) :2•если d L( X*, λ*) >0 при dx i ≠ 0 , то точка X * - точка условного локальногоминимума в задаче;•если d L( X*, λ*) <0 при dx i ≠ 0 , то точка X * - точка условного локальногомаксимума в задаче.2Пример выполнения этапа №2, 2010 г.Лунева С.Ю.

Методические указания к РГР и КР по ТО (ТО и ЧМ)стр.5Решение:Запишем классическую функцию Лагранжа:L(X, λ) = x12 + 2 x 22 − 2 x1 − 6 x 2 − 12 + λ1 (2 x1 + x 2 + 1)Запишем необходимые условия экстремума функции при ограничениях типа равенства: ∂L(X, λ)= 2 x1 − 2 + 2λ1 = 0 ∂x1 ∂L(X, λ)= 4 x 2 − 6 + λ1 = 0∂x2 ϕ1 (X) = 2 x1 + x 2 + 1 = 0Решим полученную систему:2 x1 − 2 + 2λ1 = 0 4 x 2 − 6 + λ1 = 02 x + x + 1 = 02 19λ1 = 18⇒4x 2 + λ1 = 62x + x = −12 1⇒2 x1 + 2λ1 = 24 x 2 + λ1 = 62 x + x = −12 1λ1 = 26 − λ1x 2 =4− 1 − x2x=12⇒⇒(1) −(3)− x 2 + 2λ1 = 34 x 2 + λ1 = 6 2 x + x = −12 1⇒4⋅(1) + (2)λ1* = 2 *x 2 = 1 *x1 = −1**Таким образом, получено решение системы – точка с координатами ( X , λ ) = ( −1, 1, 2)- условно-стационарная точка функции.Определим характер полученной точки с помощью достаточных условий экстремума.Запишем второй дифференциал функции Лагранжа:∂ 2 L(X, λ )=2∂x12∂ 2 L ( X , λ ) ∂ 2 L ( X, λ )==0∂x1∂x 2∂x 2∂x1∂ 2 L ( X, λ )=4∂x 22d 2 L(X, λ) = 2(dx1 )2 + 0 ⋅ dx1 ⋅ dx 2 + 0 ⋅ dx1 ⋅ dx 2 + 4(dx 2 )2d 2 L(X, λ) = 2(dx1 )2 + 4(dx 2 )2Пример выполнения этапа №2, 2010 г.TЛунева С.Ю.

Методические указания к РГР и КР по ТО (ТО и ЧМ)стр.6Запишем дифференциал ограничения ϕ1 :∂ϕ1 (X )=2∂x1∂ϕ1 (X)=1∂x 2⇒dϕ1 (X ) = 2 ⋅ dx1 + 1 ⋅ dx 2В точке X* = ( −1, 1, 2) имеем:d 2 L(X*) = 2(dx 1 ) 2 + 4(dx 2 ) 2 при условии dϕ1 (X*) = 2 ⋅ dx 1 + 1 ⋅ dx 2 = 0 ,получим:dx 2 = −2dx 1 ⇒ d 2 L(X*) = 18(dx 1 ) 2 > 0 при dx 1 ≠ 0*Следовательно, в точке X = ( −1, 1)условного минимума.Tвыполнены достаточные условия локальногоОтвет: функции f (X ) при ограничении 2 x1 + x 2 = −1 имеет условный*Tминимум в точке с координатами X = ( −1, 1) .Пример выполнения этапа №2, 2010 г.локальныйЛунева С.Ю.

Методические указания к РГР и КР по ТО (ТО и ЧМ)стр.7в) Найти решение задачи методом исключенийАлгоритм решения задачи методом исключений1. Разрешить систему ограничений относительно любых m переменных.2. Подставить полученные выражения в исходную функцию и перейти к задачебезусловной оптимизации.3. Решить полученную задачу безусловной оптимизации - найти стационарные точки ипроверить достаточные условия.4. Вернуться к исходной задаче и, используя решение задачи безусловной оптимизации,найти значения недостающих переменных.Решение:Разрешим ограничение относительно переменной x 2 : x 2 = −1 − 2x1 , и подставимвыражение для x 2 в исходную функцию:~f (X ) = f ( x1 ) == x12 + 2(−1 − 2 x1 ) 2 − 2 x1 − 6(−1 − 2 x1 ) − 12 = x12 + 2(1 + 4 x1 + 4 x12 ) − 2 x1 + 6 − 12x1 − 12 == 9 x12 + 18x1 − 4~Найдем безусловный экстремум функции f ( x1 ) :~d f ( x1 )= 18x1 + 18 ⇒ 18x1 + 18 = 0 ⇒ x1* = −1dx1~d 2 f ( x1 )~= 18 > 0 ⇒ функция f ( x1 ) имеет минимум при x1* = −12d ( x1 )Найдем оптимальное значение x 2 * : x 2 * = −1 − 2 ⋅ ( −1) = 1Окончательно, найдена точка условного минимума функции f ( X) с координатамиX* = (−1, 1)T .Ответ: функции f (X ) при ограничении 2 x1 + x 2 = −1 имеет условный*Tминимум в точке с координатами X = ( −1, 1) .Пример выполнения этапа №2, 2010 г.локальныйЛунева С.Ю.

Методические указания к РГР и КР по ТО (ТО и ЧМ)стр.8г) Найти решение задачи методом штрафной функцииАлгоритм аналитического решения задачи методом штрафной функции1. Записать штрафную функцию: F( X, r ) = f ( X) +r m 2⋅ ∑ ϕ j (X)2 j=12. Записать необходимые условия экстремума для штрафной функции: ∂F(X, r )= 0 i = 1..n∂xi3. Найти решениепараметра r .полученнойсистемы:X* (r ) . Решение системы зависит от**4.

Найти условно-стационарную точку в задаче: X = lim X ( r ) .r →∞ ∂ 2 F(X, r ) 5. Составить матрицу Гессе для штрафной функции: H( X ( r )) =  ∂x ∂x  i =1..nij j=1..n6. Исследовать знакоопределенность матрицы при r → ∞ по критерию Сильвестра.***7. Записать оценку множителей Лагранжа: λ j = lim r ⋅ ϕ j ( X ( r ))r →∞j = 1..m .Решение:Составим штрафную функцию:rF(X, r ) = x12 + 2 x 22 − 2 x1 − 6 x 2 − 12 + (2 x1 + x 2 + 1) 22Внимание ! В случае поиска условного максимума,используют штрафную функцию вида:r mF(X, r ) = f (X) − ∑ ϕ2j (X)2 j=1Запишем необходимые условия безусловного минимума штрафной функции: ∂F(X, r )= 2x1 − 2 + r ⋅ (2x1 + x 2 + 1) ⋅ 2 = 0 ∂x1 ∂F(X, r ) = 4x − 6 + r ⋅ (2x + x + 1) = 0212 ∂x 2(2 + 4r ) ⋅ x1 + 2r ⋅ x 2 = 2 − 2rПреобразуем исходную систему к виду: 2r ⋅ x1 + (4 + r ) ⋅ x 2 = 6 − rРазрешим полученную систему относительно переменных x 1 , x 2 методом Крамера:2 + 4r 2r∆== (2 + 4r ) ⋅ (4 + r ) − 4r 2 = 8 + 16r + 2r + 4r 2 − 4r 2 = 18r + 82r4+rПример выполнения этапа №2, 2010 г.Лунева С.Ю.

Методические указания к РГР и КР по ТО (ТО и ЧМ)∆1 =∆2 =2 − 2r2r6−r4+r2 + 4r 2 − 2r2r6−rстр.9= (2 − 2r ) ⋅ (4 + r ) − 2r (6 − r ) = 8 − 8r + 2r − 2r 2 − 12r + 2r 2 = −18r + 8= (2 + 4r) ⋅ (6 − r) − 2r(2 − 2r) = 12 + 24r − 2r − 4r 2 − 4r + 4r 2 = 18r + 12− 18r + 8,18r + 8Тогда- стационарная точка штрафной функции.18r + 12*x 2 (r ) =18r + 8*x1 ( r ) =Найдем координаты условного экстремума исходной задачи как предел решения задачипоиска безусловного экстремума штрафной функции:− 18r + 8*= −1,x1 = limr →∞ 18r + 8*18r + 12*=1x 2 = limr →∞ 18r + 8TПолучена точка X = ( −1, 1) - точка условного экстремума исходной задачи. 2 + 4r 2r 4 + r  2rЗапишем матрицу Гессе для штрафной функции: H( X, r ) = ∆1 = 2 + 4r > 0 при r > 0∆ 2 = (2 + 4r )(4 + r ) − 4r 2 = 8 + 16r + 2r + 4r 2 − 4r 2 = 8 + 18r > 0 при r > 0Следовательно, по критерию Сильвестра, достаточные условия минимума функцииF(X, r ) выполняются, и значит полученная точка X* = (−1, 1)T – точка условноголокального минимума функции f ( X) .*Запишем оценку λ 1 : − 18r + 8 18r + 12  − 36r + 16 + 18r + 12 + 18r + 8 *λ1 = lim r ⋅  2 ⋅++ 1 = lim r ⋅ =r →∞ 18r + 818r + 818r + 8 r →∞  36 = lim r ⋅ =2r →∞  18r + 8 Внимание !В случае поиска условного максимума,*используют формулу: λ j = − lim r ⋅ ϕ j (X * ( r ))r →∞Ответ: функции f (X ) при ограничении 2 x1 + x 2 = −1 имеет условный*Tминимум в точке с координатами X = ( −1, 1) .Пример выполнения этапа №2, 2010 г.локальный.