Разделы

Авто
Бизнес
Болезни
Дом
Защита
Здоровье
Интернет
Компьютеры
Медицина
Науки
Обучение
Общество
Питание
Политика
Производство
Промышленность
Спорт
Техника
Экономика

Вырожденность

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

С практической точки зрения данная ситуация объясняется наличием в модели избыточных ограничений.

 

Пример: max Z = 3 х1 + 9х2

 

{ х1 + 4 х2 ≤ 8 - (1) х1 + 2 х2 ≤ 4 - (2)

x1 , x 2 ≥ 0

0 итерация:

Баз. Пер. Х1 х2 х3 х4 Решение
Z - 3 - 9
х3
х4

1 итерация

Баз. Пер. Х1 х2 х3 х4 Решение
Z - 3/4 9/4
х2 1/4 1/4
х4 1/2 -1/2

2 итерация

Баз. Пер. Х1 х2 х3 х4 Решение
Z 3/2 3/2
х2 1/2 -1/2
Х1 -1

На 1 и 2 итерациях хотя состав базисных и небазисных переменных

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

 

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

 

Дата публикации:2014-01-23

Просмотров:363

Вернуться в оглавление:

Комментария пока нет...


Имя* (по-русски):
Почта* (e-mail):Не публикуется
Ответить (до 1000 символов):







 

2012-2018 lekcion.ru. За поставленную ссылку спасибо.