Решение задачи коммивояжера методом ветвей и границ

Процедура оценок.

Рассмотрим задачу коммивояжера, поставленную как задача частично целочисленного линейного программирования:

x(i,j) =1, j=1,2,...,m, (1)

x(i,j) =1, i=1,2,...,m, (2)

u(i) - u(j) + m x(i,j) m-1, i=1,2,...,m, j=1,2,...,m, i j., (3)

x(i,j) {0,1}, (4)

F(X)= r(i,j) x(i,j) min. (5)

В качестве релаксации рассмотрим задачу без условий (3). Эта задача является задачей о назначениях с аддитивным критерием. Как было показано в разделе 2.4. ограничения (4) в этой задаче могут быть заменены на условия

0 x(i,j), i=1,2,...,m, j=1,2,...,n, (6)

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

Пусть X -оптимальное решение задачи о назначениях (1), (2), (5), (6). Тогда в качестве нижней оценки может быть выбрана величина

H= F(X). (7)

Замечание.

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

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

В качестве верхней оценки может быть выбрана величина значения критерия задачи (5) на любом допустимом решении задачи коммивояжера. Приведем в качестве примера следующий приближенный, так называемый “жадный” алгоритм решения, основанный на следующей стратегии выбора маршрута движения коммивояжера: коммивояжер из очередного города переходит в город, расстояние до которого минимально из тех городов, в которых коммивояжер еще не был (включая и город, из которого начал свой путь коммивояжер). Стратегии “жадных” алгоритмов могут быть различными, и для уменьшения значения верхней оценки можно выбирать минимальное среди значений функционала задачи, найденных при различных стратегиях выбора маршрута движения коммивояжера.

Процедура ветвления.

Ветвление выбирается по всем направлениям, еще не пройденным коммивояжером.

Дата добавления: 2017-02-01; Просмотров: 65; Нарушение авторских прав?; Мы поможем в написании вашей работы!