Анализ чувствительности с помощью метода Якоби. Метод Якоби можно использовать для анализа чувствительности оптимального значения целевой функции / к малым изменениям правых частей ограничений оптимизационной задачи. В частности, можно определить, как повлияет на оптимальное значение функции / замена ограничения g,(X) = О на g,(X) = dgr Исследование такого типа именуется анализом чувствительности и в некотором смысле аналогично соответствующей процедуре, которая была рассмотрена в линейном программировании (глава 4). Следует однако заметить, что анализ чувствительности в нелинейном программировании приводит к результатам, справедливым лишь в малой окрестности экстремальной точки. Знакомство с такими процедурами будет полезно при изучении метода множителей Лагранжа.
Выше было показано, что
a/(Y, z> = vY/dY + vz/az,
dg = JdY + CdZ.
Предположим, что dg * 0, тогда
бт = jag-J"c az.
Подставляя последнее выражение в уравнение для o/(Y, Z), получаем
o/(Y,z) = vY/i-ag+vc/az,
где Vc/ = VZ./ -VY/J~C, как было определено ранее. Полученное выражение для 5/(Y, Z) можно использовать при анализе изменений целевой функции f в малой окрестности допустимой точки Х°, обусловленных малыми изменениями dg и 5Z.
В экстремальной (фактически любой стационарной) точке Х0 = (Y0, Z0) приведенный градиент Vc/ должен быть равен нулю. Следовательно, в точке Х0 имеем
5/(Y0,Z0) = VYn/J-5g(Y0,Z0)
dg YJ
вычисленному в точке Х0. Это значит, что влияние малых изменений dg на оптимальное значение функции / можно оценить через скорость изменения функции / по отношению к изменениям g. Эти величины принято называть коэффициентами чувствительности.
Пример 20.2.3
Рассмотрим задачу из примера 20.2.2. Оптимальной точкой является Х0=(х,0,х20,х3°) = (0,81, 0,35, 0,28). Так как Y0 =(х,°,х20), то
Vv„/ =
чйх,йх2,
= (2х,°,2х2) = (1,62,0,70).
Следовательно,
= VYo/J-=(1,62,0,7)
( 2 П 3 3
5 Jl 3 3,
= (0,0876,0,3067).
Это свидетельствует о том, что изменение dgx = 1 приводит к увеличению значения целевой функции / приблизительно на 0,0867. Аналогично при dg2 = 1 имеет место увеличение значения/приблизительно на 0,3067.
Использование метода Якоби в задачах линейного программирования. Рассмотрим задачу линейного программирования.
Максимизировать г - 2л:, + Зхг
при ограничениях
JCj "Ь Х2 "Ь Х3 = б,
хг - х2 + xt = 3,
2> 3 4 -
Для каждого условия неотрицательности xf > 0 введем соответствующую (неотрицательную) дополнительную переменную w2. Таким образом, дгу - w2 = 0
или ху = w2. При такой замене условия неотрицательности становятся неявными,
и исходная задача принимает вид
максимизировать z = 2wf + 3w2
при ограничениях
w, + ve, + w, = 5,
= 3.
Для метода Якоби положим Y = (ц>,, и>2) и Z = (u>3, ц>4). (В терминологии линейного программирования векторы Y и Z образованы базисными и небазисными переменными соответственно.) Следовательно,
(2w,
J- =
J 1
4ve, 4vv,
J -1
4vv, 4ve,
w, и VV2 * 0,
так что
2w, 0 4 4 0 2w4,
,VY/ = (4w„6w2),Vz/ = (0,0),
Vc/ = (0,0)-(4w„6w2)
4vv, 4vv,
4ve2 4w2,
2w, 0 0 2w4
=(-5w3,w4).
Решение системы уравнений, состоящей из уравнения V/ = 0 и ограничений задачи, позволяет определить стационарную точку w1 = 2, w2=l, w3 = 0, w4 = 0. При этом матрица Гессе имеет вид
Поскольку Н. является неопределенной матрицей, стационарная точка не будет точкой максимума.
На самом деле полученный результат не является неожиданным, поскольку (небазисные) переменные w3 и ш4 (и, следовательно, х3 и х4) равняются нулю, как и предусмотрено теорией линейного программирования. Следовательно, решение, полученное с помощью метода Якоби, определяет ту или иную крайнюю точку пространства допустимых решений рассматриваемой задачи, которая связана с конкретным выбором векторов Y и Z. При этом найденное решение может как быть, так и не быть оптимальным. Однако метод Якоби позволяет распознать оптимальное решение задачи путем использования достаточных условий экстремума.
Приведенные рассуждения свидетельствуют о том, что для оптимального решения задачи линейного программирования необходимо менять конкретный выбор Y и Z, пока не будут выполнены достаточные условия. Пусть, например, Y = (ц>2, wt) и Z = (ц>,, w3). Тогда соответствующий приведенный градиент принимает вид
VJ = (4w„0)-(6w2,0)
2ve2 l
f2w, 2w,
2ve3 0
=(-2wp6wj).
Соответствующая стационарная точка определяется значениями wl = О, w2 w3 = 0, wt=J&. Так как матрица
-2 0}
0 -6)
является отрицательно определенной, то указанная точка - точка максимума.
Полученный результат можно проверить графически, используя рис. 20.6. Первое из найденных решений (дг, = 4, дс2 = 1) не является оптимальным, в то время как второе (х, = 0, дс2 = 5) оказывается таковым. Читатель имеет возможность проверить, что две оставшиеся крайние точки пространства допустимых решений не являются точками максимума. Кроме того, с использованием достаточных условий экстремума можно показать, что в точке дг, = 0, дс2 = 0 возникает минимум целевой функции рассматриваемой задачи.
Заметим, что введенные ранее коэффициенты чувствительности VYj/J" в задаче
линейного программирования являются переменными двойственной задачи. Чтобы проиллюстрировать это на рассматриваемом численном примере, обозначим через и, и и2 соответствующие переменные двойственной задачи. В оптимальной точке и>1 = 0, w2 = VJ, w3 = 0, w4 = переменные двойственной задачи вычисляются по формуле
(«„«2) = VYr=(6w2,0)
24 2w4
=(3,0).