Cтраница 1
Методы ветвей и границ являются в настоящее время основой всех известных пакетов и библиотек прикладных программ по решению задач целочисленного и частично целочисленного лилейного программирования. Методы ветвей и границ используются для решения целочисленных задач, обладающих конечным - ( возможно, очень большим) числом допустимых планов. Разные реализации методов ветвей и границ объединяет общая идея перехода от полного перебора к сокращенному ( направленному) перебору. Сокращение перебора достигается за счет массового отсеивания неперспективных вариантов. Выявление множеств вариантов, подлежащих отсеиванию на каждом шаге, представляет собой наиболее важный этап метода, определяющий его эффективность. Этот этап существенно использует особенности структуры ограничений задачи. [1]
Согласно методу ветвей и границ расчет каждого варианта схемы разделения производится в направлении от начала схемы к ее концу. Это упрощает определение условий на входе в каждый разделительный элемент по сравнению с методом динамического программирования. Некоторое сокращение числа рассматриваемых вариантов различных элементов достигается путем отбрасывания ветвей дерева разделения, если значение критерия оптимальности для части схемы разделения превосходит значение верхней оценки критерия оптимальности. За значение верхней оценки критерия оптимальности принимается его значение для наилучшей из рассчитанных к данному моменту схем разделения. Однако при использовании метода ветвей и границ разделительные элементы одного и того же функционального назначения, входящие в разные схемы разделения, рассчитываются многократно. [2]
Согласно методу ветвей и границ, расчет каждого варианта схемы производится от начала схемы к ее концу. Некоторое сокращение числа рассматриваемых вариантов различных элементов достигается путем отбрасывания ветвей дерева разделения, если значение критерия оптимальности для части схемы превосходит значение верхней оценки критерия оптимальности. За значение верхней оценки критерия оптимальности принимается его значение для наилучшей из рассчитанных к данному моменту схем разделения. Вместе с тем метод ветвей и границ дает достаточно надежные результаты ( так же как и предыдущий метод) в случае разделения зеотропных смесей. Что касается азеотропных смесей, то использование его в предлагаемом виде невозможно. [3]
В методе ветвей и границ искомый вариант, как отмечалось, строится поэтапно, сужая на каждом из этапов множество возможных выборов. Например, в задаче о кратчайшем пути это есть подмножества тех путей, которые могут быть получены продолжением одной из исходящих из начальной вершины дуг. После этого выбирается то из подмножеств, оценка v j которого наименьшая, и оно разбивается на некоторое число подмножеств, для каждого из которых отыскивается своя оценка. [4]
Под методами ветвей и границ подразумевают алгоритмы перебора, которые появились не так давно как фундахментальный общий метод нахождения оптимальных решений дискретных оптимизационных задач. Методика ветвей и границ быстро развилась, и сейчас полный список работ, связанных с ней, насчитывает несколько сотен наименований. Хотя метод ветвей и границ был развит и обобщен многими авторами [1, 7, 60, 107, 113, 120, 123], очень немногие из них рассматривали зависимость относительных потребностей в вычислительных ресурсах от выбора параметров алгоритма. [5]
Процедура ветвления в методе ветвей и границ не гарантирует точного выбора множества, в котором находится оптимальное решение. [6]
Рассмотренный в первой главе метод ветвей и границ весьма широко применяется для решения задач технического проектирования. [7]
Реализовать в этой задаче метод ветвей и границ даже проще, чем в задаче линейного раскроя - не надо вычислять максимальное количество / - х предметов, которые могут уместиться в остаток веса, можно взять не больше одного предмета. [8]
Изложим для этой задачи метод ветвей и границ. [9]
Процесс решения задачи по методу ветвей и границ удобно изображать графически в виде древовидной структуры, в которой вершины соответствуют подзадачам, а дуги дополнительным ограничениям, возникающим в момент ветвления по какой-либо переменной. Число рядом с подзадачей обозначает хронологический порядок решения подзадач. [10]
Можно обратиться также к методу ветвей и границ, широко используемому для численного решения задач дискретного программирования. [11]
Решение данного алгоритма основано на методе ветвей и границ, а сам процесс ветвления начинается с одной из моделей, имеющей максимальное число связей с другими. [12]
В отличие от метода прямого перебора метод ветвей и границ позволяет осуществлять направленный перебор, отбрасывая заранее невыгодные варианты. [13]
Метод направленного конструирования решения в отличие от метода ветвей и границ основан на построении полного решения задачи в г-й вершине ветвления ( X) с использованием векторов частичного решения Хг, зафиксированных в ней. Полное решение Хг проверяется непосредственно на имеющиеся ограничения. [14]
Для того чтобы применить в этой задаче метод ветвей и границ мы должны описать метод получения оценки и политику ветвления. [15]