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

По условию задачи «коммивояжер» выезжает из некоторого начального города и посещает другие города в количестве n-1, где n – общее количество пунктов назначения. Задается матрица расстояний (Cij) между пунктами, где i и j изменяются от 1 до n. При этом необходимо учесть следующие ограничения:

- коммивояжер въезжает в любой пункт только 1 раз;

- коммивояжер выезжает из каждого пункта только 1 раз;

- маршрут является замкнутым, без петель.

Алгоритм решения задачи коммивояжера с использованием возможностей программы Microsoft Excel или OpenOffice Calc будет состоять из следующих пунктов:

1. Определение переменных - Хij. В задаче коммивояжера Хij может принимать одно из двух возможных значений: 1 (если поездка совершается из пункта i в пункт j) или 0 (если поездка не совершается), т.е. является булевым числом.

2. Составление целевой функции. Целевая функция задачи коммивояжера - это произведение матрицы расстояний (Cij) и матрицы переменных (Хij). В Excel предусмотрена функция СУММПРОИЗВ(Cij; Хij), в OpenOffice Calc - SUMPRODUCT(Cij; Хij).

3. Описание ограничений:

- для соблюдения ограничений того, что коммивояжер въезжает и выезжает из каждого пункта только 1 раз переменные задаются булевыми и сумма значений переменных по каждому столбцу (j) и каждой строке (i) должна быть равна единице;

- для задания замкнутости маршрута и отсутствия петель необходимо ввести дополнительные переменные U и задать на листе ограничение, соответствующее формуле:

Ui – Uj + nXij ≤ n – 1, где i и j изменяются от 2 до n [1]. Соблюдение именно этого ограничения позволит определить последовательность, в которой коммивояжер должен посещать пункты назначения;

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

4. Организация данных на листе Microsoft Excel или OpenOffice Calc.

5. Вызов надстройки Excel «Поиск решения»: Меню Данные – Анализ – Поиск решения (в более ранних версиях MS Excel Меню Сервис – Поиск решения) или надстройки Calc «Решатель»: Меню Сервис – Решатель.

6. Задание «Поиску решения» или «Решателю» всех необходимых данных.

7. Получение оптимального решения.

Соблюдение описанных действий позволит найти оптимальное решение задачи коммивояжера как в MS Excel, так и в OpenOffice Calc. Однако при выборе программы следует учитывать, что надстройка «Поиск решения» устанавливает жесткие рамки на количество ограничений решаемой задачи. В частности в MS Excel удобно решать задачи с небольшим количеством пунктов (до 10), общее количество формульных ограничений в которых не превысит 100 [2]. В «Решателе» подобных ограничений нет, но с добавлением каждого дополнительного пункта в задачу программе требуется все большее количество времени на нахождение оптимального маршрута.

Список используемых источников:

1. Серая, О.В. Применение процедуры кластеризации при решении задачи коммивояжера высокой размерности с использованием генетического алгоритма [Текст] / О.В. Серая // Вестник НТУ ХПИ. - 2006. - №23. - С.164-169.

2. Поиск решений [Электронный ресурс]. – URL: http://exsolver.narod.ru/solver.html