|
r(Q ) > ф(тс) (рассматриваем задачу на м иним ум ), то очевидно, полученное решение оптимально. Если наилучш ая оценка tj(Q ) < ф(я:), то разность А = Ф (л) T(Q) определяет погреш ность полученного реш ения [22, 2 5 ,2 7 ,2 8 ]. Эффективность метода ветвей и границ в сущ ественной степени зависит от «качества» н и ж н и х оценок. П р и пл охих оценках это ф актически полны й перебор, при достиж им ой ниж ней оценке это получение оптимального решения за один проход по дереву ветвлений. Заметим, что ф унк1дия приоритета, основанная на степени критичности работ фронта в эвристических алгоритмах распределения ресурсов, является оценкой снизу продолжительности проекта (насколько хорош а эта оценка ~ отдельный вопрос). Дадим иллю страцию метода на примере задачи обработки деталей (Рис. 1.3). Возьмем деталь 1 с минимальным Ь;И разобьем множество всех решений на два подмножества. В первом подмножестве деталь 1 делается п о следней, а во втором не делается последней. О чевидно, что .оценка снизу продолжительности обработки для первого подмножества равна П Ti = ^ a i + m in b i = 1 3 + 7 = 2 0 i=i ‘ • a для второго 56 1 1 '^2 ~ 5^oci + m in b i =13 + 9 = 2 2 t r i»l i=I Выбираем подмножество с минимальной оценкой, то есть деталь 1 обрабатывается последней. Это подмножество разбивается на два. В первом деталь 3 (имеющая минимальн}ЧО величину bj из оставш ихся деталей) обрабатывается предпоследней, а во втором нет (то есть обрабатывается первой). О ценка первого подмножества Л = ( Q ii) = т а х (1 9 ,2 0 ) = 20 а оценка второго Л = (Q iz) = m ax (2 2 , 2 0 ) = 2 2 |
о оРис. 1.5. Метод ветвей и границ Метод ветвей и границ это метод ветвлений, в котором в качестве функций оценки подмножеств берутся оценки снизу (или сверху) целевой функции задачи на данном подмножестве решений. Основное преимущество этого метода по сравнению с методом ветвлений в том, что возможна оценка близости получаемого решения к оптимальному. Действительно, если мы получили решение я со значением целевой функции ф(я), а оценки снизу остальных подмножеств ri(Q) > ф(с) (рассматриваем задачу на минимум), то очевидно, полученное решение оптимально. Если наилзшшая оценка t](Q) < ф(я), то разность Д = ф (я)-Т1(0) определяет погрешность полученного решения [22, 25, 27,28]. Эффективность метода ветвей и границ в существенной степени зависит от «качества» нижних оценок. При плохих оценках это фактически полный перебор, при достижимой нижней оценке это получение оптимального решения за один проход по дереву ветвлений. Заметим, что функция приоритета, основанная на степени критичности работ фронта в эвристических алгоритмах распределения ресурсов, является оценкой снизу продолжительности проекта (насколько хороша 48 эта оценка —отдельный вопрос). Дадим иллюстрацию метода на примере задачи обработки деталей (Рис. 1.3). Возьмем деталь 1 с минимальным Ь, и разобьем множество всех решений на два подмножества. В первом подмножестве деталь 1 делается последней, а во втором не делается последней. Очевидно, что оценка снизу продолжительности обработки для первого подмножества равна П rj = ^ a i + minbi =13+7=20 i=l a для второго II Лг “ + minbi =13+9=22 i=i Выбираем подмножество с минимальной оценкой, то есть деталь 1 обрабатывается последней. Это подмножество разбивается на два. В первом деталь 3 (имеющая минимальную величину bj из оставшихся деталей) обрабатывается предпоследней, а во втором —нет (то есть обрабатывается первой). Оценка первого подмножества Tl = (Q ii) = max(19, 20) = 20 а оценка второго Ti = (Q,2) = max (22, 20) = 22 Выбираем первое подмножество. Соответствующая очередность обработки деталей (2,3,1) с продолжительностью обработки Т = 20. Это решение оптимально, поскольку оценка остальных подмножеств больше 20 (Рис. 1.6). На Рисунке число в скобках у дуг (например (1)) показывает, какая деталь делается, а число с чертой показывает, какая деталь не делается (последней, предпоследней и т.д.). 49 |