Abstract: On the basis of optimal model of military transportation path and graph theory idea, generalized adjacent matrix and generalized cut-set-element matrix are constructed. Simple operation of the generalized cut-set-element matrix is used. Two kinds of cut set algorithm are proposed to obtain the path with a minimum generalized weight and the maximum flows of transport network. Applicable area and its complex degree are studied. This algorithm can solve all kinds of problems of military transportation path optimization with different parameters. An experiment is performed to show the effectiveness of the models and algorithms.

Key words: Cut set algorithm, Optimal path, Maximum flows, Network optimization, Military transportation

摘要： 在建立军事运输路径优化模型的基础上，结合网络图论的思想，构造了广义邻接矩阵和广义割集单元矩阵，利用广义割集单元矩阵的简单运算，提出了求解最小广义权路径的割集算法和最大流的割集算法。研究了广义割集算法的适用范围以及复杂度，利用该算法可直观快速地解决军事运输中各类参数路径优化问题。给出的算例验证了模型和算法的有效性。

关键词: 割集算法, 最优路径, 最大流, 网络优化, 军事运输

CLC Number: 

• U116