多条件约束最大流分析的几何代数方法

Geometric Algebra-based Multi-criteria Constrained Maximal Flow Analysis

针对多约束变容量条件下的应急物资调度问题,构建了基于几何代数的条件约束最大流分析模型。基于几何基编码法和几何积运算进行网络图表达、网络连通性判定与路径搜索,进而建立了基于贪心算法思想的几何代数最大流分析方法。利用几何代数运算的独立性及其与布尔逻辑运算间的内蕴联系,探讨了基于约束矩阵的多约束集成方法,实现了外部约束及权重变化条件下的网络最大流的快速计算与更新。污染物扩散条件下最大流分析的案例分析结果显示,基于几何代数的网络分析算法在网络表达、算法构造以及权重更新等方面表现出较好的优势,可有效支撑多约束下的物资调度分析。

Network analysis is a fundamental basis for community resources scheduling appli- cations. Discussed in this paper is a multi-criteria-constrained maximal flow problem with route capacity changing over time. Geometric algebra unit based coding is used to obtain a geometric algebra expression for a network diagram. Network connectivity and path search are implemented based on this geometric product. Using independent computation the inner linkage between Boolean operations in geometric algebra computation are exploited, multi- criteria are integrated based on a constrained matrix. A multi-criteria-constrained maximal flow analysis algorithm with changing route capacity is proposed. The algorithm was imple- mented and validated by maximum flow analysis dealing with pollutant dispersion cases. The results show that, under the constraints imposed by a materials scheduling analysis, the geo- metric algebra based network algorithm can effectively support multi-dimensional community networks. The algorithm also supports rapid computing and updating of the weight of exter- nal constraints as well as changes in the conditions of maximum flow problems.