Содержание:

Введение. 2

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

2. Алгоритм
метода ветвей и границ для ЗЛП.. 6

Заключение. 13

Список
использованной литературы.. 15

Введение:

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

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

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

аппарата.

Для этого применяют
специальные научные методы, объединенные общей названием «исследование
операций».

Как самостоятельное научное направление
«исследование операций» возникло и получило свое название во время Второй
мировой войны для решения проблем и наилучшей организации боевых действий, а
также прогнозирования их последствий. С помощью методов исследования операций
планировали стратегические и тактические операции в условиях неполноты знаний о
состоянии вооруженных сил противника.

Заключение:

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

бесперспективных вариантов.

Впервые метод ветвей и
границ был предложен в 1960 году А. Лендом (A. Land) и Дж. Дойг (G. Doig) для
решения полностью целочисленных и частично-целочисленных задач линейного
программирования.

Позже в 1965 году Э.
Белес (E. Balas) разработал аддитивный алгоритм для решения задач из двоичными
переменными.

Этот алгоритм с
вычислительной точки зрения оказался настолько простым (в основном используя
только операции сложения и вычитания), который рассматривали как возможный
прорыв в методах решения задач целочисленного линейного программирования (ЦЛП)
общего вида [1, с. 126].

Согласно общей идее
метода, сначала поставленная задача решается как задача линейного
программирования.

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

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

В основе метода ветвей и
границ лежит идея последовательного разбиения множества допустимых решений на
подмножества. На каждом шагу метода элементы разбиения подлежат проверке для
выяснения, содержит ли данное подмножество оптимальное решение [2, с. 94].
Рассмотрим метод границ и ветвей подробнее.

Сначала, как и в случае
метода Гомори, симплексным методом решается более простая (без условий
целочисленности) задача. Затем вводится правило перебора.

Результатом работы
алгоритма является нахождение максимума функции на допустимой множестве.

Причем множество может
быть как дискретным, так и рациональным. В ходе работы алгоритма выполняется
две операции: разбиение исходного множества на подмножества (ветви) и
нахождения оценок (границ). Существует оценка множества сверху и оценка снизу.

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

Вначале
все множество считается рекордным.

1.Рекордное множество разбивается на
подмножества.

2. Найти оценки сверху и снизу для новых
подмножеств.

3. Определить максимальную оценку снизу
всех подмножеств.

4. Удалить те множества, в которых оценка
сверху меньше максимальной оценки снизу.

5. Найти максимальную оценку сверху всех
подмножеств и считать ее рекордной.

6. Если не достигнуто дискретности, или
требуемой точности, перейти к пункту 1.

7. Результатом работы является значение
между оценкой сверху и снизу для рекордного множества [3, с. 116].

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

Фрагмент текста работы:

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

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

Общую схему метода ветвей
и границ рассмотрим на примере задачи дискретного программирования:

необходимо найти минимум
функции



















 при
условии,  что

 =

, где G — конечное множество.

Пусть

нижняя граница функции

 на
множестве G. Реализация метода базируется на разбиении (разветвлении) исходного множества

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

, то есть:

На
каждой подмножестве 

решают частичную задачу дискретного
программирования. Если найти точное решение задачи на некотором подмножестве

(1

, то его считают текущим оптимальным
решением исходной задачи,  

выбирают того из них, который имеет наименьшее
значение