Контрольная работа: Задача о составлении маршрута коммивояжера. Метод ветвей и границ

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

Еще раз отметим, что задача коммивояжера является одной из самых важнейших задач в теории графов. Возможность представления (записи) различных производственных процессов на языке теории графов и умение решить сформулированную математическую задачу позволяют найти оптимальную стратегию ведения хозяйства, сэкономить ресурсы, выполнить поставленную задачу в более короткие сроки. Очевидно, что изучение методов теории графов, методов математического программирования, системного анализа и пр. – является важным этапом подготовки инженеров в МГСУ.

Список литературы

1. Н.М. Новикова «Основы оптимизации», курс лекций. М. 1998.

2. Н. Кристофидес «Теория графов. Алгоритмический подход», М., Мир, 1978.

3. С.Е. Канторер. «Методы обоснования эффективности применения машин в строительстве». М. 1969.

4. Институт математики им. С.Л. Соболева СО РАН Лаборатория «Математические модели принятия решений», статья «Метод ветвей и границ». Адрес в интернете: http://math.nsc.ru/AP/benchmarks/index.html.

5. Е.А. Тишкин«Эвристический алгоритм решения задачи коммивояжера». Публикация на сайте http://nit.itsoft.ru. Самарский государственныйаэрокосмическийуниверситет, Россия.