Общая схема метода ветвей и границ решения ЗДП
. В начале процесса разбивается на подмножеств:
В начале должна быть вычислена величина – нижняя оценка оптимального значения на , т.е. если - решение ЗДП, то
(1) .
Для всех подмножеств в , полученных в результате разбиения, должна быть вычислена верхняя оценка функции на .
Величины и используются для сужения области поиска решения ЗДП. А именно если выполняется условие (2). (2) означает, что на множестве функция не достигает своего максимума, следовательно в дальнейшем подмножество можно не рассматривать при решении задачи. Предположим (2) выполнено для , т.е. их нужно выбросить из рассмотрения. Потом корректируем , на графе они просто вычеркиваются. Рассматриваем только оставшиеся висячие вершины подмножества. Для продолжения решения выбираем для разбиения следующее подмножество. Выбираем следующее для разбиения подмножество из условия:
(4)
Пусть разбивается на , переобозначим
Для каждого из этих подмножеств вычисляем:
(5)
Проверяем условие (5). Пусть условие (5) выполняется для (6). Нужно скорректировать два подмножества и
В дальнейшем будем рассматривать только те подмножества, которые на графе являются висячими вершинами, т.е. нерассмотренные. Дальнейший процесс решения задачи можно построить двумя способами. Граф: Первый способ: Для дальнейшего разбиения выбирается подмножество из подмножеств, полученных в результате последнего разбиения , например: Пусть это будет и производим разбиение. Дальнейший процесс будет проходить также. При этом способе можно достаточно быстро получить подмножество , содержащее всего один план задачи , то - претендент на оптимальный план. Запоминаем на графе на ветке, приводящей к ставим конец и корректируется величина , т.е. . увеличена, следовательно нужно рассмотреть все нерассмотренные подмножества. Далее продолжаем процесс решения задачи также. Второй способ: Выбирается множество для разбиения из всех висячих вершин, ещё нерассмотренных. Выбирать способ решения задачи нужно в зависимости от конкретной задачи. При любом способе решения процесс продолжаем до тех пор пока не будет выполнено следующее условие: для любого (висячие вершины). Решением задачи будет тот план, который дал последнее значение величине . Для решения конкретной ЗДП необходимо строить алгоритм метода ветвей и границ, согласно приведенной схеме. При этом нужно решить следующие проблемы: 1) как найти ; 2) по какому принципу проводить разбиение множества; 3) как вычислить .
Популярное: Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас... Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ... Как выбрать специалиста по управлению гостиницей: Понятно, что управление гостиницей невозможно без специальных знаний. Соответственно, важна квалификация... Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (361)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |