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

Продавец книг, проживающий в городе А, один раз в месяц должен посетить своих четырех клиентов, которые проживают в городах Б, В, Г и Д соответственно. Приведенная ниже таблица содержит расстояния в милях между различными городами. А Б В Г Д А 0 120 220 150 210 Б 120 0 80 110 130 В 220 110 0 160 185 Г 150 110 160 0 190 Д 210 130 185 190 0 Необходимо составить маршрут движения продавца книг, минимизирующий суммарное расстояние. Сформулируйте задачу в виде задачи о назначениях ЦЛП.

Исходная задача коммивояжера – задача целочисленная. Пусть хij=1, если продавец переезжает из i-ого города в j-ый и хij=0, если это не так. В данном случае:
городу А соответствует i=1,
городу Б соответствует i=2,
городу В соответствует i=3,
городу Г соответствует i=4,
городу Д соответствует i=5.
Количество городов n=5, коэффициенты сij – расстояние от i-го города до j-го города.
Формально введем (n+1)-ый город (т.е . 6-й город), расположенный там же, где и первый город (город А), т.е. расстояния от (n+1) города до любого другого, отличного от первого, равны расстояниям от первого города

. 6-й город), расположенный там же, где и первый город (город А), т.е. расстояния от (n+1) города до любого другого, отличного от первого, равны расстояниям от первого города