|
|
|
|
|
Основы теории принятия решениий Учебное пособие. Москва, 2002. 8. О решении задач целочисленного программирования Методы направленного перебора. Из них наиболее известен метод ветвей и границ. Суть метода такова. Каждому подмножеству Х множества возможных решений Х0 ставится в соответствие число - "граница" А(Х). При решении задачи минимизации необходимо, чтобы А(Х1) ≥ А(Х2), если Х1 входит в Х2 или совпадает с Х2 . Каждый шаг метода ветвей и границ состоит в делении выбранного на предыдущем шаге множества ХС на два - Х1С и Х2С . При этом пересечение Х1С и Х2С пусто, а их объединение совпадает с ХС . Затем вычисляют границы А(Х1С ) и А(Х2С) и выделяют "ветвь" ХС +1 - то из множеств Х1С и Х2С , для которого граница меньше. Алгоритм прекращает работу, когда диаметр вновь выделенной ветви оказывается меньше заранее заданного малого числа Для каждой конкретной задачи целочисленного программирования (другими словами, дискретной оптимизации) метод ветвей и границ реализуется по-своему. Есть много модификаций этого метода.
|
||