Метод неопределенных множителей Лагранжа

ТЕМА ЛЕКЦИИ 5 МЕТОД НЕОПРЕДЕЛЕННЫХ МНОЖИТЕЛЕЙ ЛАГРАНЖА 1. Применение метода для решения задач нелинейного программирования с ограничениями-равенствами Цель данной лекции состоит в изучении метода, который в дальнейшем будет применяться для решения задач оптимизации разработки группы залежей, связанных либо общим заданным уровнем добычи нефти (газа), либо ресурсными ограничениями (например, общими допустимыми затратами на разработку всех залежей). Этот метод неопределенных множителей Лагранжа (сокращенно метод Лагранжа) относится к методам нелинейного программирования и предназначен для решения задач оптимизации следующего вида: 𝑓(𝑥1 , … , 𝑥𝑛 ) → max (1) ℎ𝑗 (𝑥1 , … , 𝑥𝑛 ) = 0, 𝑗 = 1, 𝑚 , (2) 𝑋 где Х=(x1, …,xn) – вектор искомых переменных, причем n>m (число искомых переменных больше числа уравнений системы (2)). Для определенности задача (1),(2) поставлена как задача на поиск условного максимума. Однако нет никаких ограничений на решение задач, в которых функция цели стремится к минимуму. В задаче (1),(2) хотя бы одна из функций f(X) и hj(X) является нелинейной. Это не позволяет применить для ее решения методы линейного программирования (например, симплекс-метод), по крайней мере, без предварительного преобразования задачи (линеаризации исходных зависимостей). Будем считать, что функции f(X) и hj(X), j=1,2,…,m, являются дифференцируемыми (имеющими производные по каждой переменной). Если в исходной задаче имеются ограничения-неравенства, то их необходимо заменить эквивалентными ограничениями-равенствами (см. ниже). Кроме этого, правые части уравнений (2) должны содержать нули. Если 1 в правой части находится число, не равное нулю, то это число необходимо, не забывая минус, перевести в левую часть. Основная идея метода Лагранжа состоит в замене исходной задачи с ограничениями эквивалентной задачей без ограничений. Для этого 𝐿(𝑥1 , … , 𝑥𝑛 , 𝜆1 , … , 𝜆𝑚 ) ≡ 𝑓(𝑥1 , … , 𝑥𝑛 ) + ∑ 𝜆𝑗 ℎ𝑗 (𝑥1 , … , 𝑥𝑛 ), (3) формируется функция Лагранжа – L(x1, …,xn,1,…, m): 𝑚 𝑗=1 где =(1,…, m) – вектор дополнительных искомых переменных, которые называются множителями Лагранжа. Таких множителей столько, сколько уравнений содержится в системе (2). После этого формируется новая задача на безусловный экстремум: max min{𝐿(𝑥1 , … , 𝑥𝑛 , 𝜆1 , … , 𝜆𝑚 )}. 𝑋 Задача (4) (4) Λ представляет собой модель игры двух лиц с противоположными интересами. Один из игроков за счет выбора значений вектора Х пытается увеличить свою функцию выигрыша, в роли которой выступает функция Лагранжа (3). Его противник за счет выбора значений вектора  пытается нанести наибольший ущерб первому игроку, т.е. уменьшить функцию выигрыша (функцию Лагранжа). Именно на этом, а также на том, что в допустимом решении, т.е. при значениях первоначальных искомых переменных (x1,…,xn), удовлетворяющих всем ограничениям (2), функция Лагранжа превращается в функцию цели (1), основана эквивалентность задачи (1),(2) и задачи (4). Другими словами, введение дополнительных переменных 1,…, m и минимизация функции Лагранжа «заставляет» первоначальные искомые переменные x1, …,xn «двигаться» в область допустимых решений, где выполняются ограничения (2). Множители Лагранжа можно интерпретировать как «штрафы» за нарушение ограничений (2). Отметим, если бы функцию цели (1) необходимо было бы минимизировать, то задача (4) имела бы вид: 2 min max{𝐿(𝑥1 , … , 𝑥𝑛 , 𝜆1 , … , 𝜆𝑚 )}. 𝑋 Λ Теперь вместо задачи (1),(2) решается задача (4), которая представляет собой задачу на поиск экстремума функции (3) при отсутствии ограничений. Поэтому решение задачи (4) сводится к поиску нулей частных производных функции (3) по каждой переменной из набора {x1, …,xn,1,…, m}, т.е. к решению нелинейной (в общем случае) системы уравнений: 𝑚 𝜕ℎ𝑗 𝜕𝐿 𝜕𝑓 = +∑ = 0, 𝜕𝑥1 𝜕𝑥1 𝜕𝑥1 𝑗=1 ………………………… 𝑚 𝜕ℎ𝑗 𝜕𝐿 𝜕𝑓 = +∑ = 0, 𝜕𝑥𝑛 𝜕𝑥𝑛 𝜕𝑥𝑛 (5) 𝑗=1 𝜕𝐿 = ℎ1 (𝑥1 , … , 𝑥𝑛 ) = 0, 𝜕𝜆1 ………………………… 𝜕𝐿 = ℎ𝑚 (𝑥1 , … , 𝑥𝑛 ) = 0. 𝜕𝜆𝑚 Система уравнений (5) содержит (n+m) неизвестных и (n+m) уравнений. Причем m последних уравнений ни что иное, как исходные ограниченияравенства (2). Таким образом, решение системы уравнений (5) позволяет выполнить ограничения (2) и найти максимум функции цели (1), т.е. решить исходную задачу (1),(2). Т.к. равенство нулю производных – это лишь необходимое условие максимума дифференцируемой функции, т.е. решение системы (5) может и не привести к максимуму функции цели (1). Чтобы необходимое условие стало и достаточным необходимо ввести на вид функций f(X) и hj(X), j=1,2,…,m, дополнительные требования. В примерах по применению метода Лагранжа на этом остановимся подробнее. Итак, пусть функции f(X) и hj(X), j=1,2,…,m, удовлетворяют таким требованиям. Тогда, если система (5) имеет единственное решение, то это решение и будет оптимальным решением задачи 3 (1),(2). Если же решений несколько, то из этих решений в качестве оптимального надо выбрать то, которое соответствует наибольшему значению функции цели (1). Итак, метод Лагранжа сводится к следующим операциям: 1) составляется функция Лагранжа; 2) находится производная функции Лагранжа по каждой искомой переменной; 3) каждая производная приравнивается нулю; 4) к полученным таким образом уравнениям добавляются ограниченияравенства задачи; 5) определяется решение полученной системы уравнений, которое принимается за оптимальное решение исходной задачи. Рассмотрим пример. Пусть требуется решить задачу: найти такие x1 и x2, что x1x2→max 2x1+ x2=1. Решение этой задачи можно получить следующим образом. Выразим x2 через x1: x2=1 – 2x1. Выразим функцию цели только через x1: x1(1 – 2x1). Т.к. эта функция представляет собой параболу «ветвями вниз», то нуль ее производной по x1 будет определять точку максимума. Поэтому, решая уравнение 1 – 4x1=0, найдем сначала оптимальное значение для первой переменной: x1*=1/4, а затем и для второй: x2*=1/2. Теперь рассмотрим решение этой же задачи методом Лагранжа. Для этого преобразуем ограничение: 2x1+ x2–1=0. Составим функцию Лагранжа (т.к. ограничение одно, то и множитель Лагранжа будет один): L(x1,x2,) x1x2+(2x1+ x2-1). Найдем производные функции Лагранжа: 4 𝜕𝐿 = 𝑥2 + 2𝜆 = 0, 𝜕𝑥1 𝜕𝐿 = 𝑥1 + 𝜆 = 0, 𝜕𝑥2 𝜕𝐿 = 2𝑥1 + 𝑥2 − 1 = 0. 𝜕𝜆 Из первого уравнения выражаем x2 через : x2= – 2; из второго уравнения выражаем x1 через : x1= –; подставим полученные формулы в третье уравнение: 2(–)+(– 2) –1=0. Откуда *= – 1/4; x1*=1/4; x2*=1/2. 2. Применение метода для решения задач нелинейного программирования с ограничениями-неравенствами Рассмотрим изменения в методе Лагранжа при его применении в задаче, содержащей ограничения-неравенства: 𝑓(𝑥1 , … , 𝑥𝑛 ) → max (6) 𝑔𝑘 (𝑥1 , … , 𝑥𝑛 ) ≤ 0, 𝑘 = 1, 𝑙 . (7) 𝑋 В задаче (6),(7) число ограничений-неравенств может быть и меньше, и больше, и равно числу искомых переменных. Чтобы воспользоваться методом Лагранжа для решения задачи (6),(7) необходимо, прежде всего, ограничения-равенства. Для превратить этого в ограничения-неравенства каждое неравенство в вводится дополнительная переменная. Обозначим ее через yk. После этого k-е ограничение-неравенство заменяется эквивалентным ограничением- 𝑔𝑘 (𝑥1 , … , 𝑥𝑛 ) + 𝑦𝑘2 = 0, 𝑘 = 1, 𝑙 . (8) равенством: Выполнение каждого из уравнений (8) влечет выполнение соответствующего неравенства (7). Теперь методом Лагранжа решается задача (6),(8), в которой неизвестных (n+l) и уравнений (n+l). 5 Составим для этой задачи функцию Лагранжа, которая теперь будет зависеть от Х=(x1, …,xn), Y=(y1,…,yl) и =(1,…, l): 𝑙 𝐿(𝑥1 , … , 𝑥𝑛 , 𝜆1 , … , 𝜆𝑚 ) ≡ 𝑓(𝑥1 , … , 𝑥𝑛 ) + ∑ 𝜆𝑙 [𝑔𝑙 (𝑥1 , … , 𝑥𝑛 ) + 𝑦𝑙2 ]. (9) 𝑘=1 Найдем производные функции (9) по каждой переменой из набора {x1, …,xn,y1,…,yl,1,…, l}: 𝑙 𝜕𝐿 𝜕𝑓 𝜕𝑔𝑙 = +∑ = 0, 𝜕𝑥𝑗 𝜕𝑥𝑗 𝜕𝑥𝑗 𝑗 = 1, 𝑛 𝑙=1 𝜕𝐿 = 𝑔𝑠 (𝑥1 , … , 𝑥𝑛 ) + 𝑦𝑠2 = 0, 𝜕𝜆𝑠 𝜕𝐿 = 2𝜆𝑠 𝑦𝑠 = 0, 𝜕𝑦𝑠 𝑠 = 1, 𝑙 (10) 𝑠 = 1, 𝑙. В системе уравнений (10) неизвестных (n+2l) и уравнений (n+2l). Решая эту систему получим {x1*, …,xn*}– оптимальное решение задачи (6),(7). Рассмотрим пример. Пусть требуется решить задачу с ограниченияминеравенствами: найти такие x1 и x2, что x1x2→max (11) 2x1+ x2–10 (12) x10, x20. (13) Выполним анализ задачи. Из вида функции цели следует, что при заданных ограничениях (13) единственная возможность увеличить значение функции цели связана с увеличением x1 и x2. При этом будет увеличиваться левая часть ограничения (12). Следовательно, ограничение-неравенство (12) можно без всяких дополнительных переменных заменить ограничением равенством: 2x1+ x2–1=0. Если теперь на время «забыть» об ограничениях (13), то полученная задача полностью совпадает с задачей из предыдущего примера: x1x2→max 2x1+ x2=1. 6 Ее оптимальное решение получено выше: x1*=1/4; x2*=1/2. Т.к. это решение удовлетворяет ограничениям (13), то оно становится оптимальным и для задачи (11)-(13). Примечание. Если сразу отбросить ограничения (13), то задача (11),(12) не будет иметь решения. Т.к. в этом случае для увеличения функции цели можно неограниченно уменьшать значения искомых переменных: x1→–, x2→–. При этом ограничение (12) будет выполняться, а функция цели (11) будет стремиться к . Рассмотрим решение задачи (11)-(13) методом Лагранжа. Преобразуем ограничения-неравенства в ограничения-равенства с помощью введения дополнительных переменных y, z и w: 2x1+x2+y2–1=0 x1–z2=0 x2–w2=0. Теперь составим функцию Лагранжа, учитывая функцию цели (11) и три последних ограничения-равенства: L(x1,x2,y,z,w,,,) x1x2+(2x1+ x2+y2–1)+ ( x1–z2)+ ( x2–w2). Найдем производные функции Лагранжа по каждой переменной: 𝜕𝐿 = 𝑥2 + 2𝜆 + 𝜇 = 0, 𝜕𝑥1 (14) 𝜕𝐿 = 𝑥1 + 𝜆 + 𝛿 = 0, 𝜕𝑥2 (15) 𝜕𝐿 = 2𝑥1 + 𝑥2 + 𝑦 2 − 1 = 0, 𝜕𝜆 𝜕𝐿 = 𝑥1 − 𝑧 2 = 0, 𝜕𝜇 𝜕𝐿 = 𝑥2 − 𝑤 2 = 0, 𝜕𝛿 𝜕𝐿 = −2𝑦𝜆 = 0, 𝜕𝑦 7 (16) (17) (18) (19) 𝜕𝐿 = −2𝑧𝜇 = 0, 𝜕𝑧 𝜕𝐿 = −2𝑤𝛿 = 0. 𝜕𝑤 (20) (21) Решим систему (14)-(21). Для этого, прежде всего, заметим, что х10 и х20, т.к. в противном случае функция цели (11) равнялась бы нулю, а при х1>0 и х2>0, функция цели (11) больше нуля. Следовательно, с учетом (17) и (18) z0, w0. Тогда из (20) и (21) следует, что =0 и =0. Но тогда из (14) и (15) следует, что 0 (в ином случае х1=0 и х2=0). Поэтому из (19) следует, что y=0. Таким образом, с учетом (14)-(16) система (14)-(21) преобразуется к виду: 𝜕𝐿 = 𝑥2 + 2𝜆 = 0, 𝜕𝑥1 𝜕𝐿 = 𝑥1 + 𝜆 = 0, 𝜕𝑥2 𝜕𝐿 = 2𝑥1 + 𝑥2 − 1 = 0. 𝜕𝜆 Решая полученную систему уравнений, найдем (см. предыдущий пример, п.2) оптимальные значения искомых переменных: x1*=1/4; x2*=1/2, которые совпадают с решениями, полученными другими способами. По сути дела, метод Лагранжа – это способ сведения задач нелинейного программирования к задачам на безусловный экстремум, решение которых, в свою очередь, сводится к решению систем уравнений аналитическими или численными методами. 8