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

Пример. Пусть имеются пять пунктов, соединенных между собой дорогами так, что из любого пункта можно проехать в любой другой пункт (рис. 11). Известно время перевозки из пункта i в пункт j (табл. 17).

Таблица 17

Рис. 11

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

Решение. Для решения этой задачи необходимо соста­вить математическую модель. Введем обозначения: i и j; - номера пунктов выезда и въезда; tij - время переезда из пункта i в пункт j. Из табл. 17 видно, что tij в общем случае может быть не равно времени переезда в обратном направлении (например, когда один пункт на вершине горы, а другой - у ее подножия). Введем булевы переменные:

Составим модель (рис. 12).

Рис. 12

Из п. 1 можно выехать в любой из п. 2 или 5, или 3, или 4, или остаться в п. 1. Но при этом можно выехать только в одном единственном на­правлении. Это условие можно записать так:

или

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

Условие въезда в п. 1 аналогично условию выезда из п. 1 (рис. 12). Требование минимальной продолжительно­сти маршрута запишется в виде целевой функции:

где t_ij берутся из исходной таблицы, а δ_ij - искомые пере­менные.

Тогда всю задачу можно сформулировать:

В результате решения системы (*) получим (рис. 13) следующие значения остальные

Переходя от частной к общей постановке, задачу комми­вояжера можно сформулировать как:

Рис. 13

Поиск по сайту: