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

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

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

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

Цель работы.

Целью данной работы будет:

1. Познакомить читателя с основными понятиями теории графов.

2. Дать представление о задаче коммивояжера.

3. Описать метод ветвей и границ.

4. Привести пример использования метода ветвей и границ для решения задачи коммивояжера.