Задача коммивояжера в эксель – Поиск решения MS EXCEL (6.2). Задача коммивояжера (полный граф, нелинейная модель)

Поиск решения MS EXCEL (6.2). Задача коммивояжера (полный граф, нелинейная модель)

Решим один из вариантов задачи коммивояжера для небольшого количества городов (5-10) с помощью надстройки Поиск решения. Построим нелинейную модель.

Рассмотрим задачу коммивояжера (англ. Travelling Salesman Problem, TSP) заключающуюся в отыскании самого короткого маршрута, проходящего через заданные города по одному разу с последующим возвратом в исходный город (также рассмотрим вариант без возврата).

Задача

Найдем кратчайший путь между 5 городами, координаты которых известны. Рассмотрим замкнутый вариант задачи: коммивояжёру требуется посетить все города, после чего вернуться в исходный город.

Решение

Так как даны координаты городов, то сначала найдем расстояния между ними (см. файл примера, лист 5 городов).


Расстояния рассчитаем с помощью формулы:
=КОРЕНЬ((ИНДЕКС($C$7:$D$11;$F7+1;1)-ИНДЕКС($C$7:$D$11;G$6+1;1))^2 +(ИНДЕКС($C$7:$D$11;$F7+1;2)-ИНДЕКС($C$7:$D$11;G$6+1;2))^2)

Теперь создадим модель для Поиска решения.

Совет: Вводная статья про Поиск решения в MS EXCEL 2010 находится здесь.

Переменные (выделено зеленым). В качестве переменных модели следует взять номера городов. Так как начальная и конечная точка известны (Город0), то переменных будет 4.
Ограничения (выделено синим). Необходимо, чтобы номера городов не повторялись. Это означает, что количество уникальных (неповторяющихся) номеров городов должно быть равно 4. Для этого используется формула для подсчета уникальных значений:
=СУММПРОИЗВ(1/СЧЁТЕСЛИ(B16:B19;B16:B19))

Целевая функция (выделено красным). Длина маршрута должна быть минимальной.

Примечание: для удобства настройки Поиска решения используются именованные диапазоны.

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

Найденное Решение

Поиск решения найдет (должен найти) самый короткий маршрут, т.е. последовательность 0-1-4-2-3-0 (или обратную).

В этой простейшей задаче можно проверить, действительно ли этот маршрут имеет минимальную длину, путем перебора всех вариантов маршрутов. Это реализовано в файле примера.

Совет. Таблицы перебора перестановок от 1 до 5, от 1 до 6, … от 1 до 9 можно найти в этой статье Перебор всех возможных Перестановок в MS EXCEL.

Результаты Эволюционного метода сильно зависят от начальных условий и параметров его настройки (скорость изменения, размер совокупности). Повторный поиск, с теми же начальными условиями и параметрами, может привести к различным результатам. Убедиться в этом можно с помощью модели, созданной в файле примера на листе 11 городов.

Обнулите значения переменных модели на Листе 11 городов, запустите

Поиск решения. После окончания поиска (может занять несколько минут) опять обнулите значения переменных и перезапустите Поиск решения: найденные решения могут серьезно отличаться.

Совет. Иногда, для того чтобы улучшить найденное решение, помогает следующий прием: запустите Поиск решения, сохраните найденное решение, измените параметры поиска (например, размер совокупности), повторно запустите Поиск решения.

В файле примера также приведено решение задачи для замкнутого и незамкнутого маршрута посещения 9 городов. Решения найдены с помощью Эволюционного метода со следующими параметрами: Целочисленная оптимальность 0%, Использовать автоматическое масштабирование, Скорость изменения варьировалась 0,25-0,5; Размер совокупности варьировался 10-50.
Оба решения проверены с помощью таблиц перебора всех маршрутов (см. таблицы перебора перестановок). Если при первом прогоне Поиска решения не удавалось найти оптимальное решение, то он запускался повторно, при этом 1 или 2 параметра изменялись. После второго прогона оптимальное решение, как правило, было найдено.


Вывод: задачу коммивояжера (граф полностью связный, гамильтоновый цикл) можно решить стандартным Поиском решения с помощью построения нелинейных моделей. При количестве вершин графа (городов) <10 найденное решение можно проверить с помощью таблиц перебора перестановок, т.к. Эволюционный метод не гарантирует, что найденный путь является кратчайшим. Поиск решения может продолжаться значительное время.
Однако, более лучшей альтернативой решения этой задачи в MS EXCEL является построение линейной модели (см. статью Поиск решения MS EXCEL (6.3). Задача коммивояжера (полный граф, линейная модель)) или написание программы на VBA.

