Рис. 20.6. Пространство решений задачи ЛП
В точке (3, О) целевая функция двойственной задачи равна 5и, + Зиг = 15 и совпадает с оптимальным значением целевой функции прямой задачи. Полученное решение также удовлетворяет ограничениям двойственной задачи, т.е. является допустимым и, следовательно, оптимальным. Это значит, что коэффициенты чувствительности совпадают с переменными двойственной задачи линейного программирования.
Из процедуры применения метода Якоби к решению задач линейного программирования можно сделать несколько общих выводов. Рассмотренный численный пример показывает, что в силу необходимых условий экстремума независимые переменные задачи равны нулю. Достаточные же условия указывают на то, что матрица Гессе является диагональной. Следовательно, все диагональные элементы этой матрицы должны быть положительными, если в рассматриваемой точке имеет место минимум, и отрицательными - в случае максимума.
Из вышесказанного следует, что необходимое условие экстремума равносильно указанию на то, что оптимальное решение задачи следует искать только среди ее базисных решений. В этом случае в качестве небазисных переменных задачи линейного программирования выступают независимые переменные. Достаточное же условие приводит к выводу, что между диагональными элементами матрицы Гессе и разностями zf - с, задачи линейного программирования (см. раздел 7.2), получаемыми с помощью симплекс-метода, существует строгое соответствие.1
УПРАЖНЕНИЯ 20.2.2
1. Предположим, что задача из примера 20.2.2 решена следующим образом. Сначала из ограничений задачи выражаем переменные дг, и хг через дс3; затем используем полученные соотношения для представления целевой функции в зависимости лишь от переменной х3. Дифференцируя полученную целевую функцию по х3, находим точки минимума и максимума.
1 Формальное доказательство справедливости этих утверждений для общей задачи линейного программирования можно найти в статье Taha Н. and Curry G. "Classical Derivation of the Necessary and Sufficient Conditions for Optimal Linear Programs", Operations Research, Vol. 19, 1971, pp.1045-1049. В этой статье показано, что все основные положения симплекс-метода могут быть получены с помощью метода Якоби.
a) Будут ли производные новой целевой функции (выраженные через переменную х3) отличаться от полученных с помощью метода Якоби?
b) В чем основное отличие описанной процедуры решения задачи от метода Якоби?
2. Примените метод Якоби к решению задачи из примера 20.2.1, выбирая Y = (x2, х3) и Z = (x,).
3. С помощью метода Якоби решите следующую задачу.
Минимизировать /(X) = х,2
при ограничении
П* = с,
где С - положительная константа. Пусть теперь правая часть ограничения равна С + S, где S- малое положительное число. Найдите соответствующее изменение оптимального значения целевой функции /.
4. Решите методом Якоби следующую задачу.
Минимизировать /(X) = 5.x,2 + лг2 + 2х,х2
при ограничении
g(X) = Xlx2 - 10 = 0.
a) Найдите изменение оптимального значения целевой функции /(X), если ограничение задачи примет вид хух2 - 9,99 = 0.
b) Найдите изменение значения целевой функции /(X) в окрестности допустимой точки (2, 5) при условии, что х1х2 = 9,99 и Эх, = 0,01.
5. Решите следующую задачу.
Максимизировать /(X) = х2 + 2х\ + КЪг2 + 5х,х2
при ограничениях
g, (X) = х, + х\ + Ъхгхг -5 = 0,
g2 (X) = х,2 + 5х,х2 + х32 - 7 = 0.
Используйте метод Якоби для нахождения df(X) в окрестности допустимой точки (1, 1, 1). Пусть указанная окрестность определяется условиями dgl = -0,01, dg2 = 0,02 и дх1 = 0,01.
6. Решите следующую задачу.
Минимизировать /(X) = х,2 + х\ + х] + х\
при ограничениях
g,(X) = хг + 2х2 + Зха + 5xt - 10 = 0,
g2(X) = х1 + 2х2 + 5х3 + 6х4 -15 = 0.
а) Покажите, что при выборе х3 и xt в качестве независимых переменных метод Якоби не дает оптимального решения.
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).