где все функции ¦, g1 , g 2 ,…,g m предполагаются определенными на Е². Если точка минимума ( локального или глобального ) лежит на границе допустимого множества , определяемого записанной выше системой неравенств из (2) , (3), то градиент целевой функции не обязательно равен нулевому вектору , т.е.
Ѧ(x0 ) ¹ 0 .
Это означает , что для задач оптимизации с ограничениями условия оптимальности (теорема 3 и 4) непригодны.
При решении задач условной оптимизации ограничения учитывают , вводя функцию Лагранжа переменных X и l .
L(x, y) = l0 ¦(x) + l i g i (x) + l i g i (x), (4)
где l0 ,l1 ,l2 ,…,lm - множители Лагранжа, которые составляют вектор, обозначаемый l Î Еm .
Условимся ограничение g i (x)£ 0 называть активным в точке x0 , если это неравенство при x = x0 обращается в равенство , т.е. если g i (x0 )=0 . В случае строгого неравенства g i (x0 )< 0 данное ограничение называют неактивным в точке x0 .
На рис. изображены точка x0 , в которой оба ограничения активны, и точка х ¢, в которой оба ограничения неактивны.
Рис. Графическая иллюстрация активного
и неактивного ограничений.
Теорема ( необходимые условия минимума ).
Если x0 – точка локального минимума в задаче (1) … (3), то существуют множители Лагранжа li не равные одновременно нулю , т.е. å l i2 ¹0 и такие, что выполнены условия :
а.) стационарности Ñx L(x,l) = 0n или что то же самое
Ñx ¦(x0 ) + l i Ñg i (x0 ) = 0n ; (5)
б.) дополняющей нежесткости
l i g i (x0 ) = 0 , i = 1,2,…,m ; (6)
в.) неотрицательности (согласования знаков)
l i ³ 0 , i = 1,2,…,m ; (7)
г.) допустимости
g i (x0 ) £ 0 , i = 1,2,…,k ; g i (x0 ) = 0 , j = k+1,…,m; (8)
Заметим , что множители Лагранжа , отвечающие ограничениям – равенствам , могут быть положительными , отрицательными или же равными нулю, тогда как множители, которые соответствуют ограничениям – неравенствам, отрицательными быть не должны.
При решении задачи в силу ее линейности по l отдельно рассматриваются случаи l0 ¹0 (регулярный ) и l0 = 0 (нерегулярный ). В первом случае можно положить l0 = 1 или любой другой положительной константе. В задаче на минимум l0 = -1 или любой другой отрицательной константе в задаче на максимум.
Условие g i(x0) £ 0 , i = 1,2,…,k очевидно: точка минимума x0 должна удовлетворять исходным ограничениям, т.е. быть допустимой. Равенство (5) аналогично равенству (1.6) из теоремы (3), где вместо ¦ использована функция Лагранжа. Согласно равенствам (6) те множители Лагранжа , которые соответствуют неактивным в точке x0 ограничениям , должны обращаться в нуль. Среди перечисленных условий основным является равенство (5). Если все ограничения в точке x0 неактивны, то из (6) следует, что l1 =l2 =…=lm = 0 и условие (5) превращается в условие (1.6). Это говорит о том, что в рассматриваемом случае l1=l2=…=lm=0 ограничения фактически не учитываются и необходимым условием локального минимума в такой точке является равенство градиента целевой функции нулевому вектору.
Нередко задача оптимизации содержит дополнительное условие неотрицательности переменных x1,x2,…, xn, т.е.
¦(x)®min ;
g i(x)£ 0, i = 1,2,…,m ; x ³ 0n. Этой задаче соответствует функция Лагранжа вида L(x,l,m) = ¦(x) + å li gi (x) - åmj x j.
Необходимые условия локального минимума в точке x0 в этом случае можно записать следующим образом :
gi (x0) £ 0 , i= 1,2,…,m ; x0 ³ 0n ,
Ѧ ( x0 ) + li Ñ gi (x0) - mj e(j) = 0n
li gi (x 0) = 0 , i = 1,2,…,m ; mj xj = 0 , j = 1,2,…,n ,
li ³ 0 , i = 1,2,…,m ; mj ³ 0 , j =1,2,…,n ,
где e(j) – n- мерный вектор с нулевыми компонентами , среди которых только j-я отлична от нуля и равна единице.
Функция ¦0(x) = x12+ x22+ x32 стремится к +¥ при |x| ® +¥ , значит , по следствию из теоремы Вейерштрасса решение задачи существует , а в силу единственности критической точки решением может быть только она.
3.12. По плану производства продукции предприятию необходимо изготовить 180 изделий. Эти изделия могут быть изготовлены двумя технологическими способами. При производстве x1 изделий I способом затраты равны 4x1 + x12 руб., а при изготовлении x2 изделий II способом они составляют 8x2 + x22 руб. Определить, сколько изделий каждым из способов следует изготовить , так чтобы общие затраты на производство продукции были минимальными.
Решение. Математическая постановка задачи состоит в определении минимального значения функции
¦ = 4x1 + x12 + 8x2 + x22 (20)
при условиях
x1 + x2 = 180 , (21)
x1 , x2 ³ 0. (22)
Сначала найдем решение задачи, используя ее геометрическую интерпретацию. Областью допустимых решений исходной задачи является отрезок прямой AB (рис. 3.5 ), а линиями уровня – окружности с центром в точке Е (-2 ; -4 ).
X2
180 A
D
x1 + x2 = 180
0 B X1
рис. 3.5
Проводя из точки Е окружности разных радиусов, видим, что минимальное значение целевая функция принимает в точке D. Чтобы найти координаты этой точки , воспользуемся тем , что угловой коэффициент к окружности 4x1 + x12 + 8x2 + x22 = C в точке D совпадает с угловым коэффициентом прямой x1 + x2 = 180 и , следовательно , равен –1. Рассматривая X2 как неявную функцию от x1 и дифференцируя уравнение окружности, имеем 4 + 2x1 + 8x2¢ + 2x2 x2¢ = 0 , или 2 (2 + x1) + 2x2¢ (4 + x2) = 0 , т.е.
x2¢ = - (2 + x1 )/ (4 + x2).
Приравнивая полученное выражение для x2¢ к числу –1 , получаем одно из уравнений для определения координат точки D. Присоединяя к нему уравнение прямой , на которой лежит точка D , имеем систему
x1– x2 = 2
x1+ x2 = 180,
откуда x1*= 91; x2*= 89.
Это означает, что если предприятие изготовит 91 изделие I технологическим способом и 89 изделий II способом, то общие затраты будут минимальными и составят 17 278 руб.
Решим теперь задачу , используя метод множителей Лагранжа. Найдем минимальное значение функции (20) при условии (21) , т.е. без учета требования неотрицательности переменных. Для этого составим функцию Лагранжа
F ( x1, x2, l ) = 4x1 + x12 + 8x2 + x22 + l ( 180 – x1 – x2 ) ,
Вычислим ее частные производные по x1, x2, l и приравняем их к нулю:
¶F/¶x1 = 4 + 2x1 - l = 0,
¶F/¶x2 = 8 + 2x2 - l = 0,
¶F/¶l = 180 – x1 – x2 = 0.
Перенося в правые части первых двух уравнений l и приравнивая их левые части, получим
4 + 2x1 = 8 + 2x2 , или x1 – x2 = 2. Выражая из последнего равенства x1 имеем:
x1 = 2 + x2 . Решая последнее уравнение совместно с уравнением x1 + x2 = 180 , находим x1*= 91 и x2*= 89, т.е. получили координаты точки D , удовлетворяющей условиям (22). Эта точка является подозрительной на экстремум. Используя вторые частные производные , можно показать , что в точке D функция ¦ имеет условный минимум. Этот результат и был получен выше.
Следует отметить , что такой же результат мы получим и в том случае , если исследование на условный экстремум функции ¦ сведем к исследованию на безусловный экстремум функции ¦1 , полученной из ¦ в результате ее преобразований. А именно: если из уравнения связи (21) найдем x2 = 180 – x1 и подставим это выражение в (20) , то получим функцию одной переменной x1:
¦1 = 4x1 + x12 +8 (180 – x1) + (180 – x1)2.
Найдем стационарную точку этой функции из уравнения d¦1/dx1 = 4 + 2x1 – 8 – 2 (180 – x1) = 0 , или 4x1 – 364 = 0 , откуда x1* = 91; x2* = 89. Так же как и выше , устанавливаем , что в данной точке функция ¦ имеет минимальное значение.
l i g i (x) + 
На рис. изображены точка x0 , в которой оба ограничения активны, и точка х ¢, в которой оба ограничения неактивны.
mj e(j) = 0n 
= 2l0 x1+ 2l1 + l2 = 0,
2. Регулярный случай : l0 > 0. Положим l0 = ½. Предположим l1 ¹ 0 Þ 2x1 – x2 + x3 – 5 = 0. Выразим x1, x2 и x3 из условия а.) через l1 и l2 : x1 = -2l1 - l2 , x2 = - l2 + l1 , x3 = - l2 - l1. Подставим их в уравнения x1 + x2 + x3 = 3 , 2x1 – x2 + x3 – 5 = 0 , получим
X2
D
x1 + x2 = 180
x1– x2 = 2