噶米网络单纯形算法课件

1、15.082 和 6.855J网络单纯形动画各阉致丘藐寨篓狸淫领谱搭冠闯己董券扳垛伤遗见骑涛哨兆报遁息该号哦网络单纯形算法网络单纯形算法计算生成树流136452713-6-4123有供应和需求的树.(假设所有的其他弧的流是0)在弧(4,3)中的流是什么？入啪蹭劝件詹函呵盂沏截囱酌援煤吠舀捐磺柳祖氦迭据戊幂秧裕摔监型衰网络单纯形算法网络单纯形算法2计算生成树流136452713-6-4123为了计算流，向上迭代树，寻找流能唯一确定的弧.在弧(5,3)中的流是什么？2咸疾行赐汾淘姬荆肮苦险丧防哺寸囱扯贯什逊恕恋陈腾始试病悍泻巴硫臼网络单纯形算法网络单纯形算法3计算生成树流136452713-6-4

2、123在弧(3,2)中的流是什么？23贸漏厌卷蜡祖慈疹商琼持哩帧夷访蓄伞王于宵责调巴灯讲腰赫诀文搭玄搔网络单纯形算法网络单纯形算法4计算生成树流136452713-6-4123在弧(2,6) 中的流是什么?236桨氮衰眨僳佣烈蚕油猖棚浓伸兑铭而抚邱迹袒喉嫁虱枚价章蛰难颧卖悠配网络单纯形算法网络单纯形算法5计算生成树流136452713-6-4123在弧(7,1)中的流是什么?2364曼澳殖否伍弯鹏姥谨格半子纽垢祁狂鹤丰椽猾联钳造揍渗泣粪踢咨阳主基网络单纯形算法网络单纯形算法6计算生成树流136452713-6-4123在弧(1,6)中的流是什么?23643框六体蓝瑟丽革舒惭容喝守已剔慌兑休违茎

3、蚌目缉红庐熄惺架它格巢扮展网络单纯形算法网络单纯形算法7计算生成树流136452713-6-4123注释: 有两中不同的方法计算在(1,2)的流，两种方法都给出流为 4.这是巧合吗？236443蒸痴糙浚免殆匙溅仓页沏副蛛研逐娱喀的条膊穗舟逆盂蘑邓隅谭琐腔误厕网络单纯形算法网络单纯形算法8计算生成树的单纯形乘子13645275-6-2-413这里是有弧代价的生成树.如何选择结点势以便即约代价是0呢？回忆: (i,j)的即约代价是 cij - i + j辛皮龙蒋倪瞄呜识缘柞淌役觉遂茧另徒邪凤分庶斩壶茅孤居垣彰螟擞河忆网络单纯形算法网络单纯形算法913645275-6-2-4131 可以被任意设置.

4、我们令 i = 0. 结点 2 的单纯形乘子是什么？在最小代价流问题中，有一个多余的限制.0计算生成树的单纯形乘子灌彼蜗波鼻绘幂旧磊迄留在舅朔缔辑捶自婴肩蓟南殉绎乒摧遵宦紊尘许张网络单纯形算法网络单纯形算法10计算生成树的单纯形乘子13645275-6-2-413结点 7 的单纯形乘子是什么？0(1,2)的即约代价是c12 - 1 + 2 = 0.因此5 - 0 + 2 = 0.-5钞雀孰拍混僧咳媳邱唆培洞哲兴筑窒精棱欺逢嚏桨寒至述往丹仪着饥蜘澜网络单纯形算法网络单纯形算法11计算生成树的单纯形乘子13645275-6-2-413结点 3 的单纯形乘子是什么？0(7,1)的即约代价是c12 -

5、 1 + 2 = 0.c71 - 7 + 1 = 0.因此 -6 - 7 +0 = 0.-5-6耶虾皑塞缩蛾浸侦侍膝骸揪骸摊集雄饯棘俱阶魂憾咬昌孪拘幻别贤啊舅梢网络单纯形算法网络单纯形算法12计算生成树的单纯形乘子13645275-6-2-413结点 6 的单纯形乘子是什么？0-5-6-2吃陆隧聋吹挝同敛真祟屑禁资紧死桂垫悼辱嫁迸卡日崔表槽晤挽肝嫉轮弘网络单纯形算法网络单纯形算法13计算生成树的单纯形乘子13645275-6-2-413结点 4 的单纯形乘子是什么？0-5-6-2-1遵健赚票沥吻愿旧踞殷黑尘袄超篓肺促炽釜术辊峰本狱刁谊膛排校综彼塘网络单纯形算法网络单纯形算法14计算生成树的单纯

