А.И. Орлов       
Основы теории принятия решениий       
Учебное пособие. Москва, 2002.

8. О решении задач целочисленного программирования
    

Методы направленного перебора. Из них наиболее известен метод ветвей и границ. Суть метода такова. Каждому подмножеству Х множества возможных решений Х0 ставится в соответствие число - "граница" А(Х). При решении задачи минимизации необходимо, чтобы А(Х1) ≥ А(Х2), если Х1 входит в Х2 или совпадает с Х2 .

Каждый шаг метода ветвей и границ состоит в делении выбранного на предыдущем шаге множества ХС на два - Х и Х. При этом пересечение Х и Хпусто, а их объединение совпадает с ХС . Затем вычисляют границы А(Х) и А(Х) и выделяют "ветвь" ХС +1 - то из множеств Х и Х, для которого граница меньше. Алгоритм прекращает работу, когда диаметр вновь выделенной ветви оказывается меньше заранее заданного малого числа

Для каждой конкретной задачи целочисленного программирования (другими словами, дискретной оптимизации) метод ветвей и границ реализуется по-своему. Есть много модификаций этого метода. 

Предыдущая страница | Оглавление | Следующая страница