12. Задача коммивояжера. Метод ветвей и границ

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

Суть метода ветвей и границ – в направленном частичном переборе допустимых решений. Будем рассматривать задачу линейного программирования. Вначале она решается без ограничений на целочисленность. При этом находится верхняя граница F(x), так как целочисленное решение не может улучшить значение функции цели.

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

Ветвление производится последовательным введением дополнительных ограничений. Пусть xk – целочисленная переменная, значение которой в оптимальном решении получилось дробным. Интервал [βk] ≤ xk ≤ [βk ]+1 не содержит целочисленных компонентов решения. Поэтому допустимое целое значение xkдолжно удовлетворять одному из неравенств xk≥[βk]+1 или xk≤[βk ]. Это и есть дополнительные ограничения. Введение их в методе ветвей и границ на каждом шаге порождает две не связанные между собой подзадачи. Каждая подзадача решается как задача линейного программирования с исходной целевой функцией. После конечного числа шагов будет найдено целочисленное оптимальное решение.

Применение метода ветвей и границ рассмотрим на конкретном примере.

Пример 1. Методом ветвей и границ найти максимальное значение функции F(x) = 2x1 + 3x2 при ограничениях

3x1+4x2≤24

2x1+5x2≤22

x1,2≥0 - целые

1-й шаг метода ветвей и границ. Решается задача линейного программирования с отброшенными условиями целочисленности с помощью симплекс-метода (табл. 1 – 3).

По данным табл. 3 запишем оптимальное нецелое решение

Таблица 1 - симплекс-таблица для задачи ЛП

Таблица 2 - симплекс-таблица для задачи ЛП

Таблица 3 - симплекс-таблица для задачи ЛП

Графическая интерпретация задачи приведена на рис. 1. Здесь ОДЗП представлена четырехугольником ABCD, а координаты вершины С совпадают с x*1 и x*2 . Обе переменные в оптимальном решении являются нецелыми, поэтому любая из них может быть выбрана в качестве переменной, инициирующей процесс ветвления.

Пусть это будет x2 . Выбор x2 порождает две подзадачи (2 и 3), одна из них получается путем добавления ограничения x2≥3 к исходной задаче, а другая – путем добавления ограничения x2≤2. При этом ОДЗП разбивается на две заштрихованные области (рис. 1), а полоса значений 2 < x2 < 3 исключается из рассмотрения. Однако множество допустимых целочисленных решений сохраняется, порожденные подзадачи содержат все целочисленные решения исходной задачи.

Рисунок 1 - графическая интерпритация решения примера методом ветвей и границ

2-й шаг метода ветвей и границ. Осуществляется выбор одной из обозначенных ранее подзадач. Не существует точных методов определения, какой из подзадач отдать предпочтение. Случайный выбор приводит к разным последовательностям подзадач и, следовательно, к различным количествам итераций, обеспечивающих получение оптимального решения.

Пусть вначале решается подзадача 3 с дополнительным ограничением x2≤2 или x2+ x5 = 2 . Из табл. 3 для переменной x2 справедливо следующее выражение -2/7x3+3/7x4+x2=18/7 или x2=18/7+2/7x3-3/7x4, тогда 2/7x3-3/7x4+x5=-4/7 . Включаем ограничение в табл. 3, при этом получим новую таблицу (табл. 4).

Осуществляя оптимизацию решения, переходим к табл. 5, которой соответствует решение

Переменная x1 нецелая, поэтому ветвление необходимо продолжить; при этом возникают подзадачи 4 и 5 с ограничениями x1≤5 и x1 ≥6 соответственно. Полоса значений 5 < x1 < 6 исключается из рассмотрения.

Таблица 4 - симплекс-таблица для задачи ЛП

Таблица 5 - симплекс-таблица для задачи ЛП

3-й шаг метода ветвей и границ. Решаются подзадачи 4 и 5. Из рис. 1 видно, что оптимальное целочисленное решение подзадачи 4 достигается в вершине К с координатами x*1=5, x*2=2, однако это не означает, что найден оптимум исходной задачи. Причиной такого вывода являются еще не решенные подзадачи 3 и 5, которые также могут дать целочисленные решения. Найденное целочисленное решение F = 16 определяет нижнюю границу значений целевой функции, т.е. меньше этого значения оно быть не должно.

Подзадача 5 предполагает введение дополнительного ограничения x1≥6 в подзадачу 3 . Графическое решение на рис. 1 определяет вершину L с координатами x*1=6, x*2=3/2 , в которой достигается оптимальное решение подзадачи 5: Fmax = 16.5 . Дальнейшее ветвление в этом направлении осуществлять нецелесообразно, так как большего, чем 16, целого значения функции цели получить невозможно. Ветвление подзадачи 5 в лучшем случае приведёт к другому целочисленному решению, в котором F = 16.

4-й шаг метода ветвей и границ. Исследуется подзадача 2 с ограничением x2≥3, находится её оптимальное решение, которое соответствует вершине М (рис. 1) с координатами x*1=3.5, x*2=3. Значение функции цели при этом Fmax =16, которое не превышает найденного ранее решения. Таким образом, поиск вдоль ветви x2≥3 следует прекратить.

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

Для решения задач линейного программирования имеется широкий набор разнообразных машинных программ, которые избавляют от трудоёмкого процесса вычислений вручную. Однако интерпретация информации, выведенной на печать, невозможна без чёткого представления о том, почему и как работает симплекс-метод.