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

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

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

Образец выполнения этапа №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.

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

Тип файла PDF

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

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

Список файлов учебной работы