Android
Ios
IP-телефония
Мобильные советы
Мобильные операторы
Мтс
Мегафон

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

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

Назначение сервиса . С помощью сервиса можно проверить свое решение или получить новое решение задачи коммивояжёра двумя методами: методом ветвей и границ и венгерским методом .

Математическая модель задачи коммивояжера

Сформулированная задача - задача целочисленная. Пусть х ij =1 , если путешественник переезжает из i -ого города в j -ый и х ij =0 , если это не так.
Формально введем (n+1) город, расположенный там же, где и первый город, т.е. расстояния от (n+1) города до любого другого, отличного от первого, равны расстояниям от первого города. При этом, если из первого города можно лишь выйти, то в (n+1) город можно лишь придти.
Введем дополнительные целые переменные, равные номеру посещения этого города на пути. u 1 =0 , u n +1 =n . Для того, чтобы избежать замкнутых путей, выйти из первого города и вернуться в (n+1) введем дополнительные ограничения, связывающие переменные x ij и переменные u i (u i целые неотрицательные числа).

U i -u j +nx ij ≤ n-1, j=2..n+1, i=1..n, i≠j, при i=1 j≠n+1
0≤u i ≤n, x in+1 =x i1 , i=2..n

Методы решения задачи коммивояжера

  1. метод ветвей и границ (алгоритм Литтла или исключения подциклов). Пример решения методом ветвей и границ ;
  2. венгерский метод. Пример решения венгерским методом .

Алгоритм Литтла или исключения подциклов

  1. Операция редукции по строкам: в каждой строке матрицы находят минимальный элемент d min и вычитают его из всех элементов соответствующей строки. Нижняя граница: H=∑d min .
  2. Операция редукции по столбцам: в каждом столбце матрицы выбирают минимальный элемент d min , и вычитают его из всех элементов соответствующего столбца. Нижняя граница: H=H+∑d min .
  3. Константа приведения H является нижней границей множества всех допустимых гамильтоновых контуров.
  4. Поиск степеней нулей для приведенной по строкам и столбцам матрицы. Для этого временно нули в матице заменяэт на знак «∞» и находят сумму минимальных элементов строки и столбца, соответствующих этому нулю.
  5. Выбирают дугу (i,j) , для которой степень нулевого элемента достигает максимального значения.
  6. Разбивают множество всех гамильтоновых контуров на два подмножества: подмножество гамильтоновых контуров содержащих дугу (i,j) и не содержащих ее (i*,j*) . Для получения матрицы контуров, включающих дугу (i,j) , вычеркивают в матрице строку i и столбец j . Чтобы не допустить образования негамильтонова контура, заменяют симметричный элемент (j,i) на знак «∞». Исключение дуги достигается заменой элемента в матрице на ∞.
  7. Проводят приведение матрицы гамильтоновых контуров с поиском констант приведения H(i,j) и H(i*,j*) .
  8. Сравнивают нижние границы подмножества гамильтоновых контуров H(i,j) и H(i*,j*) . Если H(i,j)
  9. Если в результате ветвлений получается матрица (2x2) , то определяют полученный ветвлением гамильтонов контур и его длину.
  10. Сравнивают длину гамильтонова контура с нижними границами оборванных ветвей. Если длина контура не превышает их нижних границ, то задача решена. В противном случае развивают ветви подмножеств с нижней границей, меньшей полученного контура, до тех пор, пока не получится маршрут с меньшей длиной.

Пример . Решить по алгоритму Литтла задачу коммивояжера с матрицей

1 2 3 4
1 - 5 8 7
2 5 - 6 15
3 8 6 - 10
4 7 15 10 -

Решение . Возьмем в качестве произвольного маршрута: X 0 = (1,2);(2,3);(3,4);(4,5);(5,1). Тогда F(X 0) = 20 + 14 + 6 + 12 + 5 = 57
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент: d i = min(j) d ij
i j 1 2 3 4 5 d i
1 M 20 18 12 8 8
2 5 M 14 7 11 5
3 12 18 M 6 11 6
4 11 17 11 M 12 11
5 5 5 5 5 M 5
Затем вычитаем d i из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
i j 1 2 3 4 5
1 M 12 10 4 0
2 0 M 9 2 6
3 6 12 M 0 5
4 0 6 0 M 1
5 0 0 0 0 M
Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
d j = min(i) d ij
i j 1 2 3 4 5
1 M 12 10 4 0
2 0 M 9 2 6
3 6 12 M 0 5
4 0 6 0 M 1
5 0 0 0 0 M
d j 0 0 0 0 0
После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины d i и d j называются константами приведения .
i j 1 2 3 4 5
1 M 12 10 4 0
2 0 M 9 2 6
3 6 12 M 0 5
4 0 6 0 M 1
5 0 0 0 0 M
Сумма констант приведения определяет нижнюю границу H: H = ∑d i + ∑d j = 8+5+6+11+5+0+0+0+0+0 = 35
Элементы матрицы d ij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами d ij ≥ 0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением: F(M k) = ∑d ij
Причем каждая строка и столбец входят в маршрут только один раз с элементом d ij .
Шаг №1 .
Определяем ребро ветвления

i j 1 2 3 4 5 d i
1 M 12 10 4 0(5) 4
2 0(2) M 9 2 6 2
3 6 12 M 0(5) 5 5
4 0(0) 6 0(0) M 1 0
5 0(0) 0(6) 0(0) 0(0) M 0
d j 0 6 0 0 1 0
d(1,5) = 4 + 1 = 5; d(2,1) = 2 + 0 = 2; d(3,4) = 5 + 0 = 5; d(4,1) = 0 + 0 = 0; d(4,3) = 0 + 0 = 0; d(5,1) = 0 + 0 = 0; d(5,2) = 0 + 6 = 6; d(5,3) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (0 + 6) = 6 для ребра (5,2), следовательно, множество разбивается на два подмножества (5,2) и (5*,2*).
Исключение ребра (5,2) проводим путем замены элемента d 52 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (5*,2*), в результате получим редуцированную матрицу.
i j 1 2 3 4 5 d i
1 M 12 10 4 0 0
2 0 M 9 2 6 0
3 6 12 M 0 5 0
4 0 6 0 M 1 0
5 0 M 0 0 M 0
d j 0 6 0 0 0 6
Нижняя граница гамильтоновых циклов этого подмножества: H(5*,2*) = 35 + 6 = 41
Включение ребра (5,2) проводится путем исключения всех элементов 5-ой строки и 2-го столбца, в которой элемент d 25 заменяем на М, для исключения образования негамильтонова цикла.


i j 1 3 4 5 d i
1 M 10 4 0 0
2 0 9 2 M 0
3 6 M 0 5 0
4 0 0 M 1 0
d j 0 0 0 0 0

Нижняя граница подмножества (5,2) равна: H(5,2) = 35 + 0 = 35 ≤ 41
Поскольку нижняя граница этого подмножества (5,2) меньше, чем подмножества (5*,2*), то ребро (5,2) включаем в маршрут с новой границей H = 35
Шаг №2 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j 1 3 4 5 d i
1 M 10 4 0(5) 4
2 0(2) 9 2 M 2
3 6 M 0(7) 5 5
4 0(0) 0(9) M 1 0
d j 0 9 2 1 0
d(1,5) = 4 + 1 = 5; d(2,1) = 2 + 0 = 2; d(3,4) = 5 + 2 = 7; d(4,1) = 0 + 0 = 0; d(4,3) = 0 + 9 = 9;
Наибольшая сумма констант приведения равна (0 + 9) = 9 для ребра (4,3), следовательно, множество разбивается на два подмножества (4,3) и (4*,3*).
Исключение ребра (4,3) проводим путем замены элемента d 43 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (4*,3*), в результате получим редуцированную матрицу.
i j 1 3 4 5 d i
1 M 10 4 0 0
2 0 9 2 M 0
3 6 M 0 5 0
4 0 M M 1 0
d j 0 9 0 0 9
Нижняя граница гамильтоновых циклов этого подмножества: H(4*,3*) = 35 + 9 = 44
Включение ребра (4,3) проводится путем исключения всех элементов 4-ой строки и 3-го столбца, в которой элемент d 34 заменяем на М, для исключения образования негамильтонова цикла.

