摘要：单纯型算法是求解线性规划问题（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/~erodr…
点击关注，第一工夫理解华为云陈腐技术~