b) Решите задачу, выбрав х, и х3 в качестве независимых переменных, и примените достаточные условия для исследования полученной стационарной точки.

c) Найдите коэффициенты чувствительности для этой задачи. 7. Решите следующую задачу линейного программирования.

Максимизировать /(Х) = с;ху

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

й(Х) = Е Л-*,=0. - = 1,2,..., и,

х>0, j=l, 2, п.

Покажите, что если в этой задаче пренебречь условиями неотрицательности переменных, то приведенные производные Vcf(X) совпадают с разностями Ц-cv}, определяемыми условием оптимальности задачи линейного программирования (раздел 7.2), а именно

{Zj - с) = {CP, - с) для всех

Можно ли непосредственно применять метод приведенного градиента к решению задачи линейного программирования? Почему можно или почему нельзя?

Метод множителей Лагранжа. Коэффициенты чувствительности метода Якоби можно использовать для решения задач с ограничениями в виде равенств. Пусть

>i = v¥j-=£.

Следовательно,

df-kdg = 0.

Это уравнение соответствует необходимым условиям стационарности точек, так как формула для - получена с учетом того, что Vcf = 0. Представленное уравнение

можно записать в более удобной форме, если перейти к частным производным по всем переменным xjt что приводит к системе уравнений

т-(/- в) = о, У = 1,2,..., .

Полученные уравнения вместе с ограничениями задачи g(X) = 0 формируют систему, которая позволяет определить допустимые векторы X и X, удовлетворяющие необходимым условиям стационарности.

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

L(X, X) = f(X)-Xdg(X).

Функция L называется функцией Лагранжа, а параметры X - множителями Лагранжа. Как следует из определения, эти множители имеют тот же смысл, что и коэффициенты чувствительности, фигурирующие в методе Якоби. Уравнения

-=0 и -=0 дХ дХ

дают необходимые условия для определения стационарных точек функции /(X) при ограничениях g(X) = 0. Достаточные условия, используемые в методе множителей Лагранжа, будут сформулированы без доказательства. Определим матрицу

0 Р

a2L(x,x) . .

и Q = -,-\\ для всех и }

ох ох.

Матрица Нв называется окаймленной матрицей Гессе.

Пусть имеется стационарная точка (Х0, Х0) функции Лагранжа L(X, X), и окаймленная матрица Гессе Н8 вычислена в точке (Х0, Х0). Тогда Х0 является следующим.

1. Точкой максимума, если, начиная с углового минора порядка 2т + 1, последующие п-т угловых миноров окаймленной матрицы Гессе Нв образуют знакопеременный числовой ряд, в котором знак первого члена определяется множителем (-l)m+I.

2. Точкой минимума, если, начиная с углового минора порядка 2т + 1, последующие п-т угловых миноров матрицы Нв имеют знаки, определяемые множителем (-1) 1.

Эти условия являются достаточными для определения экстремальной точки. Другими словами, экстремальной может оказаться стационарная точка, не удовлетворяющая этим условиям.

Существуют другие условия определения экстремальных точек задачи, которые являются как необходимыми, так и достаточными. Однако их практическое использование часто связано со значительными вычислительными трудностями. Определим матрицу

0 Р Л ,Pr Q-uiJ

вычисленную в стационарной точке (Х0, Х0), где ju - неизвестный параметр. Пусть Д - определитель матрицы Д, тогда все п-т действительных корней ju, полинома Д = 0 должны быть

1) отрицательными, если Х0 - точка максимума,

2) положительными, если Х0 - точка минимума.

Пример 20.2.4

Рассмотрим задачу из примера 20.2.2. Функция Лагранжа имеет вид L(X,k) = л:,2 + дг2 + дг,2 -..(х, + х2 + 3х, - 2)-Х2(5х, + 2.v2 + дг, -5).

Необходимые условия экстремума записываются в виде следующей системы уравнений.

- = 2х,-X,-5Х2=0, Эх,

= 2х2-к1-2к2=0, ох2

= 2х,-ЗХ,-Х2 = 0,

= -(х,+дг2+Зх,-2) = 0,

= -(5.x, + 2х2 + х, - 5) = 0.

Решением этой системы являются векторы

Х0 = (х х2, xz) = (0,8043, 0,3478, 0,2826),

X = (Я Л2) = (0,0870, 0,3043).

В этом решении объединены результаты примеров 20.2.2 и 20.2.3. Как видим, значения множителей Лагранжа X совпадают со значениями коэффициентов чувствительности, полученными в примере 20.2.3. Это указывает на то, что эти коэффициенты не зависят от выбора вектора зависимых переменных Y при реализации метода Якоби.

Чтобы показать, что найденная точка является точкой минимума, рассмотрим матрицу

Г0 0 1 13 0 0 5 2 1 Н = 1 5 2 0 0 12 0 2 0 3 1 0 0 2,

Здесь и = 3,/и = 2ии-/и=1. Следовательно, необходимо проверить только определитель матрицы Ня, знак которого задается множителем (-1)2 в точке минимума. Так как detH* = 460 > 0, то Х0 является точкой минимума.