Совет: Решение задачи о поиске кратчайшего пути между 2-мя заданными городами можно найти в статье Поиск решения MS EXCEL (6.4). Кратчайший путь (неполный граф, линейная модель).

 

excel2.ru

Решение задачи коммивояжера при помощи надстройки MS Excel «Поиск решения»

Метод полного перебора

Мощным средством анализа данных MS Excel является надстройка «Поиск решения». С ее помощью можно определить, при каких значениях указанных влияющих ячеек формула в целевой ячейке принимает нужное значение (минимальное, максимальное или равное какой-либо величине). Для процедуры поиска решения можно задать ограничения, причем не обязательно, чтобы при этом использовались те же влияющие ячейки, данные которых, определяют значение целевой ячейки. Для расчета заданного значения применяются различные математические методы поиска. Вы можете установить режим, в котором полученные значения переменных автоматически заносятся в таблицу. Кроме того, результаты работы программы могут быть оформлены в виде отчета.

Программа Поиск решений – дополнительная надстройка табличного процессора MS Excel, которая предназначена для решения определенных систем уравнений, линейных и нелинейных задач оптимизации, используется с 1991 года.

Размер задачи, которую можно решить с помощью базовой версии этой программы, ограничивается такими предельными показателями: количество неизвестных (decision variable) – 200; количество формульных ограничений (explicit constraint) на неизвестные – 100; количество предельных условий (simple constraint) на неизвестные – 400.

Постановка задачи коммивояжера, которую необходимо решить посредством надстройки «Поиск решения» методом полного перебора следующая:

«Сотруднику компании ООО «Новые технологии» Петрову Н.И. необходимо обновить программный продукт автоматизированного учета в пяти организациях: А, Б, В, Г и Д. Он решил начать свой обход с организации «А», так как она находится на первом этаже дома, в котором проживает Петров. Сотруднику необходимо, спланировать свой маршрут таким образом, чтобы к концу рабочего дня обойти все организации в определенном порядке и выполнив свою работу, вернутся домой (в пункт «А»). В каком порядке Петрову следует обходить организации, чтобы его замкнутый тур был кратчайшим? Если расстояния между каждой парой организаций заданы следующей квадратной матрицей (5x5):



 

 

Решение: Разместим исходные данные на рабочем листе (рис 2.1). Заменим знак числом 10000 (на результат решения исключение пути не оказывает влияния).

 
 

 

Рисунок 2.1 Исходные данные задачи

Вводим формулы:

 

Таблица 1

Ячейка Формула Примечание
B9 = СУММ(B4:B8) Распространяем на диапазон B9:F9
G4 = СУММ(B4:F4) Распространяем на диапазон G4:G8
C19 =СУММПРОИЗВ(B4:F8;B13:F17) Целевая функция
E19 =B4+C5+D6+E7+F8 Исключение пути
B23 =$C$10-C10+4*C5 Распространяем на диапазон B23:E23
B24 =$D$10-C10+4*C6 Распространяем на диапазон B24:E24
B25 =$E$10-C10+4*C7 Распространяем на диапазон B25:E25
B26 =$F$10-C10+4*C8 Распространяем на диапазон B26:E26

 

Сценарий решения.

1. Запускаем надстройку MS Excel «Поиск решения» командой Сервис/ Поиск решения. И заполняем (рис. 2.2).

2. Для того чтобы выполнялись условия однократного посещения сотрудником организаций и в то же время запланированный Петровым маршрут был пройден полностью, введем ограничения: в строки B9, G4 заводим формулы из таблицы 1 и распространяем их на соответствующие диапазоны B9:F9 и G4:G8. Задаем следующие данные $B$9:$F$9=1 и $G$4:$G$8=1 в Ограничения окна «Поиск решения». Таким образом, мы можем отследить порядок обхода организаций сотрудником, оценить правильность выбора и оптимальность его маршрута.

3. Выбираем ячейку B19 и устанавливаем ее адрес в Целевую ячейку окна «Поиск решения», чтобы определить длину наикратчайшего маршрута. Для этого в ячейку B19 предварительно заносим соответствующую формулу из таблицы 1. Когда программа «Поиск решения» вычислит оптимальный маршрут Петрова и станет известен порядок обхода организаций (из Матрицы переменных) будут известны и расстояния между конкретными парами организаций. Затем при помощи простых математических подсчетов программа рассчитает протяженность оптимального маршрута.

