9.22. задачи выпуклого квадратичного программирования

9.22. задачи выпуклого квадратичного программирования

Задача максимизации квадратичной функции

л л

/ = ZW + ZC»X*+2 X cu*kXi (9.68)

j=l fc=l 1<£</<л

на множестве решений системы

J^ayXjub,, /-1,2,...,/и; (9.69)

ху>0, у =1,2,..., я, (9.70)

назьшается задачей квадратичного программирования. Если квадратичная форма

л

fc=l \<k<l<n

является отрицательно-определенной, то квадратичная функция (9.68) является вогнутой. В этом случае задача (9.68)—(9.70) называется задачей выпуклого квадратичного программирования.

ТочкаM0(x°v x°j,х°)является оптимальным решением задачи выпуклого квадратичного программирования (9.68)— (9.70) тогда и только тогда, когда существуют числа у0., v;°, / = 1, 2,

т, и м?,у' = 1, 2,я, такие, что:

х°и° = 0, 7= 1,2,..., я; (9.71)

v°y° = 0, / = 1,2,..., т; (9.72)

268

3) вектор оси = (xj*,хли, у,у^, и, и"п, v, ...,vj является опорным решением системы ограничений

^>0,

х2>0.

Так как ^— = 1 2х,, Эх,

Эх,

= 10 2х2, то система (9.73) имеет вид

1 2xj уу + щ = 0, < 10 2х2 уу + и2 = 0, Ху + х2 + Vy = 4, х^О, х2>0, ^>0, Uy>0, и2>0, Vy>0. Составим вспомогательную задачу (см. п. 9.8): 2ху + yy-Uy+Zy=l, <2x2 + yy-u2 + z2= Ю, Ху + х2 + Vy + z-i = 4,

269

Ху>0, х2>0, Уі>0, щ>0, и2>0, ух>0,

Zl>o, z2>o, z3>0;

(p = Z1 + Z2 + Z3(min).

Решая эту задачу симплекс-методом (см. п. 9.7), необходимо следить за тем, чтобы на каждом шаге базис опорного решения не содержал сопряженных векторов условий. •