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

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

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

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) на любом допустимом решении задачи коммивояжера. Приведем в качестве примера следующий приближенный, так называемый “жадный” алгоритм решения, основанный на следующей стратегии выбора маршрута движения коммивояжера: коммивояжер из очередного города переходит в город, расстояние до которого минимально из тех городов, в которых коммивояжер еще не был (включая и город, из которого начал свой путь коммивояжер). Стратегии “жадных” алгоритмов могут быть различными, и для уменьшения значения верхней оценки можно выбирать минимальное среди значений функционала задачи, найденных при различных стратегиях выбора маршрута движения коммивояжера.

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

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

 

Решение задачи целочисленного линейного программирования методом ветвей и границ.

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

Рассмотрим задачу целочисленного линейного программирования в общей постановке в матричной форме.

 

Ax b, (1)

0 x, (2)

 

x(i ) Z, i=1, 2,..., m, (3)

F( x )= ( c, x ) extr. (4)

 

Не уменьшая общности будем считать, что все коэффициенты задачи целочисленные.

Пусть x - оптимальное решение исходной задачи, y - m мерный вектор, оптимальное решение задачи линейного программирования (1), (2), (4), которая естественно является релаксацией для исходной целочисленной задачи линейного программирования.

Пусть рассматриваемая задача является задачей на максимум (extr = max ).

Тогда в качестве верхней оценки выбирается величина

V=F( с, y ), а точнее целая часть этой величины.

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

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

Если среди компонент вектора y нет дробных, то в этом направлении ветвление прекращается, т.к. лучшее решение в этом направлении исходной задачи определяется целочисленным вектором y. Пусть y(i) - некоторая дробная компонента. Ветвление происходит в направлении этой компоненты следующим образом. Пусть y(i) = [y(i)] + {y(i)}, где [s] - целая часть числа s, а {s} - дробная часть числа s. Тогда подзадачами, порожденными этим направлением, будут две задачи линейного программирования, к исходным ограничениям первой из которых добавляется ограничение

x(i) [y(i)],

а к исходным ограничениям второй задачи добавляется ограничение

[y(i)] + 1 x(i).

 

⇐ Предыдущая12345678Следующая ⇒

Поделиться:

Популярное:

1. I. Предмет и задачи дидактики
2. II. Предполагаемые союзники и их задачи
3. III. Целевые установки, задачи и направления обеспечения транспортной безопасности
4. А теперь мое решение проблемы
5. А теперь мое решение проблемы
6. Алгоритм решения транспортной задачи
7. Анализ подходов и методов решения задачи
8. Анализ современного состояния АПК в России: задачи и экономическая стратегия развития
9. БИЛЕТ 1. Цели, задачи и основные принципы православной педагогики. Сотериологический характер педагогических воззрений Святых Отцов Церкви
10. БИЛЕТ 9. Вопрос 2. Психолого-педагогические задачи процесса духовно-нравственного становления личности на этапе вхождения в мир (наследство, зачатие, внутриутробное развитие, роды, новорожденность).
11. Бухгалтерский учет: его задачи, функции и
12. В итоге в Иерархии принято решение, что в Иерархию