Метод ветвей и границ
Использование метода ветвей и границ для решения задач длительного планирования, содержащих конечное число допустимых планов. Вычисление допустимых планов и проверка планов на оптимальность. Этапы построения формальной схемы метода ветвей и границ.
| Рубрика | Математика |
| Вид | лекция |
| Язык | русский |
| Дата добавления | 14.08.2017 |
| Размер файла | 51,2 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Метод ветвей и границ
Метод ВИГ (или метод направленного перебора) относится к группе комбинаторных методов решения как линейных, так и нелинейных ЗДП. Этот метод дает общий подход к решению ЗДП, содержащих конечное число допустимых планов, и за конечное число шагов позволяет найти точное решение задач конечной размерности. Разные реализации метода объединяются общей идеей перехода от полного перебора планов к целенаправленному, сокращенному перебору. Сокращение перебора осуществляется за счет массового отсечения неперспективных планов.
Пусть имеет место задача ДП в общем виде:
(1)
Здесь f(X)- скалярная функция своих аргументов, G- конечное множество.
Несмотря на большое разнообразие алгоритмов, разрабатываемых для решения прикладных задач вида (1), им всем свойственны общие основные этапы:
1. Вычисление нижней границы целевой функции f(X) на множестве G и его подмножествах (в случае решения задачи на максимум - вычисление верхней границы),
2. Разбиение множества G на дерево подмножеств,
3. Пересчет нижней границы f(X) на подмножествах,
4. Вычисление допустимых планов,
5. Проверка планов на оптимальность,
6. В случае получения приближенного решения - оценка его точности.
Рассмотрим все эти этапы.
1. Вычисление нижней границы (оценки) целевой функции f(X) на множестве планов G или его подмножествах Gi G сводится к определению числа , для которого справедливо неравенство , или .
2. Разбиение (ветвление) множества G на дерево подмножеств.
Определение. Множества и называются разбиением множества G на подмножества Gi.
Суть метода ветвей и границ состоит в последовательном разбиении множества G на дерево подмножеств и в дальнейшем массовом отсеивании неперспективных в том или ином смысле подмножеств. При разработке конкретного алгоритма должен быть указан способ такого разбиения, также как указан метод вычисления нижней границы целевой функции на множестве G и его подмножествах.
Ветвление происходит по следующей схеме:
0-й шаг. Имеется исходное множество G=G0. Некоторым способом его разбивают на конечное число подмножеств .
к-тый (k>0) шаг. Имеются множества , еще не подвергшиеся ветвлению. По определенному правилу, указанному ниже, среди них выбирают подмножества и разбивают их на конечное число подмножеств . Затем еще не подвергавшиеся на этом шаге разбиению множества и новые подмножества , обозначают (перенумеровывают) как .(Рис.1.)
Размещено на http://www.allbest.ru/
3. Пересчет нижних границ целевой функции f(X) на подмножествах.
Очевидно, что если , то . Поэтому, разбивая в процессе решения множество G0 на подмножества , , значения нижних границ на этих подмножествах будут не меньше оценок для исходного множества G0, т.е. . В конкретных ситуациях это неравенство для некоторых i превращается из нестрогого в строгое неравенство. Чем быстрее рост оценок на подмножествах, тем эффективнее разработанный алгоритм.
4. Вычисление допустимых планов.
Для конкретных задач могут быть указаны различные способы нахождения планов в последовательно разбиваемых подмножествах. Любой такой способ опирается на специфику задачи. При разработке конкретного алгоритма необходимо указать способ определения допустимых планов.
5. Проверка планов на оптимальность.
Пусть имеется разбиение и найден некоторый план . Если при этом , то - оптимальный план исходной задачи (1).
Действительно, из последнего неравенства следует, что для , а так как , то окончательно можно записать для .
6. Оценка точности приближенного решения.
Пусть и найден некоторый план . Обозначим . Очевидно . Если разность невелика, то план можно принять за приближенное решение, а будет оценкой его точности.
Формальная схема метода ветвей и границ
0 шаг. Обозначается . Вычисляется нижняя граница целевой функции . Если при этом удается найти такой план , что , то - оптимальный план задачи (1).
Если оптимальный план не найден, то некоторым способом разбивают множество на конечное число непересекающихся подмножеств и переходят к следующему (первому) шагу.
1 шаг. Вычисляют нижние границы на полученных подмножествах: . Если удается найти такой план , что и , то - оптимальный план задачи (1).
В противном случае продолжается процесс ветвления. Для разбиения выбирают наиболее перспективное множество по правилу: . Разбивают множество . Далее переобозначают множества, не подвергшиеся разбиению на этом шаге, и новые подмножества , как , и переходят к следующему шагу. ветвь граница допустимый план
к-й шаг. Исходные множества для рассмотрения на этом этапе . Вычисляются оценки . Если удается найти такой план , что и справедливо условие , то - оптимальный план задачи (1).
В противном случае снова выбирают для разбиения наиболее перспективное множество по правилу: . Далее не подвергшиеся разбиению и , на данном шаге переобозначают как .
Этот процесс ветвления продолжается до тех пор, пока не будет найдено решение задачи (1).
Замечание. При реализации описанной выше общей схемы метода ветвей и границ для конкретных задач дискретного программирования необходимо разрабатывать правила ветвления, способы вычисления нижних границ целевой функции на рассматриваемых множествах и нахождения допустимых планов исходя из специфики этих задач.
Размещено на Allbest.ru
...Подобные документы
Формирование нижних и верхних оценок целевой функции. Алгоритм метода ветвей и границ, решение задач с его помощью. Решение задачи коммивояжера методом ветвей и границ. Математическая модель исследуемой задачи, принципы ее формирования и порядок решения.
курсовая работа [153,2 K], добавлен 25.11.2011Сущность и содержание, основные понятия и критерии теории графов. Понятие и общее представление о задаче коммивояжера. Описание метода ветвей и границ, практическое применение. Пример использования данного метода ветвей для решения задачи коммивояжера.
контрольная работа [253,0 K], добавлен 07.06.2011Методика решения задач высшей математики с помощью теории графов, ее сущность и порядок разрешения. Основная идея метода ветвей и границ, ее практическое применение к задаче. Разбиение множества маршрутов на подмножества и его графическое представление.
задача [53,0 K], добавлен 24.07.2009Суть задачи коммивояжера, ее применение. Общая характеристика методов ее решения: метод полного перебора, "жадные" методы, генетические алгоритмы и их обобщения. Особенности метода ветвей и границ и определение наиболее оптимального решения задачи.
курсовая работа [393,2 K], добавлен 18.06.2011Теория динамического программирования. Понятие об оптимальной подструктуре. Независимое и полностью зависимое множество вершин. Задача о поиске максимального независимого множества в дереве. Алгоритм Брона-Кербоша как метод ветвей, границ для поиска клик.
реферат [224,1 K], добавлен 09.10.2012Методы решения задачи коммивояжера. Математическая модель задачи коммивояжера. Алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами. Решение задачи коммивояжера с помощью алгоритма Крускала и "деревянного" алгоритма.
курсовая работа [118,7 K], добавлен 30.04.2011Формирование линеаризованного узлового уравнения разработка и транспонированной матрицы, сопротивлений ветвей и узловых проводимостей. Методика и этапы решения системы линеаризованных узловых уравнений методом Зейделя, анализ полученных результатов.
задача [144,6 K], добавлен 10.08.2013Математические модели явлений или процессов. Сходимость метода простой итерации. Апостериорная оценка погрешности. Метод вращений линейных систем. Контроль точности и приближенного решения в рамках прямого метода. Метод релаксации и метод Гаусса.
курсовая работа [96,7 K], добавлен 13.04.2011Поиск корней нелинейных САУ с помощью метода продолжения решения по параметру. Математическое описание метода. Программное обеспечение для построения графиков сходимости метода. Требования к программному обеспечению и описание логической структуры.
курсовая работа [365,5 K], добавлен 27.04.2011Сущность метода системосовокупностей как одного из распространенных и универсальных методов решения неравенств любого типа. Обобщение метода интервалов на тригонометрической окружности. Эффективность и наглядность графического метода решения задач.
методичка [303,7 K], добавлен 14.03.2011Симплексный метод как универсальное решение задач линейного программирования. Применение метода Жордана-Гаусса для системы линейных уравнений в канонической форме. Опорное решение системы ограничений. Критерий оптимальности. Задача канонической формы.
презентация [2,0 M], добавлен 11.04.2013Методы решения систем линейных алгебраических уравнений, их характеристика и отличительные черты, особенности и сферы применения. Структура метода ортогонализации и метода сопряженных градиентов, их разновидности и условия, этапы практической реализации.
курсовая работа [197,8 K], добавлен 01.10.2009Приближенные решения кубических уравнений. Работы Диофанта, Ферма и Ньютона. Интерационный метод нахождения корня уравнения. Геометрическое и алгебраическое описания метода хорд. Погрешность приближенного решения. Линейная скорость сходимости метода.
презентация [255,1 K], добавлен 17.01.2011Методы решения систем линейных уравнений. Метод Якоби в матричной записи. Достоинство итерационного метода верхних релаксаций, вычислительные погрешности. Метод блочной релаксации. Разбор метода релаксаций в системах линейных уравнений на примере.
курсовая работа [209,1 K], добавлен 27.04.2011Понятие и специфические черты системы линейных алгебраических уравнений. Механизм и этапы решения системы линейных алгебраических уравнений. Сущность метода исключения Гаусса, примеры решения СЛАУ данным методом. Преимущества и недостатки метода Гаусса.
контрольная работа [397,2 K], добавлен 13.12.2010Сравнение методов простой итерации и Ньютона для решения систем нелинейных уравнений по числу итераций, времени сходимости в зависимости от выбора начального приближения к решению и допустимой ошибки. Описание программного обеспечения и тестовых задач.
курсовая работа [3,1 M], добавлен 26.02.2011Решения интегральных уравнений на полубесконечном промежутке с ядром, зависящим от разности аргументов с помощью метода Винера-Хопфа. Решение задач в случае бесконечного и полубесконечного промежутка. Применение метода Винера-Хопфа к уравнению Лапласа.
реферат [1,3 M], добавлен 18.05.2010Изучение нестандартных методов решения задач по математике, имеющих широкое распространение. Анализ метода функциональной, тригонометрической подстановки, методов, основанных на применении численных неравенств. Решение симметрических систем уравнений.
курсовая работа [638,6 K], добавлен 14.02.2010Метод Зейделя как модификация метода простой итерации. Особенности решения систем линейных алгебраических уравнений. Анализ способов построения графика функций. Основное назначение формул Симпсона. Характеристика модифицированного метода Эйлера.
контрольная работа [191,3 K], добавлен 30.01.2014Форма для ввода целевой функции и ограничений. Характеристика симплекс-метода. Процесс решения задачи линейного программирования. Математическое описание алгоритма симплекс-метода. Решение задачи ручным способом. Описание схемы алгоритма программы.
контрольная работа [66,3 K], добавлен 06.04.2012
