K-о ограничения, приводит к изменению

вектора

Рис.3.5 Структура симплекс-таблицы .

Действительно, если то . (3.9)

Каждая i-я компонента вектора определяется следующим соотношением:

(3.10)

где - номер ограничения, правая часть которого варьируется,

- i -я строка матрицы ,

- элемент [i,k] матрицы .

Из формулы (3.10) видно, что изменяться при вариации величины будут лишь те элементы , которым в k-м столбце матрицы соответствует ненулевой элементов .

К неоптимальности прежнего базиса может привести лишь уменьшение . При положительной вариации ( ) это будет в случае <0, а при отрицательной ( ) наоборот - при >0.

Так как в общем случае при вариация b[k] могут изменяться несколько базисных элементов прежнего оптимального решения, то формулы для определения предельных вариаций и будут иметь
следующий вид:

(3.11)

(3.12)

где (3.13)

Соотношение (3.13) получается из (3.10) приравниванием последнего к нулю.

Для того, чтобы провести формальный анализ влияния на решение ЗЛП вариации большей предельной, необходимо в соответствии с соотношением (3.9) пересчитать расширенный вектор базисных компонент. Если вариация больше предельной, то в этом векторе появятся отрицательные компоненты. Базис станет сопряженным. Для нахождения нового решения ЗЛП нужно применить двойственный симплекс-метод, который либо установит пустоту измененной области допустимых решений, либо найдет новое оптимальное решение.

Классифицировать ограничения на активные и неактивные мож­но из анализа последней строки расширенной обратной базисной матрицы .

Известно, что ,

где - оптимальные значения двойственных переменных. Известно также, что

Следовательно, если , то соответствующее i-ое ограничение является активным (т.е. любое изменение b[i] приводит к изменению оптимального значения целевой функции ЗЛП), в противном случае оно является неактивным.

После проведения вариации величины b[k] меньше предельной для получения нового оптимального решения достаточно скорректировать вектор соответствии с формулой (3.10). Если же осуществляется вариация больше предельной, то после пересчета вектора среди

новых значений первых m его компонент появятся отрицательные, т.е. прежнее базисное решение станет недопустимым. При этом прежний базис станет сопряженным, т.е. таким, которому соответствуют зна­чения двойственных переменных, определяющие допустимое базисное решение двойственности ЗЛП.

Для поиска нового решения скорректированной ЗЛП, начиная с сопряженного базиса, необходимо применить алгоритм двойственного симплекс-метода. В результате его работы либо будет найдено новое оптимальное решение, либо установлено, что сделанная вариация привела к пустоте допустимого множества ЗЛП.

Анализ чувствительности оптимального решения