Решение задачи коммивояжера методом ветвей и границ
Решение задачи коммивояжера методом ветвей и границ - раздел История, Историческая справка
Рассмотрим Теперь Класс Прикладных Задач Оптимизации. Метод В...
Рассмотрим теперь класс прикладных задач оптимизации. Метод ветвей и границ используется в очень многих из них. Предлагается рассмотреть одну из самых популярных задач – задача коммивояжера. Вот ее формулировка. Имеется несколько городов, соединенных некоторым образом дорогами с известной длиной; требуется установить, имеется ли путь, двигаясь по которому можно побывать в каждом городе только один раз и при этом вернуться в город, откуда путь был начат («обход коммивояжера»), и, если таковой путь имеется, установить кратчайший из таких путей.
Большой класс прикладных задач оптимизации сводится к задачам целочисленного программирования Для решения этих задач широко применяются... При решении многомерных задач оптимизации предлагается совместное применение... Комплексное применение методов динамического программирования и ветвей и границ позволяет повысить эффективность...
Историческая справка
Впервые метод ветвей и границ был предложен Лендом и Дойгом в 1960 для решения общей задачи целочисленного линейного программирования. Интерес к этому методу и фактически его «второе рождение» связ
Описание метода
В основе метода ветвей и границ лежит идея последовательного разбиения множества допустимых решений на подмножества. На каждом шаге метода элементы разбиения подвергаются проверке д
Правила ветвления
задача коммивояжер ветвь граница
В зависимости от особенностей задачи для организации ветвления обычно используется один из двух способов:
1. ветвление множества допустимых решени
Формирование нижних и верхних оценок целевой функции
Прежде чем начать обсуждение данного вопроса, необходимо сказать, что общепринятым является применение метода ветвей и границ для задачи, в которой направление оптимизации приведено
Алгоритм метода ветвей и границ
Основные правила алгоритма могут быть сформулированы следующим образом:
1. Ветвлению в первую очередь подвергается подмножество с номером
Постановка задачи
Формализуем условие в терминах теории графов. Города будут вершинами графа, а дороги между городами – ориентированными (направленными) ребрами графа, на каждом из которых задана вес
Условие задачи
Студенту Иванову поручили разнести некоторые важные документы из 12-ого корпуса. Но, как назло, у него на это очень мало времени, да и еще надо вернуться обратно. Нужно найти кротча
Математическая модель задачи
Для решения задачи присвоим каждому пункту маршрута определенный номер: 12-ый корпус – 1, Белый дом – 2, КРК «Премьер» – 3, Администрация – 4 и 5-ый корпус – 5. Соответственно общее
Анализ множества D.
Найдем оценку снизу Н. Для этого определяем матрицу минимальных расстояний по строкам (1 где расстояние минимально в строке).
Новости и инфо для студентов