После операции приведения сокращенная матрица будет иметь вид:
i j 1 4 5 d i
1 M 4 0 0
2 0 2 M 0
3 6 M 5 5
d j 0 2 0 7
Сумма констант приведения сокращенной матрицы: ∑d i + ∑d j = 7
Нижняя граница подмножества (4,3) равна: H(4,3) = 35 + 7 = 42 ≤ 44
Поскольку 42 > 41, исключаем подмножество (5,2) для дальнейшего ветвления.
Возвращаемся к прежнему плану X 1 .
План X 1 .
i j 1 2 3 4 5
1 M 12 10 4 0
2 0 M 9 2 6
3 6 12 M 0 5
4 0 6 0 M 1
5 0 M 0 0 M
Операция редукции .
i j 1 2 3 4 5
1 M 6 10 4 0
2 0 M 9 2 6
3 6 6 M 0 5
4 0 0 0 M 1
5 0 M 0 0 M
Шаг №1 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j 1 2 3 4 5 d i
1 M 6 10 4 0(5) 4
2 0(2) M 9 2 6 2
3 6 6 M 0(5) 5 5
4 0(0) 0(6) 0(0) M 1 0
5 0(0) M 0(0) 0(0) M 0
d j 0 6 0 0 1 0
d(1,5) = 4 + 1 = 5; d(2,1) = 2 + 0 = 2; d(3,4) = 5 + 0 = 5; d(4,1) = 0 + 0 = 0; d(4,2) = 0 + 6 = 6; d(4,3) = 0 + 0 = 0; d(5,1) = 0 + 0 = 0; d(5,3) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (0 + 6) = 6 для ребра (4,2), следовательно, множество разбивается на два подмножества (4,2) и (4*,2*).
Исключение ребра (4,2) проводим путем замены элемента d 42 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (4*,2*), в результате получим редуцированную матрицу.
i j 1 2 3 4 5 d i
1 M 6 10 4 0 0
2 0 M 9 2 6 0
3 6 6 M 0 5 0
4 0 M 0 M 1 0
5 0 M 0 0 M 0
d j 0 6 0 0 0 6
Нижняя граница гамильтоновых циклов этого подмножества: H(4*,2*) = 41 + 6 = 47
Включение ребра (4,2) проводится путем исключения всех элементов 4-ой строки и 2-го столбца, в которой элемент d 24 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i j 1 3 4 5 d i
1 M 10 4 0 0
2 0 9 M 6 0
3 6 M 0 5 0
5 0 0 0 M 0
d j 0 0 0 0 0
Сумма констант приведения сокращенной матрицы: ∑d i + ∑d j = 0
Нижняя граница подмножества (4,2) равна: H(4,2) = 41 + 0 = 41 ≤ 47
Поскольку нижняя граница этого подмножества (4,2) меньше, чем подмножества (4*,2*), то ребро (4,2) включаем в маршрут с новой границей H = 41
Шаг №2 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j 1 3 4 5 d i
1 M 10 4 0(9) 4
2 0(6) 9 M 6 6
3 6 M 0(5) 5 5
5 0(0) 0(9) 0(0) M 0
d j 0 9 0 5 0
d(1,5) = 4 + 5 = 9; d(2,1) = 6 + 0 = 6; d(3,4) = 5 + 0 = 5; d(5,1) = 0 + 0 = 0; d(5,3) = 0 + 9 = 9; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (4 + 5) = 9 для ребра (1,5), следовательно, множество разбивается на два подмножества (1,5) и (1*,5*).
Исключение ребра (1,5) проводим путем замены элемента d 15 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,5*), в результате получим редуцированную матрицу.
i j 1 3 4 5 d i
1 M 10 4 M 4
2 0 9 M 6 0
3 6 M 0 5 0
5 0 0 0 M 0
d j 0 0 0 5 9
Нижняя граница гамильтоновых циклов этого подмножества: H(1*,5*) = 41 + 9 = 50
Включение ребра (1,5) проводится путем исключения всех элементов 1-ой строки и 5-го столбца, в которой элемент d 51 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i j 1 3 4 d i
2 0 9 M 0
3 6 M 0 0
5 M 0 0 0
d j 0 0 0 0
Сумма констант приведения сокращенной матрицы: ∑d i + ∑d j = 0
Нижняя граница подмножества (1,5) равна: H(1,5) = 41 + 0 = 41 ≤ 50
Поскольку нижняя граница этого подмножества (1,5) меньше, чем подмножества (1*,5*), то ребро (1,5) включаем в маршрут с новой границей H = 41
Шаг №3 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j 1 3 4 d i
2 0(15) 9 M 9
3 6 M 0(6) 6
5 M 0(9) 0(0) 0
d j 6 9 0 0
d(2,1) = 9 + 6 = 15; d(3,4) = 6 + 0 = 6; d(5,3) = 0 + 9 = 9; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (9 + 6) = 15 для ребра (2,1), следовательно, множество разбивается на два подмножества (2,1) и (2*,1*).
Исключение ребра (2,1) проводим путем замены элемента d 21 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (2*,1*), в результате получим редуцированную матрицу.
i j 1 3 4 d i
2 M 9 M 9
3 6 M 0 0
5 M 0 0 0
d j 6 0 0 15
Нижняя граница гамильтоновых циклов этого подмножества: H(2*,1*) = 41 + 15 = 56
Включение ребра (2,1) проводится путем исключения всех элементов 2-ой строки и 1-го столбца, в которой элемент d 12 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i j 3 4 d i
3 M 0 0
5 0 0 0
d j 0 0 0
Сумма констант приведения сокращенной матрицы:
∑d i + ∑d j = 0
Нижняя граница подмножества (2,1) равна: H(2,1) = 41 + 0 = 41 ≤ 56
Поскольку нижняя граница этого подмножества (2,1) меньше, чем подмножества (2*,1*), то ребро (2,1) включаем в маршрут с новой границей H = 41.
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (3,4) и (5,3).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(4,2), (2,1), (1,5), (5,3), (3,4). Длина маршрута равна F(Mk) = 41

Дерево решений.

1
(5*,2*), H=41 (5,2)
(4*,2*), H=47 (4,2) (4*,3*), H=44 (4,3)
(1*,5*), H=50 (1,5)
(2*,1*), H=56 (2,1)
(3,4) (3*,4*), H=41
(5,3) (5*,3*), H=41

ЭММиМвЛ, ИСО, МПУР

ЗАДАЧА КОММИВОЯЖЕРА

Определения

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

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

Постановка задачи

Коммивояжер должен объездить n городов. Для того чтобы сократить расходы, он хочет построить такой маршрут, чтобы объездить все города точно по одному разу и вернуться в исходный с минимумом затрат.

В терминах теории графов задачу можно сформулировать следующим образом. Задано n вершин и матрица {c ij }, где c ij ≥0 – длина (или цена) дуги (i , j ),
. Подмаршрутом коммивояжера z будем понимать цикл i 1 , i 2 ,…, i n , i 1 точек 1,2,…, n. Таким образом, маршрут является набором дуг. Если между городами i и j нет перехода, то в матрице ставится символ «бесконечность». Он обязательно ставится по диагонали, что означает запрет на возвращение в точку, через которую уже проходил маршрут коммивояжера , длина маршрута l (z ) равна сумме длин дуг, входящих в маршрут. Пусть Z – множество всех возможных маршрутов. Начальная вершина i 1 – фиксирована. Требуется найти маршрут z 0  Z , такой, что l (z 0)= min l (z ), z Z .

Решение задачи

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

Сравнивая нижние границы φ () иφ (), можно выделить то, подмножество маршрутов, которое с большей вероятностью содержит маршрут минимальной длины.

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

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

Основная идея метода ветвей и границ состоит в том, что ветвятся не все вершины. Сначала вершины просматриваются, и каждая вершина оценивается. Ветвится та вершина, которая получает лучшую оценку.

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

Оценка вершины должна удовлетворять следующим свойствам.

Алгоритм метода ветвей и границ

Шаг 1 . Строятся вершины первого уровня. Для каждой вершины подсчитывается оценка нижней (верхней) границы. Ветвится вершина, которой соответствует лучшая (минимальная или максимальная) оценка.

Шаг 2 . Для всех вершин -го уровня (
) подсчитывается оценка. Ветвится та из висячих вершин уровня
, которой соответствует лучшая (минимальная или максимальная) оценка.

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

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

Для практической реализации метода ветвей и границ применительно к задаче коммивояжера укажем прием определения нижних границ подмножеств и разбиения множества маршрутов на подмножества (ветвление).

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

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

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

Разбиение множества маршрутов на подмножества

Для выделения претендентов на включение во множество дуг, по которым производится ветвление, рассмотрим в приведенной матрице все элементы, равные нулю. Найдем степени Θ ij нулевых элементов этой матрицы. Степень нулевого элемента Θ ij равна сумме минимального элемента в строке i и минимального элемента в столбце j (при выборе этих минимумов c ij – не учитывается). С наибольшей вероятностью искомому маршруту принадлежат дуги с максимальной степенью нуля.

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

Множество маршрутов, не включающих дугу (i , j ) получаем путем замены элемента c ij на бесконечность.

Пример (Г.И. Просветов, 2009, стр. 44)

Решим задачу коммивояжера для пяти пунктов.

Расстояния между населенными пунктами заданы с помощью матрицы

,

где - длина пути от пунктаi до пункта j .

На каждом шаге ребро
либо включается в ответ (обозначение
), либо не включается в ответ (обозначение
).

Шаг 1. Нахождение константы приведения .

Находим минимальный элемент в каждой строке и вычитаем его из всех элементов этой строки. В полученной матрице находим минимальный элемент в каждом столбце и вычитаем его из каждого элемента соответствующего столбца.

Найденные минимумы в строке и столбце называются константами приведения строки или столбца соответственно. Сумма всех найденных минимумов равна 18 – константа приведения матрицы. Она дает оценку снизу на данном шаге длины маршрута.

Шаг 2 . Определение дуги, исключение которой максимально увеличивает оценку, полученную на предыдущем шаге.

С этой целью заменяем поочередно каждый из нулей на .

Элемент
имеет наибольшую сумму. Поэтому все множество маршрутов распадается на два класса:
(не содержат дугу
) и
(содержат дугу
).

Шаг 3 . Определение множества дуг для дальнейшего ветвления.

Рассмотрим множество
. Исключение дуги

на:

.

В полученной матрице нужно определить сумму констант приведения:

Нижняя граница множества
, где 18 – оценка предыдущего шага, 3 – оценка текущего шага.

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


.

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

Так как
, то дальше ветвим множество
.

Для матрицы

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

Для элемента
эта сумма наибольшая. Поэтому все множество маршрутов распадается на два класса:
(не содержит дугу
) и
(содержит дугу
).

Рассмотрим множество
. Исключение дуги
проводится с помощью замены элемента
на:

.

Определим в полученной матрице ее константу приведения:

.


Введение

1. Теоретическая часть 6

1.1 Основные понятия теории графов 6

1.2 Формулировка и некоторые свойства решений задачи коммивояжера. 8

1.3 Постановка задачи коммивояжера как задачи на графе 10

1.4 Условия существования Гамильтонова контура 10

1.5 Метод ветвей и границ…………………………………………………. 11

1.6 Практическое применение задачи коммивояжера…………………… 17

2. Практическая часть 20

Заключение

Список используемой литературы

Введение

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

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

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

Целью данной курсовой работы является рассмотрение задачи коммивояжера, способов её решения.

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

    Теоретическая часть

1.1 Основные понятия теории графов

Многие задачи принятие решений можно решить с помощью теории графов.

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

Пусть G -неориентированный граф. Геометрически граф можно представить как набор вершин (точек), определенные пары которых соединены линиями. Например, сеть дорог, соединяющих города ,,,,, можно представить в виде графа следующим образом. Города обозначены точками (вершинами), а дороги – неориентированными линиями (рис 1.1).

рис 1.1 Сеть дорог между городами.

Неориентированные линии означают наличие двустороннего движения между соответствующей парой городов. Пересечения линий не считаются вершинами.

При изображении графа не имеет значение расположение вершин на плоскости, кривизна и длина ребер (рис 1.2).

рис 1.2 Изображение графов

Вершины графов обозначаются буквами или натуральными числами. Ребра графа – пары чисел.

Маршрутом в G называется такая конечная или бесконечная последовательность ребер, что каждые два соседних ребра имеют концевую точку. Причем, одно и то же ребро Е может встречаться в маршруте несколько раз.

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

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

Граф называется сильно связным, если между каждой парой его вершин , , , существует путь () такой, что является начальной вершиной пути, а - конечной.

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

1.2 Формулировка и некоторые свойства решений задачи коммивояжера

Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,1,3.. n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Чтобы привести задачу к научному виду, введём некоторые термины. Города перенумерованы числами j Т=(1,2,3.. n ) . Тур коммивояжера может быть описан циклической перестановкой t =(j 1 , j 2 ,.., j n , j 1 ) , причём все j 1 .. j n – разные номера; повторяющийся в начале и в конце j 1 , показывает, что перестановка зациклена. Расстояния между парами вершин С ij образуют матрицу С . Задача состоит в том, чтобы найти такой тур t :

(1)

Относительно математизированной формулировки задачи коммивояжера уместно сделать два замечания.

1) В постановке С ij означали расстояния, поэтому они должны быть неотрицательными, т.е. для всех j Т :

С ij 0; C jj = ∞ (2)

(последнее равенство означает запрет на петли в туре), симметричными, т.е. для всех i , j :

С ij = С ji (3)

и удовлетворять неравенству треугольника, т.е. для всех:

С ij + С jk C ik (4)

В математической постановке говорится о произвольной матрице. Сделано это потому, что имеется много прикладных задач, которые описываются основной моделью, но всем условиям (2)-(4) не удовлетворяют. Особенно часто нарушается условие (3) (например, если С ij – не расстояние, а плата за проезд: часто туда билет стоит одну цену, а обратно – другую). Поэтому мы будем различать два варианта задачи коммивояжера: симметричную задачу, когда условие (3) выполнено, и несимметричную - в противном случае. Условия (2)-(4) по умолчанию мы будем считать выполненными.

2) В несимметричной задаче коммивояжера все туры t =(j 1 , j 2 ,.., j n , j 1 ) и t ’=(j 1 , j n ,.., j 2 , j 1 ) имеют разную длину и должны учитываться оба. Разных туров очевидно (n -1)! .

Зафиксируем на первом и последнем месте в циклической перестановке номер j 1 , а оставшиеся n -1 номеров переставим всеми (n -1)! возможными способами. В результате получим все несимметричные туры. Симметричных туров имеется в

два раза меньше, т.к. каждый засчитан два раза: как t и как t ’ . Можно представить, что С состоит только из единиц и нулей. Тогда С можно интерпретировать, как граф, где ребро (i , j ) проведено, если С ij =0 и не проведено, если С ij =1 . Тогда, если существует тур длины 0, то он пройдёт по циклу, который включает все вершины по одному разу. Такой цикл называется гамильтоновым циклом. Незамкнутый гамильтонов цикл называется гамильтоновой цепью (гамильтоновым путём).

В терминах теории графов симметричную задачу коммивояжера можно сформулировать так:

Дана полная сеть с n вершинами, длина ребра (i , j )= С ij . Найти гамильтонов цикл минимальной длины. В несимметричной задаче коммивояжера вместо «цикл» надо говорить «контур», а вместо «ребра» - «дуги» или «стрелки».

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

1.3 Постановка задачи коммивояжера как задачи на графе

Формулировка: Множество городов:
. Расстояние между городами i и j:
. П – множество перестановок элементов А, перестановка

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

1.4 Условия существования Гамильтонова контура

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

Цикл Гамильтона.

Пусть G -граф. Циклом Гамильтона называется простой цикл, который содержит все вершины данного графа.

Теорема 1.

Для того, чтобы в графе существовал цикл Гамильтона, необходимо, чтобы этот граф был связным.

Теорема 2.

В полном графе , если n>=3, цикл Гамильтона есть в полном двудольном
при m>=1, цикл Гамильтона есть.

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

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

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

Постановка задачи

Коммивояжер должен объездить n городов. Для того чтобы сократить расходы, он хочет построить такой маршрут, чтобы объездить все города точно по одному разу и вернуться в исходный с минимумом затрат.

В терминах теории графов задачу можно сформулировать следующим образом. Задано n вершин и матрица {c ij }, где c ij ≥0 – длинна (или цена) дуги (i , j ),
. Под маршрутом коммивояжера z будем понимать цикл i 1 , i 2 ,…, i n , i 1 точек 1,2,…, n. Таким образом, маршрут является набором дуг. Если между городами i и j нет перехода, то в матрице ставится символ «бесконечность». Он обязательно ставится по диагонали, что означает запрет на возвращение в точку, через которую уже проходил маршрут коммивояжера , длина маршрута l (z ) равна сумме длин дуг, входящих в маршрут. Пусть Z – множество всех возможных маршрутов. Начальная вершина i 1 – фиксирована. Требуется найти маршрут z 0  Z , такой, что l (z 0)= min l (z ), z Z .

Решение задачи

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

Сравнивая нижние границы φ () и φ (), можно выделить то, подмножество маршрутов, которое с большей вероятностью содержит маршрут минимальной длины.

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

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

Для практической реализации метода ветвей и границ применительно к задаче коммивояжера укажем прием определения нижних границ подмножеств и разбиения множества маршрутов на подмножества (ветвление).

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

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

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

Разбиение множества маршрутов на подмножества

Для выделения претендентов на включение во множество дуг, по которым производится ветвление, рассмотрим в приведенной матрице все элементы, равные нулю. Найдем степени Θ ij нулевых элементов этой матрицы. Степень нулевого элемента Θ ij равна сумме минимального элемента в строке i и минимального элемента в столбце j (при выборе этих минимумов c ij – не учитывается). С наибольшей вероятностью искомому маршруту принадлежат дуги с максимальной степенью нуля.

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

Множество маршрутов, не включающих дугу (i , j ) получаем путем замены элемента c ij на бесконечность.

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

Коммивояжер должен объездить 6 городов. Для того чтобы сократить расходы, он хочет построить такой маршрут, чтобы объездить все города точно по одному разу и вернуться в исходный с минимумом затрат. Исходный город A. Затраты на перемещение между городами заданы следующей матрицей:

Решение задачи

Для удобства изложения везде ниже в платежной матрице заменим имена городов (A, B, …, F) номерами соответствующих строк и столбцов (1, 2, …, 6).

Найдем нижнюю границу длин множества всех маршрутов. Вычтем из каждой строки число, равное минимальному элементу этой строки, далее вычтем из каждого столбца число, равное минимальному элементу этого столбца, и таким образом приведем матрицу по строкам и столбцам. Минимумы по строкам: r 1 =15, r 2 =1, r 3 =0, r 4 =16, r 5 =5, r 6 =5.

После их вычитания по строкам получим:

Минимумы по столбцам: h 1 =5, h 2 =h 3 =h 4 =h 5 =h 6 .

После их вычитания по столбцам получим приведенную матрицу:

Найдем нижнюю границу φ (Z ) = 15+1+0+16+5+5+5 = 47.

Для выделения претендентов на включение во множество дуг, по которым производится ветвление, найдем степени Θ ij нулевых элементов этой матрицы (суммы минимумов по строке и столбцу). Θ 14 = 10 + 0,
Θ 24 = 1 + 0, Θ 36 = 5+0, Θ 41 = 0 + 1, Θ 42 = 0 + 0, Θ 56 = 2 + 0, Θ 62 = 0 + 0,
Θ 63 = 0 + 9, Θ 65 = 0 + 2. Наибольшая степень Θ 14 = 10. Ветвление проводим по дуге (1, 4).

Нижняя граница для множества
остается равной 47. Для всех маршрутов множества из города A мы не перемещаемся в город D. В матрице это обозначается выставлением в ячейку (1, 4) знака ∞. В этом случае выход из города A добавляет к оценке нижней границы по крайней мере наименьший элемент первой строки. φ () = 47 + 10.

В матрице, соответствующей полагаем c 14 = ∞.

После проведения процедуры приведения с r 1 =10 получим новую нижнюю границу 57 + 10 = 67.

В матрице, соответствующей , вычеркиваем первую строку и четвертый столбец и положим c 41 = ∞, чтобы предотвратить появления цикла 1→ 4 → 1. Получим новую платежную матрицу {c 1 ij }:

Для приведения надо вычесть минимум по первому столбцу: h 1 =1. При этом нижняя граница станет равной 47+1 = 48. Сравнивая нижние границы
φ () = 67 и φ () = 48 < 67 выделяем подмножество маршрутов , которое с большей вероятностью содержит маршрут минимальной длины.

Рис. 1.4 Ветвление на первом шаге

Далее продолжаем процесс ветвления. Найдем степени Θ ij нулевых элементов этой матрицы Θ 21 =16, Θ 36 = 5, Θ 42 = 2, Θ 56 = 2, Θ 62 = 0, Θ 63 =9, Θ 65 = 2. Наибольшая степень Θ 21 . Затем множество разбивается дуге (2, 1) на два новых
и .

В матрице для вычеркиваем строку 2 и столбец 1. дуги (1, 4) и (2, 1) образуют связный путь (2, 1, 4), положим c 42 = ∞, чтобы предотвратить появления цикла 2→1→ 4 → 2.

Для приведения надо вычесть минимум по строке 4: r 4 =2. При этом нижняя граница станет равной 48+2 = 50.

Нижняя граница для , полученная как на предыдущем шаге ветвления, равна 48 + 16 = 64. Сравнивая нижние границы φ () = 64 и φ () = 50 < 64 выбираем для дальнейшего разбиения подмножество маршрутов .

Рис. 1.5 Ветвление на втором шаге

Приведенная платежная матрица для

