УПРАЖНЕНИЕ 20.1.2
1. Примените метод Ньютона-Рафсона для решения упражнений 20.1.1.1, с и 20.1.1.2, Ъ.
20.2. ЗАДАЧИ НА ЭКСТРЕМУМ ПРИ НАЛИЧИИ ОГРАНИЧЕНИЙ
В настоящем разделе рассматриваются задачи поиска экстремумов непрерывных функций при наличии ограничений на переменные. В разделе 20.2.1 рассматривается ситуация, когда дополнительные ограничения имеют вид равенств, а в разделе 20.2.2 - неравенств. Основная часть материала раздела 20.2.1 изложена в соответствии с [2].
20.2.1. Ограничения в виде равенств
В данном разделе рассматривается два метода решения оптимизационных задач при наличии ограничений в виде равенств: метод Якоби и метод Лагранжа. Метод Лагранжа можно логически получить из метода Якоби. Эта связь позволяет дать интересную экономическую интерпретацию метода множителей Лагранжа.
Метод приведенного градиента (метод Якоби). Рассмотрим задачу
минимизировать z = /(X)
при ограничениях
g(X) = 0,
X = (дг,, х2, дсл),
S (.§!> &2> *
Функции /(X) и g,(X), t= 1, 2, т, предполагаются дважды непрерывно дифференцируемыми.
Идея использования приведенного градиента заключается в том, чтобы найти замкнутое аналитическое выражение для первых частных производных функции /(X) во всех точках, удовлетворяющих ограничениям g(X) = 0. Соответствующие стационарные точки определяются из условия равенства нулю указанных частных производных. Затем можно использовать достаточные условия, сформулированные в разделе 20.1, для классификации найденных стационарных точек.
Для пояснения изложенной идеи рассмотрим функцию /(дг,, х2), график которой представлен на рис. 20.5. Предположим, что эту функцию необходимо минимизировать при ограничении
g,(*i. х2) = х2 - Ь = 0,
где Ь - некоторая константа. На рис. 20.5 видно, что кривая, которая проходит через точки А, В и С, состоит из значений функции /(дг,, х2), для которых заданное ограничение выполнено. В соответствии с рассматриваемым методом определяются компоненты приведенного градиента функции /(дг,, х2) в каждой точке кривой ABC. Точка В, в которой приведенная производная обращается в нуль, является стационарной для рассматриваемой задачи с ограничением.
Теперь рассмотрим общую математическую формулировку метода. Из теоремы Тейлора следует, что для точек X + АХ из окрестности точки X имеем
/(х+дх)-/(х) = у/-(х)дх+о(дх,2),
g(X + AX)-g(X) = Vg(X)AX + 0(Ax2).
Лх{,х2)
| |
/ J / 1 1 1 \ 1 \ \ | \ \ • : 1 ч в У7\ |
| ---- \ л:2 = 6 Линия минимального значения целевой функции |
Рис. 20.5. Иллюстрация к методу Якоби
При hxj -» 0 эти уравнения принимают вид
d/(X) = V/(X)c5X,
dg(X) = vg(X)ax.
Поскольку g(X) = 0, 9g(X) = 0 в допустимой области. Отсюда следует, что
о/(Х) - V/(X)3X = 0,
vg(x>ax = o.
Как видим, задача сводится к решению т + 1 уравнений с п + 1 неизвестными, которыми являются 9/(Х) и ЭХ. Неизвестную величину 9/(Х) можно определить, как только будет найден вектор 5Х. Это означает, что, по существу, имеется т уравнений с п неизвестными.
При т > п по меньшей мере т- п уравнений системы являются избыточными. После устранения избыточности количество независимых уравнений в системе становится равным т (< п). Если т = п, решением является ЭХ = 0. При этом точка X не имеет допустимой окрестности, и, следовательно, пространство решений задачи состоит из единственной точки. Такая ситуация является тривиальной. Ситуацию, когдат<п, рассмотрим подробно.
Пусть X = (Y, Z), где
Y = (j/p уг, ...,ym)nZ = (z1,z2, ...,zn m)
называются зависимыми и независимыми переменными соответственно. Переписывая градиенты функций / и g в новых обозначениях, получим
V/(Y, Z) - (VY/, Vz/), Vg(Y, Z) = (VYg, Vzg). Введем в рассмотрение матрицы
fvYg, ] J=vYg= ; ,
c = vzg =
Матрица JmXm называется матрицей Якоби, a CmX((1 m) - матрицей управления. Матрица Якоби J предполагается невырожденной. Это всегда можно обеспечить, поскольку рассматриваемые т уравнений являются независимыми по определению. Поэтому компоненты вектора Y можно выбрать среди компонентов вектора X таким образом, что матрица J окажется невырожденной.
Исходную систему уравнений с неизвестными 9/(Х) и ЭХ можно переписать в следующем виде
a/(Y, Z) = VY/5Y + Vz/dZ,
JdY=-caz.
Так как матрица J невырожденная, существует обратная матрица J-1. Следовательно,
oY = - jcaz.
Подставляя это выражение 5Y в уравнение для 9/(Y, Z), можно выразить df через 9Z в следующем виде
a/(Y, Z) = (yzf-VYfJ1C)dZ.
Из этого уравнения получаем формулу для производных функции f по вектору независимых переменных Z
v£/ =
a./(v,z)
= vz/-vy/j-c,
где VJ представляет вектор приведенного градиента функции / по Z. Следовательно, вектор Vc/(Y,Z) должен обращаться в нуль в стационарных точках.
Достаточные условия экстремума в стационарной точке аналогичны изложенным в разделе 20.1. В этом случае элементы матрицы Гессе будут соответствовать компонентам вектора независимых переменных Z. Между тем элементы матрицы Гессе должны быть приведенными вторыми производными. Чтобы показать, как они вычисляются, положим
ve/ = vz/-wc.