Задача коммивояжёра

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

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

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

      Вывод к главе 2:

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

                                             А’В’Г’Б’Д’А 

Если  оставишь этот, то сотри  желтое выделение!!! 

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

                                             А’В’Д’Б’Г’А 
 

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

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

ЗАКЛЮЧЕНИЕ 

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

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

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

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

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

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

Список  использованнОЙ литературы 

Учебные пособия

1. Дулькейт В.И., Файзуллин Р.Т. Приближенное решение задачи коммивояжера методом рекурсивного построения вспомогательной кривой // вычислительные методы в дискретной математике. Омск. Изд-во Омского гос.тех.ун-та. 2009. № 1 (3). С. 72-78. 
2. Прикладное программное обеспечение для решения экономических задач: лабораторный практикум. Екатеринбург: Изд-во Ур. гос.ун-та им. А.М. Горького, 2008. 30 с.

Описание  электронного ресурса 

3. Алгоритм имитации отжига [Электронный ресурс] // URL: http://www.math.nsc.ru/AP/benchmarks/UFLP/uflp_sa.html.
4. Задачи коммивояжера [Электронный ресурс] // URL: http://window.edu.ru/window_catalog/pdf2txt?p_id=26518&p_page=7.
5. Задача – коммивояжер [Электронный ресурс] // URL: http://www.ai08.org/index.php/term/,9da4ac975b546c395b9c3ba39a8d61988dac9f39ae6c59a86e3daa98418d6c395b9c3cad9a8d609853aa9f39af6c8fa86e3dab98a7606c395b9c3c349a8d61988da99f39af6c8fac649c3ea49a5960988fb19f33416c8da56e3f3f983b616c335d9c3ea59a8f61988fb09fadaf6c8da46ea93d9a9a8d61988aaf9f39af6c8f386e3daa98418e6647716da7a4af585bac66675b595eaea9546656596052a89b5e9260645d5a9f.xhtml.
6. Задача о коммивояжере [Электронный ресурс] // URL: http://mirslovarei.com/content_biz/Zadacha-O-Kommivojazhere-4474.html.
7. Задача о коммивояжере [Электронный ресурс] // URL: http://zs7.ru/text/nauka/kommivoyager.
8. Метод ветвей и границ [Электронный ресурс] // URL:   http://pco.iis.nsk.su/ICP/Practice/dd8-3/node9.html.
9. Надстройка Microsoft Excel «Поиск решения» [Электронный ресурс] // URL: http://office.microsoft.com/ru-ru/excel-help/HP005198443.aspx.
10. Практическое применение задачи коммивояжера [Электронный ресурс] // URL: http://lmatrix.ru/news2/news2_4.html.
11. Сетевые модели/ Коммивояжер [Электронный ресурс] // URL: http://exsolver.narod.ru/NFP/NFP_salesman.html.
12. Экономико-математическое моделирование в управлении компанией: оптимизация транспортных потоков [Электронный ресурс] // URL: http://www.cig-bc.ru/library/74190/78999/.