Появление вырожденного базисного решения


Рассмотрим задачу:

Решим задачу симплексным методом. Введем дополнительные переменные и составим симплекс-таблицу.

 

Базис Свободный Переменные Оценочные
  член           отношения
   
-1
-2
-4 7/3
-2  

 

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

 

Базис Свободный Переменные Оценочные
  член           отношения
   
-1
-3
-1 !

 

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

 

Базис Свободный Переменные Оценочные
  член           отношения
   
-2  
-3  
-2  
-1  

 

Решение так же вырожденно, так как основная компонента

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

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

Замечание. Вырождение, полученное при оптимальном решении может привести к альтернативному оптимуму даже при нулевых коэффициентах при всех не основных переменных в целевой функции.

 



Дата добавления: 2017-04-05; просмотров: 1398;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.007 сек.