ПОИСК Статьи Рисунки Таблицы Вырожденные задачи из "Методы оптимизации в химической технологии издание 2" При выводе основных соотношений симплексного метода допускалось, что любые т векторов из общего числа n + m + 1 векторов AJ и В, составляющих матрицу ограничений, линейно независимы. При решении практических задач данное требование, как правило, обычно выполняется. Поэтому рассмотренный выше алгоритм симплексного метода служит основой подавляющего большинства программ, составленных для решения задач линейного программирования на вычислительных машинах. . [c.454] Однако возможны случаи, когда сформулированное выше предположение и, следовательно, приведенный вывод основных, соотношений симплексного метода не подтверждаются. Задачи, в которых имеется линейная зависимость менее чем m -f 1 векторов-столбцов матрицы ограничений, называются вырожденными задачами линейного программирования. Теоретически при их решении симплексным методом может возникнуть зацикливание , обусловленное тем, что значение линейной формы не изменяется при переходе к новому базисному решению. [c.454] Одним из таких примеров является случай, когда вектор В можно представить/в виде линейной комбинации меньше чем m векторов-столбцов матрицы ограничений. [c.454] Если теперь базисное решение вместо m отличных от нуля составляющих имеет только m — 2 или меньше составляющих, не равных нулю, то возникает возможность появления цикла, в котором не происходит увеличение критерия оптимальности. [c.454] Более подробно случаи вырождения и приемы их устранения можно найти в литературе [1, 2]. [c.454] Вернуться к основной статье