double arrow

Вырожденное опорное решение


 

Базисное решение, в котором хотя бы одна из основных переменных равна нулю, называется вырожденным

С графической точки зрения решение является вырожденным, когда три или более полуплоскостей пересекаются в одной точке.

Рассмотрим на примере следующей задачи:

 

Для производства шариков для пейнтбола зимнего и летнего типа требуется соответственно по 5 г желатина, 2 и 3 мл краски на водной основе и 2 и 1 млстабилизатора. На складе производителя имеется: 15 кгжелатина, 10 л краски и стабилизатора. Стоимость шарика зимнего типа – 2руб,летнего типа1,5 руб.Необходимо найти, сколько произвести шариков каждого типа(x1 и x2). Для достижения максимальной прибыли.

 

Запишем ограничения:

 

Ограничение по желатину:

x1[шт]*5[г]+ x2[шт]*5[г]≤15000[г]  (14)

Ограничение по краске:

x1[шт]*2[мл]+ x2[шт]*3[мл]≤8000[мл]  (15)

Ограничение по стабилизатору:

x1[шт]*2[мл]+ x2[шт]*1[мл] ≤4000[мл]  (16)

 

Критерий запишется так:

F=2[руб]*x1[шт]+ 1.5[руб]*x2[шт]→max (17)

 

На графике Рис. 5видно, что три полуплоскости (14), (15), (16)пересекаются в одной точке. Решив систему уравнений:

 


x1*5+ x2*5=15000

x1*2+ x2*3=8000  (18)

x1*2+ x2*1=4000





можно найти ее координаты x1=1000, x2=2000.

Как видно из графика, она же будет и оптимальной точкой, значит оптимальная прибыль

F=2[руб]*1000[шт]+ 1.5[руб]*2000[шт]=5000[руб]

 
Рис. 5. Вырожденный случай. Пересечение трех полуплоскостей в одной точке тр

 

 


Приведем ограничения к каноническому виду и посмотрим, как это будет выглядеть в симплекс таблице:

 

1. Первый опорный план x(1)=(0,0,15000,8000,4000)

Cb БП x1 x2 x3 x4 x5 b
0 0 0 x3 x4 x5 5 2 2 5 3 1 1 0 0 0 1 0 0 0 1 15000 8000 4000
  ƒ -2 -1.5 0 0 0 0

 

Получаем первую замену x5 на x1


 

2. Второй опорный план x(2)=(2000,0,5000,4000,0)

Cb БП x1 x2 x3 x4 x5 b
0 0 2 x3 x4 x1 0 0 1 2.5 2 0.5 1 0 0 0 1 0 -2.5 -1 0.5 5000 4000 2000
  ƒ 0 -0.5 0 0 1 4000

 

Определяем вторую замену x3 на x2

3. Третий опорный план x(3)=(1000,2000,0,0,0)

Cb БП x1 x2 x3 x4 x5 b
1.5 0 2 x2 x4 x1 0 0 1 1 0 0 0.4 -0.8 -0.2 0 1 0 -1 1 1 2000 0 1000
  ƒ 0 0 0.2 0 0.5 5000

 

Получили оптимальное решение (все коэффициенты критерия ≥0). Число положительных компонент меньше числа ограничений.Значит, признак вырожденности решения в симплекс таблице: в столбце свободных членов b есть нулевой элемент.

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













Сейчас читают про: