什么是网络单纯型算法

关注

发布于: 1 小时前

摘要：单纯型算法是求解线性规划问题（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 称为根边（rootedge）(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());}