Численные методы решения задач линейного программирования. Модифицированный симплекс-метод.

В описанной реализации симплекс-метода на каждой итерации пересчитывается вся симплекс-таблица размера (m +1)* (n +1). Однако так как она определяется выбором базиса, то при выполнении алгоритма нет необходимости в информации обо всей таблице. Если число столбцов в матрице ограничений значительно больше числа ее строк, то можно понизить трудоемкость симплекс-метода, храня и преобразуя матрицу размера (m +1) * (n +1). В литературе этот алгоритм известен под названием модифицированного симплекс-метода или алгоритма с обратной матрицей.

Пусть B – произвольный базис канонической задачи, - расширенная матрица условий задачи, тогда симплекс таблица T, соответствующая базису B, имеет вид:

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

где – матрица, обратная к расширенной базисной матрице

Пусть симплекс-таблица T¢ получена в результате элементарного преобразования симплекс-таблицы T по следующим формулам:

Введем обозначения Тогда , где

.

Итак, , где . Следовательно, достаточно пересчитывать на каждой итерации матрицу M размера (m +1) * (m +1) и хранить матрицу . Требуемые элементы симплекс таблицы вычисляются по формуле по мере необходимости на шагах 1-3 симплекс-метода.

Не нашли, что искали? Воспользуйтесь поиском: