Номер варианта выбирается по параметру зачетки d 10 соотв Задача Коммивояжёра Имеется n городов, занумерованных числами 1,2,...,n. Для любой пары городов (i,j) задано расстояние (время, путевые расходы) C(i,j) 0 между ними. Поэтому в общем случае C(i,j) C(j,i). Коммивояжер, выезжая из какого-либо города, должен посетить все города по одному разу и вернуться в исходный город. Необходимо определить такую последовательность объезда городов, при которой длина маршрута была бы минимальной. Можно взять задач 5х5, вычеркнув пару строку&столбец по номеру b mod6 По номеру c По особому разрешению преподавателя можно вычеркнуть после этого столбец и строку с mod 5 (Если исп ФИО, то по а)

Постановка целочисленная ЗЛП Ограничения требуют, чтобы маршрут образовывал контур Москва Питер Астрахань Минск Киев Ростов Екатеринбург Верный Путь

Процедура коррекции длин (ввод субсидий) таможня Можно избрать

Пример 3х3 Самая зловредная θ Дерево решения Тогда верхняя граница длин всех маршрутов F(x 0 ) = = 21 - текущее значение Z 0 Нижняя оценка Z нижн =16 ( ) Меньшая оценка соответствует нашей (левой) вершине Ищем путь Ответ: его длина проверка

Алгоритм ветвей и границ Допустимый маршрут х представим как множество упорядоченных пар городов: X = (i 1,i 2 ), (i 2,i 3 ),…,(i n-1,i n ), (i n,i 1 ). Каждый допустимый маршрут представляет собой цикл, проходя по которому коммивояжер посещает каждый город ровно один раз и возвращается в исходный город. Каждая упорядоченная пара (i,j) является дугой маршрута. Длина F(X) маршрута X равна сумме соответствующих элементов C(i,j). Возможно (n-1)! маршрутов !!

Флаг Русский Польский Советский для 20 : 20*19*18… для 4 : 4 * 3 * 2 * 1 = … маршрут х X = (i 1,i 2 ), (i 2,i 3 ),…,(i n-1,i n ), (i n,i 1 ). С учётом безразличности выбора начала

- Редуцированная матрица. пусть Пусть - сумма констант редуцирования Тогда для любого маршрута Оценка длины с низу! после редукции длины всех маршрутов уменьшаются на одну и ту же величину d(X) и, следовательно, оптимальный маршрут, найденный с использованием редуцированной матрицы, оптимален и для исходной задачи.

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

В качестве начального возьмём Тогда верхняя граница длин всех маршрутов F(x 0 ) = = 65 - текущее значение Z 0 Получим редуцированную матрицу Нижняя граница d(x) = =58. в идеальном случае поиск решения заключался бы в выборе ровно одного нулевого элемента в каждой строке и каждом столбце. Другими словами, если бы такой маршрут нулевой длины мог бы быть найден, то длина оптимального маршрута равнялась бы 58 (1,2)=0, (2,1)=0, (3,1)=0, (4,2)=4, (1,5)=1, (2,3)=5, (3,4)=2, (5,2)=2. Следовательно, Arg max (r,s) C(r,s)=0 ) = (2,3). вычитаем

Верхняя граница Тогда верхняя граница длин всех маршрутов F(x 0 ) = = 65 - текущее значение Z 0 Придумаем простой путь

(1,2)=0, (2,1)=0, (3,1)=0, (4,2)=4, (1,5)=1, (2,3)=5, (3,4)=2, (5,2)=2. Следовательно, Arg max (r,s) C(r,s)=0 ) = (2,3). (5,2)=2. (1,2)=0, (2,3)=5, (3,4)=2, (1,5)=1, (2,1)=0, (3,1)=0, (4,2)=4,

(5,2)=2. (1,2)=0, (2,3)=5, (3,4)=2, (1,5)=1, (2,1)=0, (3,1)=0, (4,2)=4, Следовательно, Arg max (r,s) C(r,s)=0 ) = (2,3). «Отъехать» «Приехать» Zmin=58 Zmin=? (2,3), Zmin>= 58+5=63 не(2,3),

допустимо Левое подмножество X 1 будет содержать маршруты, которые всегда включают дугу (2,3), и поэтому вторая строка и третий столбец в матрицу C 1 не включаются. В результате будем иметь матрицу на единицу меньшего размера. Далее необходимо положить дугу с 1 (3,2)=, чтобы запретить подцикл {(2,3),(3,2)}. Оценка снизу для левого подмножества Ветвим множество имеющее меньшую оценку

(4,2)=4 С(3,4)= (4,2) запретить подцикл {(4,2)(2,3),(3,4)}. (2,3)(2,3) редуцируем Уже выбранные рёбра

Самая зловредная θ

Ответ: (3,4) (2,3)(2,3) Уже выбранные рёбра (4,1) ЗАПРЕТИТЬ (1,2) Остались (5,2) и (1,5) (1,5) (5,2) длина (2,3)(2,3)(3,4)(4,1)

Проверка / ответ Кратчайшим путём является цикл Тогда верхняя граница длин всех маршрутов F(x 0 ) = = 65 - текущее значение Z 0 (1,5) (5,2)(2,3)(2,3)(3,4)(4,1)