网络单纯形算法.ppt

下一个生成树解453这是更新的生成树解TLU3,04,24,23,22,24,01,05,3更新的乘子453这是当前乘子.TLU0-4022020021-43我们如何修改乘子？更新的乘子453这是更新的乘子.TLU0-4+?022020021-43?应该是什么值?更新的乘子453这是更新的乘子.TLU0-6-242020001-43当前生成树解是最优的吗？最优解453这是最优解.TLU0-6-242020001-43没有弧违反最优条件.13610118791252寻找圈Obtainanetwork,andusethesamenetworktoillustratetheshortestpathproblemforcommunicationnetworks,themaxflowproblem,theminimumcostflowproblem,andthemulticommodityflowproblem.Thiswillbeaveryefficientwayofintroducingthefourproblems.(Perhapsunder10minutesofclasstime.)15.082和6.855J网络单纯形动画计算生成树流136452713-6-4123有供应和需求的树.(假设所有的其他弧的流是0)在弧(4,3)中的流是什么？计算生成树流136452713-6-4123为了计算流，向上迭代树，寻找流能唯一确定的弧.在弧(5,3)中的流是什么？2计算生成树流136452713-6-4123在弧(3,2)中的流是什么？23计算生成树流136452713-6-4123在弧(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这里是有弧代价的生成树.如何选择结点势以便即约代价是0呢？回忆:(i,j)的即约代价是

cij-?i+?j计算生成树的单纯形乘子13645275-6-2-413?1可以被任意设置.我们令?i=0.结点2的单纯形乘子是什么？在最小代价流问题中，有一个多余的限制.0计算生成树的单纯形乘子13645275-6-2-413结点7的单纯形乘子是什么？0(1,2)的即约代价是c12-?1+?2=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-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网络单纯形算法4532-42,$44,$21,$45,$53,$54,