рефераты конспекты курсовые дипломные лекции шпоры

Раздел История
/
Алгоритм метода ветвей и границ

Реферат Курсовая Конспект

Выберите учебное заведение

Алгоритм метода ветвей и границ

Алгоритм метода ветвей и границ - раздел История, Историческая справка Основные Правила Алгоритма Могут Быть Сформулированы Следующи...

Основные правила алгоритма могут быть сформулированы следующим образом:

1. Ветвлению в первую очередь подвергается подмножество с номером , которому соответствует наименьшее значение нижней оценки целевой функции (I – это множество номеров всех подмножеств, (или ), находящихся на концах ветвей и ветвление которых еще не прекращено). Если реализуется изложенный выше способ ветвления множеств , то может возникнуть неоднозначность относительно выбора компоненты, по которой необходимо осуществлять очередной шаг ветвления. К сожалению, вопрос о «наилучшем» способе такого выбора с общих позиций пока не решен, и поэтому в конкретных задачах используются некоторые эвристические правила.

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

3. Ветвление подмножества прекращается, если найденное в задаче (4) оптимальное решение . Обосновывается это тем, что , и, следовательно, лучшего допустимого решения, чем в этом подмножестве не существует. В этом случае рассматривается возможность корректировки .

4. Если , где , то выполняются условия оптимальности для найденного к этому моменту лучшего допустимого решения. Обоснование такое же, как и пункта 2 настоящих правил.

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

(7)

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Историческая справка

Большой класс прикладных задач оптимизации сводится к задачам целочисленного программирования Для решения этих задач широко применяются... При решении многомерных задач оптимизации предлагается совместное применение... Комплексное применение методов динамического программирования и ветвей и границ позволяет повысить эффективность...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Алгоритм метода ветвей и границ

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Историческая справка
Впервые метод ветвей и границ был предложен Лендом и Дойгом в 1960 для решения общей задачи целочисленного линейного программирования. Интерес к этому методу и фактически его «второе рождение» связ

Описание метода
В основе метода ветвей и границ лежит идея последовательного разбиения множества допустимых решений на подмножества. На каждом шаге метода элементы разбиения подвергаются проверке д

Правила ветвления
задача коммивояжер ветвь граница В зависимости от особенностей задачи для организации ветвления обычно используется один из двух способов: 1. ветвление множества допустимых решени

Формирование нижних и верхних оценок целевой функции
Прежде чем начать обсуждение данного вопроса, необходимо сказать, что общепринятым является применение метода ветвей и границ для задачи, в которой направление оптимизации приведено

Решение задачи методом ветвей и границ
Пусть

Решение задачи коммивояжера методом ветвей и границ
Рассмотрим теперь класс прикладных задач оптимизации. Метод ветвей и границ используется в очень многих из них. Предлагается рассмотреть одну из самых популярных задач – задача комм

Постановка задачи
Формализуем условие в терминах теории графов. Города будут вершинами графа, а дороги между городами – ориентированными (направленными) ребрами графа, на каждом из которых задана вес

Условие задачи
Студенту Иванову поручили разнести некоторые важные документы из 12-ого корпуса. Но, как назло, у него на это очень мало времени, да и еще надо вернуться обратно. Нужно найти кротча

Математическая модель задачи
Для решения задачи присвоим каждому пункту маршрута определенный номер: 12-ый корпус – 1, Белый дом – 2, КРК «Премьер» – 3, Администрация – 4 и 5-ый корпус – 5. Соответственно общее

Анализ множества D.
Найдем оценку снизу Н. Для этого определяем матрицу минимальных расстояний по строкам (1 где расстояние минимально в строке).

Отсев неперспективных подмножеств.
; Подмножества D13 и D15 неперспективные.

Отсев неперспективных подмножеств
; Подмножество D143 неперспективное. Т.к.