4.2 Некоторые свойства решения параметрической задачи квадратичного программирования.
К оглавлению1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1617 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 , и является линейной. Стало быть, значения целевой функции на интервале представляют собой параболу.