МЕТОД СЕТЕВОГО ПРОГРАММИРОВАНИЯ

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