Лекции по "Развитию операционных систем"

На основе этой идеи американский математик Р.Гомори предложил ряд сходящих-ся алгоритмов решения задач дискретного линейного программирования. Ему удалось обосновать правила построения дополнительных ограничений и доказать конечность алгоритмов.

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

 

 

18.3.  Метод ветвей и границ.

 

Метод ветвей и границ относится к группе комбинаторных методов. Комби-наторные методы, исходя из конечности числа допустимых планов задачи, заменяют полный перебор всех планов их частичным направленных перебором. Комбинаторные методы в значительно меньшей степени подвержены в процессе вычислений влиянию ошибок округления, поэтому являются более предпочтительными по сравнению с мето-дами отсечения. Метод ветвей и границ – один из наиболее эффективных методов реше-ния задач комбинаторного типа.

Перейдем к изложению идеи метода ветвей и границ. Для этого рассмотрим общую задачу дискретного программирования

,

,

где W – конечное множество допустимых планов.

1.  Находим верхнюю границу (оценку) функции , т.е. такое число , что для любых

.

Если при этом удается найти такой план задачи, для которого выполняется равенство

,

то – оптимальный план задачи.

2.  Если оптимальный  план не найден, то некоторым способом разбиваем мно-жество W на конечное число непересекающихся подмножеств :

и находим для каждого из этих подмножеств верхнюю границу . Если при этом удается найти такой план , что выполняется соотношение

,

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

,

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