2.9 Модифицированный симплекс-метод

При реализации симплекс-алгоритма непосредственно в том виде, как это описано выше, нам на каждой итерации требовалось бы пересчитывать всю симплекс-таблицу размера (то + 1) X (п + 1).  При внимательном анализе алгоритма легко заметить, что этого можно избежать, если хранить и соответствующим образом преобразовывать матрицу меньшего размера (то+1) X (то+1) (при условии то <С п, что на практике бывает довольно часто). Пусть А — расширенная матрица условий задачи:

А

0

св

см

ъ

В

N

где В — базис. Тогда симплекс-таблица Г, соответствующая базису В, имеет вид

Г

-свВ'Ч

0

см - свВ~1Н 4

В~1Ь

I

в~1н

Легко проверить, что

Г = МА, (2.7)

где

М

 

-свВ-1 4

0

в-1

матрица, обратная к расширенной базисной В =

 

Таким образом, согласно (2.7) для вычисления элементов симп­лекс-таблицы наряду с А достаточно знать матрицу М. Симплекс-таблица Г', получаемая в результате преобразования текущей та­блицы Г на шаге 4 ввиду замены одного из базисных столбцов а (г ) := в, связана с ней соотношением Т' = МгеТ, где

Мг

І і о

О 1

V о о

М1г

Иг,

о \ о

1 /

Hjr = —Zis/zrs, при г ф г, prr = l/zrs, Zis — элементы ведущего столбца симплекс-таблицы Т. (Здесь предполагается, что нуме­рация строк и столбцов матрицы Mrs, как и других матриц этого пункта, начинается с 0). Следовательно, Т' = М'А, где

Таким образом, вместо вычисления всей симплекс-таблицы Г можно ограничиться пересчетом на каждой итерации лишь ма­трицы М в соответствие с формулой (2.8) и хранением матрицы А, прибегая к формуле (2.7) для вычисления тех или иных эле­ментов симплекс-таблицы лишь по мере необходимости.

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