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

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

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

 

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

 

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

 

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

 

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

 

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

 

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

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

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

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

 








Дата добавления: 2019-07-26; просмотров: 424;


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

При помощи поиска вы сможете найти нужную вам информацию.

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

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.008 сек.