Решение задачи коммивояжёра в Excel

Постановка задачи коммивояжера

Целевая функция:

Целевая функция задача коммивояжера

Ограничения на посещение только одного города:

Целевая функция задача коммивояжера

Решим данную задачу коммивояжера в Excel

Для начала запишем условие задачи в виде таблицы неизвестных переменных, матрицы расстояний, целевой функции и ограничений

Таблица Excel условие задачи

Формулы приведены ниже

Таблица с формулами задача коммивояжёра

Формула целевой функции

=СУММПРОИЗВ(C4:G8;C15:G19)

Затем переходим на вкладку Данные -> Поиск решения, вводим целевую функцию, вводим диапазон изменяемых ячеек переменных, ограничения, ставим галочку сделать переменные без ограничений неотрицательными, метод решения — поиск решения линейной задачи симплекс-методом и жмём Найти решение

Поиск решения

В результате получаем решение, то есть целевая функция равна 250

Решение задачи коммивояжёра в excel

Leave a Reply

Ваш e-mail не будет опубликован.