10.2. Метод множителей Лагранжа

Z = f(xb х2, = 0 (10.2)

при ограничениях

Si = (*i> х2, хп) = 0; і = 1, т. (10.3)

Ограничения в задаче заданы уравнениями, поэтому для ее решения можно воспользоваться классическим методом отыскания условного экстремума функций нескольких переменных.

F (хІ5 х2> хт Л], ..., Хт) =

(10.4)

= /(* 1, ХЬ ..., Хп) + Xfkjgj (хь хь ..., хп).

Л dF dF

Определим частные производные и —— и приравняем их

ЭXj OA і

нулю. В результате получим систему уравнений

(Ю.5)

Функция (10.4) называется функцией Лагранжа, а числа — множителями Лагранжа. Если функция (10.2) в точке х° = (хД х2°, х„°)

имеет экстремум, то существует такой вектор Х° = (Л!0, Х2, ..., X®), что точка (хД х20,..., х„°, АД А2°, ..., Ат°) является решением системы (10.5). Следовательно, решая систему (10.5), получим множество точек, в которых функция Z имеет экстремальные значения. При этом неизвестен способ определения точек глобального минимума или максимума. Однако, если решения системы найдены, то для определения глобального максимума (минимума) достаточно найти значения функции Z в соответствующих точках. Метод множителей Лагранжа имеет ограниченное применение, так как система (10.5), как правило, имеет несколько решений. Рассмотрим пример применения метода множителей Лагранжа.

Пример 10.3. Найти точку условного экстремума функции

Z — XjX2 х2 х3

при ограничениях

X! + х2 = 2; х2 + х3 = 2.

Решение

Составим функцию Лагранжа

