Пример выполнения этапа №2 РГР (Примеры выполнения РГР (все в одном архиве))

Образец выполнения этапа №2 РГРРасчетно-графическая работапо курсу «Теория оптимизации и численные методы».Выполнил студент группы 04-206 Иванов И.И.Вариант №1Задание:f (X) = x12 + 2x 2 2 − 2x1 − 6x 2 − 12 → extr2x1 + x 2 = −1Этап №2. Тема: Методы решения ЗНП при ограничениях типа равенстваЗадание:а) Решить задачу графически.б) Аналитически отыскать экстремум функции при ограничениях типа равенства, используя аппаратнеобходимых и достаточных условий (методом множителей Лагранжа).в) Найти решение задачи методом исключений.г) Найти решение задачи методом штрафных функций.2. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯПРИ ОГРАНИЧЕНИЯХ ТИПА РАВЕНСТВАЗадание 2а).Дано: f (X) = x12 + 2x 2 2 − 2x1 − 6x 2 − 12 → extr2x1 + x 2 = −1Преобразуем ограничение к виду: ϕ1 (X) = 02x1 + x 2 = −1 ⇒ 2x1 + x 2 + 1 = 0 ⇒ ϕ1 (X) = 2x1 + x 2 + 1Решить задачу графически.Решение:Решение задачи есть точка касания ограничения и линии уровня функции f = C , где C = const .Искомая точка касания обладает следующими свойствами:• точка касания принадлежит ограничению: 2x1Кас + x 2 Кас = −1• в точке касания градиенты функции и ограничения линейно зависимы: 2 x1Kac − 2  2  2 x1Kac − 2 4 x 2 Kac − 6KacKac∇f ( X ) = α ⋅ ∇ϕ1 ( X ) ⇒= α ⋅   ⇒= 4 x Kac − 6 121 2Воспользовавшись условиями касания, составим систему уравнений и найдем координатырешения: 2 x 1 + x 2 = −12x + x 2 = −1⇒ 1 x 1 − 1 = 4 x 2 − 6  x 1 − 4 x 2 = −5⇒(1) − 2⋅(2)*2x1 + x 2 = −1 x1 = −1⇒ *x 2 = 19x 2 = 91Образец выполнения этапа №2 РГРНайдена точка X * = (−1, 1) Т - точка касания ограничения и линии уровня функции.Построим графическую иллюстрацию решения.Ограничение в задаче - прямая с уравнением 2x1 + x 2 = −1 , она проходит через точки:x10-0.5x2-10Построим прямую на графике и обозначим ϕ1 (X) = 0 .Найдём значение функции в найденной точке касания X * = (−1, 1) Т :f = (−1) 2 + 2 ⋅ 12 − 2 ⋅ (−1) − 6 ⋅ 1 − 12 = −13Определим конфигурацию линии✸) уровня функции, вычислив инвариант:1 0D== 2 т.к.

D > 0, то искомая линия уровня эллипс.0 2Запишем уравнение линии уровня:x12 + 2x 22 − 2x1 − 6x 2 − 12 = −13x12 + 2x 22 − 2x1 − 6x 2 = −1Приведем уравнение линии уровня к каноническому виду, выделив полные квадраты:x12 − 2x1 + 2( x 22 − 3x 2 ) = −1x12 − 2 x1 + 1 − 1 + 2( x 22 − 2 ⋅ 3 x 2 + 9 − 9 ) = −12 44( 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Найдем точки пересечения эллипса с главными диагоналями:✸)см.

