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

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

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

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

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

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

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

.

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

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

Существуют следующие числовые методы решения задач линейного программирования:1) прямой симплекс-метода 2) модифицированный симплекс-метод 3) лексикографический прямой симплекс-метод 4) двухфазовый симплекс-метод 5) двойственный симплекс-метод 6) лексикографический двойственный симплекс-метод

В вырожденных задачах при детерминированном правиле выбора ведущего элемента может наблюдаться зацикливание алгоритма симплекс-метода, Для того чтобы гарантировать конечность симплекс-метода в вырожденных задачах, необходимо исключить возможность подобного зацикливания.Таким свойством обладает правило Блэнда, состоит в выборе наименьшего s. Также зацикливание можно предотвратить при использовании лексикографической процедуры выбора ведущей строки.

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

Существуют следующие числовые методы решения задач линейного программирования:1) прямой симплекс-метода 2) модифицированный симплекс-метод 3) лексикографический прямой симплекс-метод 4) двухфазовый симплекс-метод 5) двойственный симплекс-метод 6) лексикографический двойственный симплекс-метод

Рассматривается общий метод решения задачи ЛП в канонической форме, позволяющий на первом шаге найти базисное допустимое решение или установить, что Q = 0, а на втором шаге найти оптимальный базис и соответствующее ему решение, либо установить неразрешимость задачи из-за неограниченности целевой функции. При этом не предполагается, что ранг матрицы A равен m. Без ограничения общности можно считать, что система ограничений равенств Ax = b записана таким образом, что b ≥ 0 . Этого можно добиться, умножая нужные строки на -1. Тогда метод искусственного базиса можно представить в виде следующих шагов.

Шаги 0)-7) описанного выше способа получения базисного допустимого решения обычно называют первым этапом симплекс-метода, а метод в целом двухэтапным симплекс-методом. Выполнение шага 6 свидетельствует о линейной зависимости уравнений

=xA b, что позволяет удалить часть уравнений. Подобная ситуация возника-

ет, когда ранг матрицы A меньше числа уравнений m . После выполнения шага 7 имеем прямо допустимую симплекс-таблицу исходной задачи, то есть завершен 0-ой шаг алгоритма пункта 1.3, и можно переходить к его шагам 1)-4). В результате либо установим, что целевая функция w(x) не ограничена снизу, либо получим оптимальное решение.