网络单纯形算法ppt课件

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

2、3在弧在弧(2,6) 中的流是中的流是什么什么?236计算生成树流计算生成树流136452713-6-4123在弧在弧(7,1)中的流是中的流是什么什么?2364计算生成树流计算生成树流136452713-6-4123在弧在弧(1,6)中的流是中的流是什么什么?23643计算生成树流计算生成树流136452713-6-4123注释注释: 有两中不同的有两中不同的方法计算在方法计算在(1,2)的流的流，两种方法都给出流，两种方法都给出流为为 4.这是巧合吗？这是巧合吗？236443计算生成树的单纯形乘子计算生成树的单纯形乘子13645275-6-2-413这里是有弧代价的生这里是有弧代价的生成树

3、成树.如何选择结点势如何选择结点势以便即约代价是以便即约代价是0呢呢？回想回想: (i,j)的即约代的即约代价是价是 cij - i + j13645275-6-2-413 1 可以被任意设置可以被任意设置.我们令我们令 i = 0. 结点结点 2 的单纯形乘子的单纯形乘子是什么？是什么？在最小代价流问题中在最小代价流问题中，有一个多余的限制，有一个多余的限制.0计算生成树的单纯形乘子计算生成树的单纯形乘子计算生成树的单纯形乘子计算生成树的单纯形乘子13645275-6-2-413结点结点 7 的单纯形乘子的单纯形乘子是什么？是什么？0(1,2)的即约代价是的即约代价是c12 - 1 + 2

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

5、-5-6-2-1计算生成树的单纯形乘子计算生成树的单纯形乘子13645275-6-2-413结点结点 5 的单纯形乘子的单纯形乘子是什么？是什么？0-5-6-2-1-4计算生成树的单纯形乘子计算生成树的单纯形乘子13645275-6-2-413有单纯形乘子和这棵有单纯形乘子和这棵树相关树相关.它们不依弧它们不依弧流，也不依赖非树弧流，也不依赖非树弧上的代价上的代价.0-5-6-2-1-4-1网络单纯形算法网络单纯形算法124532-42, $44, $21, $45, $53, $5 4, $14, $23, $45-3最小代价流问题最小代价流问题TLU生成树流生成树流124532-41003

6、2 0135-3初始生成树解初始生成树解TLU单纯形乘子和即约代价单纯形乘子和即约代价124530-40?400 -2023-2初始单纯形乘子和即约代价初始单纯形乘子和即约代价TLUc45 = 2什么弧是违规的？什么弧是违规的？3添加违规弧到生成树，创建圈添加违规弧到生成树，创建圈124533,2 4,04,13,3弧弧(2,1) 添加到了树中添加到了树中TLU圈是什么，能圈是什么，能发送多少流？发送多少流？2, 14, 01, 05, 3u14, x14环绕圈发送流环绕圈发送流124533,0 4,24,33,3沿着圈发送沿着圈发送2 单位的流单位的流TLU下一个生成树下一个生成树是什么？是

7、什么？2, 14, 01, 05, 3u14, x14旋转旋转(pivot)之后之后124533,0 4,24,33,3更新的生成树更新的生成树TLU在旋转中，一条在旋转中，一条弧加入到弧加入到 T， 而而另一条弧从另一条弧从 T 删删除除.2, 14, 01, 05, 3u14, x14更新乘子更新乘子12453当前乘子和即约代价当前乘子和即约代价TLU0-404400 -2023-23我们如何使我们如何使cp21 = 0 ，且，且让其他树弧有让其他树弧有 0 即约代价？即约代价？从从 T 删除删除 (2,1) 把把 T 分裂成两部分分裂成两部分12453添加添加 到树的一侧不影响任何到树的

8、一侧不影响任何树弧的即约代价，除了树弧的即约代价，除了 (2,1). 为什么为什么?TLU0-404400 -2023+-2+3应该选择什么应该选择什么样的样的 值，产值，产生即约代价生即约代价 (2,1) = 0?更新的乘子和即约代价更新的乘子和即约代价12453更新的乘子和即约代价更新的乘子和即约代价.TLU0-402202 0021-43这棵树的解是这棵树的解是最优的吗？最优的吗？添加一条违反弧到生成树，创建圈添加一条违反弧到生成树，创建圈12453添加弧添加弧 (3,4) 到生成树到生成树TLU3,0 4,24,33,32, 14, 01, 05, 3圈是什么，能圈是什么，能发送多少流

9、？发送多少流？沿圈发送流沿圈发送流12453沿圈发送沿圈发送1 个单位的流个单位的流.TLU3,0 4,24,23,22, 24, 01, 05, 3下一个生成树下一个生成树解是什么？解是什么？下一个生成树解下一个生成树解12453这是更新的生成树解这是更新的生成树解TLU3,0 4,24,23,22, 24, 01, 05, 3更新的乘子更新的乘子12453这是当前乘子这是当前乘子.TLU0-402202 0021-43我们如何修改我们如何修改乘子？乘子？更新的乘子更新的乘子12453这是更新的乘子这是更新的乘子.TLU0-4 +02202 0021-43 应该是什应该是什么值么值?更新的乘

10、子更新的乘子12453这是更新的乘子这是更新的乘子.TLU0-6-24202 0001-43当前生成树解当前生成树解是最优的吗？是最优的吗？最优解最优解12453这是最优解这是最优解.TLU0-6-24202 0001-43没有弧违反最没有弧违反最优条件优条件.寻找圈寻找圈13610118791252使用深度和前驱使用深度和前驱13610118791252024depth(5) = 4;depth(3) = 2;用用 pred(5)替换结点替换结点5使用深度和前驱使用深度和前驱13610118791252023depth(9) = 3;depth(3) = 2;用用 pred(9)替换结点替换

11、结点9使用深度和前驱使用深度和前驱13610118791252022depth(2) = 2;depth(3) = 2;用用 pred(2)替换结点替换结点2;用用 pred(3)替换结点替换结点3使用深度和前驱使用深度和前驱13610118791252011depth(8) = 1;depth(7) = 1;用用 pred(8)替换结点替换结点8;用用 pred(1)替换结点替换结点7使用深度和前驱使用深度和前驱136101187912520结点结点3和和5的的最小共同祖最小共同祖先被找到先被找到.更新乘子：使用线和深度更新乘子：使用线和深度13610118791252假设弧假设弧 (1,8)将从树中删将从树中删除除.以结点以结点8为根的子树为根的子树是什么？是什么？跟随从结点跟随从结点8开始的线开始的线13610118791252什么是什么是thread(8)?跟随从结点跟随从结点8开始的线开始的线13610118791252什么是什么是thread(3)?跟随从结点跟随从结点8开始的线开始的线13610118791252什么是什么是thread(10)?跟随