网络单纯形算法

15.082 和 6.855J网络单纯形动画计算生成树流13 64 52 713-6-412 3有供应和需求的树 .(假设所有的其他弧的流是 0)在弧 (4,3)中的流是什么？2计算生成树流13 64 52 713-6-412 3为了计算流，向上迭代树，寻找流能唯一确定的弧 .在弧 (5,3)中的流是什么？23计算生成树流13 64 52 713-6-412 3在弧 (3,2)中的流是什么？2 34计算生成树流13 64 52 713-6-412 3在弧 (2,6) 中的流是什么 ?2 365计算生成树流13 64 52 713-6-412 3在弧 (7,1)中的流是什么 ?2 36 46计算生成树流13 64 52 713-6-412 3在弧 (1,6)中的流是什么 ?2 36 437计算生成树流13 64 52 713-6-412 3注释 : 有两中不同的方法计算在 (1,2)的流，两种方法都给出流为 4.这是巧合吗？2 36 44 38计算生成树的单纯形乘子13 64 52 75 -6-2-413这里是有弧代价的生成树 .如何选择结点势以便即约代价是 0呢？回忆 : (i,j)的即约代价是 cij - i + j913 64 52 75 -6-2-4131 可以被任意设置 .我们令 i = 0. 结点 2 的单纯形乘子是什么？在最小代价流问题中，有一个多余的限制 .0计算生成树的单纯形乘子10计算生成树的单纯形乘子13 64 52 75 -6-2-413结点 7 的单纯形乘子是什么？0 (1,2)的即约代价是c12 - 1 + 2 = 0.因此 5 - 0 + 2 = 0.-511计算生成树的单纯形乘子13 64 52 75 -6-2-413结点 3 的单纯形乘子是什么？0 (7,1)的即约代价是c12 - 1 + 2 = 0.c71 - 7 + 1 = 0.因此 -6 - 7 +0 = 0.-5-612计算生成树的单纯形乘子13 64 52 75 -6-2-413结点 6 的单纯形乘子是什么？0-5-6-213计算生成树的单纯形乘子13 64 52 75 -6-2-413结点 4 的单纯形乘子是什么？0-5-6-2 -114计算生成树的单纯形乘子13 64 52 75 -6-2-413结点 5 的单纯形乘子是什么？0-5-6-2 -1-415计算生成树的单纯形乘子13 64 52 75 -6-2-413有单纯形乘子和这棵树相关 .它们不依弧流，也不依赖 非树弧上 的代价 .0-5-6-2 -1-4 -116网络单纯形算法124532 -42, $44, $21, $45, $53, $5 4, $14, $2 3, $45 -3最小代价流问题TLU17生成树流124532 -410032 01 35 -3初始生成树解TLU18单纯形乘子和即约代价124530 -40?400 -20 23 -2初始单纯形乘子和即约代价TLUc45 = 2什么弧是违规的？319添加违规弧到生成树，创建圈124533,2 4,04,1 3,3弧 (2,1) 添加到了树中TLU圈是什么，能发送多少流？2, 14, 01, 05, 3u14, x1420环绕圈发送流124533,0 4,24,3 3,3沿着圈发送 2 单位的流TLU下一个生成树是什么？2, 14, 01, 05, 3u14, x1421旋转 (pivot)之后124533,0 4,24,3 3,3更新的生成树TLU在旋转中，一条弧加入到 T， 而另一条弧从 T 删除 .2, 14, 01, 05, 3u14, x1422更新乘子12453当前乘子和即约代价TLU0 -404400 -20 23 -23我们如何使c21 = 0 ，且让其他树弧有 0 即约代价？23从 T 删除 (2,1) 把 T 分裂成两部分12453添加 到树的一侧不影响任何树弧的即约代价，除了 (2,1). 为什么 ?TLU0 -404400 -20 23+ -2+3应该选择什么样的 值，产生即约代价 (2,1) = 0?24更新的乘子和即约代价12453更新的乘子和即约代价 .TLU0 -402202 00 21 -43这棵树的解是最优的吗？25添加一条违反弧到生成树，创建圈12453添加弧 (3,4) 到生成树TLU3,0 4,24,3 3,32, 14, 01, 05, 3 圈是什么，能发送多少流？26沿圈发送流12453沿圈发送 1 个单位的流 .TLU3,0 4,24,2 3,22, 24, 01, 05, 3 下一个生成树解是什么？27下一个生成树解12453这是更新的生成树解TLU3,0 4,24,2 3,22, 24, 01, 05, 328更新