Условие задачи. 
Метод ветвей и границ. 
Теория графов. 
Решение задачи коммивояжера

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

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

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

(9).

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

(10).

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

(11).

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

(8 а).

(9 а).

(10 а).

(11 а).