图论动画-网络单纯形算法

《图论动画-网络单纯形算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、15.082和6.855J网络单纯形动画计算生成树流136452713-6-4123有供应和需求的树.(假设所有的其他弧的流是0)在弧(4,3)中的流是什么？2计算生成树流136452713-6-4123为了计算流，向上迭代树，寻找流能唯一确定的弧.在弧(5,3)中的流是什么？23计算生成树流136452713-6-4123在弧(3,2)中的流是什么？234计算生成树流136452713-6-4123在弧(2,6)中的流是什么?2365计算生成树流136452713-6-4123在弧(7,1)中的流是什么?23646计算生成树流1

2、36452713-6-4123在弧(1,6)中的流是什么?236437计算生成树流136452713-6-4123注释:有两中不同的方法计算在(1,2)的流，两种方法都给出流为4.这是巧合吗？2364438计算生成树的单纯形乘子13645275-6-2-413这里是有弧代价的生成树.如何选择结点势以便即约代价是0呢？回忆:(i,j)的即约代价是cij-i+j913645275-6-2-4131可以被任意设置.我们令i=0.结点2的单纯形乘子是什么？在最小代价流问题中，有一个多余的限制.0计算生成树的单纯形乘子10计算生成树

3、的单纯形乘子13645275-6-2-413结点7的单纯形乘子是什么？0(1,2)的即约代价是c12-1+2=0.因此5-0+2=0.-511计算生成树的单纯形乘子13645275-6-2-413结点3的单纯形乘子是什么？0(7,1)的即约代价是c12-1+2=0.c71-7+1=0.因此-6-7+0=0.-5-612计算生成树的单纯形乘子13645275-6-2-413结点6的单纯形乘子是什么？0-5-6-213计算生成树的单纯形乘子13645275-6-2-413结点4的单纯形乘子是什么？0-5-6-2-114

4、计算生成树的单纯形乘子13645275-6-2-413结点5的单纯形乘子是什么？0-5-6-2-1-415计算生成树的单纯形乘子13645275-6-2-413有单纯形乘子和这棵树相关.它们不依弧流，也不依赖非树弧上的代价.0-5-6-2-1-4-116网络单纯形算法124532-42,$44,$21,$45,$53,$54,$14,$23,$45-3最小代价流问题TLU17生成树流124532-4100320135-3初始生成树解TLU18单纯形乘子和即约代价124530-40?400-2023-2初始单纯形乘子和即约代价TLU

5、c45=2什么弧是违规的？319添加违规弧到生成树，创建圈124533,24,04,13,3弧(2,1)添加到了树中TLU圈是什么，能发送多少流？2,14,01,05,3u14,x1420环绕圈发送流124533,04,24,33,3沿着圈发送2单位的流TLU下一个生成树是什么？2,14,01,05,3u14,x1421旋转(pivot)之后124533,04,24,33,3更新的生成树TLU在旋转中，一条弧加入到T，而另一条弧从T删除.2,14,01,05,3u14,x1422更新乘子12453当前乘子和即约代价TLU0-404

6、400-2023-23我们如何使cp21=0，且让其他树弧有0即约代价？23从T删除(2,1)把T分裂成两部分12453添加到树的一侧不影响任何树弧的即约代价，除了(2,1).为什么?TLU0-404400-2023+-2+3应该选择什么样的值，产生即约代价(2,1)=0?24更新的乘子和即约代价12453更新的乘子和即约代价.TLU0-4022020021-43这棵树的解是最优的吗？25添加一条违反弧到生成树，创建圈12453添加弧(3,4)到生成树TLU3,04,24,33,32,14,01,05,3圈是什么，能发送多

7、少流？26沿圈发送流12453沿圈发送1个单位的流.TLU3,04,24,23,22,24,01,05,3下一个生成树解是什么？27下一个生成树解12453这是更新的生成树解TLU3,04,24,23,22,24,01,05,328更新的乘子12453这是当前乘子.TLU0-4022020021-43我们如何修改乘子？29更新的乘子12453这是更新的乘子.TLU0-4+022020021-43应该是什么值?30更新的乘子12453这是更新的乘子.TLU0-6-242020001-43当前生成树解是最优的吗？31最优解1245

8、3这是最优解.TLU0-6-242020001-43没有弧违反最优条件.32寻找圈1361011879125233使用深度和前驱13610118791252024depth(5)=4;depth(3)=2;用pred(5)替换结点534使用深度和前