Степени Θ ij нулевых элементов этой матрицы Θ 36 = 5, Θ 45 = 0, Θ 56 = 22, Θ 62 = 13, Θ 63 =7, Θ 65 = 0. Наибольшая степень Θ 56. Затем множество разбивается дуге (2, 1) на два новых и .

Нижняя граница для равна 50 + 22 = 72. В матрице для вычеркиваем строку 5 и столбец 6 и полагаем c 65 = ∞. Получим матрицу:

Для приведения надо вычесть минимум по строке 3: r 3 =5. При этом нижняя граница станет равной 50+5 = 55. Выбираем для дальнейшего разбиения подмножество маршрутов.

Рис. 1.6 Ветвление на третьем шаге

Приведенная платежная матрица для

Для приведения надо вычесть минимум по строке 4: r4=7. При этом нижняя граница станет равной 55+7 = 62. После приведения получим

Из матрицы 22 получаем два перехода с нулевой длинной: (4, 3) и (6, 2).

Рис. 1.7 Ветвление на четвертом шаге

Рис. 1.8 Дерево ветвления с оценками

Полученный маршрутом коммивояжера z 0 = (1, 4, 3, 5, 6, 2, 1) или (A-D-C-E-F-B-A).

1.6 Практическое применение задачи коммивояжера

Кроме очевидного применения задачи коммивояжера на практике, существует ещё ряд задач, сводимых к решению задачи коммивояжера.

Задача о производстве красок .

Имеется производственная линия для производства n красок разного цвета; обозначим эти краски номерами 1,2… n. Всю производственную линию будем считать одним процессором.. Будем считать также, что единовременно процессор производит только одну краску, поэтому краски нужно производить в некотором порядке Поскольку производство циклическое, то краски надо производить в циклическом порядке =(j 1 ,j 2 ,..,j n ,j 1). После окончания производства краски i и перед началом производства краски j надо отмыть оборудование от краски i. Для этого требуется время C. Очевидно, что C зависит как от i, так и от j, и что, вообще говоря,C≠C. При некотором выбранном порядке придется на цикл производства красок потратить время:

Где t k - чистое время производства k-ой краски (не считая переналадок). Однако вторая сумма в правой части постоянна, поэтому полное время на цикл производства минимизируется вместе с общим временем на переналадку.

Таким образом, задача коммивояжера и задача о минимизации времени переналадки – это просто одна задача, только варианты ее описаны разными словами.

Задача о дыропробивном прессе .

Дыропробивной пресс производит большое число одинаковых панелей – металлических листов, в которых последовательно по одному пробиваются отверстия разной формы и величины. Схематически пресс можно представить в виде стола, двигающегося независимо по координатам x, y, и вращающегося над столом диска, по периметру которого расположены дыропробивные инструменты разной формы и величины. Каждый инструмент присутствует в одном экземпляре. Диск может вращаться одинаково в двух направлениях (координата вращения z). Имеется собственно пресс, который надавливает на подвешенный под него инструмент тогда, когда под инструмент подведена нужная точка листа.

Операция пробивки j-того отверстия характеризуется четверкой чисел (x j ,y j ,z j ,t j), где x j ,y j - координаты нужного положения стола, z j - координата нужного положения диска и t j - время пробивки j-того отверстия.

Производство панелей носит циклический характер: в начале и конце обработки каждого листа стол должен находиться в положениях (x 0 , y 0) диск в положении z 0 причем в этом положении отверстие не пробивается. Это начальное состояние системы можно считать пробивкой фиктивного нулевого отверстия. С параметрами (x 0 ,y 0 ,z 0 ,0).

Чтобы пробить j-е отверстие непосредственно после i-того необходимо произвести следующие действия:

    Переместить стол по оси x из положения x i в положение x j , затрачивая при этом время t (x) (|x i -x j |)=t i , j (x) .

    Проделать то же самое по оси y, затратив время t i , j (y) .

    Повернуть головку по кратчайшей из двух дуг из положения z i в положение z j , затратив время t i , j (z) .

    Пробить j-тое отверстие, затратив время t j .

Конкретный вид функций t (x) , t (y) , t (z) зависит от механических свойств пресса и достаточно громоздок. Явно выписывать эти функции нет необходимости

Действия 1-3 (переналадка с i-того отверстия j-тое) происходит одновременно, и пробивка происходит немедленно после завершения самого длительного из этих действий. Поэтому

С = max(t (x) , t (y) , t (z))

Теперь, как и в предыдущем случае, задача составления оптимальной программы для дыропробивного пресса сводится к задаче коммивояжера (здесь - симметричной).

    Практическая часть

Инвестор, располагающий суммой в 300 тысяч денежных единиц, может вложить свой капитал в акции автомобильного концерна А и строительного предприятия В. Чтобы уменьшить риск, акций А должно быть приобретено по крайней мере в два раза больше, чем акций В, причём последних можно купить не более чем на 100 тысяч денежных единиц. Дивиденды по акциям А составляют 8% в год, по акциям В – 10%. Какую максимальную прибыль можно получить в первый год?

