|
О ценка второго подмножества: фо = 1 0 + 7 = 17. Е й соответствует о пти мальное решение в этом подмножестве Xj = Х4 = 1, ха = Хз = О, со значением целевой фзлпсции фо = 17. Выбираем первое подмножество, а следовательно, и оптимальное решение Х = Ха = 1, Хз = Х4 = О, фо = 18. Дерево ветвлений приведено на рис. 2.7. Интересно сравнить описанны й способ получения оценок для задач целочисленного линейного программирования с известными способами. В основном применяются два способа. В соответствии с первы м из н и х реш аю тся 73 целочисленного программирования т задач о ранце с каж ды м ограничением отдельно. О чевидно, что наихудшее решение (по значению целевой ф ункции) определяет оценку сверху исходной задачи. Для наш его примера имеем две задачи о ранце З а д а ч а !. m ax (lO x j + 8 x 2 + 6 x 3 + 7 x 4) 6 X1 + 3X2 = 2 X3 + 5 X4 < 1 1 Ее решение Х; = Хт= Хз = 1, Х4 = 0; ф] = 24 З а д а ч а 2. m ax (lO x j + 8 x 2 + 6 x 3 + 7 x 4) 3xi + 5x2 = 6x3 + Х4 < 11 Ее решение x i = Х2 = Х4 = 1, хз = 0; ф] = 25. Т аким образом, оценка сверху оптимального реш ения исходной задачи в данном случае равна 24, что больше чем оценка 21, полученная методом сетевого программирования. Более того, поскол ьку обе рассмотренные задачи о ранце получаю тся в методе сетевого программирования (первая при Sn = с ;, Si2 = О, а вторая, наоборот, при Si2 = Cj, Sji = 0), то м ож но утверждать, что применение метода сетевого проф аммирования дает лучш ие (или такие же) оценки. |
Выбираем первое подмножество, а следовательно, и оптимальное решение X] = Х2 = 1, хз = Х4= О, фо= 18. Дерево ветвлений приведено на Рис. 5.1. Интересно сравнить описанный способ получения оценок для задач целочисленного линейного программирования с известными способами. В основном применяются два способа. В первом решаются m задач о ранце с каждым ограничением отдельно. Очевидно, что наихудшее решение (по значению целевой функции) определяет оценку сверху исходной задачи. Для нашего примера имеем две задачи о ранце Задача 1. max (lO xi + 8x2 + 6x3 + 7x4) 6x1+ 3x2 = 2хз + 5X4 ^ 11 Х1=Х2 = Хз= 1,Х4=0, ф, = 24 max (lO xi + 8x2 + 6x3 + 7x4) 3xi + 5x2 = 6x3+ Х4 < 11 Ее решение Задача 2. Ее решение Х = Х2 = Х4 = 1, Хз = О, ф1 = 25. Таким образом, оценка сверху оптимального решения исходной задачи в данном случае равна 24, что больше чем оценка 21, полученная методом дихотомического программирования. Более того, поскольку обе рассмотренные задачи о ранце получаются в методе дихотомического программирования (первая при Зц = Cj, Sj2= О , а вторая наоборот, при 66 |