Приложение к №22Образец выполнения этапа №2 РГР(x 2 − 3 ) 22 = 1 ⇒ (x − 3 ) 2 = 9⇒x1 = 1 ⇒22494Получены точки с координатами: (1, 0) и (1, 3)x2 − 3 = ± 3⇒22( x1 − 1) 2= 1 ⇒ ( x1 − 1) 2 = 9⇒ x1 − 1 = ± 322922Получены точки с координатами: (−1.1213, 3 ) и (3.1213, 3 )22x2 = 3⇒⇒x2 = 3x2 = 0x 2 = 3.1213x1 = −1.1213Найдем еще несколько точек для построения эллипса, выразив x1 из канонического уравненияэллипса:(x 2 − 3 ) 22 ⋅ 9 +1x1 = ± 1 −294x2x100.511.522.5312.581133.121332.58111x11-0.5811-1-1.1213-1-0.58111Построим на чертеже линию уровня функции.3x2ϕ(X) = 0f=0f * = -131X*1x104Образец выполнения этапа №2 РГРЗадание 2б).Дано: f (X) = x12 + 2x 2 2 − 2x1 − 6x 2 − 12 → extr2x1 + x 2 = −1Решить задачу методом множителей Лагранжа (аналитически отыскать экстремумфункции при ограничениях типа равенства, используя аппарат необходимых и достаточныхусловий)Решение:Запишем классическую функцию Лагранжа:L(X, λ ) = x12 + 2x 22 − 2 x1 − 6x 2 − 12 + λ1 (2x1 + x 2 + 1)Запишем необходимые условия экстремума функции при ограничениях типа равенства: ∂L ( X , λ )= 2 x 1 − 2 + 2λ 1 = 0 ∂x1 ∂L ( X , λ )= 4 x 2 − 6 + λ1 = 0 ∂x 2 ϕ1 ( X) = 2 x 1 + x 2 + 1 = 0Решим полученную систему:2 x 1 − 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⇒2x 1 + 2λ1 = 24 x 2 + λ 1 = 62x + x = −12 1λ1 = 26 − λ1x 2 =4−1 − x 2x1 =2⇒⇒(1)−(3) − x 2 + 2λ 1 = 34 x 2 + λ 1 = 62x + x = −12 1⇒4⋅(1)+( 2)λ1* = 2*x 2 = 1 *x1 = −1Таким образом, получено решение системы – точка с координатами (X * , λ* ) = (−1, 1, 2) T - условностационарная точка функции.Определим характер полученной точки с помощью достаточных условий экстремума.Запишем второй дифференциал функции Лагранжа:∂ 2 L( X , λ )∂x12=2∂ 2 L ( X, λ ) ∂ 2 L ( X, λ )==0∂x1∂x 2∂x 2 ∂x1∂ 2 L( X , λ )∂x 22=45Образец выполнения этапа №2 РГРd 2 L(X, λ ) = 2(dx1 ) 2 + 0 ⋅ dx1 ⋅ dx 2 + 0 ⋅ dx1 ⋅ dx 2 + 4(dx 2 ) 2⇒d 2 L(X, λ ) = 2(dx1 ) 2 + 4(dx 2 ) 2Запишем дифференциал ограничения ϕ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(dx1 ) 2 + 4(dx 2 ) 2 при условии dϕ1 (X * ) = 2 ⋅ dx1 + 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) при ограничении 2x1 + x 2 = −1 имеет условный локальный минимум вточке с координатами X * = (−1, 1) T .6Образец выполнения этапа №2 РГРЗадание 2в).Дано: f (X) = x12 + 2x 2 2 − 2x1 − 6x 2 − 12 → extr2x1 + x 2 = −1Найти решение задачи методом исключенийРешение:Разрешим ограничение относительно переменной x 2 : x 2 = −1 − 2x1 , и подставим выражение дляx 2 в исходную функцию:~f ( X ) = f ( x1 ) == x12 + 2(−1 − 2 x1 ) 2 − 2 x1 − 6(−1 − 2x1 ) − 12 = x12 + 2(1 + 4x1 + 4x12 ) − 2x1 + 6 − 12x1 − 12 == 9x12 + 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) при ограничении 2x1 + x 2 = −1 имеет условный локальный минимум вточке с координатами X * = (−1, 1) T .7Образец выполнения этапа №2 РГРЗадание 2г).Дано: f (X) = x12 + 2x 2 2 − 2x1 − 6x 2 − 12 → extr2x1 + x 2 = −1Найти решение задачи методом штрафной функцииРешение:Составим вспомогательную функцию:rF(X, r ) = x12 + 2 x 22 − 2 x1 − 6 x 2 − 12 + (2 x1 + x 2 + 1) 22Внимание ! В случае поиска условного максимума,r mиспользуют функцию вида: F(X, r ) = f (X) − ∑ ϕ 2j (X)2 j =1Запишем необходимые условия безусловного минимума вспомогательной функции: ∂F(X, r )= 2 x1 − 2 + r ⋅ (2 x1 + x 2 + 1) ⋅ 2 = 0 ∂x1 ∂F(X, r ) = 4 x − 6 + r ⋅ (2x + x + 1) = 0212 ∂x 2(2 + 4r ) ⋅ x1 + 2r ⋅ x 2 = 2 − 2rПреобразуем исходную систему к виду: 2r ⋅ x1 + (4 + r ) ⋅ x 2 = 6 − rРазрешим полученную систему относительно переменных x1 , x 2 по правилу Крамера:2 + 4r 2 r∆== (2 + 4r ) ⋅ (4 + r ) − 4r 2 = 8 + 16r + 2r + 4r 2 − 4r 2 = 18r + 82r4+r∆1 =∆2 =2 − 2r2r6−r4+r2 + 4r 2 − 2r2r6−r= (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 + 8x1* (r ) =Найдем координаты условного экстремума исходной задачи, как предел решения задачи поискабезусловного экстремума вспомогательной функции:− 18r + 8x1* = lim= −1,r →∞ 18r + 818r + 12x 2* = lim=1r →∞ 18r + 88Образец выполнения этапа №2 РГРПолучена точка X * = (−1, 1) T - точка условного экстремума исходной задачи. 2 + 4r 2r Запишем матрицу Гессе для вспомогательной функции: H(X, r ) = 4 + r  2r∆1 = 2 + 4r > 0 при r → ∞∆ 2 = (2 + 4r )(4 + r ) − 4r 2 = 8 + 16r + 2r + 4r 2 − 4r 2 = 8 + 18r > 0 при r → ∞Следовательно, по критерию Сильвестра, достаточные условия минимума функции 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) при ограничении 2x1 + x 2 = −1 имеет условный локальный минимум вточке с координатами X * = (−1, 1) T .9.