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