网络单纯型算法简介

云小凡 发表于 2021/06/22 19:52:22 2021/06/22
【摘要】 网络单纯型是指如下形式的LP问题:其中, ,每列只包含一个1和一个-1,其他系数都是0。下面是一个例子:该问题可以看做是最小费用流问题(Minimum cost flow problems)的图形式。图G=(V,E),顶点V表示行(约束),边E表示列(变量),对于矩阵A中一个列,第i行有个1,第k行有个-1,表示图G中的一条边(i,k)。对于上述例子,可以用下图表示:网络流问题满足Hoffm...

【前言】单纯型算法是求解线性规划问题(LP)的一个经典算法,在单纯型算法中最耗时的模块是计算矩阵的逆。网络单纯形算法是单纯形算法的一个特殊版本,它使用生成树基来更有效地解决具有纯网络形式的线性规划问题。这样的LP问题可以用有向图上的公式来建模,作为一个最小费用流问题。

网络单纯型是指如下形式的LP问题:
image.png
其中,每列只包含一个1和一个-1,其他系数都是0。
下面是一个例子:
image.png
该问题可以看做是最小费用流问题(Minimum cost flow problems)的图形式。
图G=(V,E),顶点V表示行(约束),边E表示列(变量),对于矩阵A中一个列,第i行有个1,第k行有个-1,表示图G中的一条边(i,k)。

对于上述例子,可以用下图表示:
image.png
网络流问题满足Hoffman&Gale’s conditions,因此可以确保得到整数解。

【关联矩阵】:
对于图G=(V,E)的关联矩阵A可以表示为:
image.png
上例中的关联矩阵可以表示为:
image.png

【路径】:
image.png
image.png
连通图:图中任意两个顶点都有路径。
生成树:图G的一个子图T,包含图G中所有顶点。
性质:rank(A)=n-1,n是结点个数。

我们新增一个变量w,A中增加一个列image.png,r∈{1,2……n}中任意一个值,w=0,则LP模型为:image.png
其中,r称为根节点(root vertex),w称为根边(root edge)(going nowhere)
对于上述例子,假如选择根节点 r=2
image.png
A 是图G的关联矩阵,T是G的生成树,则(A│e_r )的基B=e_r∪{a_e |e∈T}

【单纯型算法】:
image.png
image.png
image.png

我们可以从根节点进行先序遍历,得到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());
}
image.png

参考文献:https://www.cs.upc.edu/~erodri/webpage/cps/theory/lp/network/slides.pdf

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区),文章链接,文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:cloudbbs@huaweicloud.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。