Российский экономический

Рис. 6.7.
Древовидная структура метода ветвей и границ
В качестве альтернативного можно рассмотреть подход, основанный на 
том, что в момент ветвления решаются сразу обе задачи, а далее ветвление 
производится для той подзадачи (из всего списка еще не прозондированных 
подзадач), для которой оценка значения целевой функции является максималь-
ной. Основанием для такого подхода является ожидание найти оптимальное 
решение исходной целочисленной задачи с большей вероятностью в подзада-
чах с высоким значением оценки целевой функции. По сравнению с «подходом 
обратного хода» этот подход ведет к порождению большего числа подзадач. В 
терминах древовидной интерпретации решения этот подход может приводить к 
перепрыгиванию с одной ветки решения на другую. Поэтому он условно может 
быть назван «прыгающий подход». 
В заключение хотелось бы сделать еще одно замечание весьма полезное 
при построении конкретных вычислительных алгоритмов метода. В процессе 
решения мы решаем подзадачи, которые, по сути, являются задачами линейно-
го программирования. Естественно, что в этом случае мы используем один из 
алгоритмов симплекс-метода. Однако, как нетрудно заметить, подзадача, полу-
ченная в результате ветвления, отличается от «породившей» ее задачи одним 
127

---

дополнительным ограничением. Поскольку «породившая» ее задача была уже 
решена, нецелесообразно, решая подзадачу симплекс-методом, начинать про-
цедуру решения с самого начала. Целесообразно добавить строку в последнюю 
симплекс-таблицу, полученную при решении «породившей» задачи.
Можно утверждать, что в настоящее время алгоритмы метода ветвей и 
границ являются наиболее надежным средством решения целочисленных за-
дач, встречающихся в практических исследованиях. 
Контрольные вопросы 
1. Поясните класс задач целочисленного программирования. 
2. Приведите примеры задач целочисленного программирования. 
3. Сформулируйте задачу коммивояжера.
4. Каково содержание метода отсекающих плоскостей? 
5. Каков алгоритм метода ветвей и границ? 
128

---