Z-Уу = У) > 0 для всех J-
Эти уравнения, именуемые условиями ортогональности и нормировки, определяют единственное решение для yj при условии, что все уравнения независимы и п + 1 = N. Задача усложняется при N > п + 1, так как в этом случае решение для I/. не является единственным. Ниже показано, что и в этом случае существует возможность однозначно определить у. для минимизации функции z.
Пусть yj - элементы единственного решения представленной выше системы
уравнений. Тогда величины г* и х], i = 1, 2,п , определяются следующим образом. Рассмотрим величину
Поскольку Z* = -г , то
П Пс)"
В последнем выражении учтено условие X"-iav-vj = • Следовательно, значение г" можно вычислить, как только будут определены все уг При известных у] я z можно определить U] = у*г* Значения х] находятся как решение системы уравнений
Рассмотренная процедура показывает, что исходная задача минимизации позино-ма z может быть сведена к решению системы линейных уравнений относительно у. При этом значения всех у* определяются из необходимых условий существования
минимума. Можно показать, что эти условия являются также и достаточными. Доказательство этого приводится в книге [2].
Фактически переменные yt определяют двойственные переменные, соответствующие прямой задаче минимизации z. Чтобы установить эту зависимость, запишем целевую функцию прямой задачи в виде
Определим теперь функцию
Поскольку " ,у, = 1 и yj > О, в силу неравенства Коши1 имеем w<z.
Функция w с переменными ух, у2, yN определяет задачу, двойственную к исходной. Поскольку w является нижней границей значений z и рассматривается задача минимизации г, то, максимизируя функцию w, мы получим
w = max w = min z = z
У) *:
Это значит, что максимальное значение w (= w ) на множестве допустимых значений г/, совпадает с минимальным значением z (= z") на множестве допустимых значений xt.
Пример 21.2.4
В этом примере рассматривается задача, где N = п + 1, так что решение, получаемое из условий ортогональности и нормировки, является единственным. (Следующий пример иллюстрирует случай, когда N > п + 1.)
Рассмотрим задачу
минимизировать z = 7х,х; + 3x,xf + 5х~3х,х3 + х,х,х3.
Эту функцию можно записать в виде
z = 7х!х,-х" + 3x°xU2 + 5х73х\х\ + х\х\х\,
так что здесь
(с,, с2, с3, ct) = (7, 3, 5, 1), а,, а,, а,3 а14 Г 1 0-3 Г
а,. а„ а,, а,.
-1111 0-211
чя3, а,, а33 а,4/
Условия ортогональности и нормировки приводят к системе уравнений
Эта система имеет единственное решение
.1.1
Следовательно,
= 15,23.
1 Неравенство Коши (неравенство между средним арифметическим и средним геометрическим) устанавливает, что при Zj > 0 выполняется J,%Zy - Г1"-гу" Где "О > и Xjiy = •
Пример 21.2.5
Рассмотрим задачу
минимизировать г = 5.v,.v, + 2.v, .v, + 5.v, + .vj1. Условия ортогональности и нормировки приводят к системе уравнений
1-11 0 1 10-1 1 11 1
Уз 04
Поскольку N > п + 1, эти уравнения не позволяют непосредственно определить искомые значения у/. Выражая уи у2 и у, через у4, имеем
| -1 п | f-vl | | 0 1 |
| 1 0 | 1 V, 1 - | | |
| 1 b | | | У-у,, |
V, =-
I - 3 \-
Двойственную задачу можно записать в следующем виде.
Максимизировать iv =
-.0.5(1 3..I
0,5(1-Зу4)
0.5(1- у4)
Из уравнения U) = y)z следует, что
7,v,.v, = (/, =-(15,23) = 7,615,
3.v,jc,2 ={/, =-(15,23) = 2,538,
5л,3хЛ=(/3=(15.23) = 3,173,
.v,.v:.v, = U4 = -(15.23) = 1,904. 8
Эта система имеет решение =1,316, л* =1,21, .vj =1,2, которое является оптимальным решением прямой задачи.