 |
 |
 |
 |
|
 |
 |
25
содержит нулевые элементы.
Задача ЛП, имеющая вырожденные планы, называется вырожденной. При «выходе» на
вырожденный план мы фактически получаем разложение столбца
b по системе из меньшего, чем m,
количества столбцов а
j
и, следовательно, лишаемся возможности корректно определить, ввод какого
столбца в базис приведет к росту значения целевой функции. Подобные ситуации, в конечном счете,
могут привести к зацикливанию вычислительного процесса, т. е. бесконечному перебору одних и тех же
базисов.
С точки зрения первой геометрической интерпретации ЗЛП ситуация вырожденности означает, что
через некоторую угловую точку многогранного множества допустимых планов задачи,
соответствующую текущему базисному плану, проходит более чем m гиперплоскостей ограничений
задачи. Иными словами, одно или несколько ограничений в данной точке являются избыточными.
Последнее предоставляет повод для размышлений об экономической стороне проблемы вырожденности
как проблемы наличия избыточных ограничений и в некоторых случаях определяет пути ее решения.
С точки зрения второй геометрической интерпретации ЗЛП вырожденность означает «попадание»
линии, проходящей через вершину вектора b параллельно оси аппликат, в ребро конуса, натянутого на
систему расширенных векторов текущего базиса. Так, в случае, изображенном на рис. 1.6, эта линия по-
падает в ребро, определяемое вектором а
j2
, т. е., несмотря на то что текущий базис содержит столбцы
а
j1
и а
j2
, для представления вектора b достаточно только одного а
j2
.
Из данной интерпретации вытекает и идея метода решения вырожденных задач ЛП, получившего
названия метода возмущений: при выходе на вырожденный план осуществляется незначительный сдвиг
вектора b и вырожденность (как это видно из иллюстрации) устраняется.
Необходимо, однако, сказать, что рассмотренная здесь проблема зацикливания для большинства
практически значимых задач является достаточно редкой и маловероятной. Более того, она очень часто
разрешается за счет ошибок округлений при выполнении расчетов на ЭВМ.
1.4.5. Нахождение допустимого базисного плана. В рассмотренном выше примере исходный
базисный план, необходимый для начала вычислений по симплекс-методу, был подобран за счет
особенностей матрицы условий. Действительно, данная матрица уже содержала необходимое
количество «почти базисных» столбцов. Очевидно, что для подавляющего большинства задач ЛП
невозможно подобным образом сразу и в явном виде указать исходный допустимый базисный план.
Вообще говоря, существуют различные приемы решения данной задачи. Мы остановимся на одном из
них, получившем название метода минимизации невязок. Его сильной стороной, безусловно, является
универсальность. Xотя, в некоторых частных случаях, он может оказаться слишком громоздким.
Идея метода минимизации невязок состоит в построении соответствующей вспомогательной задачи,
для которой можно в явном виде указать исходный базисный план, и решении ее с помощью процедуры
симплекс-метода.
Не умаляя общности, можно считать, что вектор ограничений в исходной задаче неотрицателен, т. е.
b
i
? 0,
i
1: m. Тогда для КЗЛП максимизации функции