Преобразование целевой функции при переходе от одного опорного решения к другому

Пусть имеется опорное решение задачи линейного программирования с базисом Значение целевой функции задачи на этом решении Используя преобразование Жордана с разрешающим элементом , перейдем к другому опорному решению:

с базисом т.е. введем в базис вектор и исключим .

Пересчитав правые части с помощью преобразований Жордана, получим выражение для целевой функции задачи на новом опорном решении .

Здесь через обозначена величина, называемая оценкой разложения вектора условий по базису опорного решения и вычисляемая по формуле:

или в векторной записи

, (2.2.1)

где - вектор коэффициентов целевой функции при базисных переменных; вектор коэффициентов разложения вектора по базису опорного решения; - коэффициент целевой функции при переменной .

Находим приращение целевой функции при переходе от одного опорного решения к другому:

.