Появление вырожденного базисного решения
Рассмотрим задачу:
Решим задачу симплексным методом. Введем дополнительные переменные и составим симплекс-таблицу.
Базис | Свободный | Переменные | Оценочные | ||||
член | отношения | ||||||
-1 | |||||||
-2 | |||||||
-4 | 7/3 | ||||||
-2 |
Так как полученное решение не оптимально, переходим к новой симплекс-таблице. Причем, в качестве разрешающей строки можно взять как первую, так и вторую.
Базис | Свободный | Переменные | Оценочные | ||||
член | отношения | ||||||
-1 | |||||||
-3 | |||||||
-б | |||||||
-1 | ! |
Полученное решение вырожденно, так как основная переменная и вновь не является оптимальным. Переходим к новой симплекс-таблице.
Базис | Свободный | Переменные | Оценочные | ||||
член | отношения | ||||||
-2 | |||||||
-3 | |||||||
-2 | |||||||
-1 |
Решение так же вырожденно, так как основная компонента
При этом целевая функция не увеличилась, но и не ухудшилась. Выполненный шаг, хотя и не улучшил значение целевой функции, лишнем не является, так как привел к новому базисному решению. На практике, наличие пустых шагов может привести к зацикливанию задачи.
Вывод. Если на каком-либо шаге симплекс-метода наибольшее возможное значение переменной достигается в нескольких уравнениях одновременно, то в качестве разрешающего можно выбрать одно из них (в симплекс-таблице совпадение оптимальных оценочных отношений). Тогда на следующем шаге получим вырожденное базисное решение, переход к очередному базисному решению может не изменить значение целевой функции.
Замечание. Вырождение, полученное при оптимальном решении может привести к альтернативному оптимуму даже при нулевых коэффициентах при всех не основных переменных в целевой функции.
Дата добавления: 2017-04-05; просмотров: 1391;