Численные методы оптимизации. Рейзлин В.И. - 81 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

81
Если же присутствуют и свободные переменные, то необходимо
данные переменные сделать базисными. И после того, как свободная переменная
станет базисной, в процессе определения разрешающего элемента при поиске
опорного и оптимального планов данная строка не учитывается (но преобразует-
ся).
7.2. Вырожденность в задачах линейного программирования
Рассматривая симплекс-метод, мы предполагали, что задача линейного
программирования является невырожденной, т.е. каждый опорный план содер-
жит ровно
m
положительных компонент, где
m
– число ограничений в задаче. В
вырожденном опорном плане число положительных компонент оказывается
меньше числа ограничений: некоторые базисные переменные, соответствующие
данному опорному плану, принимают нулевые значения. Используя геометриче-
скую интерпретацию для простейшего случая (рис. 38), когда
2nm
(число
небазисных переменных равно 2), легко отличить вырожденную задачу от невы-
рожденной. В вырожденной задаче в одной вершине многогранника условий пе-
ресекается более двух прямых, описываемых уравнениями вида
0
i
x
. Это зна-
чит, что одна или несколько сторон многоугольника условий стягиваются в точ-
ку.
Рис. 38. К понятию вырожденности
Аналогично при
3nm
в вырожденной задаче в одной вершине пересе-
кается более 3-х плоскостей
0
i
x
.
В предположении о невырожденности задачи находилось только одно зна-
чение
min 0
ii
i
il il
bb
aa





, по которому определялся индекс выводимого из ба-
зиса вектора условий (выводимой из числа базисных переменной).
В вырожденной задаче
min 0
ii
i
il il
bb
aa





может достигаться на нескольких
индексах сразу (для нескольких строк). В этом случае в находимом опорном
плане несколько базисных переменных будут нулевыми.
Если задача линейного программирования оказывается вырожденной, то
при плохом выборе вектора условий, выводимого из базиса, может возникнуть
бесконечное движение по базисам одного и того же опорного плана. Это – так
называемое явление зацикливания. Хотя в практических задачах линейного про-

Страницы