3.3. Базис задачи квадратичного программирования. Оптимальный и невырожденный базисы.
К оглавлению1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1617 18
Поскольку ранг матрицы A равен m (см 3.1), система векторов
являются линейно независимой системой векторов. В то же время, легко видно, что линейная оболочка, натянутая на систему векторов P совпадает с пространством Em+n, т.е L(P)=En+m.
Следовательно из системы векторов 3.2.4 можно образовать конечное число базисов N евклидова пространства En+m, содержащих в себе векторы P1, .. Pm. Такие базисы пространства En+m будем называть базисами задачи квадратичного программирования, и обозначать следующим образом:
(3.3.1)
|
Для упрощения схемы алгоритма, запишем базис (3.3.1) в следующем виде:
(3.3.2) |
Здесь Á1 и Á2 - наборы индексов. В случае, если Á1=Á2 будем считать базис UÁ1,Á2 порожденным одним множеством индексов Á=Á1.
(3.3.3) |
Коэффициенты разложения вектора b по базису UÁ1,Á2 будем называть базисными переменными, остальные коэффициенты - небазисными переменными.
Базис UÁ1,Á2 назовем оптимальным, если его базисные переменные удовлетворяют условиям Куна-Таккера (3.2.3).
Базис называется невырожденным, если все его базисные переменные, соответствующие компонентам вектора x отличны от нуля, т.е.
(3.3.4) |
Задачу (3.1.2) будем называть невырожденной, если все ее базисы невырождены. В противном случае назовем задачу вырожденной.
Поскольку ранг матрицы A равен m (см 3.1), система векторов
являются линейно независимой системой векторов. В то же время, легко видно, что линейная оболочка, натянутая на систему векторов P совпадает с пространством Em+n, т.е L(P)=En+m.
Следовательно из системы векторов 3.2.4 можно образовать конечное число базисов N евклидова пространства En+m, содержащих в себе векторы P1, .. Pm. Такие базисы пространства En+m будем называть базисами задачи квадратичного программирования, и обозначать следующим образом:
(3.3.1)
|
Для упрощения схемы алгоритма, запишем базис (3.3.1) в следующем виде:
(3.3.2) |
Здесь Á1 и Á2 - наборы индексов. В случае, если Á1=Á2 будем считать базис UÁ1,Á2 порожденным одним множеством индексов Á=Á1.
(3.3.3) |
Коэффициенты разложения вектора b по базису UÁ1,Á2 будем называть базисными переменными, остальные коэффициенты - небазисными переменными.
Базис UÁ1,Á2 назовем оптимальным, если его базисные переменные удовлетворяют условиям Куна-Таккера (3.2.3).
Базис называется невырожденным, если все его базисные переменные, соответствующие компонентам вектора x отличны от нуля, т.е.
(3.3.4) |
Задачу (3.1.2) будем называть невырожденной, если все ее базисы невырождены. В противном случае назовем задачу вырожденной.