Линия уровня, соответствующая максимальному параметру С и проходящая через какую-либо точку допустимого множества, изображена на рис. 9.4 - АА, Координаты оптимальной точки находятся из системы уравнений
.3*4
откуда XI Х2
2x1 +2=2,
9.5. Метод множителей Лагранжа
Геометрическая интерпретация метода Лагранжа основана на том, что линия уровня целевой функции с максимальным значением будет касаться линии границы в точке, являющейся оптимальным решением задачи.
Пусть требуется решить задачу нелинейного программирования следующего вида:
/(xi,...,x„)->max(min). gl (xi,...,x„)=Z>i, g2 (х,,...,х„)=Й2,
где функции / и gi, i = \,m непрерывны, и непрерывны их частные про-
изводные по ху, j= 1,« .
Для решения поставленной задачи может быть применен метод множителей Лагранжа. Объясним идею метода на примере задачи нелинейного программирования, зависящей от двух переменных и имеющей только одно ограничение:
max/(xi,X2) g(xi,X2) = fe.
Будем исходить из геометрической интерпретации задачи, описанной в параграфе 9.4. А именно, заметим, что линия уровня с максимальным значением параметра С будет касаться линии границы в точке, являющейся оптимальным решением задачи. Схематично это изображено на рис. 9.5.
fix)
Рис. 9.5
Поскольку две гладкие линии (имеющие непрерывные частные производные) касаются друг друга в точке х*, то их векторы-нормали сона-правлены. Поскольку вектор-нормаль есть градиенты функций (вектор частных производных), то справедливо векторное соотношение
/ (х ) = (х ), где Я есть некоторый коэффициент пропорционально-СТИ. Координаторами векторов / (х ) и g (х ) являются значения част-ных производных функций/и g соответственно в точке х .
gix) =
дх\ дХ2
dg . dg Щдх2)
Из условия пропорциональности в точке х имеем
Sjcj dxi
дх2 дх2
Для определения значений х и Х2, в которых функция / достигает максимума, к этим уравнениям надо добавить условие принадлежности точки X* графику функции gx*,X2=i.
Окончательно получаем систему уравнений, определяющую оптимальное решение поставленной задачи
dxi dxi
дх2 дх2 8{х\,Х2) = Ь.
Введем новую функцию
,Х2,Я) = /(1 ,Х2 ) + Я() - g(xi Х2 )).
Тогда последняя система перепишется в виде
дР{х1,Х2,Л) df{xi,X2) Sg{xi,X2)Q,
dxidxiSxTj
дР{х1,Х2,Я) df{x\,X2) 6g(xi,X2) dx2dx2dx2
= b-g{xi,X2) = 0.
Функцию F называют функцией Лагранжа.
Приведем ниже алгоритм метода множителей Лафанжа решения задач нелинейного программирования.
Этап 1. Составляют функцию Лафанжа
F(xi,...,x„,Ai,...,A) =
= /(xj,) + 2 Л- (» - gi {х\.«)) /=1
Этап 2. Находят частные производные функции Лафанжа по х и Л,-, у = 1,и; i = \,m и приравнивают их к нулю
dF df
dXj dXj ,-=1 dXj
(9.5)
g,(xi,...,x,,) = i,-, /= \,m.
Этап 3. Решают систему (9.5) и определяют точки, в которых функция /(xi,...,x„) может иметь экстремум.