Примеры решения задач к экзаменационному вопросу 21 (Примеры решения задач к экзаменационным вопросам)
Описание файла
Файл "Примеры решения задач к экзаменационному вопросу 21" внутри архива находится в папке "Примеры решения задач к экзаменационным вопросам". PDF-файл из архива "Примеры решения задач к экзаменационным вопросам", который расположен в категории "". Всё это находится в предмете "теория оптимизации и численные методы" из 4 семестр, которые можно найти в файловом архиве МАИ. Не смотря на прямую связь этого архива с МАИ, его также можно найти и в других разделах. Архив можно найти в разделе "к экзамену/зачёту", в предмете "теория оптимизации и численные методы" в общих файлах.
Просмотр PDF-файла онлайн
Текст из PDF
Тема: Методы решения ЗНП при ограничениях типа неравенстваПример №1Дано:f (X) = (x1 − 4) 2 + (x 2 − 4) 2 → extrx1 + x 2 ≤ 4x1 + x 2 ≥ −4Аналитически отыскать экстремум функции при ограничениях типа неравенства,используя аппарат необходимых и достаточных условий.Решение:Преобразуем ограничения к виду: ϕ j ( X ) ≤ 0x1 + x 2 − 4 ≤ 0ϕ1 (X)− x1 − x 2 − 4 ≤ 0ϕ2 (X)Построим на чертеже множество допустимых решений, задаваемое ограничениями.1. Запишем классическую функцию Лагранжа:L(X, λ ) = ( x − 4) 2 + ( x 2 − 4) 2 + λ 1 ( x 1 + x 2 − 4) + λ 2 (− x 1 − x 2 − 4)2.
Запишем необходимые условия экстремума функции при ограничениях типа неравенства:∂L= 2( x 1 − 4) + λ 1 − λ 2 = 0 ∂x 1∂L= 2( x 1 − 4) + λ 1 − λ 2 = 0 ∂x 1λ 1 ( x 1 + x 2 − 4) = 0λ 2 ( − x 1 − x 2 − 4) = 0 3. Решим полученную систему, рассматривая все случаи:Случай (а)Ограничение ϕ1 ( X ) = x 1 + x 2 − 4 < 0 - пассивно, следовательно λ 1 = 0 .Ограничение ϕ2 (X) = − x1 − x 2 − 4 < 0 - пассивно, следовательно λ 2 = 0 .Тогда получим и решим следующую систему уравнений: 2( x 1 − 4 ) = 0x1 = 4 2( x − 4 ) = 0x = 4 2 2⇒ ⇒ A = ( 4, 4, 0, 0)λ1 = 0λ1 = 0λ 2 = 0λ 2 = 0Т.о.
получено первое решение системы – точка A с координатами A = (4, 4, 0, 0) . Построим этуточку на чертеже.x2f(X)=constOA4ϕ1(X)=0x1ϕ2(X)=0BСлучай (b)Ограничение ϕ1 ( X ) = x 1 + x 2 − 4 = 0 - активно.Ограничение ϕ2 (X) = − x1 − x 2 − 4 = 0 - активно.Из чертежа следует, что система решений не имеет, т.к. ограничения задаются параллельнымипрямыми и общих точек не имеют.Случай (c)Ограничение ϕ1 ( X ) = x 1 + x 2 − 4 = 0 - активно.Ограничение ϕ2 (X) = − x1 − x 2 − 4 < 0 - пассивно, следовательно λ 2 = 0 .Тогда получим и решим следующую систему уравнений: 2( x 1 − 4 ) + λ 1 = 0x1 = 2 2( x − 4 ) + λ = 0x = 2 2 21⇒ ⇒ B = ( 2, 2, 4, 0)x 1 + x 2 − 4 = 0λ1 = 4λ 2 = 0λ 2 = 0Т.о. получено второе решение системы – точка В с координатами B = (2, 2, 4, 0) .
Построим этуточку на чертеже.Случай (d)Ограничение ϕ1 ( X ) = x 1 + x 2 − 4 < 0 - пассивно, следовательно λ 1 = 0 .Ограничение ϕ2 (X) = − x1 − x 2 − 4 = 0 - активно.Тогда получим и решим следующую систему уравнений: 2( x 1 − 4 ) − λ 2 = 0 2( x − 4 ) − λ = 0 22⇒λ1 = 0− x 1 − x 2 − 4 = 0 x 1 = −2 x = −2 2⇒ C = ( −2, − 2, 0, − 12)λ1 = 4λ 2 = 0Т.о.
получено третье решение системы – точка С с координатами C = ( −2, − 2, 0, − 12) .Построим эту точку на чертеже.4. Отбракуем лишние точки:КоординатыB = (2, 2, 4, 0)ПринадлежностьМНР∉ МНР,отбраковывается∈ МНРλ1 > 0 λ 2 = 0кандидат на минимумC = (−2, − 2, 0, − 12)∈ МНРλ1 = 0 λ 2 < 0кандидат на максимумA = (4, 4, 0, 0)Знак λ jВывод____________Исключаем точку A , поскольку она не принадлежит множеству допустимых решений, изоставшихся точек: B - кандидат на минимум, C - кандидат на максимум.Таким образом, после отбраковки остались две точки:B = (2, 2, 4, 0)- точка является кандидатом на минимумC = (−2, − 2, 0, − 12)- точка является кандидатом на максимум5. Проверим достаточные условия 1-го порядка: в точках B и C . ДУ 1-го порядка невыполняются, т.к. число активных ограничений в этих точках меньше числа переменных.6. Проверим достаточные условия экстремума 2-го порядкаСоставляем второй дифференциал функции Лагранжа:∂ 2L∂x12=2∂ 2L∂ 2L==0∂x1∂x 2 ∂x1∂x 2∂ 2L∂x 22=2d 2 L = 2(dx 1 ) 2 + 2(dx 2 ) 2Составляем дифференциалы ограничений:∂ϕ1=1∂x1∂ϕ2= −1∂x1∂ϕ1=1∂x 2∂ϕ2= −1∂x 2⇒dϕ1 (X) = dx1 + dx 2⇒dϕ2 (X) = −dx1 − dx 2Точка B = ( 2, 2, 4, 0) - кандидат на минимум, активно ограничение ϕ1 , λ1 = 4 ≠ 0 .Имеемd 2 L(B) = 2(dx 1 ) 2 + 2(dx 2 ) 2приусловииdϕ1 (B) = dx 1 + dx 2 = 0 ,получимd 2 L(B) = 4(dx 2 ) 2 > 0 при dx 2 ≠ 0 , следовательно, точка B – условный локальный минимум.Точка C = ( −2, − 2, 0, − 12) - кандидат на максимум, активно ограничение ϕ 2 , λ 2 = −12 ≠ 0 .Имеем2d 2 L(C) = 2(dx 1 ) 2 + 2(dx 2 ) 2приусловииdϕ 2 (C) = −dx 1 − dx 2 = 0 ,2d L(C) = 4(dx 2 ) > 0 при dx 2 ≠ 0 , но точка кандидат на максимум – в C экстремума нет.Ответ: получена точка B = ( 2, 2) - условный локальный минимум.получимПример №2Дано:f ( X ) = x 12 + ( x 2 − 6) 2 → extrx1 + x 2 ≤ 4x 12 − x 2 ≤ 2Аналитически отыскать экстремум функции при ограничениях типа неравенства, используяаппарат необходимых и достаточных условий.Решение:Преобразуем ограничения к виду: ϕ j ( X ) ≤ 0x 1 + x 2 ≤ 4 ⇒ x 1 + x 2 − 4 ≤ 0 ⇒ ϕ1 ( X ) = x 1 + x 2 − 4x 12 − x 2 ≤ 2 ⇒ x 12 − x 2 − 2 ≤ 0 ⇒ ϕ 2 ( X ) = x 12 − x 2 − 2Построим на чертеже множество допустимых решений, задаваемое ограничениями.1.
Запишем классическую функцию Лагранжа:L( X, λ ) = x 12 + ( x 2 − 6) 2 + λ1 ( x 1 + x 2 − 4) + λ 2 ( x 12 − x 2 − 2)2. Запишем необходимые условия экстремума функции при ограничениях типа неравенства:∂L= 2 x 1 + λ 1 + 2λ 2 x 1 = 0 ∂x 1∂L= 2( x 2 − 6) + λ 1 − λ 2 = 0 ∂x 2λ 1 ( x 1 + x 2 − 4) = 02λ 2 ( x 1 − x 2 − 2) = 0 3. Решим полученную систему, рассматривая все случаи:Случай (а)Ограничение ϕ1 ( X ) = x 1 + x 2 − 4 < 0 - пассивно, следовательно λ 1 = 0 .Ограничение ϕ 2 ( X ) = x 12 − x 2 − 2 < 0 - пассивно, следовательно λ 2 = 0 .Тогда получим и решим следующую систему уравнений:2 x 1 = 0x 1 = 0 2( x − 6) = 0x = 6 2⇒ 2⇒λ1 = 0λ 1 = 0λ 2 = 0λ 2 = 0Т.о.
получено первое решение системы – точка A с координатами A = (0, 6, 0, 0) . Построим этуточку на чертеже.Случай (b)Ограничение ϕ1 ( X ) = x 1 + x 2 − 4 = 0 - активно.Ограничение ϕ 2 ( X ) = x 12 − x 2 − 2 = 0 - активно.Тогда получим и решим следующую систему уравнений: 2 x 1 + λ 1 + 2λ 2 x 1 = 0 2 x 1 + λ 1 + 2λ 2 x 1 = 0 2( x − 6) + λ − λ = 0 2 ( x − 6) + λ − λ = 01212 2 2⇒ ⇒x + x − 4 = 0x=−x+41221x 2 − x − 2 = 0x 2 − ( − x + 4) − 2 = 01211 2 x 1 + λ 1 + 2λ 2 x 1 = 0 2( x − 6) + λ − λ = 012 2⇒x = − x + 421x 2 + x − 6 = 011 2 x 1 + λ 1 + 2 λ 2 x 1 = 0− 6 + λ 1 − 6λ 2 = 0 2( x 2 − 6) + λ 1 − λ 2 = 02 + λ 1 − λ 2 = 0 2 x 1 + λ 1 + 2λ 2 x 1 = 0 x 2 = 7x 2 = 7 2( x − 6) + λ − λ = 012 2 x 1 = −3 x 1 = −3⇒ ⇒ ⇒x 2 = − x 1 + 42x+λ+2λx=04+λ+4λ=0112112x = − 1 ± 25 2( x 2 − 6) + λ 1 − λ 2 = 0− 8 + λ 1 − λ 2 = 0 12 x 2 = 2x 2 = 2 x = 2x = 2 1 1x 1 = 2 x 1 = −3x = 7x = 2 2 2λ 1 = −3.6λ 1 = 5.6λ 2 = −1.6λ = −2.42Т.о.
получено второе и третье решение системы – точки B, C с координатами соответственно:B = (−3, 7, − 3.6, − 1.6) , C = (2, 2, 5.6, − 2.4) .Построим эти точки на чертеже.Случай (c)Ограничение ϕ1 ( X ) = x 1 + x 2 − 4 = 0 - активно.Ограничение ϕ 2 (X) = x 12 − x 2 − 2 < 0 - пассивно, следовательно λ 2 = 0 .Тогда получим и решим следующую систему уравнений:2 x 1 + λ 1 = 0λ 1 = −2x 1λ 1 = −2 x 1 x 1 = −1 2( x − 6) + λ = 0 2 ( x − 6) − 2 x = 0x − x = 6x = 5 2 2 2111⇒ ⇒ ⇒ 2x 1 + x 2 − 4 = 0x 1 + x 2 − 4 = 0x 1 + x 2 = 4λ1 = 2λ 2 = 0λ 2 = 0λ 2 = 0λ 2 = 0Т.о.
получено четвертое решение системы – точка D с координатами D = (−1, 5, 2, 0) . Построимэту точку на чертеже.Случай (d)Ограничение ϕ1 ( X ) = x 1 + x 2 − 4 < 0 - пассивно, следовательно λ 1 = 0 .Ограничение ϕ 2 (X) = x 12 − x 2 − 2 = 0 - активно.Тогда получим и решим следующую систему уравнений:x = ± 15 λ 2 = −12 12x=1111 2x 2 = 2 λ1 = 02 x 1 + 2 λ 2 x 1 = 02x 1 (1 + λ 2 ) = 0λ = 0 2 2( x − 6) − λ = 0 2( x − 6 ) − λ = 0 1 x 1 − x 2 − 2 = 022 2 2⇒ ⇒⇒ λ 2 = −1λ = 0λ=0 1 1 x 1 = 0x = 022x − x − 2 = 0x − x − 2 = 0 2 x − λ = 12 1121222 x 2 = −2 λ 1 = 0λ = 0 x = −2 1 2λ 2 = −16Т.о.
получено пятое, шестое и седьмое решение системы – точки E, F, G с координатамисоответственно:E = (− 15 , 11 , 0, − 1) , F = ( 15 , 11 , 0, − 1) , G = (0, − 2, 0, − 16) .2222Построим эти точки на чертеже.4. Отбракуем лишние точки:ТочкаA = (0, 6, 0, 0)B = ( −3, 7, − 3.6, − 1.6)Проверка точек на принадлежностьМДР:ϕ1 ( X ) ≤ 0 и ϕ 2 ( X ) ≤ 0УсловияВыводточка неϕ1 ( A) = 2 > 0принадлежит МДРϕ 2 ( A ) = −8 < 0иотбраковываетсяточкаϕ1 (B) = 0принадлежит МДРϕ (B) = 02C = ( 2, 2, 5.6, − 2.4)ϕ1 (C) = 0ϕ 2 (C ) = 0D = (−1, 5, 2, 0)ϕ1 (D) = 0ϕ 2 (D) = −6 < 0E = (− 15 , 11 , 0, − 1)22ϕ1 (E ) = −1.239 < 0ϕ 2 (E) = 0F = ( 15 , 11 , 0, − 1)22ϕ1 (F) = 4.239 > 0G = (0, − 2, 0, − 16)ϕ1 (G ) = −6 < 0ϕ 2 (F) = 0ϕ 2 (G ) = 0Проверка условий на знак λ jУсловияВывод__________λ1 < 0точкаявляетсякандидатомнамаксимумМножителиЛагранжаразныхзнаков,точкаотбраковываетсяточкаявляетсякандидатомнаминимумточкаявляетсякандидатомнамаксимумλ2 < 0точкапринадлежит МДРλ1 > 0точкапринадлежит МДРλ1 > 0точкапринадлежит МДРλ1 = 0точка непринадлежит МДРиотбраковываетсяточкапринадлежит МДРλ2 < 0λ2 = 0λ2 < 0__________λ1 = 0точкаявляетсякандидатомнамаксимумλ2 < 0Таким образом, после отбраковки остались четыре точки:B = (−3, 7, − 3.6, − 1.6)- точка является кандидатом на максимумD = (−1, 5, 2, 0)- точка является кандидатом на минимум- точка является кандидатом на максимумE = (− 15 , 11 , 0, − 1)22G = (0, − 2, 0, − 16)- точка является кандидатом на максимум5.
Поверим достаточные условия 1-го порядка в каждой из полученных точек:ТочкаАктивные ограниченияB = (−3, 7, − 3.6, − 1.6)D = (−1, 5, 2, 0)E = (− 15 , 11 , 0, − 1)22G = (0, − 2, 0, − 16)ϕ1 = 0ϕ2 = 0числоактивныхограничений равночислу переменных –ϕ1 = 0числоактивныхограничений меньшечисла переменных –достаточные условияпервого порядка невыполненычислоактивныхограничений меньшечисла переменных –достаточные условияпервого порядка невыполненычислоактивныхограничений меньшечисла переменных –достаточные условияпервого порядка невыполненыϕ2 = 0ϕ2 = 0Знак λ jВыводλ1 < 0_____достаточные условияпервогопорядкавыполнены – точкаусловный локальныймаксимумнеобходима проверкадостаточных условийвторого порядка_____необходима проверкадостаточных условийвторого порядка_____необходима проверкадостаточных условийвторого порядкаλ2 < 0Таким образом, получено: точка B = ( −3, 7, − 3.6, − 1.6) – условный локальный максимум функции.6.
Для оставшихся точек проверим достаточные условия экстремума второго порядка.Запишем второй дифференциал функции Лагранжа:∂2L= 2 + 2λ 2∂x 12∂2L∂2L==0∂x 1∂x 2 ∂x 2 ∂x 1∂2L=2∂x 22d 2 L = ( 2 + 2λ 2 )(dx 1 ) 2 + 2(dx 2 ) 2Запишем дифференциал ограничения ϕ1 :∂ϕ1∂ϕ1dϕ1 ( X ) = 1 ⋅ dx 1 + 1 ⋅ dx 2=1=1⇒∂x 1∂x 2Запишем дифференциал ограничения ϕ 2 :∂ϕ 2∂ϕ 2dϕ 2 ( X ) = 2x1 ⋅ dx 1 − 1 ⋅ dx 2= 2x 1= −1⇒∂x 1∂x 2Исследуем точку D = ( −1, 5, 2, 0) - кандидат на минимум, активным в ней является ограничениеϕ1 , при этом λ1 = 2 ≠ 0 .Имеем d 2 L( D) = 2(dx1 ) 2 + 2(dx 2 ) 2 при условии dϕ1 ( D) = 1 ⋅ dx1 + 1 ⋅ dx 2 = 0 , получимdx1 = −dx 2 ⇒ d 2 L( D) = 4(dx 2 ) 2 > 0 при dx 2 ≠ 0 , следовательно, точка D = ( −1, 5, 2, 0) –условный локальный минимум.Исследуем точку E = ( − 15 , 11 , 0, − 1) - кандидат на максимум, активным в ней является22ограничение ϕ 2 , при этом λ 2 = −1 ≠ 0 .Имеем d 2 L( E) = 2(dx 2 ) 2 при условии dϕ 2 ( E ) = −2 15 ⋅ dx 1 − 1 ⋅ dx 2 = 0 , получим2dx 2 = −2 15 dx 1 ⇒ d 2 L( E ) = 60(dx 1 ) 2 > 0 при dx 1 ≠ 0 , но точка кандидат на максимум – в Е2экстремума нет.Исследуем точкуG = (0, − 2, 0, − 16) - кандидат на максимум, активным в ней являетсяограничение ϕ 2 , при этом λ 2 = −16 ≠ 0 .Имеем d 2 L(G ) = −30(dx 1 ) 2 + 2(dx 2 ) 2 при условии dϕ 2 (G ) = −1 ⋅ dx 2 = 0 , получимdx 2 = 0 ⇒ d 2 L(G ) = −30(dx1 ) 2 < 0условный локальный максимум.приdx 1 ≠ 0 , следовательно, точкаОтвет: получены точкиB = ( −3, 7)D = (−1, 5)G = (0, − 2)- условный локальный максимум- условный локальный минимум- условный локальный максимумG = (0, − 2, 0, − 16).