< индекс---содержание № 3---след. статья в № 3---след. в рубрике >
УДК 65.012
МЕТОД СЕТЕВОГО ПРОГРАММИРОВАНИЯ
В.Н. Бурков, И.В. Буркова, М.В. Попок, Т.И. Овчинникова
Институт проблем управления им. В.А. Трапезникова, г. Москва
Предложен новый подход к задачам дискретной оптимизации, названный методом сетевого программирования, в основу которого положена возможность представления функции многих переменных в виде суперпозиции более простых функций. Структура такой суперпозиции представляется в виде сети, входы которой соответствуют переменным, а выходы – функции. Показано, что если сеть является деревом, то решение задачи сводится к последовательному решению более простых задач. В общем случае предложено преобразовать сеть в дерево путем разделения вершин сети. Доказано, что решение задачи для преобразованной структуры дает нижнюю оценку для целевой функции исходной задачи (если решается задача минимизации). Метод проиллюстрирован на примере известной задачи о камнях.
Многие задачи дискретной оптимизации сводятся к следующей постановке: определить вектор x = {xi} с дискретными компонентами, минимизирующий аддитивную функцию
(1)
при ограничении
(2)
f(x) ³ b.
Любая функция дискретных переменных допускает сетевое представление, такое, что вычисление значений функции сводится к последовательному вычислению значений более простых функций. В частности, любая функция дискретных переменных допускает дихотомическое представление, когда вычисление значения функции сводится к последовательному вычислению значений функций двух переменных. Так, функция f(x) = f0[f1(x1, x2), f2(x2, x3)] допускает дихотомическое представление (рис. 1). При этом функции f0, f1 и f2 удобно представлять в матричном виде (рис. 2). Такое представление широко используется в методах комплексного оценивания программ развития предприятий, регионов, результатов деятельности подразделений, уровня безопасности объектов и др.
В работах [1, 2] доказаны теоремы о представлении непрерывных функций нескольких переменных суперпозициями непрерывных функций меньшего числа переменных (в частности, двух переменных). Так, например, любая непрерывная функция трех переменных представима в виде [2] f (x1, x2, x3) = h1 (x1, j1 (x2, x3)) + h2 (x1, j2 (x2,x3)) + h3 (x1, j3 (x2, x3)). Ее сетевое представление приведено на рис. 3.
В сетевом виде можно представить и систему неравенств. Рассмотрим, например, систему неравенств
(3)
.
Без ограничения общности можно принять, что bj – положительные и одинаковые числа, bj = b > 0. В этом случае систему неравенств (3) можно заменить одним неравенством f(х) ≤ b, где
Очевидно, что функция f(х) допускает сетевое представление, если все функции fj допускают такое представление.
В настоящей работе описывается новый метод решения дискретной оптимизации, использующий сетевое представление функции f(x). Его естественно назвать методом сетевого программирования (в частном случае дихотомического представления получаем метод дихотомического программирования [3]).
Рис. 1. Дихотомическое представление функции дискретных переменных
Рис. 2. Представление функций f0, f1 и f2 в матричном виде
Рис. 3. Сетевое представление непрерывных функций трех переменных
Предложенный подход к решению задач дискретной оптимизации применим к любой задаче данного класса, поскольку любая функция дискретных переменных допускает сетевое представление. Если целевая функция не аддитивная, то вводом новой переменной всегда можно перейти к задаче с аддитивной целевой функцией, как это показано на примере задачи о камнях. Вопрос об эффективности применения метода сетевого программирования к решению конкретных задач дискретной оптимизации, конечно, требует дальнейших исследований. Заметим, что метод можно применить и к непрерывным задачам.
1. Арнольд В.И. О функциях трех переменных // Доклады АН СССР. – 1957. – № 2.
2. Колмогоров А.Н. О представлении непрерывных функций нескольких переменных суперпозициями непрерывных функций меньшего числа переменных // Доклады АН СССР. – 1956. – № 2.
3. Бурков В.Н., Буркова И.В. Задачи дихотомической оптимизации // Материалы междунар. науч.-техн. конф. “Системные проблемы качества, математического моделирования, информационных и электронных технологий”. – М., 2003. – С. 23 – 28.
( (0742) 334-90-51
E-mail: irbur27@mail.ru