Введение в нелинейное программирование

Тема 3. Введение в нелинейное программирование Лекция 8 2 Различные виды задач нелинейного программирования.  Задача безусловной оптимизации.  Задача условной оптимизации.  Стандартная задача нелинейного программирования.  Задача нелинейного программирования смешанного типа. 3 Задача безусловной оптимизации Задача нахождения max f  X  ( x1 , x2 )    min f  X    ( x1 , x2 )  без дополнительных ограничений называется задачей нелинейного программирования без ограничений (задачей безусловной оптимизации) M 4 – всегда выпукло Задача условной оптимизации Задача нахождения max f  X  ( x1 , x2 )    min f  X   ( x1 , x2 )  при ограничениях g i ( x1 , x2 )  0, i  1,..., m, называется задачей нелинейного программирования с ограничениями типа равенств (задачей условной оптимизации) 5 𝑀– выпукло, если 𝑔𝑖 𝑥1 , 𝑥2 , 𝑖 = 1, … , 𝑚, – линейные Стандартная задача нелинейной оптимизации max f ( x1 , x2 ) ( x1 , x2 ) при ограничениях gi ( x1 , x2 )  0, i  1,..., m M – выпуклое, если g i – вогнутые 6 min f ( x1 , x2 ) ( x1 , x2 ) при ограничениях gi ( x1 , x2 )  0, i  1,..., m M – выпуклое, если g i – выпуклые Задача нелинейного программирования смешанного типа max f  X  ( x1 , x2 ) при ограничениях g i ( x1 , x2 )  0, i  1,..., r ,    min f  X   ( x1 , x2 )  M – выпукло, если: g i ( x1 , x2 )  вогнутые g i ( x1 , x2 )  0, i  r  1,..., p, g i ( x1 , x2 )  выпуклые g i ( x1 , x2 )  0, i  p  1,..., m, g i ( x1 , x2 )  линейные 7 Необходимые и достаточные условия оптимальности 8  Необходимые условия позволяют найти точки, подозрительные на экстремум.  Достаточные условия позволяют убедиться в том, что найденная точка – искомое решение.  Если какие-то условия являются необходимыми и достаточными одновременно, они однозначно определяют решение оптимизационной задачи. Корректность обращение к Excel Если необходимые условия являются достаточными, обращение к Excel корректно. Общая идея. Необходимые условия являются достаточными для любого типа оптимизационной задачи, если: 9 1. Целевая функция выпукла (min) или вогнута (max) на 𝑀. 2. Множество допустимых решений 𝑀 – выпукло. Необходимые условия оптимальности в задаче безусловной оптимизации Если X  x1 , x2  M – оптимальное решение в задаче безусловной оптимизации: * * * max f ( x , x ) ( x1 , x2 ) 1 2    min f ( x1 , x2 )   ( x1 , x2 )  то выполняется следующее условие (условие стационарной точки): 10 f ( X * )  0, i  1,2. xi Достаточность условий оптимальности Если f ( x1, x2 ) – вогнутая (выпуклая) для 2 любых ( x1 , x2 )  R то стационарная точка X  x , x * * 1 * 2  является решением задачи безусловной оптимизации на максимум (на минимум). 11 Пример 1 Запишите необходимые условия оптимальности и проверьте их достаточность: min f  x1 , x2 , x3   min  x12  2 x22  3x32  2 x1 x2  2 x1 x3  Задача безусловной оптимизации. Необходимые условия оптимальности:  f 0   x1  f 0   x2  f 0   x3  f  2 x1  2 x2  2 x3   x1  f  4 x2  2 x1   x2  f  6 x3  2 x1   x3 2 x1  2 x2  2 x3  0  4 x2  2 x1  0 6 x  2 x  0 1  3 Решение этой системы – стационарная точка. Будет ли она точкой минимума? 12 Пример 1 Проверим выпуклость функции 𝑓 𝑥1 , 𝑥2 , 𝑥3 . Построим матрицу Гессе и изучим её знакоопределённость. 2 f  2; x12 2 f  2; x1x2  f  4; x22  f  2; x1x3 2 f  6; x32 2 f  0; x2 x3 2 1  2  0; 2 2 2 2   4  0; 2 4  2 2 2    H ( x1 , x2 , x3 )   2 4 0   2 0 6   2 2 2  2  2 4 0  8  0. 2 0 6 Все ведущие главные миноры матрицы Гессе положительны. Следовательно, матрица является положительно определённой. 13 Из этого следует, что функция 𝑓 𝑥1 , 𝑥2 , 𝑥3 является строго выпуклой на всей области определения. Пример 1 Вывод. В рассматриваемой задаче безусловной оптимизации целевая функция является строго выпуклой на всей области определения. Таким образом, необходимые условия являются достаточными. Стационарная точка (решение системы) является точкой минимума. 14 Необходимые условия оптимальности в задаче условной оптимизации max f ( x , x ) ( x1 , x2 ) 1 2 g i ( x1 , x2 )  0, i  1,..., m, Функция Лагранжа: m L( x1 , x2 1 , 2 ,..., m )  f ( x1 , x2 )   i g i ( x1 , x2 ). i 1 Если 𝑋 ∗ = 𝑥1∗ , 𝑥2∗ – оптимальное решение в задаче условной оптимизации: max f ( x , x ) ( x1 , x2 ) 1 2 g i ( x1 , x2 )  0, i  1,..., m, то существует вектор 15   *  1* , *2 ,..., *m : Необходимые условия оптимальности (условия Лагранжа) m L( x1 , x2 1 , 2 ,..., m )  f ( x1 , x2 )   i g i ( x1 , x2 ). i 1 Условия оптимальности  f ( x1 , x2 ) * g i ( x1 , x2 )   i  0, j  1,2,  x i 1 x j j   g ( x * , x * )  0, i  1,..., m.  i 1 2 * * m Условия допустимости * * Достаточность условий оптимальности Если функция 𝑓 𝑥1 , 𝑥2 – вогнутая (выпуклая в случае минимизации) для любых 𝑥1 , 𝑥2 ∈ 𝑀, а функции 𝑔𝑖 𝑥1 , 𝑥2 , 𝑖 = 1, … , 𝑚, являются линейными, то стационарная точка 𝑋 ∗ = 𝑥1∗ , 𝑥2∗ является решением задачи условной оптимизации. 17 Пример 2 Запишите необходимые условия оптимальности и проверьте их достаточность: min f  x1 , x2 , x3   min  x12  2 x22  3 x32  2 x1 x2  2 x1 x3  x1  x2  x3  1, x1  x2  2. x1  x2  x3  1  0, x1  x2  2  0. Задача условной оптимизации. Для составления функции Лагранжа ограничения переписаны таким образом, чтобы функции 𝑔𝑖 𝑥1 , 𝑥2 , 𝑥3 , 𝑖 = 1, 2, были записаны в явном виде. Функция Лагранжа для данного примера имеет: L  x1 , x2 , x3 , 1 , 2   x12  2 x22  3x32  2 x1 x2  2 x1 x3  1  x1  x2  x3  1  2  x1  x2  2  18 Пример 2 L  x1 , x2 , x3 , 1 , 2   x12  2 x22  3x32  2 x1 x2  2 x1 x3  1  x1  x2  x3  1  2  x1  x2  2  Выпишем условия Лагранжа для данной функции. Для этого вычислим производные от функции Лагранжа по всем переменным и приравняем их к нулю.  L  2 x1  2 x2  2 x3  1  2   x1  L  4 x2  2 x1  1  2   x  2   L  6 x3  2 x1  1   x  3  L  x1  x2  x3  1     1  L  x1  x2  2      2 19 Условия оптимальности 2 x1  2 x2  2 x3  1  2  0 4 x  2 x      0 2 1 1 2   6 x3  2 x1  1  0 x  x  x 1  0  1 2 3   x1  x2  2  0 Условия допустимости Пример 2 Вывод. В рассматриваемой задаче условной оптимизации: 1. Целевая функция является строго выпуклой на всей области определения (показано в Примере 1). 2. Множество допустимых решений задано линейными ограничениями (следовательно, является выпуклым). Таким образом, необходимые условия являются достаточными. Стационарная точка (решение системы) является точкой минимума. 20 Необходимые условия оптимальности в стандартной ЗНЛП Функция Лагранжа: m L( x1 , x2 1 , 2 ,..., m )  f ( x1 , x2 )   i g i ( x1 , x2 ). i 1 Если X *  x1* , x2*  M – оптимальное решение в стандартной задаче нелинейной оптимизации: max f ( x , x ) ( x1 , x2 ) 1 2 gi ( x1 , x2 )  0, i  1,...,m, то существует вектор 21  *  0, i  1,..., m, i  *  1* , *2 ,..., *m : Необходимые условия оптимальности (условия Куна - Таккера) Условия оптимальности Условия допустимости  g i ( x1 , x 2 )  0, i  1,..., m,  * * * * m  f ( x1 , x2 ) * g i ( x1 , x2 )   i  0, j  1,2,  x j i 1  x j * g ( x* , x* )  0, i  1,..., m.  i i 1 2 * * Условия связности Достаточность условий оптимальности Если функция 𝑓 𝑥1 , 𝑥2 – вогнутая (выпуклая) для любых 𝑥1 , 𝑥2 ∈ 𝑀, и функции 𝑔𝑖 𝑥1 , 𝑥2 , 𝑖 = 1, … , 𝑚, – вогнутые (выпуклые), то стационарная точка 𝑋 ∗ = 𝑥1∗ , 𝑥2∗ является решением стандартной задачи нелинейного программирования на максимум (минимум). 23 Пример 3 Запишите необходимые условия оптимальности и проверьте их достаточность: min f  x1 , x2 , x3   min  x12  2 x22  3x32  2 x1 x2  2 x1 x3  x1  x2  x3  1,  x1  x2  x3  1  0, x12  x2  2  x12  x2  2  0 x1  0, x2  0.  x1  0,  x2  0. Стандартная задача нелинейной оптимизации. Для построения функции Лагранжа ограничения переписаны так, чтобы функции 𝑔𝑖 𝑥1 , 𝑥2 , 𝑥3 , 𝑖 = 1, … , 4, имели явный вид. Функция Лагранжа для данного примера имеет вид: L  x1 , x2 , x3 , 1 , 2 , 3 , 4   x12  2 x22  3 x32  2 x1 x2  2 x1 x3  1   x1  x2  x3  1  24 2   x12  x2  2   3   x1   4   х2  Пример 3 Запишем условия Куна-Таккера, для чего продифференцируем функцию Лагранжа по переменным 𝑥𝑗 , 𝑗 = 1, 2, 3, и добавим условия связности и допустимости. L  x1 , x2 , x3 , 1 , 2 , 3 , 4   x12  2 x22  3 x32  2 x1 x2  2 x1 x3  1   x1  x2  x3  1  2   x12  x2  2   3   x1   4   х2   L  2 x1  2 x2  2 x3  1  22  3   x  1  L  4 x2  2 x1  1  2  4   x  2  L  6 x3  2 x1  1   x  3 25  2 x1  2 x2  2 x3  1  22 x1  3  0 4 x  2 x        0 1 1 2 4  2 6 x3  2 x1  1  0  x  x  x  1  0  1 2 3  x12  x2  2  0   x1  0  x  0  2 1   x1  x2  x3  1  0  2   x12  x2  2   0  3   x1   0  4   x2   0 Достаточность необходимых условий в примере 3 Выпуклость целевой функции уже доказана в примере 1. Необходимо проверить выпуклость функций, задающих множество допустимых решений 𝑀.  x1  x2  x3  1  0,  x12  x2  2  0  x1  0,  x2  0. В данном примере НЕ все функции, задающие ограничения, являются линейными. Рассмотрим нелинейное ограничение. 26 По свойству выпуклых функций известно, что данное ограничение будет определять выпуклое множество в том случае, если функция в его левой части – выпуклая. Исследуем выпуклость данной функции с помощью матрицы Гессе. Матрица Гессе для нелинейного ограничения в примере 3 g  x12  x2  2 g  2 x1 ; x1 2 g  2; 2 x1 g  1; x2 2 g  0; 2 x2 2 g 0 x1x2 1  2  0,  2 0 H  x1 , x2       2 0 2  0 0 0 Один из главных ведущих миноров оказался равным 0. Необходимо проверить, нет ли отрицательных среди просто главных миноров. Осталось рассмотреть один главный минор: 12  0 27 Матрица Гессе для нелинейного ограничения примере 3 Это означает, что матрица Гессе для функции 𝑔 𝑥1 , 𝑥2 является положительно полуопределённой. Следовательно, функция 𝑔 𝑥1 , 𝑥2 = 𝑥12 − 𝑥2 − 2 является выпуклой (не строго). Этого достаточно, чтобы заключить, что неравенство x12  x2  2  0 задаёт выпуклое множество по свойству выпуклых функций. 28 Пример 3 Вывод. В рассматриваемой стандартной задаче оптимизации: 1. Целевая функция является строго выпуклой на всей области определения (показано в Примере 1). 2. Множество допустимых решений является выпуклым, т.к. часть ограничений определяются линейными неравенствами, а нелинейное ограничение задаёт выпуклое множество по свойству. Таким образом, необходимые условия являются достаточными. Стационарная точка (решение системы) является точкой минимума. 29 Замечание Рассмотрим условия связности: i* gi ( x1* , x2* )  0, i  1,..., m. Для его выполнения достаточно, чтобы один из множителей этого произведения равнялся 0. Множители Лагранжа неотрицательны по условию. Если в результате решения системы получилось, что какой-либо множитель Лагранжа 𝜆∗𝑖 > 0, это означает, что соответствующее ему ограничение должно выполняться на оптимальном решении как равенство (т.е., являться активным): i*  0  gi ( x1* , x2* )  0 Если какое-либо ограничение не является активным (ресурс расходуется не полностью), то соответствующий множитель Лагранжа обращается в 0 на оптимальном решении: 30 gi ( x1* , x2* )  0  i*  0 Необходимые условия оптимальности в смешанной ЗНЛП max f ( x , x ) ( x1 , x2 ) 1 2 gi ( x1 , x2 )  0, i  1,..., r , gi ( x1 , x2 )  0, i  r  1,..., p, gi ( x1 , x2 )  0, i  p  1,..., m,  gi ( x1 , x2 )  0 gi ( x1 , x2 )  0   , i  p  1,..., m  gi ( x1 , x2 )  0 31  gi ( x1 , x2 )  0 , i  p  1,..., m   gi ( x1 , x2 )  0 Сведение смешанной ЗНЛП к стандартной ЗНЛП max f ( x , x ) ( x1 , x2 ) 1 2 gi ( x1 , x2 )  0, i  1,..., r ,  gi ( x1 , x2 )  0, i  r  1,..., p,  gi ( x1 , x2 )  0, i  p  1,..., m, gi ( x1 , x2 )  0, i  p  1,..., m 32 i ,i  1,..., m  m1 m1  m  p Домашнее задание № 4 Записать необходимые условия оптимальности и проверить их достаточность. СРОК 14.04.2020 33 Выводы  Обращение к «Поиску решения» MS Excel будет корректным только в случае, когда необходимые условия являются достаточными.  Таким образом, перед обращением к Excel для решения ЗНЛП необходимо убедиться в достаточности необходимых условий. В обобщённом виде (для ЗНЛП любого типа) эти условия можно записать следующим образом: 1. Должна иметь место выпуклость (в случае поиска минимума) или вогнутость (в случае поиска максимума) целевой функции. 2. Множество допустимых решений должно быть выпуклым. При выполнении этих условий можно сделать вывод о том, что обращение к «Поиску решений» корректно. 34 Пример 4 Организация реализует автомобили двумя способами: через розничную и оптовую торговлю. При реализации 𝑥1 автомобилей в розницу расходы на реализацию равны 4𝑥1 + 𝑥12 руб., а при продаже оптом 𝑥2 автомобилей расходы составляют 𝑥22 руб. Найти оптимальный способ реализации автомобилей, минимизирующий суммарные расходы, если общее число предназначенных для продажи автомобилей составляет 200 шт, при этом в розницу должно быть продано не менее 50 шт. 35 Математическая модель. Пример 4 𝑥1 , шт. – число автомобилей, реализуемых в розницу 𝑥2 , шт. – число автомобилей, реализуемых оптом 4𝑥1 + 𝑥12 + 𝑥22 → 𝑚𝑖𝑛 𝑥1 + 𝑥2 = 200 𝑥1 ≥ 50 𝑥1 ≥ 0, 𝑥2 ≥ 0 Смешанная задача нелинейной оптимизации. 36 Проверка корректности обращения к Excel Проверим выпуклость целевой функции: 4𝑥1 + 𝑥12 + 𝑥22 2 0  2   Убедитесь, что матрица Гессе данной функции: H  x1 , x2    Проверьте, что матрица является положительно определённой. Следовательно, целевая функция является строго выпуклой. 2. Множество допустимых решений данной задачи выпукло, т.к. задано линейными ограничениями. Таким образом, обращение к Excel является корректным. 1. 37 Решение в Excel =4*C3+C3^2 38 =D3^2 4𝑥1 + 𝑥12 + 𝑥22 → 𝑚𝑖𝑛 𝑥1 + 𝑥2 = 200 𝑥1 ≥ 50 𝑥1 ≥ 0, 𝑥2 ≥ 0 =СУММ(C9:D9) Поиск решения 39 Анализ решения на чувствительность Отчет по устойчивости 40 Анализ решения на чувствительность Нормированный (приведённый) градиент (аналог нормированной стоимости в ЗЛП) – показывает скорость изменения значения ЦФ при изменении значения этой переменной. (Равен 0, если значение соответствующей переменной не достигает ни одной из своих явно заданных границ.) 41 Анализ решения на чувствительность Отчет по устойчивости 42 Анализ решения на чувствительность Множитель Лагранжа (аналог теневой цены, т.е. двойственной оценки, в ЗЛП) – показывает мгновенную скорость изменения значения ЦФ при изменении правой части данного ограничения. (Множитель Лагранжа отличен от 0 тогда и только тогда, когда данное ограничение является связанным в оптимальном решении.) 43 Анализ решения на чувствительность Отчет по устойчивости 44 Лабораторная работа № 3 Необходимо решить задачу нелинейного программирования в соответствии со своим вариантом. Не забудьте проверить корректность обращения к Excel. Срок выполнения работы: 21.04.2020 для обеих групп. 45