Метод ветвей и границ контрольная (стр. 3 из 3)

Если t>17/2, то

не является планом задачи, так как третья компонента 17 – 2t есть отрицательное число. Поскольку среди элементов 1-й строки табл. 2.42 нет отрицательных при t>17/2 исходная задача неразрешима.

Исследуем теперь разрешимость задачи при t< -7/4. В этом случае Х= (0,5 -3t, 7+4t, 13+t, 0) (см. табл.2.41) не является планом задачи, так как третья компонента 7+4t есть отрицательное число. Чтобы при данном значении параметра найти оптимальный план (это можно сделать, так как в строке вектора Р₃стоит отрицательное число -1/2), нужно исключить из базиса вектор Р₃ и ввести в базис вектор Р₅ (табл. 2.43).

Таблица 2.43

i	Базис	Сб	Р0	3	-2	5	0	-4
				Р1	Р2	Р3	Р4	Р5
1	Р5	-4	-14-8t	-4	0	-2	0	1
2	Р4	0	20+5t	3	0	1	1	0
3	Р2	-2	12+t	1	1	1	0	0
4			32+30t	11	11	1	0	0

Как видно из табл. 2.43,

является оптимальным планом задачи для всех значений параметра t, при которых

Таким образом, если

, то задача (80)-(82) имеет оптимальный план , при котором

Из табл. 2.43 так же видно, что при t<4 задача неразрешима, поскольку в строке вектора Р₄ нет отрицательных элементов.

Итак, если

, то задача не имеет оптимального плана; если оптимальный план, а если , то - оптимальный план, а если , то - оптимальный план, а если , то задача неразрешима.