О методах декомпозиции разреженных недоопределенных систем с матрицами полного и неполного ранга

Abstract

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