Анализ использования метода ветвей и границ в задачах целочисленной оптимизации
 Скачать 82.16 Kb.
|
|
«Устойчивое развитие науки и образования»      Устойчивое развитие науки и образования. 2020. № 1. УДК 656.2-50: 519.8 Мищенко Д.В., Кобак В.Г. АНАЛИЗ ИСПОЛЬЗОВАНИЯ МЕТОДА ВЕТВЕЙ И ГРАНИЦ В ЗАДАЧАХ ЦЕЛОЧИСЛЕННОЙ ОПТИМИЗАЦИИ Донской государственный технический университет Аннотация: В статье рассматривается способы применения метода ветвей и границ. Дается определение метода, его свойств, плюсов и минусов. Проводится анализ и выделяются эффективные сферы для его использования. Также проведен анализ задач, с которыми алгоритм плохо справляется. Ключевые слова: метод ветвей, задача назначения, минимизация, максимизация, алгоритм оптимизации. UDC 656.2-50: 519.8 Mishchenko D.V., Kobak V.G. ANALYSIS OF THE BRANCHES AND BOUNDARIES METHOD USE IN TASKS OF INTEGRAL OPTIMIZATION Don State Technical University Abstract: The article discusses how to use the branch and bound method. The definition of the method, its properties, pluses and minuses is given. The analysis is carried out and effective areas for its use are highlighted. Also, an analysis of tasks with which the algorithm does not cope well. Keywords: branch method, assignment problem, minimization, maximization, optimization algorithm. В данной работе проводится анализ использования метода ветвей и границ в задачах целочисленной оптимизации. Метод ветвей и границ относится к группе комбинаторных методов дискретного программирования. Одними из первых данный метод использовали Литтл, Мурти, Суини и Кэрел в 60-х годах 20 века при решении задачи о коммивояжере [1]. В основе метода ветвей и границ лежит идея последовательного разбиения множества допустимых решений на подмножества, при этом, на каждом шаге метода элементы разбиения проверяются на наличие оптимального решения, посредством вычисления оценки снизу для целевой функции в данном подмножестве. Если оценка снизу не меньше наилучшего из найденных решений, то подмножество отбрасывается. Если значение целевой функции на найденном решении меньше наилучшего, то происходит смена наилучшего 84 «Устойчивое развитие науки и образования» Устойчивое развитие науки и образования. 2020. № 1. решения. Если удается отбросить все подмножества, то оптимальным решением является наилучшее из найденных решений, иначе из оставшихся разбиений выбирается наиболее перспективное, и оно делится на подмножества, которые вновь проверяются на наличие наилучшего решения и т.д. Окончанием работы алгоритма является найденное наилучшее решение. Главный недостаток алгоритма метода ветвей и границ заключается в необходимости полностью решать задачи линейного программирования, ассоциированные с каждой из вершин многогранника допустимых решений. Для задач большой размерности это требует значительных и, в известной степени, неоправданных с практической точки зрения затрат времени. Так, например, в задаче “о трех станках” рассматривается пример [2] и решение с использованием данного метода. В результате работы на основании результатов можно сказать, что описываемый алгоритм работает быстрее для задач с высоким оптимальным значением целевой функции. Благодаря эффективной стратегии ветвления алгоритм быстро находит хорошие решения, и, если оптимальное значение целевой функции велико, то многие ветви отбрасываются, потому что предложенная верхняя граница обычно намного более точная для таких случаев. В статье [3] рассматривается и обосновывается применение метода ветвей и границ для решения задачи сетевого планирования и управления при наличии нескольких ограничений на ресурсы. Следует отметить, что задача сетевого планирования с ограниченными ресурсами принадлежит к группе сложных комбинаторных задач, и часто метод ветвей и границ является единственной техникой, позволяющей создавать оптимальные решения в рамках приемлемого вычислительного усилия. Комбинаторная задача определяется как задача назначения дискретных численных значений некоторым определенным наборам переменных Х таким образом, чтобы удовлетворить набору ограничений и минимизировать некоторую целевую функцию f(x). При этом при задании ограничений и целевой функции допускается довольно большая гибкость вычислений [4]. Также в статье [5] рассматривается применение эвристик для метода ветвей и границ для решения задачи оптимизации сети передачи данных. При решении оптимизационных задач методом ветвей и границ можно добиться существенного сокращения времени работы алгоритма за счет нахождения некоторого решения с использованием жадных или, например, эвристических алгоритмов, тем самым уменьшив число операций ветвления и сократив перебор рассматриваемых вариантов. Такой подход доказал свою эффективность при решении однокритериальных задач [5]. Однако авторы столкнулись с тем, что при решении бикритериальных задач с использованием концепции оптимальности по Парето эффективность такого подхода еще необходимо проверить. В работе предлагается применить генетический алгоритм для нахождения субоптимального множества решений, которым изначально инициализируется множество рекордов R метода ветвей и границ. Это позволит на раннем этапе работы метода отсечь 85  «Устойчивое развитие науки и образования» Устойчивое развитие науки и образования. 2020. № 1. заведомо неоптимальные подмножества решений. В результате применение описанных эвристик позволило более чем в два раза сократить время работы алгоритма на сетях размерности не менее 35, что подтвердило их эффективность. В работе [6] использование метода и ветвей и границ для решения задачи коммивояжера привело в гарантированному уменьшению вычислительной сложности решения задачи в первом приближении на порядок. Дополнительная память для хранения значений потенциалов столбцов и векторов решения не превысила объема O(2 ). Таким образом, несмотря на отмеченные недостатки данного метода, можно утверждать, что в настоящее время алгоритмы метода являются наиболее надежным средством решения целочисленных задач, встречающихся в практических исследованиях. Это не означает, однако, что любая целочисленная задача может быть решена с помощью рассматриваемого метода. Тем не менее проблема выбора между методом отсечений и методом ветвей и границ в подавляющем большинстве случаев обоснованно разрешается в пользу последнего. Список литературы Little J.D.C., Murty K.G., Sweeney D.W., and Karel C. An algorithm for the Traveling Salesman Problem // Operation Research, 1963. № 11. P. 972-989. Шкурба В.В. Задача трех станков. М.: Наука (Физматлит), 1975 Князева Маргарита Владимировна Метод ветвей и границ для решения задачи сетевого планирования с ограниченными ресурсами // Известия ЮФУ. Технические науки. 2010. №7. Demeulemeester, E.L., Herroelen W.S., Project Sheduling, a Research Handbook. Department of Applied Economics Katholieke Universiteit, Leuven Belgium, Kluwer Academic Publishers, 2002. – 685 p. Алексеев, О.Г. Комплексное применение методов дискретной оптимизации / О.Г. Алексеев. – М.: Наука. Гл. ред. физ-мат. лит., 1987. – 248 с © Мищенко Д.В., Кобак В.Г., 2020 86 |