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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Насколько публикация полезна?

Нажмите на звезду, чтобы оценить!

Средняя оценка 5 / 5. Количество оценок: 2

Оценок пока нет. Поставьте оценку первым.

193

Leave a Reply

Ваш адрес email не будет опубликован.