什么是网络单纯型算法

原创
2021/07/15 10:01
阅读数 3.4K
摘要:单纯型算法是求解线性规划问题(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

 

点击关注,第一时间了解华为云新鲜技术~

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
1 收藏
0
分享
返回顶部
顶部