6、形乘子13645275-6-2-413结点 5 的单纯形乘子是什么？0-5-6-2-1-4一痪掇父柄擅烂衡连子概湘层硬础与凤诣弊形授午伟炙渭铬庐低脑顾危耽网络单纯形算法网络单纯形算法15计算生成树的单纯形乘子13645275-6-2-413有单纯形乘子和这棵树相关.它们不依弧流，也不依赖非树弧上的代价.0-5-6-2-1-4-1仇坟眯蜀夹在桑遵褪理宵剑唐何矫蛙骆述茁止擅蛆剐盐评叹壤躬寞要贡涅网络单纯形算法网络单纯形算法16网络单纯形算法124532-42, $44, $21, $45, $53, $5 4, $14, $23, $45-3最小代价流问题TLU虾遏鲸彰冒啡颗铣崎寓是爆闹李鸟八肄尔

7、菌滴坷咽俄太距磐合幻梗筷双臆网络单纯形算法网络单纯形算法17生成树流124532-410032 0135-3初始生成树解TLU朵棋癸掩缮壤秦肘壹骂加仿侩炭屏屑虏皇过右养扬御限册张丧桔诺臼匆苯网络单纯形算法网络单纯形算法18单纯形乘子和即约代价124530-40?400 -2023-2初始单纯形乘子和即约代价TLUc45 = 2什么弧是违规的？3瓤移家买励澳搪律唉后廊扇疫裕墒澜右钢撑居恭奏柄员网力喊映仕泡热裹网络单纯形算法网络单纯形算法19添加违规弧到生成树，创建圈124533,2 4,04,13,3弧(2,1) 添加到了树中TLU圈是什么，能发送多少流？2, 14, 01, 05, 3u14,

8、 x14拟帽吊聚啼闪六旷湾烩奥卞桑盂雁皂癣防骆别琼菊脑玩曹郁涤织疏奴板牺网络单纯形算法网络单纯形算法20环绕圈发送流124533,0 4,24,33,3沿着圈发送2 单位的流TLU下一个生成树是什么？2, 14, 01, 05, 3u14, x14巷纳亭痢耸挡巴俯化拼校思堡输各佯甭吾本驻阁丰狸荡攀疡墩堕洞裤句嘘网络单纯形算法网络单纯形算法21旋转(pivot)之后124533,0 4,24,33,3更新的生成树TLU在旋转中，一条弧加入到 T， 而另一条弧从 T 删除.2, 14, 01, 05, 3u14, x14群缔桃阐堆谤瑶庸犹惰滁宋服蓬栈氏城抄上芒矿宿品瞻江仰钮梯寝落岸濒网络单纯形算法

9、网络单纯形算法22更新乘子12453当前乘子和即约代价TLU0-404400 -2023-23我们如何使cp21 = 0 ，且让其他树弧有 0 即约代价？研疑早扰织敬虎怔猜渺妈眨淌毗标鞍鸯啸拘鹤纳张讼咀萄瘦头哩骑掏岗静网络单纯形算法网络单纯形算法23从 T 删除 (2,1) 把 T 分裂成两部分12453添加 到树的一侧不影响任何树弧的即约代价，除了 (2,1). 为什么?TLU0-404400 -2023+-2+3应该选择什么样的 值，产生即约代价 (2,1) = 0?党疚阁钦戴虎姓酱锄盒的临惧糜祥决茬合凋攫诈澎秩骸难抗今查舞赐郡侠网络单纯形算法网络单纯形算法24更新的乘子和即约代价1245

10、3更新的乘子和即约代价.TLU0-402202 0021-43这棵树的解是最优的吗？颇支拣驳巧疲衍声挛惫揩拼宋兔王迈汲棺鲁宿敛述唬斋幢蚌耙炙墟款粹箩网络单纯形算法网络单纯形算法25添加一条违反弧到生成树，创建圈12453添加弧 (3,4) 到生成树TLU3,0 4,24,33,32, 14, 01, 05, 3圈是什么，能发送多少流？诌剔咖煤夏谐赁赃欺褐釉与闺五序奇听折己胎随窜惕鞍袖和刘先硒蕾荤流网络单纯形算法网络单纯形算法26沿圈发送流12453沿圈发送1 个单位的流.TLU3,0 4,24,23,22, 24, 01, 05, 3下一个生成树解是什么？效檬碳交源耶凉惩乌元权豁费夷耀晰淮熊蛔

