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

1、網(wǎng)絡單純形算法15.082 和和 6.855J網(wǎng)絡單純形動畫網(wǎng)絡單純形動畫網(wǎng)絡單純形算法2計算生成樹流計算生成樹流136452713-6-4123有供應和需求的樹有供應和需求的樹.(假設所有的其他弧假設所有的其他弧的流是的流是0)在弧在弧(4,3)中的流是中的流是什么？什么？網(wǎng)絡單純形算法3計算生成樹流計算生成樹流136452713-6-4123為了計算流，向上為了計算流，向上迭代樹，尋找流能迭代樹，尋找流能唯一確定的弧唯一確定的弧.在弧在弧(5,3)中的流是中的流是什么？什么？2網(wǎng)絡單純形算法4計算生成樹流計算生成樹流136452713-6-4123在弧在弧(3,2)中的流是中的流是什么？什

2、么？23網(wǎng)絡單純形算法5計算生成樹流計算生成樹流136452713-6-4123在弧在弧(2,6) 中的流是中的流是什么什么?236網(wǎng)絡單純形算法6計算生成樹流計算生成樹流136452713-6-4123在弧在弧(7,1)中的流是中的流是什么什么?2364網(wǎng)絡單純形算法7計算生成樹流計算生成樹流136452713-6-4123在弧在弧(1,6)中的流是中的流是什么什么?23643網(wǎng)絡單純形算法8計算生成樹流計算生成樹流136452713-6-4123注釋注釋: 有兩中不同的有兩中不同的方法計算在方法計算在(1,2)的流的流，兩種方法都給出流，兩種方法都給出流為為 4.這是巧合嗎？這是巧合嗎？2

3、36443網(wǎng)絡單純形算法9計算生成樹的單純形乘子計算生成樹的單純形乘子13645275-6-2-413這里是有弧代價的生這里是有弧代價的生成樹成樹.如何選擇結點勢如何選擇結點勢以便即約代價是以便即約代價是0呢呢？回憶回憶: (i,j)的即約代的即約代價是價是 cij - i + j網(wǎng)絡單純形算法1013645275-6-2-413 1 可以被任意設置可以被任意設置.我們令我們令 i = 0. 結點結點 2 的單純形乘子的單純形乘子是什么？是什么？在最小代價流問題中在最小代價流問題中，有一個多余的限制，有一個多余的限制.0計算生成樹的單純形乘子計算生成樹的單純形乘子網(wǎng)絡單純形算法11計算生成樹的

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

5、6-2-413結點結點 6 的單純形乘子的單純形乘子是什么？是什么？0-5-6-2網(wǎng)絡單純形算法14計算生成樹的單純形乘子計算生成樹的單純形乘子13645275-6-2-413結點結點 4 的單純形乘子的單純形乘子是什么？是什么？0-5-6-2-1網(wǎng)絡單純形算法15計算生成樹的單純形乘子計算生成樹的單純形乘子13645275-6-2-413結點結點 5 的單純形乘子的單純形乘子是什么？是什么？0-5-6-2-1-4網(wǎng)絡單純形算法16計算生成樹的單純形乘子計算生成樹的單純形乘子13645275-6-2-413有單純形乘子和這棵有單純形乘子和這棵樹相關樹相關.它們不依弧它們不依弧流，也不依賴流，也

6、不依賴非樹弧非樹弧上上的代價的代價.0-5-6-2-1-4-1網(wǎng)絡單純形算法17網(wǎng)絡單純形算法網(wǎng)絡單純形算法124532-42, $44, $21, $45, $53, $5 4, $14, $23, $45-3最小代價流問題最小代價流問題TLU網(wǎng)絡單純形算法18生成樹流生成樹流124532-410032 0135-3初始生成樹解初始生成樹解TLU網(wǎng)絡單純形算法19單純形乘子和即約代價單純形乘子和即約代價124530-40?400 -2023-2初始單純形乘子和即約代價初始單純形乘子和即約代價TLUc45 = 2什么弧是違規(guī)的？什么弧是違規(guī)的？3網(wǎng)絡單純形算法20添加違規(guī)弧到生成樹，創(chuàng)建圈添加

7、違規(guī)弧到生成樹，創(chuàng)建圈124533,2 4,04,13,3弧弧(2,1) 添加到了樹中添加到了樹中TLU圈是什么，能圈是什么，能發(fā)送多少流？發(fā)送多少流？2, 14, 01, 05, 3u14, x14網(wǎng)絡單純形算法21環(huán)繞圈發(fā)送流環(huán)繞圈發(fā)送流124533,0 4,24,33,3沿著圈發(fā)送沿著圈發(fā)送2 單位的流單位的流TLU下一個生成樹下一個生成樹是什么？是什么？2, 14, 01, 05, 3u14, x14網(wǎng)絡單純形算法22旋轉旋轉(pivot)之后之后124533,0 4,24,33,3更新的生成樹更新的生成樹TLU在旋轉中，一條在旋轉中，一條弧加入到弧加入到 T， 而而另一條弧從另一條弧

