|
Она имеет два решения: Х = Х4 = 1, х2 = Хз = 0 и Х = Хг= хз = 1, х* = О. В обоих случаях (р! = 1 1 . Задача 2. ф2 = тах (4 х+5 х2 +4 хз+2 х4 ), 3 x1 + 5 х2 +6 х3 +Зх4 < 1 1 . Ее решение: X] = Х2 = Х4 = 1, хз = 0, ср2 = 11. Оценка сверху исходной задачи фо = (р! + (р2 = 2 2 . Для улучшения оценки увеличим Б21 и на единицу, уменьшив на единицу Ь22 и 8 4 2 . Получаем две новые оценочные задачи. Задача 1. ф1 = шах(6 х!+4 х2 +2 хз+6 х4 ), 6х1+3х2+2хз+5х4 < 1 1 . Ее решения: XI = Х4 = 1, хг = хз = 0; Х = Х2 = хз = 1, Х4 = 0; Х2 = Хз = Х4 = I, XI = 0 ; ф! = 1 2 . Задача 2. ф2 = тах (4 х!+4 х2 +4 хз+1 х4 ), З Х 1+ 5Х 2+ 6Х 3+ З Х4 <11. Ее решение: X] = х2 = Х4 = 1, хз = 0; ф2 = 9. Оценка сверху исходной задачи уменьшилась на единицу: ф0 = ф1 + ф 2 = 2 1 . Применим метод ветвей и границ. Разобьем множество всех решений на два подмножества. В первом подмножестве Х = 1, а во втором X) = 0. Оценим первое подмножество. Положив в ограничениях (10) и (11) XI = 1 , получим следующие две задачи: Задача 1. ф1 = тах (4 х2 +2 хз+6 х4 ), Зхг+2хз+5х4 < 5. Ее решения: Х4 = 1, Х2 = хз = 0; Х2 = хз = 1, Х4 = 0; ф! = 6 . Задача 2. ф2 = тах (4 х2 +4 хз+1 х4 ), 5 Х2 +6 Х3 +ЗХ4 < 8 . Ее решение: Х2 = Х4 = 1, Хз = 0; ф2 = 5. Оценка сверху первого подмножества: Фо= ф1 + Ф2 + С1 = 2 1 . 53 |
Задача 1. cpi = та х (6х+3х2+2хз+5х4), 6xi+3x2+2x3+5x4 <11. Она имеет два решения: Х = Х4= I, х2= х3= 0 и xj = х2= Х3= 1, Х4= О. В обоих случаях ipi = 11. Задача 2. <р2 max(4xi+5x2+4x3+2x4), 3xi+5x2+6x3+3x4 <11. Ее решение: X =X 2= X41, х3= 0, ф2= 11. Оценка сверху исходной задачи Фо= ф! + ф222. Для улучшения оценки увеличим s2i и S41 на единицу, уменьшив на единицу s22 и s42. Получаем две новые оценочные задачи. Задача 1. ф! = тах(6х+4х2+2хз+6х4), 6xj+3x2+2x3+5x4 < 11. (10) Ее решения: Х = Х4= 1,X2 = X3= 0; xj = х2= х3= 1, Х4= 0; х2= хз = х4 = 1, Х = 0; Ф, = 12. Задача 2. ф2= max(4xi+4x2+4x3+ lx 4), 3xi+5x2+6x3+3x4 < 11. (11) Ее решение: Х = х2 = Х4= 1, хз = 0; ф2= 9. Оценка сверху исходной задачи уменьшилась на единицу: ф0 = ф 1 + ф 2 = 21. Применим метод ветвей и границ. Разобьем множество всех решений на два подмножества. В первом подмножестве Xj = 1, а во втором X] 0. Оценим первое подмножество. Положив в ограничениях (10) и (11) Xj = 1, получим следующие две задачи: Задача 1. ф] = тах(4х2+2хз+6х4), Зх2+2хз+5х4 ^5. Ее решения: Х4= 1, х2= Хз = 0; х2= х3= 1, х4= 0; ф = 6. Задача 2. ф2= тах(4х2+4хз+1Х4), 5х2+6х3+Зх4 ^ 8. Ее решение: х2= X4 = 1, х3= 0; ф2= 5. Оценка сверху первого подмножества: ф0= ф1+ ф2+ С! = 21. Оценим второе подмножество (xj = 0). Заметим, что при xj = 0 любое решение является допустимым для первой оценочной задачи. Поэтому достаточно решить вторую задачу, положив Sj2= Ci, i = 2 ,3 ,4 . Ее решение х2= х3= 1, Х4= 0 является оптимальным во втором подмножестве со значением целевой |