Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

Сходимость симплекс-метода

Сходимость симплекс-метода. Вырожденность в задачах ЛП. Важнейшим свойством любого вычислительного, алгоритма является сходимость, т. е. возможность получения в ходе его применения искомых результатов (с заданной точностью) за конечное число шагов (итераций).

Легко заметить, что проблемы со сходимостью симплекс-метода потенциально могут возникнуть на этапе выбора значения r (п. 2") в случае, когда одинаковые минимальные значения отношения

будут достигнуты для нескольких строк таблицы Т (q) одновременно. Тогда на следующей итерации столбец b(q+1)) будет содержать нулевые элементы. Напомним, что

F допустимый базисный план канонической задачи ЛП, соответствующий базису β(q), называется вырожденным, если некоторые его базисные компоненты равны нулю, т. е. вектор b(q)) содержит нулевые элементы.

Задача ЛП, имеющая вырожденные планы, называется вырожденной. При «выходе» на вырожденный план мы фактически получаем разложение столбца b по системе из меньшего, чем m, количества столбцов аj и, следовательно, лишаемся возможности корректно определить, ввод какого столбца в базис приведет к росту значения целевой функции. Подобные ситуации, в конечном счете, могут привести к зацикливанию вычислительного процесса, т. е. бесконечному перебору одних и тех же базисов.

С точки зрения первой геометрической интерпретации ЗЛП ситуация вырожденности означает, что через некоторую угловую точку многогранного множества допустимых планов задачи, соответствующую текущему базисному плану, проходит более чем m гиперплоскостей ограничений задачи. Иными словами, одно или несколько ограничений в данной точке являются избыточными. Последнее предоставляет повод для размышлений об экономической стороне проблемы вырожденности как проблемы наличия избыточных ограничений и в некоторых случаях определяет пути ее решения.

С точки зрения второй геометрической интерпретации ЗЛП вырожденность означает «попадание» линии, проходящей через вершину вектора b параллельно оси аппликат, в ребро конуса, натянутого на систему расширенных векторов текущего базиса. Так, в случае, изображенном на рис. 1.6, эта линия попадает в ребро, определяемое вектором аj2 , т. е., несмотря на то что текущий базис содержит столбцы аj1 и аj2, для представления вектора b достаточно только одного аj2.

Из данной интерпретации вытекает и идея метода решения вырожденных задач ЛП, получившего названия метода возмущений: при выходе на вырожденный план осуществляется незначительный сдвиг вектора b и вырожденность (как это видно из иллюстрации) устраняется.

Необходимо, однако, сказать, что рассмотренная здесь проблема зацикливания для большинства практически значимых задач является достаточно редкой и маловероятной. Более того, она очень часто разрешается за счет ошибок округлений при выполнении расчетов на ЭВМ.