Историческая справка
Введение
Большой класс прикладных задач оптимизации сводится к задачам целочисленного программирования. Для решения этих задач широко применяются комбинаторные методы, основанные на упорядоченном переборе наиболее перспективных вариантов. Комбинаторные методы решения можно разделить на две группы: методы динамического программирования и методы ветвей и границ.
При решении многомерных задач оптимизации предлагается совместное применение методов ветвей и границ и динамического программирования. На первом этапе задача решается методом динамического программирования отдельно по каждому из ограничений. Последовательности, полученные в результате решения функционального уравнения динамического программирования, в дальнейшем используется для оценки верхней (нижней) границы целевой функции. На втором этапе задача решается методом ветвей и границ. При использовании этого метода определяется способ разбиения всего множества допустимых вариантов на подмножества, то есть способ построения дерева возможных вариантов, и способ оценки верхней границы целевой функции.
Комплексное применение методов динамического программирования и ветвей и границ позволяет повысить эффективность решения дискретных задач оптимизации. При решении задач большой размерности с целью уменьшения членов оптимальной последовательности используются дополнительные условия отсечения.
Историческая справка
Этот метод является наиболее общим среди всех методов дискретного программирования и не имеет принципиальных ограничений по применению. Алгоритм… Метод ветвей и границ – один из комбинаторных методов. Его суть заключается в…Описание метода
В основе метода ветвей и границ лежит идея последовательного разбиения множества допустимых решений на подмножества. На каждом шаге метода элементы… Если удается отбросить все элементы разбиения, то рекорд – оптимальное решение… При применении метода ветвей и границ к каждой конкретной задаче в первую очередь должны быть определены две важнейшие…Правила ветвления
В зависимости от особенностей задачи для организации ветвления обычно используется один из двух способов: 1. ветвление множества допустимых решений исходной задачи D; 2. ветвление множества D' получаемого из D путем снятия условия целочисленности на переменные.Формирование нижних и верхних оценок целевой функции
Прежде чем начать обсуждение данного вопроса, необходимо сказать, что общепринятым является применение метода ветвей и границ для задачи, в которой… (2)Алгоритм метода ветвей и границ
Основные правила алгоритма могут быть сформулированы следующим образом: 1. Ветвлению в первую очередь подвергается подмножество с номером , которому… 2. Если для некоторого i-го подмножества выполняется условие , то ветвление его необходимо прекратить, так как…Решение задачи методом ветвей и границ
Пример
Найдем решение задачи
- целые.
Решение. Находим решение без учет целочисленности задачи симплексным методом.
Рассмотрим следующую пару задач:
Задача №1
изадача №2
Первая задача имеет оптимальный план
вторая – неразрешима.
Проверяем на целочисленность план первой задачи. Это условие не выполняется, поэтому строим следующие задачи:
Задача №1.1
и задача №1.2
Задача №1.2 неразрешима, а задача №1.1 имеет оптимальный план 
, на котором значение целевой функции 
.
В результате получили, что исходная задача целочисленного программирования имеет оптимальный план 
и 
.
Решение задачи коммивояжера методом ветвей и границ
Рассмотрим теперь класс прикладных задач оптимизации. Метод ветвей и границ используется в очень многих из них. Предлагается рассмотреть одну из…Постановка задачи
Формализуем условие в терминах теории графов. Города будут вершинами графа, а дороги между городами – ориентированными (направленными) ребрами… Очевидно, в полном орграфе циклы указанного выше типа есть. Заметим, что… Отсюда следует, что задачу о коммивояжере достаточно решить для полных орграфов с весовой функцией. Сформулируем…Условие задачи
Студенту Иванову поручили разнести некоторые важные документы из 12-ого корпуса. Но, как назло, у него на это очень мало времени, да и еще надо…Математическая модель задачи
Для решения задачи присвоим каждому пункту маршрута определенный номер: 12-ый корпус – 1, Белый дом – 2, КРК «Премьер» – 3, Администрация – 4 и 5-ый… (8)Решение задачи методом ветвей и границ
задача коммивояжер ветвь граница
Анализ множества D.
=> ;Отсев неперспективных подмножеств.
; Подмножества D13 и D15 неперспективные. Т.к. , но , то далее будем рассматривать подмножество D14.Отсев неперспективных подмножеств
; Подмножество D143 неперспективное. Т.к. , но , то далее будем рассматривать подмножество D145.Список литературы
1. Абрамов Л.А., Капустин В.Ф. Математическое программирование. – Л.: Изд-во ЛГУ, 1981. -328 с.
2. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. – М.: Наука, 1987. -294 с.
3. Корбут А.А., Финкелгейн Ю.Ю. Дискретное программирование. М.: Наука. 1969. -240 с
4. Кузнецов Ю.Н. и др. Математическое программирование: Учебное пособие. – 2-е изд., перераб и доп. – М.: Высшая школа, 1980. -300 с.
5. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. – М.: Мир, 1985. -213 с.
Размещено на Allbest.ru