Задача о коммивояжере (стр. 3 )

Таблица 10.

	1	2	3	4	5
1	¥	7	2	9	0
2	10	¥	0	10	5
3	5	3	¥	0	0
4	12	0	3	¥	7
5	¥	0	0	0	¥
b	5	0	0	0	0

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

Таблица 11.

	1	2	3	4	5
1	¥	7	2	9	02
2	5	¥	05	10	5
3	05	3	¥	00	00
4	7	03	3	¥	7
5	¥	00	00	00	¥

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

Таблица 12.

	1	2	3	4	5
1	¥	7	¥	9	02
2	5	¥	05	10	5
3	05	3	¥	00	00
4	7	03	3	¥	7
5	¥	00	00	00	¥

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

Таблица 13.

	2	3	4	5
1	7	¥	9	012
2	¥	05	10	5
4	03	3	¥	7
5	00	¥	09	¥

Далее выполняется разбиение множества на два подмножества: и (табл. 14, рис. 1).

Таблица 14.

	2	3	4
2	¥	013	10
4	03	3	¥
5	00	¥	010

На последней итерации множество разбивается на два подмножества: и (табл. 15, рис. 1).

Таблица 15.

	2	4
4	0¥	¥
5	¥	0¥

Результат решения задачи может быть представлен в виде матрицы перездов вида:

.

или в виде маршрута: . Стоимость оптимального маршрута (значение целевой функции) составляет: z=50.

Контрольные вопросы

1. Чем отличается модель задачи о коммивояжере от модели задачи о назначении? Можно ли решить задачу о коммивояжере методом потенциалов? Почему?

2. Объясните шаги алгоритма метода ветвей и границ для задачи о коммивояжере на произвольном примере.