|
близости получаемого решения к оптимальному. Действительно, если мы получили решение л со значением целевой функции ф(л), а оценки снизу остальных подмножеств ц(0)> ф(л) (рассматриваем задачу на минимум), то очевидно, полученное решение оптимально. Если наилучшая оценка Г(0) < ф(л), то разность А = ф (л) г(<3) определяет погрешность полученного решения [22, 25, 27, 28]. Эффективность метода ветвей и границ в существенной степени зависит от «качества» нижних оценок. При плохих оценках это фактически полный перебор, при достижимой нижней оценке это получение оптимального решения за один проход по дереву ветвлений. Заметим, что функция приоритета, основанная на степени критичности работ фронта в эвристических алгоритмах распределения ресурсов, является оценкой снизу продолжительности проекта (насколько хороша эта оценка отдельный вопрос). Дадим иллюстрацию метода на примере задачи обработки деталей (рис. 1.4.3). Возьмем деталь 1с минимальным Ъ\ и разобьем множество всех решений на два подмножества. В первом подмножестве деталь 1 делается последней, а во втором не делается последней. Очевидно, что оценка снизу продолжительности обработки для первого подмножества равп п на Л = -ьттЬ ;=13+7=20, а для второго г)2= + штЬ, =13+9=22. ¡=1 * 1=1 ы Выбираем подмножество с минимальной оценкой, то есть деталь 1обрабатывается последней. Это подмножество разбивается на два. В первом деталь 3 (имеющая минимальную величину Ь,из оставшихся деталей) обрабатывается предпоследней, а во втором нет (то есть обрабатывается первой). Оценка первого подмножества Л“ (Он) = тах (19, 20) = 20 а оценка второго Л= (012) = гпах(22, 20) = 22 Выбираем первое подмножество. 38 |
качественно характеризующую вероятность того, что в данном подмножестве найдется оптимальное или хотя бы «достаточно хорошее» решение, то мы получаем алгоритм поиска решения, двигаясь по ветви дерева, имеющей максимальное значение функции оценки (или минимальное, если вероятность наличия достаточно хорошего решения тем больше чем меньше значение функции оценки). В задачах календарного планирования метод ветвлений реализуется в так называемых эвристических алгоритмах распределения ресурсов [7, 10, 19, 26,27]. © © © О О © Рис. 1.5. 3. Метод ветвей и границ Метод ветвей и границ это метод ветвлений, в котором в качестве функций оценки подмножеств берутся оценки снизу (или сверху) целевой функции задачи на данном подмножестве решений. Основное преимущество этого метода по сравнению с методом ветвлений в том, что возможна оценка близости получаемого решения к оптимальному. Действительно, если мы получили решение 7Гсо значением целевой функции ф(1г), а оценки снизу остальных подмножеств tj(Q) ^ф(т) (рассматриваем задачу на минимум), то очевидно, полученное решение оптимально. Если наилучшая оценка r(Q) < ф (тг), то разность Д = Ф (тг) n(Q) определяет погрешность полученного решения [22, 25, 27, 28]. Эффективность метода ветвей и границ в существенной степени зависит от «качества» нижних оценок. При плохих оценках это фактически полный перебор, при достижимой нижней оценке это получение оптимального решения за один проход по дереву ветвлений. 82 Заметим, что функция приоритета, основанная на степени критичности работ фронта в эвристических алгоритмах распределения ресурсов, является оценкой снизу продолжительности проекта (насколько хороша эта оценка —отдельный вопрос). Дадим иллюстрацию метода на примере задачи обработки деталей (Рис. 1.3). Возьмем деталь 1 с минимальным bj и разобьем множество всех ^ решений на два подмножества. В первом подмножестве деталь 1 делается последней, а во втором не делается последней. Очевидно, что оценка снизу продолжительности обработки для первого подмножества равна П Til ~ ^ c ti + minbi =13+7=20 i=i 1 а для второго П Ц2 ~ S a ' + minbi =13+9=22 w w Выбираем подмножество с минимальной оценкой, то есть деталь 1 обрабатывается последней. Это подмножество разбивается на два. В первом деталь 3 (имеющая минимальную величину bi из оставшихся деталей) обрабатывается предпоследней, а во втором нет (то есть обрабатывается первой). Оценка пер•' вого подмножества V = (Q n) = max (19, 20) = 20 а оценка второго V = (Q12) = max (22,20) = 22 Выбираем первое подмножество. Соответствующая очередность обработки деталей (2,3,1) с продолжительностью обработки Т = 20. Это решение оптимально, поскольку оценка остальных подмножеств больше 20 (Рис. 1.6). На Рисунке число в скобках у дуг (например (1)) показывает, какая деталь делается, а число с чертой показывает, какая деталь не делается (последней, предпоследней и т.д.). Рис. 1.6. 83 |