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

В задаче коммивояжера для формирования оптимального маршрута объезда n городов необходимо выбрать один лучший из (n-1)! вариантов по критерию времени, стоимости или длине маршрута. Эта задача связана с определением гамильтонова цикла минимальной длины. В таких случаях множество всех возможных решений следует представить в виде дерева - связного графа, не содержащего циклов и петель. Корень дерева объединяет все множество вариантов, а вершины дерева — это подмножества частично упорядоченных вариантов решений.
Вершина (i, j) соответствует подмножеству всех маршрутов, содержащих ребро (i,j), а вершина (i*,j*) — подмножеству всех маршрутов, где это ребро отсутствует.
Процесс разбиения на эти подмножества можно рассматривать как ветвление дерева. Поэтому метод называется методом поиска по дереву решений, или методом ветвей и границ.
Метод ветвей и границ представляет собой алгоритм направленного перебора множества вариантов решения задачи. Сущность метода ветвей и границ состоит в том, что от корня дерева ветвятся не все вершины.

Метод ветвей и границ решения целочисленных задач линейного программирования (ЦЗЛП)

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

В случае когда целочисленные переменные являются булевыми, применяются комбинированные методы. Булевы свойства переменных существенно упрощают поиск решения.

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

Согласно общей идее метода, сначала решается задача с ослабленными ограничениями (задача линейного программирования). Пусть хr — целочисленная переменная, значение xr* которой в оптимальном решении ослабленной задачи является дробным. Интервал [xr*] < xr < [xr*] +1 не содержит допустимых целочисленных компонент решения. Поэтому допустимое целое значение хr должно удовлетворять одному из неравенств xr ≤[ xr* ] или хr ≥[ xr* ] +1.
Введение этих условий в задачу с ослабленными ограничениями порождает две не связанные между собой задачи. В таком случае говорят, что исходная задача разветвляется (или разбивается) на две подзадачи. Осуществляемый в процессе ветвления учет необходимых условий целочисленности позволяет исключить части многогранника допустимых решений, не содержащие точек с целыми координатами.

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

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

Рассмотрим задачу целочисленного линейного программирования (ЗЦЛП) :
Найти вектор , максимизирующий линейную форму (3.1)
и удовлетворяющий условиям:

x1, x2,…,xp –целые (p≤n) (3.4)
Пусть, для каждой целочисленной переменной можно указать верхнюю и нижнюю границы, в пределах которых безусловно содержатся ее оптимальные значения, то есть
Vj ≤xj≤ Wj, (3.5)
При этом в систему функциональных ограничений необходимо включить р неравенств (3.5).

В начале любой S-й итерации метода ветвей и границ необходимо иметь:
1. Основной список задач линейного программирования, каждая из которых должна быть решена в последующих итерациях (на первой итерации список содержит одну ЗЛП- задачу 1 (3.1- 3.3) и (3.5).
2. Нижнюю границу оптимального значения линейной формы задачи (3.1) - (3.3), (3.5) Z0(s). На первой итерации в качестве Z0(1) можно взять значение функции f(x) в любой целочисленной точке x, лежащей внутри области(3.2) - (3.5). Если такую точку указать трудно, то можно положить Z0(1) = - ∞, но это приводит к значительному увеличению числа итераций.

загрузка...