4.2 Некоторые свойства решения параметрической задачи квадратичного программирования.

К оглавлению1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
17 18 

                Пусть получено решение задачи (4.1.1) при некотором значении параметра, равном m0 . Это означает, что получен вектор x*(m0) , а также набор индексов Á(m0) , и порожденный им оптимальный базис. Рассмотрим множество таких m , для которых это решение остается оптимальным и допустимым. Для этого запишем условия Куна-Таккера:

 

 

(4.1.2)

      

                Как следует из постановки задачи, правую часть выражения (4.1.2) можно представить в следующем виде:

 

 

(4.1.3)

 

                Разложив вектор R по указанному базису, и подставив это разложение в (4.1.3), получим следующие выражения для коэффициентов разложения (4.1.2):

 

 

(4.1.4)

 

                Здесь - коэффициенты разложения вектора R по базису. Условием нарушения оптимальности решения является факт обращения в ноль одного из неотрицательных коэффициентов (4.1.4). Отсюда следует, что интервал, на котором исходное решение является оптимальным, является отрезком следующего вида:

 

(4.1.5)

 

                где

 

 

(4.1.6)

 

                а

 

 

(4.1.7)

 

                Из выражений (4.1.4) вытекает также тот факт, что на интервалах (4.1.5) вектор-функция x*(m) представляет собой отрезок прямой в пространстве En , и является линейной. Стало быть, значения целевой функции на интервале представляют собой параболу.      

                Пусть получено решение задачи (4.1.1) при некотором значении параметра, равном m0 . Это означает, что получен вектор x*(m0) , а также набор индексов Á(m0) , и порожденный им оптимальный базис. Рассмотрим множество таких m , для которых это решение остается оптимальным и допустимым. Для этого запишем условия Куна-Таккера:

 

 

(4.1.2)

      

                Как следует из постановки задачи, правую часть выражения (4.1.2) можно представить в следующем виде:

 

 

(4.1.3)

 

                Разложив вектор R по указанному базису, и подставив это разложение в (4.1.3), получим следующие выражения для коэффициентов разложения (4.1.2):

 

 

(4.1.4)

 

                Здесь - коэффициенты разложения вектора R по базису. Условием нарушения оптимальности решения является факт обращения в ноль одного из неотрицательных коэффициентов (4.1.4). Отсюда следует, что интервал, на котором исходное решение является оптимальным, является отрезком следующего вида:

 

(4.1.5)

 

                где

 

 

(4.1.6)

 

                а

 

 

(4.1.7)

 

                Из выражений (4.1.4) вытекает также тот факт, что на интервалах (4.1.5) вектор-функция x*(m) представляет собой отрезок прямой в пространстве En , и является линейной. Стало быть, значения целевой функции на интервале представляют собой параболу.