Заключение

Задача коммивояжера была поставлена в 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/.

1 http://mirslovarei.com/content_biz/Zadacha-O-Kommivojazhere-4474.html

2 http://ru.wikipedia.org/wiki/Гамильтонов-цикл

3 http://ru.wikipedia.org/wiki/Задача_коммивояжёра

4 http://pco.iis.nsk.su/ICP/Practice/dd8-3/node9.html

22