F— (xl5 х2, х3, Al5 Х2) = = х{х2 + x^3 + Х{(х{ + х2 — 2) + А2(х2 + х3 — 2)

и продифференцируем ее по всем переменным: Xj, х2, х3, Аь Х2. Приравнивая производные к нулю, получим систему уравнений

= 0 = 0 = 0

х2 х2

х{+ х2

х2+ х2

-2 =0 -2 =0

Из первого и третьего уравнения следует, что Хх = Х2 = —х2, тогда

Xi — 2х2 + х3 = 0;

хх + х2 = 2; х2 + хз = 2.

Решая систему, получим хх = х2 = х3 = 1;

Z= 2.

10.3.

Возьмем для простоты целевую функцию с двумя независимыми переменными:

Z=F(X19X2). (10.6)

Изобразим линии уровня этой функции на рис. 10.3.

Выберем некоторую точку А и вычислим для нее значение Z. Если сдвинуться из точки А на одно и то же расстояние в разных направлениях, то функционал Z изменится на разную величину.

Чтобы быстрее достичь экстремума, надо двигаться в направлении наибольшего изменения Z.

Найдем частные производные функции Z и вычислим их значения в точке А Получим (dz) idZ) )

А

Примем найденные числа за координаты некоторого вектора и построим этот вектор на рис. 10.3. Оказывается, что если из точки А перемещаться вдоль прямой, параллельной указанному вектору, то функция Z будет изменяться быстрее всего: в направлении вектора увеличиваться, в обратном — уменьшаться.

Вектор, координатами которого служат значения частных про-изводных функции Z= F(xb х2), называется градиентом этой функции и обозначается

gradZ

dZ dZ дх{/ дх2л

В каждой точке градиент будет свой. Он показывает направление наибольшего возрастания функции в данной точке, которое всегда перпендикулярно проходящей через нее линии уровня. \ (дгЛ 1 На этом свойстве и основан градиентный метод решения задач нелинейного программирования. Выбрав в области допустимых решений первоначальную точку А и убедившись, что она не является оптимальной, дальнейшее движение осуществляем целенаправленно. Для этого вычисляем в выбранной точке координаты градиента целевой функции

ЭZ дхх

Составляем параметрические уравнения прямой, проходящей через точку А параллельно градиенту:

(А) I 3Z

*!=*,< ЧэГ

і )л

(10.7)

дх->

х2-х2 +

az

Лп -г

njA

В случае нахождения максимума перемещаемся по прямой в направлении градиента (/ > 0), для минимизации функции движемся в противоположном направлении (/ < 0).

При этом возможны два способа перемещения.

Из начальной точки движемся в направлении градиента до тех пор, пока целевая функция перестанет возрастать.

Такой порядок расчетов соответствует наискорейшему подъему и применяется тогда, когда значение функционала вычислить проще, чем его градиент.

В задачах на минимум движение происходит в сторону убывания функции, и такой метод носит название наискорейшего спуска.

Из начальной точки по линии, параллельной градиенту, пе-ремещаемся на некоторый интервал Л, характеризуемый значением параметра t. Во второй точке определяем свой градиент и по новому направлению снова перемещаемся на величину А. Получаем третью точку и т. д. Так небольшими переходами, корректируя всякий раз направление движения, достигаем точки, соответствующей оптимальному значению функционала (максимум, минимум). Признаком достижения оптимума является получение нулевых составляющих градиента.

При перемещении по направлению градиента может оказаться, что найденная точка лежит вне области (т. е. на данном шаге пересечена граница области). В этом случае экстремум, как правило, достигается на границе, и его нахождение усложняется.

Возврат в область простым уменьшением последнего шага неэффективен, поскольку нет уверенности, что экстремальная точка находится в пересечении с границей именно этого направления. Необходим возврат с одновременным смещением в сторону оптимума.

Рассмотрим рис. 10.4, где область допустимых решений показана жирными линиями, а линия уровня функционала — тонкими.

Из точки А перемещаемся по нормали к линии уровня и попадаем за границу области в точку В. Так как оптимум достигается в точке Л/, возврат в область по линии ВА бесполезен.

Рассмотрим подробно участок нарушенной границы, представленный на рис.

Направление первоначального движения АВ перпендикулярно касательной в точке А. При возвращении из точки В в заданную область будем перемещаться по прямой BQ, которая перпендикулярна к касательной, проведенной через точку Q. Иными словами, ВС должно быть нормалью к границе yt. Новое направление ВС отклонится от прежнего АВ на угол а. Отклонение будет в ту сторону, где

находится точка, соответствующая оптимальному плану. Так как точка В находится вблизи границы, за направление возврата в область можно принять направление градиента функции yt в точке В.

Придя в точку С, движемся по направлению grad Z, попадаем в точку D и т. д. (рис. 10.4). Признаком получения оптимума является коллинеарность векторов grad Z и grad yt. Коллинеарность векторов проверяется пропорциональностью соответствующих координат.

Для ускорения сходимости процесса, после одного-двух зигзагов, делают шаг в направлении АС, т. е. почти параллельно границе, при этом параметр t берут больше обычного. Из новой точки продолжается опять зигзагообразное движение к оптимуму.

Пример 10.4. Найти максимум функции Z = Xj2 + 4х2 при ус-ловии

4хх2 + 9Х22 < 36; Х\ > 0; х2 > 0.

Решение

Уравнение границы перепишем в другом виде у = 36 — 4хх2 - 9Х22 > 0.

Возьмем произвольную точку А (2; 1): так как ул = 11 > 0, следовательно, она принадлежит области допустимых решений

Z^ = 22 + 4 • 1 = 8.

Частные производные функции Z имеют вид:

dZ Эхо

az 9xi

= 4;

= 2xj;

в точке А: (dz) — А- f9Z1 А [ax2J = 4.

Следовательно, grad ZA (4; 4) и в точке А функции Z не достигает максимума. Запишем уравнение прямой, проходящей через точку А, параллельную градиенту:

х\ =2 + 4/; х2 =1 + 4/.

Полагая t = 0,05, получим

хх =2 + 4*0,05 = 2,2; х2 =1 + 4-0,05 = 1,2.

Точка В (2,2; 1,2) лежит в заданной области, так как Ув = 36 - 4 • 2,22 - 9 • 1,22 = 3,68 > 0; ZB=2,22 + 4 • 1,2 = 9,64.

'dZ"

Для перехода в новую точку находим координаты градиента для точки В:

= 2,2 = 4,4; 9Z

дхі

= 4.

Составляем уравнение линии перемещения из точки В:

хх = 2,2 + 4,4/; х2 = 1,2 + 4/.

Придавая параметру / прежнее значение, получаем:

хх = 2,42; *2 = 1,40,

попадаем в точку С (2,42; 1,40), так как

ус = 36 - 4 • 2,422 - 9 • 1,402 = -5,04 < 0.

Следовательно, точка С лежит вне области допустимых решений.

о*] дх2

•і \ dxj

ІL

VdxUc

-25,2;

= -19,4;

\ ""2 / grad-25,2).

Движение из точки С будем осуществлять вдоль линии

х{ = 2,42 - 19,4/; х2 = 1,40 - 25,2/.

Учитывая большую абсолютную величину координат градиента, уменьшим параметр /, допустим / = 0,01. Получим точку D (2,23; 1,15).

Проверяем принадлежность точки D заданной области:

yD = 36 - 4 • 2,232 - 9 • 1,152 = 4,22 > 0. Условие выполняется, решение допустимо:

ZZ) = 2,232 + 4. 1,15 = 9,57,

которое, по сравнению с точкой В, несколько уменьшилось. В най-денных соседних точках В и D значения Z близки между собой, это указывает на смещение оптимальной точки вдоль линии уровня целевой функции. Для ускорения сходимости процесса сделаем шаг в направлении BD. Координатами вектора, параллельного BD, будут разности соответствующих координат точек В и D:

x(m=x(D)_x(B)^22 з_2)20 = 0)03;

=1,15-1,20 = -0,05.

Уравнение прямой, проходящей через точку D в направлении BD, имеет вид:

хх = 2,23 + 0,03/; х2 = 1,15 - 0,05/.

Параметр / надо брать большим, чтобы сдвиг вдоль границы был существенным. Полагая / = 5, получим точку Е (2,38; 0,90)

уЕ = 6,09 >0; ZE = 2,382 + 4 • 0,90 = 9,26.

Точка Е лежит в заданной области. Из точки Е переместимся параллельно градиенту Z. Для этого находим

dZ

:4,76;

дх2

= 4; gradZ?(4,76; 4);

хх = 2,38 + 4,76/; х2 = 0,90 + 4/.

При / = 0,05 переходим в точку F (2,62; 1,10). Точка Улежит за границей области, так как

уЕ = 36 - 4 • 2,622 - 9 • 1,102 = -2,31 < 0.

Ъу\

= -21,0;

= -19,8;

Возврат в допустимую область необходимо вести по направлению вектора

Прежде чем делать переход, вычислим отношения одноименных координат grad ZE и grad yF:

4 76 4

- = -0,226; -^— = -0,202.

-21,0 -19,8

Отношения близки друг к другу, т. е. векторы grad ZE и grad yF практически коллинеарны и противоположно направлены. Движение по ним будет происходить взад-вперед через границу. Поэтому, чтобы попасть в область ближе к границе, положим t = 0,005 и перейдем в точку G (2,52; 1,00)

yG = 36 - 4 • 2,522 - 9 • 1,002 = 1,6 > 0.

Следовательно, точка лежит в заданной области: ZG = 2,522 + 4 • 1,00 = 10,35.

Полученный результат хх = 2,52; х2 = 1,00; Z= 10,35 можно считать оптимальным: его можно уточнить дальнейшими шагами до полной коллинеарности градиентов целевой и граничной функций.

Движение точки во время поиска можно представить на рис. 10.6.