Обращение базиса и симплекс-множители

Вспомним вид общей задачи ЛП в стандартной форме:

Минимизировать

при ограничениях

(3.1)

Матрица A может быть разбита следующим образом:

A = (BR) (3.2)

где B - матрица с коэффициентом на диагонали x₁, x₂,…, x_m, a R – матрица размерностью m × n − m (остаток матрицы A).

Запишем уравнение (3.1) в виде

(BR) x = b (3.3)

Канонический вид для некоторого базиса может быть получен умножением вектора исходных ограничении на матрицу, полученную обращением этого базиса. Таким образом, каноническая форма для базиса получается умножением уравнения (3.3) на матрицу В^-1.

B ⁻¹ (BR) x = B ⁻¹ b,

Тогда получим соотношение

I_m (B^{- 1} R) x =b ^/ (это - уравнение (3.2а)) (3.4)

или

(3.4б)

что соответствует канонической форме для ограничений. В (3.4) I_m – единичная матрица, b ^/ = B ⁻¹ b

Если а_j — столбец из коэффициентов при переменной х_j в ограничении (3.1), то

(3.4а)

представляет собой столбец из коэффициентов при х_j в канонической форме для всех столбцов j = m +1,…, n.

В каждой канонической форме относящиеся к ней базисные переменные были исключены из целевой функции z. В симплекс-методе это делается итеративно, например на каждой стадии с использованием исходного вида ограничений (3.1).