4. Устанавливаем еще одно ограничение в окно «Поиск решения»: $E$19=0. В указанную ячейку вводим формулу из таблицы 1 и исключаем таким образом, заведомо ложный порядок движения Петрова в порядке обхода организаций.

5. В связи с тем, что ячейки диапазона B4:F8 – изменяемые, в Ограничение окна «Поиск решения» необходимо добавить строку B$4$:F$8$=двоичное.

6. Заводим в ячейки B23; B24; B25; B26 соответствующие формулы из таблицы 1 и распространяем их на следующие диапазоны: B23:E23 B24:E24; B25:E25; B26:E26 для учета всех возможных вариантов обхода организаций сотрудником и выбора из них оптимального. Формулы задаем таким образом, чтобы обеспечить исключение ложного пути, соблюдая условие задачи об обходе всех организаций по одному разу.

7. Добавляем в Ограничения окна «Поиск решения» $B$23:$E$26 ≤ 3.

 

 
 

 

 

 

Рисунок 2.2 Окно «Поиск решения»

 

Так как это линейная модель, то необходимо фиксировать в окне Параметры поиска решений на позицию Линейная модель и Неотрицательные значения (рис. 2.3). После того, как все поля и ячейки заполнены нажимаем кнопку «Выполнить» и появляется окно диалога с описанием результатов процесса оптимизации. Чтобы отобразить найденное решение в ячейках листа, устанавливаем переключатель «Сохранить найденное решение» и нажимаем кнопку ОК. Найденная минимальная величина помещается в целевую ячейку, а переменные ячейки заполняются оптимальными значениями переменных, которые удовлетворяют установленным ограничениям.

 

 

 

Рисунок 2.3 Окно «Параметры поиска решения»

Таким образом, получаем следующий результат. Если Петров переходит из организации в организацию, то на рис. 2.4 в диапазоне B4:F8 мы будем наблюдать порядок его перемещений. Если видим, что в ячейке, которая отнесена к организации «В» стоит единица, значит сотрудник посетил эту организацию следующей за пунктом «А». Если в ячейке ноль – сотрудник организацию не посещал.

 

 

 
 

 

Рисунок 2.4 Результаты решения задачи коммивояжера

Вывод:

 

 

В ходе анализа полученных результатов, приходим к выводу: наиболее оптимальным маршрут Петрова будет в том случае, если он начал свой путь с организации «А», посетит другие организации в следующем порядке «В», затем «Д», далее «Б» и «Г», из которой вернется к началу своего пути (в организацию «А»). представим путь схематически:

А’В’Д’Б’Г’А

 

 

Длина кратчайшего маршрута (значение целевой ячейки) в результате составит – 21.

Задача решена. Кратчайший маршрут Петрова найден.

 

 

ЗАКЛЮЧЕНИЕ

Задача коммивояжера была поставлена в 1934 году. Ее сущность заключается в поиске оптимального маршрута движения при необходимости посетить все запланированные объекты с наименьшими финансовыми и временными издержками. Как правило, речь идет о простом перемещении по заданным точкам, либо с перевозкой груза небольшого формата на транспортном средстве.

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

Среди современных практических приложений задачи можно выделить: доставку продуктов в магазин со склада, работу почтальона по разноске корреспонденции, мониторинг объектов (нефтяные вышки, базовые станции сотовых операторов), изготовление отверстий на специализированном станке.

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

В работе была поставлена задача, сводимая к задаче коммивояжера, и составлена схема оптимального маршрута, подробно рассмотрен порядок выбора кратчайшего пути при помощи использования надстройки MS Excel «Поиск решения» методом полного перебора. Результаты решения были выведены на отдельный рабочий лист Excel.

Изучение особенностей задачи коммивояжера позволило сделать следующий вывод: актуальным в настоящее время остается поиск точных и приближенных способов решения этой задачи как с теоретической, так и с практической точек зрения. Более того, темпы современной жизни меняют отношение человека ко времени, сегодня пользователь не любит ждать, изыскивает возможности сократить время ожидания, найти оптимальное решение в кратчайшие сроки. Все это свидетельствует о росте в будущем потребности в эффективном решении задач коммивояжера и иных родственных им оптимизационных задач, которые позволили бы существенно сэкономить ограниченные ресурсы организаций.

 

Министерство образования и науки РФ

ГБОУ СПО «Шадринский политехнический колледж»

 

Заведующая учебной частью

____________ Блинова Н.А.

«____»______________20__г

 

Курсовая работа

по дисциплине «Математические методы»

на тему «Задача о коммивояжере. Метод полного перебора»

»

 

