網(wǎng)絡單純形算法ppt課件

1、15.082 和和 6.855J網(wǎng)絡單純形動畫網(wǎng)絡單純形動畫計算生成樹流計算生成樹流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、成樹.如何選擇結(jié)點勢如何選擇結(jié)點勢以便即約代價是以便即約代價是0呢呢？回想回想: (i,j)的即約代的即約代價是價是 cij - i + j13645275-6-2-413 1 可以被任意設置可以被任意設置.我們令我們令 i = 0. 結(jié)點結(jié)點 2 的單純形乘子的單純形乘子是什么？是什么？在最小代價流問題中在最小代價流問題中，有一個多余的限制，有一個多余的限制.0計算生成樹的單純形乘子計算生成樹的單純形乘子計算生成樹的單純形乘子計算生成樹的單純形乘子13645275-6-2-413結(jié)點結(jié)點 7 的單純形乘子的單純形乘子是什么？是什么？0(1,2)的即約代價是的即約代價是c12 - 1 + 2

4、= 0.因此因此5 - 0 + 2 = 0.-5計算生成樹的單純形乘子計算生成樹的單純形乘子13645275-6-2-413結(jié)點結(jié)點 3 的單純形乘子的單純形乘子是什么？是什么？0(7,1)的即約代價是的即約代價是c12 - 1 + 2 = 0.c71 - 7 + 1 = 0.因此因此 -6 - 7 +0 = 0.-5-6計算生成樹的單純形乘子計算生成樹的單純形乘子13645275-6-2-413結(jié)點結(jié)點 6 的單純形乘子的單純形乘子是什么？是什么？0-5-6-2計算生成樹的單純形乘子計算生成樹的單純形乘子13645275-6-2-413結(jié)點結(jié)點 4 的單純形乘子的單純形乘子是什么？是什么？0

5、-5-6-2-1計算生成樹的單純形乘子計算生成樹的單純形乘子13645275-6-2-413結(jié)點結(jié)點 5 的單純形乘子的單純形乘子是什么？是什么？0-5-6-2-1-4計算生成樹的單純形乘子計算生成樹的單純形乘子13645275-6-2-413有單純形乘子和這棵有單純形乘子和這棵樹相關樹相關.它們不依弧它們不依弧流，也不依賴非樹弧流，也不依賴非樹弧上的代價上的代價.0-5-6-2-1-4-1網(wǎng)絡單純形算法網(wǎng)絡單純形算法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什么弧是違規(guī)的？什么弧是違規(guī)的？3添加違規(guī)弧到生成樹，創(chuàng)建圈添加違規(guī)弧到生成樹，創(chuàng)建圈124533,2 4,04,13,3弧弧(2,1) 添加到了樹中添加到了樹中TLU圈是什么，能圈是什么，能發(fā)送多少流？發(fā)送多少流？2, 14, 01, 05, 3u14, x14環(huán)繞圈發(fā)送流環(huán)繞圈發(fā)送流124533,0 4,24,33,3沿著圈發(fā)送沿著圈發(fā)送2 單位的流單位的流TLU下一個生成樹下一個生成樹是什么？是

7、什么？2, 14, 01, 05, 3u14, x14旋轉(zhuǎn)旋轉(zhuǎn)(pivot)之后之后124533,0 4,24,33,3更新的生成樹更新的生成樹TLU在旋轉(zhuǎn)中，一條在旋轉(zhuǎn)中，一條弧加入到弧加入到 T， 而而另一條弧從另一條弧從 T 刪刪除除.2, 14, 01, 05, 3u14, x14更新乘子更新乘子12453當前乘子和即約代價當前乘子和即約代價TLU0-404400 -2023-23我們?nèi)绾问刮覀內(nèi)绾问筩p21 = 0 ，且，且讓其他樹弧有讓其他樹弧有 0 即約代價？即約代價？從從 T 刪除刪除 (2,1) 把把 T 分裂成兩部分分裂成兩部分12453添加添加 到樹的一側(cè)不影響任何到樹的

8、一側(cè)不影響任何樹弧的即約代價，除了樹弧的即約代價，除了 (2,1). 為什么為什么?TLU0-404400 -2023+-2+3應該選擇什么應該選擇什么樣的樣的 值，產(chǎn)值，產(chǎn)生即約代價生即約代價 (2,1) = 0?更新的乘子和即約代價更新的乘子和即約代價12453更新的乘子和即約代價更新的乘子和即約代價.TLU0-402202 0021-43這棵樹的解是這棵樹的解是最優(yōu)的嗎？最優(yōu)的嗎？添加一條違反弧到生成樹，創(chuàng)建圈添加一條違反弧到生成樹，創(chuàng)建圈12453添加弧添加弧 (3,4) 到生成樹到生成樹TLU3,0 4,24,33,32, 14, 01, 05, 3圈是什么，能圈是什么，能發(fā)送多少流

9、？發(fā)送多少流？沿圈發(fā)送流沿圈發(fā)送流12453沿圈發(fā)送沿圈發(fā)送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我們?nèi)绾涡薷奈覀內(nèi)绾涡薷某俗?？乘子？更新的乘子更新的乘?2453這是更新的乘子這是更新的乘子.TLU0-4 +02202 0021-43 應該是什應該是什么值么值?更新的乘

10、子更新的乘子12453這是更新的乘子這是更新的乘子.TLU0-6-24202 0001-43當前生成樹解當前生成樹解是最優(yōu)的嗎？是最優(yōu)的嗎？最優(yōu)解最優(yōu)解12453這是最優(yōu)解這是最優(yōu)解.TLU0-6-24202 0001-43沒有弧違反最沒有弧違反最優(yōu)條件優(yōu)條件.尋找圈尋找圈13610118791252使用深度和前驅(qū)使用深度和前驅(qū)13610118791252024depth(5) = 4;depth(3) = 2;用用 pred(5)替換結(jié)點替換結(jié)點5使用深度和前驅(qū)使用深度和前驅(qū)13610118791252023depth(9) = 3;depth(3) = 2;用用 pred(9)替換結(jié)點替換

11、結(jié)點9使用深度和前驅(qū)使用深度和前驅(qū)13610118791252022depth(2) = 2;depth(3) = 2;用用 pred(2)替換結(jié)點替換結(jié)點2;用用 pred(3)替換結(jié)點替換結(jié)點3使用深度和前驅(qū)使用深度和前驅(qū)13610118791252011depth(8) = 1;depth(7) = 1;用用 pred(8)替換結(jié)點替換結(jié)點8;用用 pred(1)替換結(jié)點替換結(jié)點7使用深度和前驅(qū)使用深度和前驅(qū)136101187912520結(jié)點結(jié)點3和和5的的最小共同祖最小共同祖先被找到先被找到.更新乘子：使用線和深度更新乘子：使用線和深度13610118791252假設弧假設弧 (1,8)將從樹中刪將從樹中刪除除.以結(jié)點以結(jié)點8為根的子樹為根的子樹是什么？是什么？跟隨從結(jié)點跟隨從結(jié)點8開始的線開始的線13610118791252什么是什么是thread(8)?跟隨從結(jié)點跟隨從結(jié)點8開始的線開始的線13610118791252什么是什么是thread(3)?跟隨從結(jié)點跟隨從結(jié)點8開始的線開始的線13610118791252什么是什么是thread(10)?跟隨