Введение

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

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

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

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

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

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

---

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

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

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

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

задача коммивояжер ветвь граница

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

1. 
   ветвление множества допустимых решений исходной задачи D;
   
2. 
   ветвление множества D' получаемого из D путем снятия условия целочисленности на переменные.
   

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

---

Второй способ ветвления –более универсальный, чем первый. Для осуществления ветвления некоторой области D_i' этим способом на D_i' решается оптимизационная задача с целевой функцией исходной задачи и действительными переменными.

Ветвление осуществляется, если в оптимальном решении значение хотя бы одной целочисленной по исходной постановке задача переменной не является целочисленным. Среди этих переменных выбирается одна, например j – я. Обозначим ее значение в найденном оптимальном решении x⁰[j]. Говорят, что ветвление осуществляется по переменной x[j]. Область D_i' разделяется на две подобласти D_i1' и D_i2' следующим образом:
(1)
где [x⁰[j]] –целая часть значения x⁰[j]

На рис. 2 условно дана геометрическая интерпретация такого ветвления.



Рис. 2. Геометрическая интерпретация ветвления
Видно, что при этом из области D_i' удаляется часть между плоскостями вновь введенных ограничений. Так как переменная x[j] по условиям области допустимых решений исходной задачи –целочисленная, то из подобласти допустимых решений исходной задачи. D_i(D_i D_i') при таком изъятии не исключается ни одного решения.

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

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

---

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

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

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

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

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


Вывод

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

Содержание:

1. 
   Введение
   
2. 
   Историческая справка
   
3. 
   Описание метода
   
4. 
   Правила ветвления
   
5. 
   Алгоритм метода ветвей и границ
   
6. 
   Вывод
   
7. 
   Список литературы
   

---

Список использованных литератур:

1. Абрамов Л.А., Капустин В.Ф. Математическое программирование. – Л.: Изд-во ЛГУ, 1981. -328 с.

2. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. – М.: Наука, 1987. -294 с.

3. Корбут А.А., Финкелгейн Ю.Ю. Дискретное программирование. М.: Наука. 1969. -240 с

---

Смотрите также файлы

• 6. 3 Генетический полиморфизм полиморфизм единичного нуклеотида (snp).docx

• Конспект по предмету русский язык.docx

• Отчет по дисциплине интеллектуальные информационные системы по лабораторной работе 4 Рекурсивные программы.docx

• Другой пример апперцепции.docx

• Методические указания к выполнению выпускной квалификационной работы для студентов высших учебных заведений, обучающихся по специальности.doc