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

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

Формулы пересчета правых частей уравнений системы при преобразовании Жордана имеют вид

; ; i = 1, 2, …, m; i ¹ l.

Используя эти формулы, получим

т. е. . (4.6)

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

. (4.7)

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

(4.8)

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

, (4.9)

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

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

Решение. Задача имеет начальное опорное решение с базисом . Для удобства расчета запишем исходные данные в следующую таблицу, называемую симплексной (табл. 4.2).