|
Обозначим через Y q(Z ) минимальное значение Y (Z ). О ценочная задача сводится к минимизации ф ункции одного переменного Yo(Z) + m Z —> m in. (3.18) Берем То = A /m , где А = , и решаем задачу 2. Е сли Фтах(То) < А , то I увеличиваем То до Т ] так, чтобы появился хотя бы один новы й вектор Qj. Если ФтахСТ’1) < А , то продолжаем уве)гичение Т до тех пор, пока не получим величину Тк та кую , что Фтах(Тк) ^ А . В еличина Тк является ниж ней оценкой для задачи 1. Далее м ож но применить метод ветвей и границ на основе полученной оценки. П р и м е р 3 .1 . П усть m = 3 и имеется 7 камней, и х веса приведены в табл. 3.1. Таблица 3.1. И сходны е данные к примеру 3.1 128 i 1 2 3 4 5 6 7 ai 1 0 1 2 13 14 18 19 2 2 1 ш аг. Имеем А = 108, То = 33. Имеется только одно решение: Q = (4, 7) с величиной М = 33. 2 ш аг. Увеличиваем То до Т = 3 7 . И мею тся следзчощие решения: Q i = (5,6), Q2 ^ ( 4 , 7 ), О з = ( 1 , 2 , 3 ) , Q 4 = (3,7). Соответственно M i = 37, М г = 36, М з = 35, М 4 = 35. В ы пиш ем систему неравенств; У 5 + У б + . z > 3 7 У4 + у , + z > 3 6 У , + У 2 + У з + z > 3 5 У з + у , + z > 3 5 Имеем; Z , = 3 7 , у^ = 0 , Y „ ( 3 7 ) = 111, Z, = 3 6 , у , =1, Y , (36) = 109, Z , = 3 5 , Уз = 2 , у , = 1 , ¥ Д 3 5 ) = 108. |
Обозначим через 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 в первую группу. Исключая эти камни, рассматриваем задачу меньшей размерности. Имеем |