Методы декомпозиции разреженных cистем линейных алгебраических уравнений для оценки трафика обобщенного мультиграфа

Проблема определения местонахождения датчиков в сети для мониторинга потоков стала объектом повышенного интереса в последние несколько лет из-за ее значимости в областях управления и контроля трафика. Основой для моделирования процессов оценки потоков в обобщенной мультисети является разреженная недоопределенная система линейных алгебраических уравнений специального вида. Датчики расположены в узлах мультисети для заданных долей потоков на дугах в пределах соответствующего диапазона. Рассматриваемая проблема местоположения датчиков, как известно, является $NP$-полной. Разработаны эффективные алгоритмы определения рангов матриц каждой из независимых подсистем, полученных в результате применения теории декомпозиции. Из равенства суммы рангов матриц независимых подсистем и числа неизвестных в независимых подсистемах следуют условия единственности решения специальной разреженной системы линейных алгебраических уравнений. Результаты исследования могут быть также применены для построения оптимальных решений задач математического программирования.