Студента: _________/Рудакова М.В./

Руководитель: _____________/Ханина О.В./

 

Шадринск, 2012 г.


Рекомендуемые страницы:


Воспользуйтесь поиском по сайту:

megalektsii.ru

6.2 Решение вExcel

Коммивояжеру, находящемуся в Париже, необходимо посетить три города. Он получил информацию о стоимости проезда самолетом в каждый из выбранных городов и стоимость проезда из одного города в другой. На основе добытых данных он составил матрицу стоимостей (см. табл.) проезда в выбранные города и обратно. Зная матрицу стоимостей коммивояжеру надо так составить маршрут путешествия, чтобы затраты на путешествие были бы минимальными и чтобы выполнялось требование: каждый пункт посещается только один раз.

Прибыл в

Выехал из

Париж

Берлин

Рим

Лондон

Париж

270

430

160

Берлин

70

160

10

Рим

200

130

350

Лондон

210

160

250

Вид электронной таблицы, созданной для решения задачи, представлен на рис. 1.

Рисунок 1

Здесь заданы стоимости проезда из города в город (блок B3:E6). Значения переменных располагаются в блоке B10:E13.

Для вычислений необходимо задать размерность задачи n(количество городов) — ячейкаG19.

Целевая функция расположена в ячейке G14. Ограничения находятся в блоках B14:E14 (коммивояжер въезжает один раз в каждый город) и F10:F13 (коммивояжер выезжает из каждого города один раз). В задаче коммивояжера есть ряд специфических ограничений по дополнительным переменным(см. мат модель). Формулы этих ограничений находятся в блоке ячеек B20:D22. Значения самих переменных располагаются в блокеC16:E16.

Вид электронной таблицы в режиме отображения формул представлен на рис. 2.

Рисунок 2

На рис. 3 представлена запись условий задачи в окне «Поиск решения». Хотя дополнительные переменные не относятся к целевой функции, они, также как и , являются изменяемыми, поэтому адреса содержащих их ячеек должны быть введены в поле Изменяя ячейки одновременно с адресами переменных целевой функции (через «;»).

Рисунок 3

По результатам поиска решения найден ответ задачи: из Парижа коммивояжер летит в Лондон, оттуда в Рим, затем в Берлин, откуда возвращается в Париж. Общая стоимость перелета составит 610 д. е. (см. рис. 4).

Рисунок 4

Задание 3. Решить задачу коммивояжера

Зная расстояния между населенными пунктами коммивояжеру надо так составить маршрут путешествия, чтобы каждый пункт посещался только один раз и затраты времени на путешествие были бы минимальными. Матрица расстояний (стоимостей переезда) представлена в виде:

Вариант 1

прибыл в

выехал из

1

2

3

4

5

1

1

2

5

2

2

1

5

6

4

3

6

3

4

2

4

5

1

1

5

5

4

3

4

2

Вариант 2

прибыл в

выехал из

1

2

3

4

5

1

2

4

10

4

2

1

15

6

4

3

6

3

14

2

4

5

21

10

5

5

14

3

4

7

Вариант 3

прибыл в

выехал из

1

2

3

4

5

1

2

30

1

4

2

1

5

6

2

3

6

12

8

12

4

5

6

10

7

5

14

13

14

7

Вариант 4

прибыл в

выехал из

1

2

3

4

5

1

2

5

2

1

2

4

6

5

1

3

2

4

3

6

4

1

1

5

4

5

4

3

4

5

Вариант 5

прибыл в

выехал из

1

2

3

4

5

1

12

40

1

14

2

10

15

16

7

3

6

12

8

12

4

15

16

11

9

5

14

13

14

7

Вариант 6

прибыл в

выехал из

1

2

3

4

5

1

12

23

4

14

2

9

15

10

5

3

12

8

6

12

4

11

9

12

16

5

14

13

10

8

Вариант 7

прибыл в

выехал из

1

2

3

4

5

1

10

2

7

3

2

3

4

2

1

3

2

12

5

4

4

7

3

11

6

5

14

2

8

2

Вариант 8

прибыл в

выехал из

1

2

3

4

5

1

1

14

9

6

2

2

12

4

4

3

3

6

11

1

4

5

9

21

10

5

14

43

4

7

Вариант 9

прибыл в

выехал из

1

2

3

4

5

1

2

4

10

4

2

1

15

6

4

3

6

3

14

2

4

5

21

10

5

5

14

3

7

3

Вариант 10

прибыл в

выехал из

1

2

3

4

5

1

12

5

6

11

2

5

8

3

4

3

10

6

2