8、從 T 刪刪除除.2, 14, 01, 05, 3u14, x14網(wǎng)絡單純形算法23更新乘子更新乘子12453當前乘子和即約代價當前乘子和即約代價TLU0-404400 -2023-23我們如何使我們如何使c 21 = 0 ，且讓，且讓其他樹弧有其他樹弧有 0 即約代價？即約代價？網(wǎng)絡單純形算法24從從 T 刪除刪除 (2,1) 把把 T 分裂成兩部分分裂成兩部分12453添加添加 到樹的一側不影響任何樹到樹的一側不影響任何樹弧的即約代價，除了弧的即約代價，除了 (2,1). 為為什么什么?TLU0-404400 -2023+ -2+ 3應該選擇什么應該選擇什么樣的樣的 值，值，產(chǎn)生即約代產(chǎn)生

9、即約代價價 (2,1) = 0?網(wǎng)絡單純形算法25更新的乘子和即約代價更新的乘子和即約代價12453更新的乘子和即約代價更新的乘子和即約代價.TLU0-402202 0021-43這棵樹的解是這棵樹的解是最優(yōu)的嗎？最優(yōu)的嗎？網(wǎng)絡單純形算法26添加一條違反弧到生成樹，創(chuàng)建圈添加一條違反弧到生成樹，創(chuàng)建圈12453添加弧添加弧 (3,4) 到生成樹到生成樹TLU3,0 4,24,33,32, 14, 01, 05, 3圈是什么，能圈是什么，能發(fā)送多少流？發(fā)送多少流？網(wǎng)絡單純形算法27沿圈發(fā)送流沿圈發(fā)送流12453沿圈發(fā)送沿圈發(fā)送1 個單位的流個單位的流.TLU3,0 4,24,23,22, 24,

10、 01, 05, 3下一個生成樹下一個生成樹解是什么？解是什么？網(wǎng)絡單純形算法28下一個生成樹解下一個生成樹解12453這是更新的生成樹解這是更新的生成樹解TLU3,0 4,24,23,22, 24, 01, 05, 3網(wǎng)絡單純形算法29更新的乘子更新的乘子12453這是當前乘子這是當前乘子.TLU0-402202 0021-43我們如何修改我們如何修改乘子？乘子？網(wǎng)絡單純形算法30更新的乘子更新的乘子12453這是更新的乘子這是更新的乘子.TLU0-4 + 02202 0021-43 應該是什應該是什么值么值?網(wǎng)絡單純形算法31更新的乘子更新的乘子12453這是更新的乘子這是更新的乘子.TL

11、U0-6-24202 0001-43當前生成樹解當前生成樹解是最優(yōu)的嗎？是最優(yōu)的嗎？網(wǎng)絡單純形算法32最優(yōu)解最優(yōu)解12453這是最優(yōu)解這是最優(yōu)解.TLU0-6-24202 0001-43沒有弧違反最沒有弧違反最優(yōu)條件優(yōu)條件.網(wǎng)絡單純形算法33尋找圈尋找圈13610118791252網(wǎng)絡單純形算法34使用深度和前驅使用深度和前驅13610118791252024depth(5) = 4;depth(3) = 2;用用 pred(5)替換結點替換結點5網(wǎng)絡單純形算法35使用深度和前驅使用深度和前驅13610118791252023depth(9) = 3;depth(3) = 2;用用 pred(

12、9)替換結點替換結點9網(wǎng)絡單純形算法36使用深度和前驅使用深度和前驅13610118791252022depth(2) = 2;depth(3) = 2;用用 pred(2)替換結點替換結點2;用用 pred(3)替換結點替換結點3網(wǎng)絡單純形算法37使用深度和前驅使用深度和前驅13610118791252011depth(8) = 1;depth(7) = 1;用用 pred(8)替換結點替換結點8;用用 pred(1)替換結點替換結點7網(wǎng)絡單純形算法38使用深度和前驅使用深度和前驅136101187912520結點結點3和和5的的最小共同祖最小共同祖先被找到先被找到.網(wǎng)絡單純形算法39更新乘子：使用線和深度更新乘子：使用線和深度13610118791252假設弧假設弧 (1,8)將從樹中刪將從樹中刪除除.以結點以結點8為根的子樹為根的子樹是什么？是什么？網(wǎng)絡單純形算法40跟隨從結點跟隨從結點8開始的線開始的線13610118791252什么是什么是thread(8)?網(wǎng)絡單純形算法41跟隨從結點跟隨從結點8開始的線開始的線13610118791252什么是什么是thread(3)?網(wǎng)絡單純形算法42跟隨從結點跟隨從結點8開始的線開始的線13610118791252什么是什么是thread(10)?網(wǎng)絡單純形算法43