2. Вариация коэффициентов цф
Пусть R(c) – задача ЛП, ограничения совпадают с ограничениями задачи P , ЦФ имеет вид f (c;x) = c · x.
Определение: Множество всех векторов c таких, что является решением задачи R(c), назовем областью постоянства оптимального решения (ОПОР).
Графически для прямой задачи – решение остается неизменным при изменении коэффициентов ЦФ, когда изменяется ее градиент (происходит поворот целевой функции вокруг оптимальной точки).
Определение: Пусть β – произвольный базис матрицы A0, . Для любого положим .
Утверждение: Вектор принадлежит ОПОР, если и только если существует оптимальный в задаче R(c) базис β матрицы A0, для которого .
Определение: Множество – это множество всех базисов β матрицы A0 таких, что .
Для каждого положим .
Следствие (общее описание ОПОР): .
Зафиксируем .
Зная базисную матрицу , найдем матрицу .
эквивалентно (**).
После приведения задачи R(c) (или P) к базису условия (**) для базисной части полностью выполнены. Достаточно рассмотреть эти условия для небазисной компоненты
Пусть вектор , где . Тогда условие (**) запишется следующим образом:
Эту систему чаще всего рассматривают для найденного оптимального базиса , описывая таким образом .
Утверждение: Если – невырожденное решение задачи P,
то .
Обозначим для разрешимой задачи R(c) через – оптимальное значение ЦФ. Кроме того, для всякого базиса β матрицы A0 и любого вектора положим .
Свойства векторов ОПОР:
Если , то является решением задачи R(c);
Если , то ;
Если , то есть вектор двойственных оценок для задачи R(c).
Прогноз максимального значения ЦФ
Пусть , где .
Вычислим матрицу и для всех j.
Если неравенства
выполняются, то и вектор оптимален в обеих задачах P и R(c), поэтому .
Если неравенства не выполняются, то исследователю проще решить новую задачу.
Прогноз двойственных оценок
Двойственные оценки отражают относительную полезность ингредиентов.
Утверждение: Если и , то вектор является решением задачи R*(c). В частности, при решением задачи является вектор .
Частный случай: вариация одного коэффициента ЦФ
Пусть изменяется только одна компонента вектора (с номером k):
и .
Тогда неравенства перепишутся следующим образом
.
Рассмотрим 2 случая.
1) . Тогда для всех базисных компонент.
Для и неравенство принимает вид и оно всегда выполняется, так как все неотрицательны.
При получаем или .
Следовательно, .
2) . Пусть . Тогда и для всех . Поэтому неравенства перепишутся в виде
.
Это система линейных неравенств относительно одной переменной .
Если , то соответствующее неравенство выполняется при любом . Если , то, разделив неравенства на него, получим нижнюю неположительную границу для .
Если , то аналогичным образом получим верхнюю неотрицательную границу.
Вектор двойственных оценок вычислим следующим образом
,
где – элементы матрицы