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

Введение

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

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

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

 

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

Этот метод является наиболее общим среди всех методов дискретного программирования и не имеет принципиальных ограничений по применению. Алгоритм… Метод ветвей и границ – один из комбинаторных методов. Его суть заключается в…  

Описание метода

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

Правила ветвления

В зависимости от особенностей задачи для организации ветвления обычно используется один из двух способов: 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