5.15. Как строить дерево ветвлений и вычислять нижние границы целевой функции для задачи о рюкзаке?

Обозначим через оптимальное решение вспомогательной ЗР при условии

,

Каждый допустимый вариант решения ЗР определяется бинарным вектором .

Легко видеть, что для любого вектора , т.е. значение является верхней границей для целевой функции.

Дерево ветвлений строится следующим простейшим способом. Множество всех возможных разбивается на два подмножества: первое с , второе с . На втором уровне любое из двух подмножеств можно разбить на два в зависимости от того, или и так далее. Таким образом после какого-то -го разбиения в каждом векторе допустимых решений, обозначенном через , будут определены первые элементов. Естественно, каждое “уточнение” допустимого множества решений за счет добавления элемента требует проверки условия и в случае его нарушения вычеркивания как недопустимого соответствующего подмножества из дерева. Допустимость же этого подмножества приводит к необходимости решения ЗР с меньшим числом переменных и уменьшенным “объемом” рюкзака. Обозначим для

, .

Уточненная вспомогательная ЗР в таком случае имеет вид.

Найти такие, что ,

и при этом

достигает максимума.

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

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

5.16. Как строить дерево ветвлений и вычислять нижние границы целевой функции для задачи коммивояжера?

Далее будем работать с матрицей расстояний, причем несуществующие или запрещенные переходы между городами будем обозначать символом . Вначале все .

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

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

Число называется коэффициентом приведения.

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