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

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

Таблица 4.1

Из пункта i	В пункт j

Рис. 4.3

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

Решение

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

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

d₁₁ + d₁₂ + d₁₃ + d₁₄ + d₁₅ = 1 или

или для произвольного i -го пункта

.

Рис. 4.4

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

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

min L = t ₁₁d_{11 +} t ₁₂d_{12 +} t ₁₃d₁₃ + t ₁₄d₁₄ +

+ t ₁₅d₁₅ + t ₂₁d₂₁ + t ₂₂d₂₂ +... + t ₅₅d₅₅,

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

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

В результате решения системы (_*) получим (рис. 5.5) следующие значения d₁₅⁰ = d₅₂⁰ = d₂₃⁰ = d₃₄⁰ = d₄₁⁰ = 1, остальные d _ij ⁰ = 0;

min L = 10 + 8 + 10 + 20 + 14 = 62.

Рис. 4.5

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