КОМПЛЕКСНОЕ ПРИМЕНЕНИЕ МЕТОДА ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ И МЕТОДА ВЕТВЕЙ И ГРАНИЦ ДЛЯ РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ

М.А. Алпатов, Р.В. Бубнов
(Саратовский государственный технический университет, Россия)

Большой класс прикладных задач оптимизации сводится к задачам целочисленного программирования. Для решения этих задач широко применяются комбинаторные методы, основанные на упорядоченном переборе наиболее перспективных вариантов [I]. Комбинаторные методы решения можно разделить на две группы: методы динамического программирования и методы ветвей и границ.

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

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

На основе комплексного применения методов динамического программирования и ветвей и границ разработан алгоритм решения задачи и составлена про1рамма оптимизации для компьютеров типа IBM PC на C++ Builder 3.0. Решение примеров на ЭВМ показало практическую реализуемость алгоритма и его достаточную эффективность.

Результаты научных исследований предполагается использовать для оптимизации структур электромеханических систем на государственном предприятии производственном объединении "Корпус".

ЛИТЕРАТУРА

1. Корбут А.А., Финкелыгггейн Ю.Ю. Дискретное программирование. М.: Наука. 1969.

2. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. -М.: Наука, 1987.