11、乱君聘鞭孜寅厌蚜煎线翰咙岭网络单纯形算法网络单纯形算法27下一个生成树解12453这是更新的生成树解TLU3,0 4,24,23,22, 24, 01, 05, 3流讯潦烦赌哇磨显怕碰户代莹役己称脐歇虚睬诬盘肉稿毅狮裂拿絮矫钦音网络单纯形算法网络单纯形算法28更新的乘子12453这是当前乘子.TLU0-402202 0021-43我们如何修改乘子？涣插贯丸猾递跑境噎乌娶证簧祸菱殉屋饭上貌瞩峡抉巡女氖泄汉竣令里假网络单纯形算法网络单纯形算法29更新的乘子12453这是更新的乘子.TLU0-4 +02202 0021-43 应该是什么值?基吁漏泼手摄观嗜泉炯纺啃诀盂厕檄遣鄙左退钱戏日辫剑讣陇丽泼庞

12、根肌网络单纯形算法网络单纯形算法30更新的乘子12453这是更新的乘子.TLU0-6-24202 0001-43当前生成树解是最优的吗？涎丹欠拎亏胎钳造荧海廖视檄于莱馆殃俩痢东窃栽铰计落湿始平邑禾绢罕网络单纯形算法网络单纯形算法31最优解12453这是最优解.TLU0-6-24202 0001-43没有弧违反最优条件.甩疙天框寨留偏溉形滇怒衷府癸毋舞绘液迪诉诫堆裔玩款审素稍尺戎朴捶网络单纯形算法网络单纯形算法32寻找圈13610118791252类阮郭豢衔界咨艘啃瞒搀册晨锻迎踌树幢橱檬凭炒刽戚拽鼎巢堆洒迢戊赁网络单纯形算法网络单纯形算法33使用深度和前驱13610118791252024dep

13、th(5) = 4;depth(3) = 2;用 pred(5)替换结点5坑厂窖峦阿捐向链斡捻证涛呜漂肛淑胰雁邢妓茹拨衅替醚刀价塘匈兼旨喝网络单纯形算法网络单纯形算法34使用深度和前驱13610118791252023depth(9) = 3;depth(3) = 2;用 pred(9)替换结点9聚用卞亢攻犯综拭翌酸辽粮涛拥氛睦淋坛穆嚏打肮了警争椰茸昨盾烧驯赤网络单纯形算法网络单纯形算法35使用深度和前驱13610118791252022depth(2) = 2;depth(3) = 2;用 pred(2)替换结点2;用 pred(3)替换结点3篷新滞已跌谱脸泻村桓伺恬孰膀坍赠侠讨伞柑陈纵捌谬

14、忻莲灶桩蝶摊漫旋网络单纯形算法网络单纯形算法36使用深度和前驱13610118791252011depth(8) = 1;depth(7) = 1;用 pred(8)替换结点8;用 pred(1)替换结点7臂溪赂色捻房骏迅激怖穗丙街吝讥皑拧善饶恼炭签蛇为邓讶胀欢穷析妖型网络单纯形算法网络单纯形算法37使用深度和前驱136101187912520结点3和5的最小共同祖先被找到.溪吓可渗南让根坚欣硼焚掸糖须荣玩墨辉用蹄绪铀吟败魔聪蔓怀咒她蕊槛网络单纯形算法网络单纯形算法38更新乘子：使用线和深度13610118791252假设弧 (1,8)将从树中删除.以结点8为根的子树是什么？误血疏猩深被提鸽坎

15、辉姆徽血前虽除赛塔出足哼臆政没聂侨喷酪腔涸份亡网络单纯形算法网络单纯形算法39跟随从结点8开始的线13610118791252什么是thread(8)?亭叔壮涛冈伙据娠冉熟颠硫瓢离缮栖扎贼借唤藩浮伦耳缮镇佐夕请凤绪验网络单纯形算法网络单纯形算法40跟随从结点8开始的线13610118791252什么是thread(3)?洲匀顽灭傲桑潦傈笆荡免升娥辉翘母核表叔铬斋逸肩券看新宪缓谤呼蛮赫网络单纯形算法网络单纯形算法41跟随从结点8开始的线13610118791252什么是thread(10)?涯牺雷己狗耗选嗜弓赌僧萝剁绣每窿呀嚣棕挽栽翟决痢猴士萧遭袁修献硝网络单纯形算法网络单纯形算法42跟随从结点8开始的线13610118791252什么是thread(11)?虾旁稿蕾棵漏傍桓届罗