Проверяемый текст
Михин, Петр Валентинович; Модели и методы оптимизации планов проектных работ (Диссертация 2005)
[стр. 129]

Нетрудно показать, что дальнейшее уменьш ение 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.
Имеем
[стр. 94]

Обозначим через 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 в первую группу.
Исключая эти камни, рассматриваем задачу меньшей размерности.
Имеем


[стр.,95]

для нее также 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

[Back]