3

4

1

2

4

4

5

3

2

5

7

Вариант 11

прибыл в

выехал из

1

2

3

4

5

1

2

22

9

4

2

1

6

2

5

3

8

11

7

12

4

4

9

8

6

5

9

10

14

12

Вариант 12

прибыл в

выехал из

1

2

3

4

5

1

20

15

2

9

2

5

7

12

3

3

2

10

3

6

4

11

3

5

14

5

4

5

4

8

Вариант 13

прибыл в

выехал из

1

2

3

4

5

1

1

2

5

2

2

1

5

6

4

3

6

3

4

2

4

5

1

1

5

5

4

3

4

2

Вариант 14

прибыл в

выехал из

1

2

3

4

5

1

12

5

6

11

2

5

8

3

4

3

10

6

2

3

4

1

2

4

4

5

3

2

5

7

Вариант 15

прибыл в

выехал из

1

2

3

4

5

1

2

4

10

4

2

1

15

6

4

3

6

3

14

2

4

5

21

10

5

5

14

3

7

3

Вариант 16

прибыл в

выехал из

1

2

3

4

5

1

11

25

3

14

2

9

15

6

17

3

5

5

12

10

4

11

9

16

15

5

7

12

14

10

Контрольные вопросы

  1. Перечислите этапы решения задач оптимизации

  2. Какие виды задач можно решать методами линейного программирования?

  3. Опишите процедуру задания ограничений при решении задач оптимизации

  4. Дайте определение компьютерной модели

  1. В чем заключается отличие компьютерной и математической модели поставленной задачи?

  2. Как задается метод решения при поиске оптимального решения задачи?

  3. Что понимается под целевой ячейкой?

  4. Дайте определение теневой цены.

  5. Зачем необходимо проводить анализ чувствительности решения?

  6. Что понимается под оптимальным решением задачи?

45

studfiles.net

Поиск решения MS EXCEL (6.3). Задача коммивояжера (полный граф, линейная модель)

Решим один из вариантов задачи коммивояжера для небольшого количества городов (5-10) с помощью надстройки Поиск решения. Построим линейную модель.

Рассмотрим задачу коммивояжера (англ. Travelling Salesman Problem, TSP) заключающуюся в отыскании самого короткого маршрута, проходящего через заданные города по одному разу с последующим возвратом в исходный город (также рассмотрим вариант без возврата). Подобная задача решена в статье Поиск решения MS EXCEL (6.2). Задача коммивояжера (полный граф, нелинейная модель) с помощью нелинейной модели.

Задача

Найдем кратчайший путь между 5 городами, координаты которых известны. Сначала рассмотрим замкнутый вариант задачи: коммивояжёру требуется посетить все города, после чего вернуться в исходный город.

Создание модели

Так как даны координаты городов, то сначала найдем расстояния между ними (см. файл примера, лист 5 городов).

Расстояния рассчитаем с помощью формулы:
=КОРЕНЬ((ИНДЕКС($C$7:$D$11;$A16+1;1)-ИНДЕКС($C$7:$D$11;B$15+1;1))^2+(ИНДЕКС($C$7:$D$11;$A16+1;2)-ИНДЕКС($C$7:$D$11;B$15+1;2))^2)

Теперь создадим модель для Поиска решения.

Совет: Вводная статья про Поиск решения в MS EXCEL 2010 находится здесь.

Переменные (выделено зеленым). В качестве переменных модели следует взять номера всех маршрутов соединяющих города. Маршрут из города 0 в город 1 эквивалентен маршруту из 1 в 0, так как направление обхода городов не имеет значения. Необходимо соединить все города (полный граф).

Ограничения (выделено синим). Необходимо, чтобы из каждого города был 1 входящий и 1 исходящий маршрут.

Целевая функция (выделено красным). Длина маршрута должна быть минимальной.

Примечание: для удобства настройки Поиска решения используются именованные диапазоны.

Найденное Решение

Поиск решения гарантировано найдет самый короткий маршрут, т.к. построенная нами модель линейная.

Данную задачу можно решить для максимального количества городов =20, т.к. число маршрутов (ребер) вычисляется по формуле n*(n-1)/2, а количество переменных у Поиска решения ограничено 200.

Также в файле примера приведено решение задачи для прохождения 5 городов по незамкнутому маршруту, а также задачу для 9 городов.

Совет: Решение задачи о поиске кратчайшего пути между 2-мя заданными городами можно найти в статье Поиск решения MS EXCEL (6.4). Кратчайший путь (неполный граф, линейная модель).

excel2.ru