3.3. Базис задачи квадратичного программирования. Оптимальный и невырожденный базисы.

К оглавлению1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
17 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) будем называть невырожденной, если все ее базисы невырождены. В противном случае назовем задачу вырожденной.