|
О ценка сверху исходной задачи уменьш илась на единицу: фо=ф1 + ф2 = 21. прим еним метод ветвей и границ. Разобьем множество всех реш ений на два подмножества. В первом подмножестве Xi = 1, а во втором = 0. О ценим первое подмножество. П олож ив в ограничениях (10) и (11) x i = 1, получим следующие две задачи: З а д а ч а 1. ф1 = тах(4х2+2хз+6х4), Зх 2+2хз+5х 4 < 5. Ее решения: Х4 = 1, Хг = Хз = 0; Хг = Хз = 1, Х4 = 0; ф] = 6 . З а д а ч а 2. ф2 = тах(4х2+4хз+1х4), 5х2+6хз+Зх4 < 8 . Ее решение: Х2 = Хд = 1, Хз = 0; фг = 5. О ценка сверху первого подмножества: ф0 = ф1 + Ф2 + С] = 2 1 . Оценим второе подмножество (x i = 0). Заметим, что при x i = О любое реш ение является допустимы м для первой оценочной задачи. П оэтом у достаточно решить вторую задачу, полож ив Sj2 = Ci, i = 2 , 3 ,4 . Ее решение Х2 = х з = 1 , Х4 = О является оптимальным во втором подмножестве со значением целевой ф ункции Фо 14. Выбираем первое подмножество, имеющее больш ую оценку. Разбиваем первое подмножество на два. В одном из них Хз = 1, а в д ругом — Х2 = 0. Оценим первое подмножество (хг = 1 ). Рассматривая два оф аничения 2хз+5х4 < 2 , 6 Хз+ЗХ4 < 3 , видим, что единственное решение х з = Х 4 = 0 , следовательно оно оптимально в данном подмножестве со значением целевой ф ункции фо = 18. Оценим второе подмножество (хг = 0). В данном случае достаточно сравнить два варианта: Хз = 1, Х4 = О ф1 = 6 и хз = О, Х4 = 1, ф] = 7. 72 |
Оценка сверху первого подмножества: фО= ф1 +ф2+С, =21. Оценим второе подмножество (xi = 0). Заметим, что при Х = Олюбое решение является допустимым для первой оценочной задачи. Поэтому достаточно решить вторую задачу, положив Sfj = с,-, i = 2 ,3 ,4 . Ее решение Х2= Хз = 1, Х4= 0 является оптимальным во втором подмножестве со значением целевой функции фо= 14. Выбираем первое подмножество, имеющее большую оценку. Разбиваем первое подмножество на два. В одном из них Хз = 1, а в другом Х2 0. Оценим первое подмножество (хз = !)• Рассматривая два ограничения 2хз+5х4< 2, 6Хз+ЗХ4<3, видим, что единственное решение Хз = Х4= О, следовательно оно является оптимальным решением в данном подмножестве со значением целевой функции фо= 18. Оценим второе подмножество (хг = 0). В данном случае достаточно сравнить два варианта: 1)Хз=1,Х4 = 0ф = 6 2 )х з = 0 , Х4 = 1 ,ф = 7 Оценка второго подмножества: Фо= 10 + 7 = 17. Ей соответствует оптимальное решение в этом подмножестве XI =Х4 = 1,Х2“ Хз = 0, со значением целевой функции фо= 17. 65 |