Пусть цены на акции одинаковы для A и B и равны: ЦA = ЦB = 1 тыс.

  • Решение задачи на нахождение оптимального пути методом ветвей и границ

    Курсовая работа >> Математика

    Математическая постановка задачи коммивояжёра 5 1.2.Метод ветвей и границ. 5 1.3. Алгоритм решения 6 1.4. Схема решения задачи 6 ... множество допустимых решений (планов) некоторым способом разбивается... данной проблемы и её решение с помощью метода ветвей...

  • Применение муравьиных алгоритмов при решении задач оптимизации

    Задача >> Информатика

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

  • Применение NP-полных задач в ассиметрично-ключевой криптографии

    Курсовая работа >> Информатика

    Представление о способах решения данной задачи и носит... обращающий её в 1. Свидетель – такой набор. Задача о... решение «пятнашек» размера Задача коммивояжёра Проблема раскраски графа Задача о вершинном покрытии Задача о покрытии множества Задача о клике Задача ...

  • Языки программирования (6)

    Реферат >> Информатика

    Виртуальные понятия, существующие в её рамках - таблица, табличное пространство... интеллекта. Это предполагает развитие способов решения задач по аналогии, методов дедукции... привлекаются для решения NP-полных задач , например, задачи коммивояжёра . ИИ занимается...

    • 1.9 ООП 14090 – 07 КР ПЗ

    Лист

    № докумен.

    Подпись

    Дата

    Разраб.

    Ковешников Д.В.

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

    Литера

    Лист

    Листов

    Руков.

    Селютина О.Н.

    К идее метода ветвей и границ приходили многие исследователи, но Литтл с соавторами на основе указанного метода разработали удачный алгоритм решения ЗК и тем самым способствовали популяризации подхода. С тех пор метод ветвей и границ был успешно применен ко многим задачам, для решения ЗК было придумано несколько других модификаций метода, но в большинстве учебников излагается пионерская работа Литтла.

    Общая идея тривиальна: нужно разделить огромное число перебираемых вариантов на классы и получить оценки (снизу - в задаче минимизации, сверху - в задаче максимизации) для этих классов, чтобы иметь возможность отбрасывать варианты не по одному, а целыми классами. Трудность состоит в том, чтобы найти такое разделение на классы (ветви) и такие оценки (границы), чтобы процедура была эффективной.

    Таблица 2

    Таблица 3

    Таблица 4

    Изложим алгоритм Литтла на примере 1 предыдущего раздела. Повторно запишем матрицу:

    Нам будет удобнее трактовать С ij как стоимость проезда из города i в город j. Допустим, что добрый мэр города j издал указ выплачивать каждому въехавшему в город коммивояжеру 5 долларов. Это означает, что любой тур подешевеет на 5 долларов, поскольку в любом туре нужно въехать в город j. Но поскольку все туры равномерно подешевели, то прежний минимальный тур будет и теперь стоить меньше всех. Добрый же поступок мэра можно представить как уменьшение всех чисел j-го столбца матрицы С на 5. Если бы мэр хотел спровадить коммивояжеров из j-го города и установил награду за выезд в размере 10 долларов, это можно было бы выразить вычитанием 10 из всех элементов j-й той строки. Это снова бы изменило стоимость каждого тура, но минимальный тур остался бы минимальным. Итак, доказана следующая лемма.

    Вычитая любую константу из всех элементов любой строки или столбца матрицы С, мы оставляем минимальный тур минимальным.

    Для алгоритма нам будет удобно получить побольше нулей в матрице С, не получая там, однако, отрицательных чисел. Для этого мы вычтем из каждой строки ее минимальный элемент (это называется приведением по строкам, см. табл. 3), а затем вычтем из каждого столбца матрицы, приведенной по строкам, его минимальный элемент, получив матрицу, приведенную по столбцам, см. табл. 4).

    Прочерки по диагонали означают, что из города i в город i ходить нельзя. Заметим, что сумма констант приведения по строкам равна 27, сумма по столбцам 7, сумма сумм равна 34.

    Тур можно задать системой из шести подчеркнутых (выделенных другим цветом) элементов матрицы С, например, такой, как показано на табл. 2. Подчеркивание элемента означает, что в туре из i-го элемента идут именно в j-тый. Для тура из шести городов подчеркнутых элементов должно быть шесть, так как в туре из шести городов есть шесть ребер. Каждый столбец должен содержать ровно один подчеркнутый элемент (в каждый город коммивояжер въехал один раз), в каждой строке должен быть ровно один подчеркнутый элемент (из каждого города коммивояжер выехал один раз); кроме того, подчеркнутые элементы должны описывать один тур, а не несколько меньших циклов. Сумма чисел подчеркнутых элементов есть стоимость тура. На табл. 2 стоимость равна 36, это тот минимальный тур, который получен лексикографическим перебором.

    Теперь будем рассуждать от приведенной матрицы на табл. 2. Если в ней удастся построить правильную систему подчеркнутых элементов, т.е. систему, удовлетворяющую трем вышеописанным требованиям, и этими подчеркнутыми элементами будут только нули, то ясно, что для этой матрицы мы получим минимальный тур. Но он же будет минимальным и для исходной матрицы С, только для того, чтобы получить правильную стоимость тура, нужно будет обратно прибавить все константы приведения, и стоимость тура изменится с 0 до 34. Таким образом, минимальный тур не может быть меньше 34. Мы получили оценку снизу для всех туров.

    Теперь приступим к ветвлению. Для этого проделаем шаг оценки нулей. Рассмотрим нуль в клетке (1,2) приведенной матрицы. Он означает, что цена перехода из города 1 в город 2 равна 0. А если мы не пойдем из города 1 в город 2? Тогда все равно нужно въехать в город 2 за цены, указанные во втором столбце; дешевле всего за 1 (из города 6). Далее, все равно надо будет выехать из города 1 за цену, указанную в первой строке; дешевле всего в город 3 за 0. Суммируя эти два минимума, имеем 1+0=1: если не ехать «по нулю» из города 1 в город 2, то надо заплатить не меньше 1. Это и есть оценка нуля. Оценки всех нулей поставлены на табл. 5 правее и выше нуля (оценки нуля, равные нулю, не ставились).

    Выберем максимальную из этих оценок (в примере есть несколько оценок, равных единице, выберем первую из них, в клетке (1,2)).

    Итак, выбрано нулевое ребро (1,2). Разобьем все туры на два класса - включающие ребро (1,2) и не включающие ребро (1,2). Про второй класс можно сказать, что придется приплатить еще 1, так что туры этого класса стоят 35 или больше.

    Что касается первого класса, то в нем надо рассмотреть матрицу на табл. 6 с вычеркнутой первой строкой и вторым столбцом.

    Таблица 5

    Таблица 7

    Дополнительно в уменьшенной матрице поставлен запрет в клетке (2,1), т.к. выбрано ребро (1,2) и замыкать преждевременно тур ребром (2,1) нельзя. Уменьшенную матрицу можно привести на 1 по первому столбцу, так что каждый тур, ей отвечающий, стоит не меньше 35. Результат наших ветвлений и получения оценок показан на рис. 6.

    Кружки представляют классы: верхний кружок - класс всех туров; нижний левый - класс всех туров, включающих ребро (1,2); нижний правый - класс всех туров, не включающих ребро (1,2). Числа над кружками - оценки снизу.

    Продолжим ветвление в положительную сторону: влево - вниз. Для этого оценим нули в уменьшенной матрице C на табл. 7. Максимальная оценка в клетке (3,1) равна 3. Таким образом, оценка для правой нижней вершины на рис. 7 есть 35+3=38. Для оценки левой нижней вершины на рис. 7 нужно вычеркнуть из матрицы C еще строку 3 и столбец 1, получив матрицу C[(1,2), (3,1)] на табл. 8. В эту матрицу нужно поставить запрет в клетку (2,3), так как уже построен фрагмент тура из ребер (1,2) и (3,1), т.е. , и нужно запретить преждевременное замыкание (2,3). Эта матрица приводится по столбцу на 1 (табл. 9), таким образом, каждый тур соответствующего класса (т.е. тур, содержащий ребра (1,2) и (3,1)) стоит 36 и более.

    Таблица 9

    Таблица 11

    Оцениваем теперь нули в приведенной матрице C[(1,2), (3,1)] нуль с максимальной оценкой 3 находится в клетке (6,5). Отрицательный вариант имеет оценку 38+3=41. Для получения оценки положительного варианта убираем строчку 6 и столбец 5, ставим запрет в клетку (5,6), см. табл. 10. Эта матрица неприводима. Следовательно, оценка положительного варианта не увеличивается (рис. 8).

    Оценивая нули в матрице на табл. 10, получаем ветвление по выбору ребра (2,6), отрицательный вариант получает оценку 36+3=39, а для получения оценки положительного варианта вычеркиваем вторую строку и шестой столбец, получая матрицу на табл. 11.

    В матрицу надо добавить запрет в клетку (5,3), ибо уже построен фрагмент тура и надо запретить преждевременный возврат (5,3). Теперь, когда осталась матрица 2х2 с запретами по диагонали, достраиваем тур ребрами (4,3) и (5,4). Мы не зря ветвились, по положительным вариантам. Сейчас получен тур: 1>2>6>5>4>3>1 стоимостью в 36. При достижении низа по дереву перебора класс туров сузился до одного тура, а оценка снизу превратилась в точную стоимость.

    Итак, все классы, имеющие оценку 36 и выше, лучшего тура не содержат. Поэтому соответствующие вершины вычеркиваются. Вычеркиваются также вершины, оба потомка которой вычеркнуты. Мы колоссально сократили полный перебор. Осталось проверить, не содержит ли лучшего тура класс, соответствующий матрице С , т.е. приведенной матрице С с запретом в клетке 1,2, приведенной на 1 по столбцу (что дало оценку 34+1=35). Оценка нулей дает 3 для нуля в клетке (1,3), так что оценка отрицательного варианта 35+3 превосходит стоимость уже полученного тура 36 и отрицательный вариант отсекается.

    Для получения оценки положительного варианта исключаем из матрицы первую строку и третий столбец, ставим запрет (3,1) и получаем матрицу. Эта матрица приводится по четвертой строке на 1, оценка класса достигает 36 и кружок зачеркивается. Поскольку у вершины «все» убиты оба потомка, она убивается тоже. Вершин не осталось, перебор окончен. Мы получили тот же минимальный тур, который показан подчеркиванием на табл. 2.

    Удовлетворительных теоретических оценок быстродействия алгоритма Литтла и родственных алгоритмов нет, но практика показывает, что на современных ЭВМ они часто позволяют решить ЗК с n = 100. Это огромный прогресс по сравнению с полным перебором. Кроме того, алгоритмы типа ветвей и границ являются, если нет возможности доводить их до конца, эффективными эвристическими процедурами.

    Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

    хорошую работу на сайт">

    Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

    Размещено на http://www.allbest.ru/

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

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

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

    При применении метода ветвей и границ к каждой конкретной задаче в первую очередь должны быть определены две важнейшие его процедуры: 1) ветвления множества возможных решений; 2) вычисления нижних и верхних оценок целевой функции.

    1 . 1 Правила ветвления

    В зависимости от особенностей задачи для организации ветвления обычно используется один из двух способов:

    1. ветвление множества допустимых решений исходной задачи D;

    2. ветвление множества D" получаемого из D путем снятия условия целочисленноти на переменные.

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

    Второй способ ветвления - более универсальный, чем первый. Для осуществления ветвления некоторой области D i " этим способом на D i " решается оптимизационная задача с целевой функцией исходной задачи и действительными переменными.

    Ветвление осуществляется, если в оптимальном решении значение хотя бы одной целочисленной по исходной постановке задача переменной не является целочисленным. Среди этих переменных выбирается одна, например j - я. Обозначим ее значение в найденном оптимальном решении x 0 [j]. Говорят, что ветвление осуществляется по переменной x[j]. Область D i " разделяется на две подобласти D i1 " и D i2 " следующим образом:

    где ] - целая часть значения x 0 [j]

    На рис. 2 условно дана геометрическая интерпретация такого ветвления.

    Размещено на http://www.allbest.ru/

    Рис. 2. Геометрическая интерпретация ветвления

    Видно, что при этом из области D i " удаляется часть между плоскостями вновь введенных ограничений. Так как переменная x[j] по условиям области допустимых решений исходной задачи - целочисленная, то из подобласти допустимых решений исходной задачи. D i (D i D i ") при таком изъятии не исключается ни одного решения.

    1 . 2 Формирование нижних и верхних оценок целевой функции

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

    где х - вектор оптимизационных переменных, среди которых часть действительных, а часть целочисленных; f(x) - в общем случае нелинейная целевая функция; D - область допустимых решений задачи дискретного программирования общего вида.

    Нижние оценки целевой дикции в зависимости от выбранного способа ветвления могут определяться либо для подобластей D i D либо для подобластей D i " D" (D i " и D" получены из соответствующих множеств D i и D путем снятия условий целочисленности на дискретные переменные).

    Нижней оценкой целевой функции f(x) на множестве D i (или D i ") будем называть величину:

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

    На рис. 3 показан такой идеальный случай, когда нижние оценки (соединены ломаной штрихпунктирной линией) правильно отражают соотношения между действительными минимальными значениями f(x) (соединены штриховой линией) для четырех подмножеств допустимых решений D 1 , D 2 , D 3 , D 4 .

    Один из универсальных способов вычисления нижних оценок заключается в решении следующей задачи:

    Определенная таким образом о i является нижней оценкой f(x) на D i (или D i "), так как D i D i ".

    Если при решении задачи (4) установлено, что, то для общности будем полагать, что.

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

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

    Затем при определении более лучшего допустимого решения верхнюю оценку корректируют:

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

    1 .3 Алгоритм метода ветвей и границ

    Основные правила алгоритма могут быть сформулированы следующим образом:

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

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

    3. Ветвление подмножества прекращается, если найденное в задаче (4) оптимальное решение. Обосновывается это тем, что, и, следовательно, лучшего допустимого решения, чем в этом подмножестве не существует. В этом случае рассматривается возможность корректировки.

    4. Если, где, то выполняются условия оптимальности для найденного к этому моменту лучшего допустимого решения. Обоснование такое же, как и пункта 2 настоящих правил.

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

    1 .4 Решение задачи методом ветвей и границ

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

    Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи.

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

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

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

    Определяя эти числа, находим симплексным методом решение двух задач линейного программирования

    Возможны четыре случая при решении этой пары задач:

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

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

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

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

    Таким образом, при решении задачи получаем схему:

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

    Составляет дополнительные ограничения на дробную компоненту плана.

    Находим решение двух задач с ограничениями на компоненту.

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

    Найдем решение задачи

    Решение. Находим решение без учет целочисленности задачи симплексным методом.

    Рассмотрим следующую пару задач:

    Первая задача имеет оптимальный план

    вторая - неразрешима.

    Проверяем на целочисленность план первой задачи. Это условие не выполняется, поэтому строим следующие задачи:

    Задача 1.1

    Задача 1.2

    Задача 1.2 неразрешима, а задача №1.1 имеет оптимальный план, на котором значение целевой функции.

    В результате получили, что исходная задача целочисленного программирования имеет оптимальный план и.

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

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

    2.1 Постановка задачи

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

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

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

    пусть - полный ориентированный граф и - весовая функция; найти простой остовный ориентированный цикл («цикл коммивояжера») минимального веса.

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

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

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

    Слова привести матрицу по строкам означают, что все строки матрицы приводятся. Аналогичный смысл имеют слова привести матрицу по столбцам.

    Наконец, слова привести матрицу означают, что матрица сначала приводится по строкам, а потом приводится по столбцам.

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

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

    Первый шаг. Фиксируем множество всех обходов коммивояжера (т.е. всех простых ориентированных остовных циклов). Поскольку граф - полный, это множество заведомо не пусто. Сопоставим ему число, которое будет играть роль значения на этом множестве оценочной функции: это число равно сумме констант приведения данной матрицы весов ребер графа. Если множество всех обходов коммивояжера обозначить через G, то сумму констант приведения матрицы весов обозначим через j(G). Приведенную матрицу весов данного графа следует запомнить; обозначим ее через M 1 ; таким образом, итог первого шага:

    множеству G всех обходов коммивояжера сопоставлено чис-ло j(G) и матрица M 1 .

    Второй шаг. Выберем в матрице M 1 самый тяжелый нуль; пусть он стоит в клетке; фиксируем ребро графа и разделим множество G на две части: на часть, состоящую из обходов, которые проходят через ребро, и на часть, состоящую из обходов, которые не проходят через ребро.

    Сопоставим множеству следующую матрицу M 1,1: в матрице M 1 заменим на Ґ число в клетке. Затем в полученной матрице вычеркнем строку номер i и столбец номер j, причем у оставшихся строк и столбцов сохраним их исходные номера. Наконец, приведем эту последнюю матрицу и запомним сумму констант приведения. Полученная приведенная матрица и будет матрицей M 1,1 ; только что запомненную сумму констант приведения прибавим к j(G) и результат, обозначаемый в дальнейшем через j(), сопоставим множеству.

    Теперь множеству тоже сопоставим некую матрицу M 1,2 . Для этого в матрице M 1 заменим на Ґ число в клетке и полученную в результате матрицу приведем. Сумму констант приведения запомним, а полученную матрицу обозначим через M 1,2 . Прибавим запомненную сумму констант приведения к числу j(G) и полученное число, обозначаемое в дальнейшем через j(), сопоставим множеству.

    Теперь выберем между множествами и то, на котором минимальна функция j (т.е. то из множеств, которому соответствует меньшее из чисел j() и j()).

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

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

    К выбранному множеству с сопоставленными ему матрицей и числом j повторим все то же самое и так далее, пока это возможно.

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

    После этого осуществляется улучшение рекорда вплоть до получения окончательного ответа.

    2.2 Условие задачи

    Студенту Иванову поручили разнести некоторые важные документы из 12-ого корпуса. Но, как назло, у него на это очень мало времени, да и еще надо вернуться обратно. Нужно найти кротчайший путь. Расстояния между объектами даны в таблице

    2.3 Математическая модель задачи

    Для решения задачи присвоим каждому пункту маршрута определенный номер: 12-ый корпус - 1, Белый дом - 2, КРК «Премьер» - 3, Администрация - 4 и 5-ый корпус - 5. Соответственно общее количество пунктов. Далее введем альтернативных переменных, принимающих значение 0, если переход из i-того пункта в j-тый не входит в маршрут и 1 в противном случае. Условия прибытия в каждый пункт и выхода из каждого пункта только по одному разу выражаются равенствами (8) и (9).

    Для обеспечения непрерывности маршрута вводятся дополнительно n переменных и дополнительных ограничений (10).

    Суммарная протяженность маршрута F , которую необходимо минимизировать, запишется в следующем виде:

    В нашем случае эти условия запишутся в следующем виде:

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

    1) Анализ множества D.

    Найдем оценку снизу Н . Для этого определяем матрицу минимальных расстояний по строкам (1 где расстояние минимально в строке).

    Аналогично определяем матрицу минимальных расстояний по столбцам.

    Выберем начальный план: . Тогда верхняя оценка:

    Очевидно, что, где означает переход из первого пункта в j-тый. Рассмотрим эти подмножества по порядку.

    2) Анализ подмножества D 12 .

    3) Анализ подмножества D 13 .

    4) Анализ подмножества D 14 .

    5) Анализ подмножества D 15 .

    6) Отсев неперспективных подмножеств.

    Подмножества D 13 и D 15 неперспективные. Т.к. , но, то далее будем рассматривать подмножество D 14 .

    7) Анализ подмножества D 142 .

    8) Анализ подмножества D 143 .

    9) Анализ подмножества D 145 .

    10) Отсев неперспективных подмножеств

    Подмножество D 143 неперспективное. Т.к. , но, то далее будем рассматривать подмножество D 145 .

    11) Анализ подмножества D 1452 .

    ветвь граница целевой алгоритм

    12) Анализ подмножества D 1453 .

    Оптимальное решение: .

    Таким образом, маршрут студента: 12-ый корпус - Администрация - 5-ый корпус - Белый дом - КРК Премьер - 12-ый корпус.

    Размещено на http://www.allbest.ru/

    Список использованной литературы

    1. Абрамов Л.А., Капустин В.Ф. Математическое программирование. - Л.: Изд-во ЛГУ, 1981. -328 с.

    2. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. - М.: Наука, 1987. -294 с.

    3. Корбут А.А., Финкелгейн Ю.Ю. Дискретное программирование. М.: Наука. 1969. -240 с

    4. Кузнецов Ю.Н. и др. Математическое программирование: Учебное пособие. - 2-е изд., перераб и доп. - М.: Высшая школа, 1980. -300 с.

    5. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. - М.: Мир, 1985. -213 с.

    Размещено на Allbest.ru

    ...

    Подобные документы

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

      курсовая работа , добавлен 08.11.2009

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

      курсовая работа , добавлен 01.10.2009

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

      курсовая работа , добавлен 05.03.2012

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

      дипломная работа , добавлен 07.02.2013

      Методы ветвей и границ первого и второго порядка. Оптимальный и пассивный поиск. Недостатки метода Ньютона. Метод золотого сечения. Примеры унимодальных функций. Динамическое и линейное программирование. Метод Жордана-Гаусса. Решение задачи коммивояжера.

      курсовая работа , добавлен 20.07.2012

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

      курсовая работа , добавлен 08.08.2013

      Оптимизация решения задачи с помощью алгоритма отжига. Анализ теории оптимизации как целевой функции. Метод градиентного спуска. Переменные и описание алгоритма отжига. Представление задачи коммивояжера через граф. Сведение задачи к переменным и решение.

      курсовая работа , добавлен 21.05.2015

      Постановка линейной целочисленной задачи. Метод отсекающих плоскостей. Дробный алгоритм решения полностью целочисленных задач. Эффективность отсечения Гомори. Сравнение вычислительных возможностей метода отсекающих плоскостей и метода ветвей и границ.

      курсовая работа , добавлен 25.11.2011

      Задача о ранце как задача комбинаторной оптимизации. Задача о загрузке, рюкзаке, ранце. Постановка и NP-полнота задачи. Классификация методов решения задачи о рюкзаке. Динамическое программирование. Метод ветвей и границ. Сравнительный анализ методов.

      курсовая работа , добавлен 18.01.2011

      Поиск верхних и нижних границ для оптимального значения на подобласти допустимых решений. Методы и проблемы решения задач нелинейного программирования. Написание и отладка программы. Создание программы для решения задачи "коммивояжёра" прямым алгоритмом.



    Печать
    Также интересно:
    Как выбрать центральный процессор, и зачем это нужно?
    Восстановления раздела recovery ASUS
    Где взять биткоин бесплатно?
    Рекомендуем почитать:
    Как защитить свой форум на Simple Machines (SMF) от спама
    2024-04-11 00:07:07
    Как защитить свой форум на Simple Machines (SMF) от спама
    Установка виндовс с флешки через биос
    2024-04-11 00:07:07
    Установка виндовс с флешки через биос
    Тестирование web сервисов
    2024-04-09 00:06:08
    Тестирование web сервисов
    В продолжение темы:
    Расширение VK Helper – ваш незаменимый помощник
    Android
    Расширение VK Helper – ваш незаменимый помощник

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

    ×
    Новые статьи
    /
    Популярные
    Риски и последствия временной регистрации для собственника
    2024-04-05 00:05:57
    Риски и последствия временной регистрации для собственника
    Мегафон
    Смартфон Mi4 Xiaomi: отзывы и технические характеристики
    2024-04-04 00:06:07
    Смартфон Mi4 Xiaomi: отзывы и технические характеристики
    Tele2
    Технология HTML – язык гипертекстовой разметки текста
    2024-04-04 00:06:07
    Технология HTML – язык гипертекстовой разметки текста
    Мегафон
    Рейтинг бесплатных антивирусов: обзор, описание и отзывы
    2024-04-03 00:06:53
    Рейтинг бесплатных антивирусов: обзор, описание и отзывы
    Tele2
    Как выбрать систему для загрузки по умолчанию
    2024-04-03 00:06:53
    Как выбрать систему для загрузки по умолчанию
    Android
    Как подключить ide жесткий диск к новой материнской плате
    2024-04-03 00:06:53
    Как подключить ide жесткий диск к новой материнской плате
    Билайн
    Координаты в Google Earth
    Координаты в Google Earth
    Как скачать и установить программу Dropbox
    Как скачать и установить программу Dropbox
    Путь в digital: как открыть веб-студию
    Путь в digital: как открыть веб-студию
    Расшифровка, определение, перевод
    Расшифровка, определение, перевод
    Как отключить услуга Билайн «Привет Как поставить мелодию на вызов билайн
    Как отключить услуга Билайн «Привет Как поставить мелодию на вызов билайн
    Телефонная атака: методы борьбы и средства защиты Флудить — что это значит
    Телефонная атака: методы борьбы и средства защиты Флудить — что это значит
    © amok.ru 2024 г. Мобильные телефоны и связь