КАТЕГОРИИ:
Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)
Применение метода ветвей и границ для решения задачи коммивояжера
|
|
|
|
Задача коммивояжера
Имеется n городов, пронумерованных числами 1, 2,..., n. Для любой пары городов (i, j) задано расстояние (время, путевые расходы) C(i,j) ³ 0 между ними. Поэтому в общем случае C(i, j) ¹ C(j, i). Коммивояжер, выезжая из какого-либо города, должен посетить все города по одному разу и вернуться в исходный город. Необходимо определить такую последовательность объезда городов, при которой длина маршрута была бы минимальной.
Другая интерпретация этой задачи связана с минимизацией времени переналадок при обработке на одном станке партии из n различных деталей. Здесь C(i, j) – время переналадки при переходе от обработки детали i к обработке детали j. Требуется найти последовательность обработки деталей, минимизирующую общее время переналадок.
Для записи постановки задачи в терминах целочисленного линейного программирования определим переменные следующим образом: 
= 1, если коммивояжер переезжает из i -го города в j -й; 
– в противном случае. Тогда задача заключается в отыскании значений переменных 
, удовлетворяющих следующим соотношениям:
(5.1)
при условиях
(въезд в город j); (5.2)
(выезд из города i); (5.3)
(i ¹ j); (5.4)
xij = {0,1}, 
, целые, i = 1,..., m, j = 1,..., n. (5.5)
Ограничения (5.4) требуют, чтобы маршрут образовывал контур.
Допустимый маршрут х представим как множество упорядоченных пар городов:
х = 
.
Каждый допустимый маршрут представляет собой цикл, проходя по которому коммивояжер посещает каждый город ровно один раз и возвращается в исходный город. Каждая упорядоченная пара (i, j) является дугой маршрута. Длина F (х) маршрута х равна сумме соответствующих элементов C (i, j). Заметим, что множество всех допустимых маршрутов X содержит (n-1)! элементов.
Обозначим через 
матрицу расстояний. Чтобы запретить переезды вида (i,i), положим C (i, i) = +∞ (i = 1,…, n).
Пусть 
.
Тогда 
– редуцированная матрица.
Пусть d (X) = 
– сумма констант редуцирования.
Тогда для любого маршрута 
F (х) = 
=
= 
+ d (X) ≥ d (X) (5.6)
Неравенство (5.6) показывает, что d (X) является оценкой снизу для множества Х. Кроме того, после редукции длины всех маршрутов уменьшаются на одну и ту же величину d (X) и, следовательно, оптимальный маршрут, найденный с использованием редуцированной матрицы, оптимален и для исходной задачи.
Ветвление
Процесс ветвления можно представить в виде дерева, каждая вершина которого соответствует некоторому множеству маршрутов, являющемуся подмножеством множества Х. При этом начальная вершина соответствует множеству всех маршрутов Х (рис. 5.6). 
Рис. 5.6. Ветвление
На каждом шаге из числа кандидатов на ветвление выбирается множество Х 1 с наименьшей оценкой. Оно разветвляется на два подмножества 
и 
. Подмножество состоит из всех маршрутов множества Х 1, содержащих некоторую выбранную на данном шаге дугу (r, s), подмножество – из всех маршрутов множества Х 1, не содержащих дуги (r,s).
Ребро дерева, соединяющее вершины Х 1 и , помечается (r, s), а ребро дерева, соединяющее Х 1 и , помечается 
.
Пусть 
– редуцированная матрица, соответствующая вершине Х 1. Опишем способ выбора дуги (r, s). Он основан на стремлении сделать оценку 
поменьше, а оценку 
– больше, для того чтобы увеличить вероятность выбора для дальнейшего ветвления множества . Стремление к уменьшению приводит к выбору такой дуги (m,n), для которой
(m,n) = 0, (5.7)
поскольку все маршруты множества содержат дугу (m,n). Стремление же увеличить приводит к выбору среди дуг, удовлетворяющих условию (5.7), той дуги, для которой значение функции
максимально, т.е.
Смысл введения функции 
состоит в том, что величина 
является оценкой снизу для длины любого маршрута из Х 1, не содержащего дуги (m,n), так как величина выражает дополнительное расстояние, которое коммивояжер проезжает в случае, когда в маршрут не включена дуга (m,n).
Построение редуцированных матриц 
и 
и вычисление оценок снизу
Положим:
Искомая редуцированная матрица получается из 
с помощью описанной выше процедуры редуцирования. Сумма констант редуцирования равна при этом 
, а величина
= d (Х 1) +
является оценкой снизу для целевой функции F (x) на множестве .
Рассмотрим теперь множество . Все маршруты из этого множества содержат дугу (r,s). Найдем максимальный связанный путь, который принадлежит всем маршрутам множества Х 1 и содержит дугу (r,s). Пусть этот путь начинается в городе m и заканчивается в городе t (может быть, m = r или t = s, или то и другое одновременно). Чтобы запретить подцикл, начинающийся и заканчивающийся в m, положим 
(t,m) = +∞. Остальные элементы матрицы полагаем равными соответствующим элементам матрицы , при этом строку, соответствующую городу r, и столбец, соответствующий городу s, в матрицу не включаем, поскольку все маршруты из содержат дуги (r,s).
Редуцированная матрица расстояний для вершины получается из матрицы с помощью операции редуцирования. При этом оценка снизу для функции F (x) на множестве вычисляется по формуле
= d (Х 1) + t,
где t – сумма констант редуцирования.
Формирование списка кандидатов на ветвление
После вычисления каждой из оценок 
(i = 1,2) следует проверить, не состоит ли множество 
из единственного маршрута. Если в каждой строке и в каждом столбце матрицы 
оказалось лишь по одному элементу, отличному от +¥, то множество содержит единственный маршрут, длина которого равна . В этом случае верхняя граница (наименьшее из уже вычисленных значений F (x)) полагается равной минимуму из предыдущего значения Z 0 и , т.е.
Z 0 = min { Z 0, }.
Если содержит более одного маршрута и меньше текущего значения Z 0, то множество включается в число кандидатов на ветвление. Остановка производится, если наименьшая из оценок снизу кандидатов на ветвление не меньше текущего значения Z 0.
Пример 5.2. Решить методом ветвей и границ задачу коммивояжера с матрицей
Возьмем в качестве произвольного допустимого маршрута:
x 0 = {(1,2), (2,3), (3,4), (4,5), (5,1)}.
Тогда F(x 0) = 10 + 10 + 20 + 15 + 10 = 65 – текущее значение Z 0 – (верхняя граница длин всех маршрутов).
Получим редуцированную матрицу 
.
0 0 9 12 0
Нижняя граница d (x) = 10 + 1 + 8 + 10 + 8 + 9 + 12 = 58. Данное значение является нижней границей длин всех маршрутов. Заметим, что в идеальном случае поиск решения заключался бы в выборе ровно одного нулевого элемента в каждой строке и каждом столбце. Другими словами, если бы такой маршрут нулевой длины мог быть найден, то длина оптимального маршрута равнялась бы 58. Исходя из верхней и нижней границ, можно заключить, что 58 ≤ F (x *) ≤ 65.
Выберем дугу (r,s) с помощью вычисления значений функции Q(m,n).
Q(1,2) = 0, Q(2,1) = 0, Q(3,1) = 0, Q(4,2) = 4, Q(1,5) = 1, Q(2,3) = 5, Q(3,4) = 2, Q(5,2) = 2.
Следовательно, Q(r,s) = Q(2,3). Осуществим разбиение (ветвление). Правое подмножество X 2 будет содержать все маршруты, которые исключают дугу (2,3). Поэтому C 2 (2,3) = +∞.
~ 
~ 
= 
Оценка снизу для правого подмножества X 2 определяется следующим образом:
d (X 2) = d (X) + Θ(2,3) = 58 + 5 = 63 < Z 0.
Левое подмножество X 1 будет содержать маршруты, которые всегда включают дугу (2,3), и поэтому вторая строка и третий столбец в матрицу C 1 не включаются. В результате будем иметь матрицу на единицу меньшего размера. Далее необходимо положить C 1 (3,2) = +∞, чтобы запретить подцикл {(2,3),(3,2)}. В результате получим матрицу
C 1 = 
= 
.
Оценка снизу для левого подмножества:
d (X 1) = d (X) + t = 58 + 0 = 58 < Z 0,
где t – константа приведения матрицы С1
В списке кандидатов на ветвление множества X 1 и X 2. Так как d (X 1) < d (X 2), будем производить ветвление множества X 1. Выберем дугу (r,s) с помощью значений функции Q(m,n) для матрицы.
Q(1,2) = 0, Q(1,5) = 2, Q(3,1) = 2, Q(3,4) = 3, Q(4,2) = 4, Q(5,2) = 2.
Следовательно, Q(r,s) = 4, (r,s) = (4,2).
Правая подматрица:
C 4 = 
~ 
= 
.
Оценка снизу для правого подмножества:
d (X 4) = d (X 1) + Θ(4,2) = 58 + 4 = 62 < Z 0.
Левая подматрица. Левое подмножество X 3 будет содержать маршруты, которые всегда включают дугу (4,2), и поэтому четвертая строка и второй столбец в матрицу C 3 не включаются. В результате будем иметь матрицу на единицу меньшего размера. Далее необходимо положить C 3 (3,4) = +∞, чтобы запретить подцикл {(4,2),(2,3),(3,4)}. В результате получим матрицу
C 3 = 
~ 
~ 
= 
.
d (X 3) = d (X 1) + t = 58 + 5 = 63 < Z 0.
В списке кандидатов на ветвление множества X 3, X 4, X 2.
Минимальная нижняя оценка оказалась у множества X 4, следовательно, для дальнейшего разбиения выбираем множество X 4.
Определим дугу (r,s) с помощью значений функции Q(m,n) для матрицы .
Q(1,2) = 0, Q(1,5) = 1, Q(3,1) = 0, Q(3,4) = 3, Q(4,1) = 1, Q(5,2) = 2.
Следовательно, Q(r,s) = 3, (r,s) = (3,4).
Правая подматрица:
C 6 = 
~ 
= 
.
Оценка снизу для правого подмножества:
d (X 6) = d (X 4) + Θ(3,4) = 62 + 3 = 65 = Z 0.
Следовательно, множество X 6 исключаем из списка.
Левая подматрица. Левое подмножество X 5 будет содержать маршруты, которые всегда включают дугу (3,4), и поэтому третья строка и четвертый столбец в матрицу C 5 не включаются. В результате будем иметь матрицу на единицу меньшего размера. Далее необходимо положить C 5 (4,2) = +∞, чтобы запретить подцикл {(2,3), (3,4), (4,2)}, однако это условие оказалось уже выполненным. В результате получим матрицу
C 5 = 
= 
.
Оценка снизу для левого подмножества:
d (X 5) = d (X 4) + t = 62 + 0 = 62 < Z 0.
В списке кандидатов на ветвление множества X 3, X 5, X 2.
Минимальная нижняя оценка оказалась у множества X 5, следовательно, для дальнейшего разбиения выбираем множество X 5. Определим дугу (r,s) с помощью значений функции Q(m,n) для матрицы .
Q(1,2) = 0, Q(1,5) = 1, Q(4,1) = 3, Q(5,2) = 2.
Следовательно, Q(r,s) = 3, (r,s) = (4,1).
Правая подматрица:
C 8 = 
~ 
~ 
= 
.
Оценка снизу для правого подмножества:
d (X 8) = d (X 5) + Θ(4,1) = 62 + 3 = 65 = Z 0.
Следовательно, множество X 8 исключаем из списка.
Левая подматрица. Левое подмножество X 7 будет содержать маршруты, которые всегда включают дугу (4,1), и поэтому четвертая строка и первый столбец в матрицу C 7 не включаются. В результате будем иметь матрицу на единицу меньшего размера. Далее необходимо положить C 7 (1,2) = +∞, чтобы запретить подцикл {(2,3), (3,4), (4,1), (1,2)}.
C 7 = 
= 
.
Оценка снизу для левого подмножества:
d (X 7) = d (X 5) + t = 62 + 0 = 62 < Z 0.
В списке кандидатов на ветвление множества X 3, X 7, X 2. Множество X 7 содержит единственный маршрут с минимальной нижней оценкой, поэтому задача решена.
X 1 = 
= X *;
Z 0= F (x *) = 10 + 8 + 10 + 20 + 14 = 62.
Представим процесс решения в виде дерева (см. рис. 5.7).
Рис. 5.7.
Контрольные вопросы
1. Запишите задачу целочисленного линейного программирования.
2. Сформулируйте алгоритм метода ветвей и границ.
3. Перечислите область применения ЗЦЛП.
4. С какими трудностями приходится сталкиваться при алгоритмизации методов решения ЗЦЛП?
5. Приведите классификацию методов решения ЗЦЛП.
6. Какая задача называется задачей с ослабленными ограничениями?
7. Сформулируйте принцип ветвления в методе ветвей и границ.
8. Какую задачу решает понятие границы в методе ветвей и границ?
9. Сформулируйте постановку задачи коммивояжера.
10. Сформулируйте алгоритм метода ветвей и границ для решения задачи коммивояжера.
Задание №14
Решите ЗЦЛП методом ветвей и границ.
1. max(3 x1 + 4 x2) 2. max(3 x1 + 4 x2)
4 x1 + 5 x2 £ 20 x1 + 7 x2 £ 21
x1 + 6 x2 £ 12 x1 + x2 £ 4
0£ x1 £ 5 0 £ x1 £ 4
0£ x2 £ 4 0 £ x2 £ 3
x1, x2 ³ 0 x1, x2 ³ 0
x1, x2 – целые. ` x1, x2 – целые.
3. max(x1 + x2) 4. max(4 x1 + x2)
3 x1 + 4 x2 £ 12 2 x1 - 3 x2 £ 6
3 x1 + 2 x2 £ 9 4 x1 + 9 x2 £ 18
0£ x1 £ 4 0 £ x1 £ 2
0£ x2 £ 2 0 £ x2 £ 3
x1, x2 ³ 0 x1, x2 ³ 0
x1, x2 – целые. x1, x2 – целые.
5. max(3 x1 + x2) 6. max(x1 + 2 x2)
4 x1 + 3 x2 £ 18 x1 + x2 £ 5
x1 + 2 x2 £ 6 3 x1 + 8 x2 £ 24
0£ x1 £ 5 0 £ x1 £ 5
0£ x2 £ 3 0 £ x2 £ 3
x1, x2 ³ 0 x1, x2 ³ 0
x1, x2 – целые. x1, x2 – целые.
7. max(2 x1 + x2) 8. max(3 x1 - 2 x2)
5 x1 + 2 x2 £ 30 2 x1 + 3 x2 £ 6
3 x1 + 8 x2 £ 48 x1 - x2 £ 2
0£ x1 £ 6 0 £ x1 £ 3
0£ x2 £ 6 0 £ x2 £ 3
x1, x2 ³ 0 x1, x2 ³ 0
x1, x2 – целые. x1, x2 – целые.
9. max(3 x1 + 2 x2) 10. max(x1 + 2 x2)
2 x1 + x2 £ 7 5 x1 + 9 x2 £ 45
4 x1 + 3 x2 £ 18 x1 + 3 x2 £ 12
0£ x1 £ 3 0 £ x1 £ 9
0£ x2 £ 4 0 £ x2 £ 3
x1, x2 ³ 0 x1, x2 ³ 0
x1, x2 – целые. x1, x2 – целые.
11. max(2 x1 + 5 x2) 12. max(4 x1 + 6 x2)
4 x1 + 5 x2 £ 20 3 x1 + 7 x2 £ 21
x1 + 6 x2 £ 12 x1 + x2 £ 4
0£ x1 £ 6 0 £ x1 £ 5
0£ x2 £ 5 0 £ x2 £ 4
x1, x2 ³ 0 x1, x2 ³ 0
x1, x2 – целые. x1, x2 – целые.
13. max(2 x1 + 3 x2) 14. max(5 x1 + 2 x2)
3 x1 + 4 x2 £ 12 2 x1 - 3 x2 £ 6
3 x1 + 2 x2 £ 9 4 x1 + 9 x2 £ 18
0£ x1 £ 6 0 £ x1 £ 3
0£ x2 £ 3 0 £ x2 £ 3
x1, x2 ³ 0 x1, x2 ³ 0
x1, x2 – целые. x1, x2 – целые.
15. max(4 x1 + 2 x2) 16. max(2 x1 + 5 x2)
4 x1 + 3 x2 £ 18 x1 + x2 £ 5
x1 + 2 x2 £ 6 3 x1 + 8 x2 £ 24
0£ x1 £ 6 0 £ x1 £ 4
0£ x2 £ 4 0 £ x2 £ 4
x1, x2 ³ 0 x1, x2 ³ 0
x1, x2 – целые. x1, x2 – целые.
17. max(3 x1 + 2 x2) 18. max(5 x1 - 3 x2)
5 x1 + 2 x2 £ 30 2 x1 + 3 x2 £ 6
3 x1 + 8 x2 £ 48 x1 - x2 £ 2
0£ x1 £ 7 0 £ x1 £ 3
0£ x2 £ 6 0 £ x2 £ 3
x1, x2 ³ 0 x1, x2 ³ 0
x1, x2 – целые. x1, x2 – целые.
19. max(4 x1 + 3 x2) 20. max(x1 + 3 x2)
2 x1 + x2 £ 7 5 x1 + 9 x2 £ 45
4 x1 + 3 x2 £ 18 x1 + 3 x2 £ 12
0£ x1 £ 4 0 £ x1 £ 8
0£ x2 £ 4 0 £ x2 £ 3
x1, x2 ³ 0 x1, x2 ³ 0
x1, x2 – целые. x1, x2 – целые.
21. max(4 x1 + 4 x2) 22. max(3 x1 + 3 x2)
4 x1 + 5 x2 £ 20 3 x1 + 7 x2 £ 21
x1 + 6 x2 £ 12 x1 + x2 £ 4
0£ x1 £ 6 0 £ x1 £ 4
0£ x2 £ 5 0 £ x2 £ 3
x1, x2 ³ 0 x1, x2 ³ 0
x1, x2 – целые. x1, x2 – целые.
23. max(2 x1 + 3 x2) 24. max(5 x1 + x2)
3 x1 + 4 x2 £ 12 2 x1 - 3 x2 £ 6
3 x1 + 2 x2 £ 9 4 x1 + 9 x2 £ 18
0£ x1 £ 4 0 £ x1 £ 2
0£ x2 £ 2 0 £ x2 £ 3
x1, x2 ³ 0 x1, x2 ³ 0
x1, x2 – целые. x1, x2 – целые.
25. max(4 x1 + x2)
4 x1 + 3 x2 £ 18
x1 + 2 x2 £ 6
0£ x1 £ 5
0£ x2 £ 3
x1, x2 ³ 0
x1, x2 – целые.
Задание №15
Решите методом ветвей и границ следующую задачу коммивояжера:
1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
9. 
10. 
11. 
12. 
13. 14. 
15. 
16. 
17. 
18. 
19. 
20. 
21. 
22. 
23. 
24. 
25. 
ТЕМА 6.
|
|
|
|
|
Дата добавления: 2014-12-29; Просмотров: 729; Нарушение авторских прав?; Мы поможем в написании вашей работы!