Математические методы исследования операций в экономике (стр. 9 из 37)

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

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

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

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

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

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

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

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

1.4.5. Нахождение допустимого базисного плана. В рассмотренном выше примере исходный базисный план, необходимый для начала вычислений по симплекс-методу, был подобран за счет особенностей матрицы условий. Действительно, данная матрица уже содержала необходимое количество «почти базисных» столбцов. Очевидно, что для подавляющего большинства задач ЛП невозможно подобным образом сразу и в явном виде указать исходный допустимый базисный план. Вообще говоря, существуют различные приемы решения данной задачи. Мы остановимся на одном из них, получившем название метода минимизации невязок. Его сильной стороной, безусловно, является универсальность. Xотя, в некоторых частных случаях, он может оказаться слишком громоздким.

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

Не умаляя общности, можно считать, что вектор ограничений в исходной задаче неотрицателен, т. е. bⁱ ≥ 0,iÎ 1: m. Тогда для КЗЛП максимизации функции

на множестве, определяемом ограничениями

строится вспомогательная задача

Как видно из (1.36)-(1.39), задача (

,
) отличается от задачи (D,f) матрицей, получаемой в результате добавления кисходной матрице А единичной матрицы, которой соответствуют дополнительные (фиктивные) переменные х_n₊₁,...,х_n+m. Данным переменным (собственно говоря, их и называют невязками) в целевой функции
отвечают коэффициенты (-1), а переменным х₁,...,х_n, которые являются общими для обеих задач, — нулевые коэффициенты. Существенной особенностью (
,
) является наличие в ней очевидного исходного базиса, образуемого добавленными столбцами, и соответствующего плана с базисными компонентами х_n+i = b_i ≥ 0, iÎ 1: m. В силу структуры целевой функции f̃ в процесс поиска ее максимума процедурой симплекс-метода фиктивные переменные (невязки) х_n+i должны минимизироваться желательно до нуля, что может быть достигнуто за счет последовательного перевода их в небазисные компоненты плана. Если в оптимальном плане х̃, полученном в результате решения вспомогательной задачи, последние m компонент (т. е. невязки) равны нулю, то его начальные n компонент удовлетворяют системе ограничений, определяющих область D, и
легко (простым отбрасыванием невязок) может быть преобразован в стартовый допустимый план основной задачи (D, f). При этом все строки симплекс-таблицы, полученной на последней итерации вспомогательной задачи (за исключением нулевой), могут быть перенесены в первую таблицу основной задачи. Элементы же нулевой строки для вновь формируемой симплекс-таблицы вычисляются по формулам:

где β^(*) — базис, полученный на последней итерации вспомогательной задачи.

В случае, когда оптимальный план вспомогательной задачи х̃ все же содержит не равные нулю фиктивные компоненты (т. е.

(
)<0), мы приходим к заключению об отсутствии допустимых планов у исходной задачи (D, f), т. е.D = Ø.

1.5. МОДИФИЦИРОВАННЫЙ СИМПЛЕКС-МЕТОД

1.5.1. Вычислительная схема, основанная на преобразовании обратных матриц. Анализируя вычислительную процедуру симплекс-метода с позиций оценки трудоемкости, нетрудно заметить, что наиболее критичным в этом плане является этап пересчета значений А и b при переходе от одного базисного плана к другому (п. 3 алгоритма). Однако в том случае, когда число ограничений задачи m явно меньше количества переменных n, можно добиться существенной «экономии», выполняя на очередной итерацииq преобразование Жордана—Гауссане над матрицей А(β^(q)), а над матрицей Δ^-1(β^(q)). При этом учитывается и то, что при необходимости, применяя формулу (1.26), всегда можно получить А(β^(q))по Δ^-1(β^(q)). Более того, для выполнения описанных выше действий симплекс-процедуры нам в действительности не требовалась матрица А(β^(q))целиком. Реально в ней использовались только строка оценок a₀(β^(q)) и ведущий столбецa^l(β^(q)). Данные соображения положены в основу вычислительной схемы симплекс-метода, основанной на преобразовании обратных матриц, которую также называют модифицированным симплекс-методом. Впервые данный алгоритм был предложен в 1951 г. в работах Л. В. Канторовича.