Бережная_Матметоды моделирования эк cистем

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

имеет экстремум, то суш^ествует такой вектор А.^ = (Л/^, ^2^, ..., Х^), что точка (xi^, Х2^,..., х„^, Xi^, Х2, ..., Xj^) является решением сис­ темы (10.5). Следовательно, решая систему (10.5), получим множе­ ство точек, в которых функция Z имеет экстремальные значения. При этом неизвестен способ определения точек глобального мини­ мума или максимума. Однако, если решения системы найдены, то для определения глобального максимума (минимума) достаточно найти значения функции Z в соответствующих точках. Метод мно­ жителей Лагранжа имеет офаниченное применение, так как систе­ ма (10.5), как правило, имеет несколько решений. Рассмотрим пример применения метода множителей Лагранжа.

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

Z = ^\^2 "^ ^2 ^3

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

Xi + ^2 = 2;

^2 + Х3 = 2.

Решение

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

F = (xj, Х2, Хз, Xi, Х2) =

= Х1Х2 + Х2х:з + X^ixi + Х2 — 2) + ^2(^2 + Х3 — 2)

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

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

тогда

350

Xi + X2 = 2;

X2 + Хз = 2.

Решая систему, получим Xj = Х2 = Хз = 1;

Z = 2 .

10.3. Градиентный метод

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

Z=/'(Xi,X2). (10.6)

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

^2

\1

Рис. 10.3. Линии уровня функции Z

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

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

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

А

351

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

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

gradZ dZ dZ ЭхlA

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

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

dZ dxi) ^dx2j

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

'-JA)JdZ]

dZ_

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

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

352

1. Из начальной точки движемся в направлении градиента до тех пор, пока целевая функция перестанет возрастать. Это движе­ ние осуществляется постепенным увеличением параметра /, при­ чем, для каждого значения находится величина функционала, а также проверяется допустимость полученного решения. Достигнув наивысшей в данном направлении точки (точка В на рис. 10.3), снова определяем градиент и по новому направлению перемещаем­ ся на максимально возможную величину и т. д.

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

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

ляющих градиента.

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

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

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

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

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

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

353

>f2

- • x i

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

Рис. 10.5. Участок области допустимых решений

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

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

354

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

Пример 10.4. Найти максимум функции Z = х^^ + 4x2 "Р^ У^' ловии

4xi^ + 9x2^ < 36; xi > 0; Х2 > 0.

Решение

Уравнение границы перепишем в другом виде

у = 36 - 4x1^ - 9x2^ > 0.

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

Z^ = 2^ + 4 . 1 = 8.

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

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

XI =2 + 4/;

Х2=1 + 4/.

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

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

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

Z^= 2,2^ + 4 . 1,2 = 9,64.

355

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

-..г^,, g)^M.

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

Хх = 2,2 + 4,4/; JC2 = 1,2 + 4Г.

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

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

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

З;^ = 36 ~ 4 • 2,42^ - 9 • 1,40^ = -5,04 < 0.

Следовательно, точка С лежит вне области допустимых реше­ ний. Необходимо вернуться в область и сдвинуться в сторону оп­ тимума. Находим градиент граничной функции в точке С:

Шг'^- ду = -25,2;

УдХ2 grad3;c(-19,4; -25,2).

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

xi = 2,42 - 19,4/; Х2 = 1,40 - 25,2/.

Учитывая большую абсолютную величину координат градиен­ та, уменьшим параметр /, допустим / = 0,01.

Получим точку D (2,23; 1,15).

Проверяем принадлежность точки D заданной области: д;^ = 36 - 4 • 2,23^ - 9 • 1,15^ = 4,22 > 0.

Условие выполняется, решение допустимо:

356

Z^) = 2,23^ + 4- 1,15 = 9,57,

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

^(BD)^^(D) ^^(В) =2,23-2,20 = 0,03;

хр>=х<^>-х(^> =1,15-1,20 = ^0,05.

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

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

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

УЕ = 6,09 > 0; Zj, = 2,38^ + 4 • 0,90 = 9,26.

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

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

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

д;^ = 36 - 4 • 2,62^ - 9 • 1,10^ = -2,31 < 0.

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

357

Прежде чем делать переход, вычислим отношения одноимен­ ных координат grad Z^ и grad yf.

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

д;^; = 36 - 4 . 2,52^ -- 9 • 1,00^ = 1,6 > 0.

Следовательно, точка лежит в заданной области:

Z(; = 2,52^ + 4- 1,00= 10,35.

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

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

Рис. 10.6. Пример нахождения оптимального решения

358

10.4. Многоцелевые задачи линейного программирования

Известно, что экономическая эффективность производства ко­ личественно измеряется системой экономических показателей. Так, в промышленном производстве важными показателями эффектив­ ности являются: рост производительности труда, прибыль, рента­ бельность и др. Максимальное значение одного из показателей еще не означает, что то или иное предприятие работает лучше. Только система показателей может характеризовать эффективность всего производства.

Задачи, решаемые с учетом множества показателей или крите­ риев, носят название многоцелевых. Планы задач, полученные по разным критериям, будут отличаться один от другого. Можно для каждого плана определить все интересующие нас показатели, и по­ сле их сравнения остановиться на том, который позволяет полу­ чить достаточно высокую эффективность всего производства. Если же из полученных планов нельзя выбрать план, который обеспечи­ вал бы необходимую эффективность, можно воспользоваться спе­ циальным методом, так называемым методом уступок.

Рассмотрим первый прием на конкретной задаче.

Спомощью двух операций производится два вида продукции -

Аи В. При производстве продукта А на каждой операции затрачи­ вается 3 часа, а при производстве продукта В соответственно 4 и 5 часов. Общее наличие времени для первой и втЬрой операции 18 и 21 час. Стоимость единицы продукции А — 3 руб., а продукции В ~ 8 руб.

Провести анализ работы предприятия с учетом различных целей: а) максимум прибыли; б) максимум выпуска продукции;

в) наилучшее использование оборудования.

Обозначим через Xj и Х2 количество продукции видов А и В, вы­ пущенных предприятием.

Используя введенные переменные, ограничения можно записать

3xi + 4x2 ^ 18; 3xi + 5x2 - 21; xj > 0; Х2 > 0.

Полученные ограничения можно записать в виде уравнений

3xi + 4x2 + ^3 ^ 18; 3xi + 5x2 + ^4 ^ 21,

359