Симплекс-множители

Можно умножить ограничения на π₁, π₂, …., π_m, прибавить к выражению для функции z и получить соотношение

(3.5)

Значения π_i можно выбрать так, что коэффициенты при базисных переменных в уравнениях (3.5) станут нулевыми. Значения π_i. называются симплекс-множителями. Если x₁, x₂,…,x_m - базисные переменные (при этом не происходит потери общности), то π_i определяются из системы уравнений

т.е. , (3.6)

где В^Т матрица из коэффициентов при базисных переменных, а - коэффициенты при базисных переменных в исходном виде для функции z. Так как

(3.7)

Однако может быть, что значения π₁, …, π_m легче получить, просматривая симплекс-таблицы.

Рассмотрим снова таблицу примера 1 предыдущей лекции.

Коэффициенты при x₃ и x₄ в оптимальном виде для функции z равны соответственно 2/7 и 4/7; это и есть симплекс-множители для оптимального базиса.

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

Умножив ограничения (как показано выше) на π₁ и π₂ и прибавив их к функции z, получим

(3.8)

что и является окончательным видом для функции z.

Далее из уравнения (3.5) для функции z в окончательном виде ясно, что коэффициенты при базисных переменных будут нулевыми благодаря выбору π_i, а коэффициенты при небазисных переменных будут положительны. При этом (так как небазисные элементы равны 0) каждое слагаемое в левой части уравнения (3.5) равно 0; либо переменная, либо коэффициент при ней равны 0. Следовательно, оптимальное значение для функции z определяется формулой

т.е. (3.9)

Для только что рассмотренного примера это очевидно (см. уравнение (3.8)).

Во многих задачах множители π_i допускают важную экономическую интерпретацию. Симплекс-множители и обращение оптимального базиса играют важную роль в понимании того, как меняется решение, если слегка изменить условия задачи.