Применение конструктивных методов декомпозиции для решения одной нелинейной задачи сетевой оптимизации

Abstract

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