Билет № 12. Метод ветвей и границ для решения проблемы RCPSP (Precedence Tree)

RCPSP – проблема расчета расписания проекта в условиях ограниченных возобновляемых ресурсов

Метод ветвей и границ — общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. По существу, метод является комбинаторным (представляет собой алгоритм перебора) с отсевом подмножеств множества допустимых решений, не содержащих оптимальных решений. Метод был впервые предложен Ленд и Дойг в 1960 г. для решения задач целочисленного линейного программирования.

Общая идея метода может быть описана на примере поиска минимума и максимума функции f(x) на множестве допустимых значений x. Функция f и x могут быть произвольной природы. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ).

Процедура нахождения оценок заключается в поиске верхних и нижних границ для оптимального значения на подобласти допустимых решений (то есть нахождения времени начала каждой работы и общей продолжительности проекта).

Интерес к этому методу и фактически его “второе рождение” связано с работой Литтла, Мурти, Суини и Кэрела, посвященной задаче коммивояжера.

Задача коммивояжёра заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов. Наряду с применением метода ветвей и границ к решению данной задачи можно также применить метод генетических алгоритмов, а также алгоритм муравьиной колонии. Все эффективные (сокращающие полный перебор) методы решения задачи коммивояжёра — методы эвристические.

Начиная с этого момента, появилось большое число работ, посвященных методу ветвей и границ и различным его модификациям. Столь большой успех объясняется тем, что авторы первыми обратили внимание на широту возможностей метода, отметили важность использования специфики задачи и сами воспользовались спецификой задачи коммивояжера. В основе метода ветвей и границ лежит идея последовательного разбиения множества допустимых решений на подмножества (стратегия “разделяй и властвуй”). На каждом шаге метода элементы разбиения подвергаются проверке для выяснения, содержит данное подмножество оптимальное решение или нет. Проверка осуществляется посредством вычисления оценки снизу для целевой функции на данном подмножестве. Если оценка снизу не меньше рекорда — наилучшего из найденных решений, то подмножество может быть отброшено. Проверяемое подмножество может быть отброшено еще и в том случае, когда в нем удается найти наилучшее решение. Если значение целевой функции на найденном решении меньше рекорда, то происходит смена рекорда. По окончанию работы алгоритма рекорд является результатом его работы. Если удается отбросить все элементы разбиения, то рекорд — оптимальное решение задачи. В противном случае, из неотброшенных подмножеств выбирается наиболее перспективное (например, с наименьшим значением нижней оценки), и оно подвергается разбиению. Новые подмножества вновь подвергаются проверке и т.д.

3 правила применения метода:

1. Выстраиваем расписание по возрастанию порядкового номера

2. Каждая последующая работа должна выполняться не раньше предыдущей

3. Если получаем число большее уже найденного раннее, то вычеркиваем эту ветку

Эвристическая схема метода ветвей и границ

Процедура ветвления рассматривает все допустимые варианты построения перестановок.

Процедура отсева предполагает, что если значение верхней (достижимой) оценки в одной из вершин дерева ветвлений не больше значения нижней оценки в другой вершине, то вторая вершина исключается из рассмотрения (3 правило).

Процедура останова определяет окончание процесса вычислений. Если осталась неотброшенной лишь одна вершина, в которой значения оценок совпадают, то найдено оптимальное решение задачи, которое определяется перестановкой, соответствующей верхней оценке.

Пример:

Множество путей решений, которые не имеют конфликтов ресурсов и отношений предшествований – конечное.

Сам пример смотрим в файле Excel <Пример 12>.

Применение на практике: задача коммивояжера и задача о ранце. Формулировка задачи о коммивояжере приведена выше.

Задача о ранце. Название это получила от максимизационной задачи укладки как можно большего числа нужных вещей в рюкзак при условии, что общий объём (или вес) всех предметов ограничен. Подобные задачи часто возникают в экономике, прикладной математике, криптографии. В общем виде, задачу можно сформулировать так: из неограниченного множества предметов со свойствами „стоимость“ и „вес“, требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при одновременном соблюдении ограничения на суммарный вес. Существует 2 разновидности задачи о ранце: 1. Каждый предмет из множества можно выбирать бесконечное кол-во раз. 2. Каждый предмет можно использовать только один раз.

Пример применения метода ветвей и границ на практике можно посмотреть в учебнике Разу (стр. 365-369. Глава «дерево решений») – лежит на ящике. (отправила на почту)

Правила приоритета при построении расписания проекта:

Существует как прямой проход (FW) расписания проект, так и обратный (BW)

1. Правила, основанные на внутренней информации о работах (по самому короткому времени выполнения работы, по саму длинному, рандом)

2. Правила, основанные на информации о сети (наибольшее число последователей)

3. Правила, основанные на информации СРМ (ранние и поздние сроки финиша и страта, полный, свободный и независимый резервы)

4. Правила, основанные на ресурсах (по наибольшему/ наименьшему количеству задействованных ресурсов; по суммарной стоимости работы

5. Гибридные правила (смешение правил)

Все эти правила статистически плохи, т.е. для каждого проекта будет подходить то или иное правило только.