左逢源，王晓峰,2+，任雪娇，张丹丹

(1.北方民族大学 计算机科学与工程学院，宁夏 银川 750021；2.北方民族大学 宁夏智能信息与大数据处理重点实验室，宁夏 银川 750021)

0 引 言

线性规划(linear programming)是运筹学中研究、发展较成熟的一个重要分支，是一种用来辅助科研人员进行科学研究的数学方法。线性规划问题特指目标函数和约束条件皆为线性的最优化问题，线性规划方程用来求解问题最优解[8]。其中，网络最大流问题是一类特殊的线性规划问题，在线性规划方程中用maxf*来表示目标函数，f*代表目标最大流值,各边容量限制及节点流量守恒定律分别代表两类约束条件。

信念传播(belief propagation，BP)算法，又名和-积信息传递，是一种迭代求解概率图模型中统计推断问题的方法，尤其在组合优化问题的求解中有极好效果，所有信息的传播可以并行实现[9]。BP算法以实时性以及求解精度高等优点得到了广泛应用，如权重匹配问题[10]、最短路径和网络流匹配问题等[11]。BP算法主要思想定义请参见文献[12]。过去几年间，科研人员做了大量的研究工作来了解在组合优化条件下的BP算法性能。特别是几类图模型下的组合优化问题，研究了信念传播算法的收敛性以及正确性。根据一些文献可知有些特殊的线性规划问题可以映射成因子图所对应的问题模型[13],进而利用BP算法求解问题。目前，最大流问题的复杂性随着实际问题规模的增大而增大，复杂度以指数级增长，而利用BP算法求解线性规划问题时运算复杂度只与节点线性相关，且节点间信息传递并行实现，极大减少了时间复杂度，节省了人力、物力等。……