|
Оценим второе подмножество (Х = 0). Заметим, что при Х = 0 любое решение является допустимым для первой оценочной задачи. Поэтому достаточно решить вторую задачу, положив $¡2 = с,-, [=2,3,4. Ее решение Х2 = Хз = 1 , Х4 = 0 является оптимальным во втором подмножестве со значением целевой функции <ро= 14. Выбираем первое подмножество, имеющее большую оценку. Разбиваем первое подмножество на два. В одном из них Х2 = 1, а В ДруГОМ Х2 = 0. Оценим первое подмножество (хг = 1). Рассматривая два ограничения 2хз+5х4 < 2 , 6 Х3+ЗХ 4 < 3 , видим, что единственное решение хз = Х4 = 0 , следовательно оно оптимально в данном подмножестве со значением целевой функции фо = 18. Оценим второе подмножество (Х2 = 0). В данном случае достаточно сравнить два варианта: хз = 1, Х4 = 0 ф! = 6 и х3 = 0, хд = 1, ч>1 = 7. Оценка второго подмножества: фо = 10 + 7 = 17. Ей соответствует оптимальное решение в этом подмножестве XI = Х4 = 1 , Х2 = Хз = 0 , со значением целевой функции (ро= 17. Выбираем первое подмножество, а следовательно, и оптимальное решение Х]=Х2 = 1 , хз = Х4 = 0, ср0 = 18. Дерево ветвлений приведено на рис. 1.5.7. 54 Рис. 1.5.7. Интересно сравнить описанный способ получения оценок для задач целочисленного линейного программирования с известными способами. В основном применяются два способа. В соответствии с первым из них решаются т задач о ранце с каждым ограничением отдельно. Очевидно, что наи |
функции фо= 14. Выбираем первое подмножество, имеющее большую оценку. Разбиваем первое подмножество на два. В одном из них Х2 = 1, а в другом х20. Оценим первое подмножество (х2= 1). Рассматривая два ограничения 2хз+5х4 <2, 6 Х 3 + З Х 4 < 3, видим, что единственное решение х3= Х4= 0, следовательно оно оптимально в данном подмножестве со значением целевой функции ф0= 18. Оценим второе подмножество (х2= 0). В данном случае достаточно сравнить два варианта: хз = 1, X4= 0 ф = 6 и х3= 0, X4 = 1, = 7. Оценка второго подмножества: фо = 10 + 7 = 17. Ей соответствует оптимальное решение в этом подмножестве xj = Х4= 1, х2= х3= 0, со значением целевой функции фо = 17. Выбираем первое подмножество, а следовательно, и оптимальное решение X] = Х2= 1, Хз = Х4= 0, фо = 18. Дерево ветвлений приведено на рис. 2.7. Интересно сравнить описанный способ получения оценок для задач целочисленного линейного программирования с известными способами. В основном применяются два способа. В соответствии с первым из них решаются Рис. 2 .7. Дерево ветвлений в задаче целочисленного программирования т задач о ранце с каждым ограничением отдельно. Очевидно, что наихудшее решение (по значению целевой функции) определяет оценку сверху исходной задачи. Для нашего примера имеем две задачи о ранце Задача 1. шах (1Oxj + 8x2+ 6x3+ 7x4) 6x1 + 3 x2 = 2хз + 5 x4 ^ 11 Ее решение Х = Хг= Х3= 1, Х4= 0; ф\ = 24 Задача 2. max (10xi + 8x2+ 6х3+ 7x4) 3xi + 5х26x3+ Х4 й 1 1 Ее решение Х\ = х2 = Х4= 1, Хз = 0; ф( = 25. 97 |