摘要：单纯型算法是求解线性规划问题（LP）的一个经典算法，在单纯型算法中最耗时的模块是计算矩阵的逆矩阵的算法。网络单纯形算法是单纯形算法的一个特殊版本，它使用生成树基来更有效地解决具有纯网络形式的线性规划问题。
本文分享自华为云社区《网络单纯型算法简介》，原文作者：云小凡 。
前言
单纯型算法是求解线性规划问题（LP）的一个经典算法，在单纯型算法中最耗时的模块是计算矩阵的逆矩阵的算法。网络单纯形算法是单纯形算法的一个特殊版本，它使用生成树基来更有效地解决具有纯网络形式的线性规划问题。这样的LP问题可以用有向图上的公式来建模，作为一个最小费用流问题。
网络单纯型是指如下形式的LP问题：
![]()
其中，每列只包含一个1和一个-1，其他系数都是0。下面是一个例子：
![]()
该问题可以看做是最小费用流问题（Minimum cost flow problems）的图形式。图G=（V,E），顶点V表示行（约束），边E表示列（变量），对于矩阵A中一个列，第i行有个1，第k行有个-1，表示图G中的一条边（i，k）。
对于上述例子，可以用下图表示：
![]()
网络流问题满足Hoffman&Gale’s conditions,因此可以确保得到整数解。
关联矩阵：
对于图G=（V,E）的关联矩阵A可以表示为：
![]()
上例中的关联矩阵可以表示为：
![]()
路径：
![]()
![]()
连通图：图中任意两个顶点都有路径。
生成树：图G的一个子图T，包含图G中所有顶点。
性质：rank(A)=n-1，n是结点个数。
我们新增一个变量w，A中增加一个列
![]()
，r∈{1,2……n}中任意一个值，w=0，则LP模型为：
![]()
其中，r称为根节点(root vertex)，w称为根边（root edge）(going nowhere)
对于上述例子，假如选择根节点 r=2
![]()
A 是图G的关联矩阵，T是G的生成树，则(A│e_r )的基B=e_r∪{a_e |e∈T}
单纯型算法：
![]()
![]()
![]()
我们可以从根节点进行先序遍历，得到y2=0, y1-y2=1, y1-y3=10，即依次遍历基5，基1，基4
伪代码：(递归)
solve(Vertex p,Tree S){//p是树S的根节点
Vertex v=root(S);
if(v==r) y[r]=c[w];
else if ((p,v)∈E y[v]=y[p]-c[(p,v)];
else y[v]=y[p]+c[(v,p)];
solve(v,S.left());
solve(v,S.right());
}
![]()
参考文献：https://www.cs.upc.edu/~erodri/webpage/cps/theory/lp/network/slides.pdf
点击关注，第一时间了解华为云新鲜技术~
