Алгоритм оптимизации однородного потока на взвешенном графе с ограничениями на пропускную способность вершин

Abstract

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

We propose an iterative algorithm for selecting optimal source intensities of the uniform flow in the weakly connected weighted graph, while every pair of its vertices is connected by no more than one path, with constraints on the bandwidth of vertices and fixed transmission (transformation) ratio of flow along the arcs. The computational scheme is an iterative procedure that uses a piecewise linear approximation of the function of the flow sources intensity at the vertices of the graph. The algorithm can be used to select the optimal water conservation measures providing normative quality of surface water in the basin according to the dominant or integral indicator of return water composition.