Нетрудно показать, что дальнейшее уменьш ение Z не приводит к уменьш ению оценки. П оэтом у оптимальное zq = Z2 = 35. Берем Х51 = x^i = 1, то есть, помещаем кам ни 5 и 6 в первую группу. И с ключая эти кам ни, рассматриваем задачу меньш ей размерности. Имеем для нее такж е Y o ( 3 5 ) = 7 1 = А 3 7 . Получаем оптимальное решение: X i2 = Х 2 2 = Х 3 2 = 1 , Х 4 3 = Х т з = 1 С О З Н а Ч е Н И б М T m in = ^ 3 7 . Дадим обобщение описанного метода на случай, ко гд а T j различны. О пределим Т = m ax Т. J ■ ' и добавим к имею щ имся п камням еще m ф иктивны х камней, вес которы х равен 129 а . = 7 Т . _ ^ , i = n + l, n + m М ы получили «задачу о камнях» с дополнительными условиями п+т (3.19) i=n+-I Суть этих условий в том, что в каж ды й я щ и к м ож но поместить один и только один ф иктивны й камень. Т аким образом, для ф иктивны х камней мы имеем два ограничения (3.5) и (3.19), то есть в каж д ы й я щ и к м ож но поместить только один ф иктивны й камень и каж ды й камень моиспо поместить только в один ящ ик. Разделим ка ж д ую верш ину сетевого представления та кже на две вершины. О дной вершине поставим в соответствие часть веса yi, а второй (aj-yi). Вторая задача сводится, ка к и ранее, к одной задаче о ранце с дополнительны м и условиями (3.19). О бозначим через Q = ( Q j} множество векторов X,удовлетворяющ их (3.14) и (3.19) и упорядоченны х по убы ванию M j. Далее решение оценочной задачи происходит аналогично описанном у выше. Рассмотрим пример 3.1, полагаем, что кам ни 5 и 6 ф иктивные, то есть Т ] = 36, Т 2 = 18, Т з= 17. Выписы ваем множества Qj до тех пор, пока кажды й камень не войдет хотя бы в одно множество. Возьмем Т = 37. Имеем |
Обозначим через Yo(Z) минимальное значение Y(Z). Оценочная задача сводится к минимизации функции одного переменного Y ,(Z) + m Z -> m in . (3.3.19) Берем Тд = А / т , где А = 2 ]а ,,, и решаем задачу 2. Если Ф ,„„(ТЭ < А , I то увеличиваем То до T i так, чтобы появился хотя бы один новый вектор Qj. Если Ф „„(Т ,) < А, то продолжаем увеличение Т до тех пор, пока не получим величину Тк такую, что Ф „„ (Т,^) S А . Величина Ть является нижней оценкой для задачи 1 . Далее можно применить метод ветвей и границ на основе полученной оценки. Пример 3.3.1. Пусть m = 3 и имеется 7 камней следующего веса: 94 i 1 2 3 4 5 6 7 10 12 13 14 18 19 22 1 шаг. Имеем А = 108, То = 36. Имеется только одно решение: Q = (4,7) с величиной М = 36. 2 шаг. Увеличиваем То до Ti=37. Имеются следующие решения: Qi=(5,6), Q2={4,7), Оз=(1,2,3), Q4 = (3,7). Соответственно Mi=37, М2=36, Мз=35, М 4=35. Выпишем систему неравенств: У ,+ У *+ z ^37 у, + у , + z ^36 У1+ У 1+ У 3+ 2^:35 у ,+ y ,+ z £ 3 5 Имеем: Z ,= 3 7 ,y,= 0 ,Y „(3 7 ) = I lI , Z ,= 3 6 ,y ,= l,Y /3 6 ) = 109, Z ,= 3 5 ,y ,= 2 ,y ,= l,Y „(3 5 ) = 108. Нетрудно показать, что дальнейшее уменьшение Z не приводит к уменьшению оценки. Поэтому оптимальное = Z , = 35. Берем Xj, =х^, =1, то есть, помещаем камни 5 и 6 в первую группу. Исключая эти камни, рассматриваем задачу меньшей размерности. Имеем для нее также Yo(35)=71=A-37. Получаем оптимальное решение: X,J = Xjj = Xjj = 1, Х^, = Х„ = l ОЗНаЧеНИбМ Tmin=37. Дадим обобще1ше описанного метода на случай, когда Tj различны. Определим Т = тахТ, J ' и добавим к имеющимся п камням еще m фиктивных камней, вес которых равен а, = Т -Т .„, i = n + l,n + m Мы получили «задачу о камнях» с дополнительными условиями п+п» (3.3.20) i»+l Суть этих условий в том, что в каждый ящик можно поместить один и только один фиктивный камень. Таким образом, для фиктивных камней мы имеем два ограничения (3.3.5) и (3.3.20), то есть в каждый ящик можно поместить только один фиктивный камень и каждый камень можно поместить только в один ящик. Разделим каждую вершину сетевого представления также на две вершины. Одной вершине поставим в соответствие часть веса yj, а второй (а]-у[). Вторая задача сводится, как и ранее, к одной задаче о ранце с дополнительными условиями (3.3.20). Обозначим через Q = {Qj} множество векторов X,удовлетворяющих (3.3.5) и (3.3.20) и упорядоченных по убыванию M j. Далее решение оценочной задачи происходит аналогично описанному выше. Рассмотрим пример 3.3.1, полагаем, что камни 5 и 6 фиктивные, то есть Ti=36, Тг=18, Тз=17. Выписываем множества Q j до тех пор, пока каждый камень не войдет хотя бы в одно множество. Возьмем Т = 37. Имеем Qi=(I,3,4), Qi=(4,7), Оз=(1,2,3), Q4=(3,7), Qs=(2,7), Q6=(4,6). Q,=(4,5). Заметим, что для множества Q? имеем М?= 32. Поэтому величину Т следует взять не менее 38. Следующее множество с величиной М>37 существует при Т=40. Таких множеств два Q i=(I,2,5) и Q2=(5,7). Изменив соот95 |