網(wǎng)絡(luò)單純形算法

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

2、生成樹(shù)流計(jì)算生成樹(shù)流 1 36 4 5 27 1 3 -6 -4 1 2 3 在弧在弧(3,2)中的流是中的流是 什么？什么？ 23 網(wǎng)絡(luò)單純形算法 5 計(jì)算生成樹(shù)流計(jì)算生成樹(shù)流 1 36 4 5 27 1 3 -6 -4 1 2 3 在弧在弧(2,6) 中的流是中的流是 什么什么? 23 6 網(wǎng)絡(luò)單純形算法 6 計(jì)算生成樹(shù)流計(jì)算生成樹(shù)流 1 36 4 5 27 1 3 -6 -4 1 2 3 在弧在弧(7,1)中的流是中的流是 什么什么? 23 64 網(wǎng)絡(luò)單純形算法 7 計(jì)算生成樹(shù)流計(jì)算生成樹(shù)流 1 36 4 5 27 1 3 -6 -4 1 2 3 在弧在弧(1,6)中的流是中的流是 什么

3、什么? 23 64 3 網(wǎng)絡(luò)單純形算法 8 計(jì)算生成樹(shù)流計(jì)算生成樹(shù)流 1 36 4 5 27 1 3 -6 -4 1 2 3 注釋注釋: 有兩中不同的方有兩中不同的方 法計(jì)算在法計(jì)算在(1,2)的流，的流， 兩種方法都給出流為兩種方法都給出流為 4.這是巧合嗎？這是巧合嗎？ 23 64 43 網(wǎng)絡(luò)單純形算法 9 計(jì)算生成樹(shù)的單純形乘子計(jì)算生成樹(shù)的單純形乘子 1 36 4 5 27 5 -6 -2 -4 1 3 這里是有弧代價(jià)的生這里是有弧代價(jià)的生 成樹(shù)成樹(shù).如何選擇結(jié)點(diǎn)勢(shì)如何選擇結(jié)點(diǎn)勢(shì) 以便即約代價(jià)是以便即約代價(jià)是0呢呢 ？ 回憶回憶: (i,j)的即約代的即約代 價(jià)是價(jià)是 cij - i +

4、 j 網(wǎng)絡(luò)單純形算法 10 1 36 4 5 27 5 -6 -2 -4 1 3 1 可以被任意設(shè)置可以被任意設(shè)置. 我們令我們令 i = 0. 結(jié)點(diǎn)結(jié)點(diǎn) 2 的單純形乘子的單純形乘子 是什么？是什么？ 在最小代價(jià)流問(wèn)題中在最小代價(jià)流問(wèn)題中 ，有一個(gè)多余的限制，有一個(gè)多余的限制. 0 計(jì)算生成樹(shù)的單純形乘子計(jì)算生成樹(shù)的單純形乘子 網(wǎng)絡(luò)單純形算法 11 計(jì)算生成樹(shù)的單純形乘子計(jì)算生成樹(shù)的單純形乘子 1 36 4 5 27 5 -6 -2 -4 1 3 結(jié)點(diǎn)結(jié)點(diǎn) 7 的單純形乘子的單純形乘子 是什么？是什么？ 0 (1,2)的即約代價(jià)是的即約代價(jià)是 c12 - 1 + 2 = 0. 因此因此5 -

5、 0 + 2 = 0.-5 網(wǎng)絡(luò)單純形算法 12 計(jì)算生成樹(shù)的單純形乘子計(jì)算生成樹(shù)的單純形乘子 1 36 4 5 27 5 -6 -2 -4 1 3 結(jié)點(diǎn)結(jié)點(diǎn) 3 的單純形乘子的單純形乘子 是什么？是什么？ 0 (7,1)的即約代價(jià)是的即約代價(jià)是 c12 - 1 + 2 = 0. c71 - 7 + 1 = 0. 因此因此 -6 - 7 +0 = 0. -5 -6 網(wǎng)絡(luò)單純形算法 13 計(jì)算生成樹(shù)的單純形乘子計(jì)算生成樹(shù)的單純形乘子 1 36 4 5 27 5 -6 -2 -4 1 3 結(jié)點(diǎn)結(jié)點(diǎn) 6 的單純形乘子的單純形乘子 是什么？是什么？ 0 -5 -6 -2 網(wǎng)絡(luò)單純形算法 14 計(jì)算生成

6、樹(shù)的單純形乘子計(jì)算生成樹(shù)的單純形乘子 1 36 4 5 27 5 -6 -2 -4 1 3 結(jié)點(diǎn)結(jié)點(diǎn) 4 的單純形乘子的單純形乘子 是什么？是什么？ 0 -5 -6 -2 -1 網(wǎng)絡(luò)單純形算法 15 計(jì)算生成樹(shù)的單純形乘子計(jì)算生成樹(shù)的單純形乘子 1 36 4 5 27 5 -6 -2 -4 1 3 結(jié)點(diǎn)結(jié)點(diǎn) 5 的單純形乘子的單純形乘子 是什么？是什么？ 0 -5 -6 -2 -1 -4 網(wǎng)絡(luò)單純形算法 16 計(jì)算生成樹(shù)的單純形乘子計(jì)算生成樹(shù)的單純形乘子 1 36 4 5 27 5 -6 -2 -4 1 3 有單純形乘子和這棵有單純形乘子和這棵 樹(shù)相關(guān)樹(shù)相關(guān).它們不依弧它們不依弧 流，也不依賴(lài)

7、流，也不依賴(lài)非樹(shù)弧非樹(shù)弧 上上的代價(jià)的代價(jià). 0 -5 -6 -2 -1 -4 -1 網(wǎng)絡(luò)單純形算法 17 網(wǎng)絡(luò)單純形算法網(wǎng)絡(luò)單純形算法 1 2 4 5 3 2-4 2, $4 4, $2 1, $4 5, $5 3, $5 4, $1 4, $2 3, $4 5-3 最小代價(jià)流問(wèn)題最小代價(jià)流問(wèn)題 T L U 網(wǎng)絡(luò)單純形算法 18 生成樹(shù)流生成樹(shù)流 1 2 4 5 3 2-4 1 0 0 3 2 0 1 3 5-3 初始生成樹(shù)解初始生成樹(shù)解 T L U 網(wǎng)絡(luò)單純形算法 19 單純形乘子和即約代價(jià)單純形乘子和即約代價(jià) 1 2 4 5 3 0-4 0 ? 4 0 0 -2 0 2 3-2 初始單純

8、形乘子和即約代價(jià)初始單純形乘子和即約代價(jià) T L U c45 = 2 什么弧是違規(guī)的？什么弧是違規(guī)的？ 3 網(wǎng)絡(luò)單純形算法 20 添加違規(guī)弧到生成樹(shù)，創(chuàng)建圈添加違規(guī)弧到生成樹(shù)，創(chuàng)建圈 1 2 4 5 3 3,2 4,0 4,1 3,3 弧弧(2,1) 添加到了樹(shù)中添加到了樹(shù)中 T L U 圈是什么，能圈是什么，能 發(fā)送多少流？發(fā)送多少流？ 2, 1 4, 0 1, 0 5, 3 u14, x14 網(wǎng)絡(luò)單純形算法 21 環(huán)繞圈發(fā)送流環(huán)繞圈發(fā)送流 1 2 4 5 3 3,0 4,2 4,3 3,3 沿著圈發(fā)送沿著圈發(fā)送2 單位的流單位的流 T L U 下一個(gè)生成樹(shù)下一個(gè)生成樹(shù) 是什么？是什么？ 2

9、, 1 4, 0 1, 0 5, 3 u14, x14 網(wǎng)絡(luò)單純形算法 22 旋轉(zhuǎn)旋轉(zhuǎn)(pivot)之后之后 1 2 4 5 3 3,0 4,2 4,3 3,3 更新的生成樹(shù)更新的生成樹(shù) T L U 在旋轉(zhuǎn)中，一條在旋轉(zhuǎn)中，一條 弧加入到弧加入到 T， 而而 另一條弧從另一條弧從 T 刪刪 除除. 2, 1 4, 0 1, 0 5, 3 u14, x14 網(wǎng)絡(luò)單純形算法 23 更新乘子更新乘子 1 2 4 5 3 當(dāng)前乘子和即約代價(jià)當(dāng)前乘子和即約代價(jià) T L U 0-4 0 4 4 0 0 -2 0 2 3-2 3 我們?nèi)绾问刮覀內(nèi)绾问筩 21 = 0 ，且讓其，且讓其 他樹(shù)弧有他樹(shù)弧有 0

10、即即 約代價(jià)？約代價(jià)？ 網(wǎng)絡(luò)單純形算法 24 從從 T 刪除刪除 (2,1) 把把 T 分裂成兩部分分裂成兩部分 1 2 4 5 3 添加添加 到樹(shù)的一側(cè)不影響任何樹(shù)到樹(shù)的一側(cè)不影響任何樹(shù) 弧的即約代價(jià)，除了弧的即約代價(jià)，除了 (2,1). 為為 什么什么? T L U 0-4 0 4 4 0 0 -2 0 2 3+ -2+ 3 應(yīng)該選擇什么應(yīng)該選擇什么 樣的樣的 值，值， 產(chǎn)生即約代產(chǎn)生即約代 價(jià)價(jià) (2,1) = 0? 網(wǎng)絡(luò)單純形算法 25 更新的乘子和即約代價(jià)更新的乘子和即約代價(jià) 1 2 4 5 3 更新的乘子和即約代價(jià)更新的乘子和即約代價(jià). T L U 0-4 0 2 2 0 2 0

11、0 2 1-4 3 這棵樹(shù)的解是這棵樹(shù)的解是 最優(yōu)的嗎？最優(yōu)的嗎？ 網(wǎng)絡(luò)單純形算法 26 添加一條違反弧到生成樹(shù)，創(chuàng)建圈添加一條違反弧到生成樹(shù)，創(chuàng)建圈 1 2 4 5 3 添加弧添加弧 (3,4) 到生成樹(shù)到生成樹(shù) T L U 3,0 4,2 4,3 3,3 2, 1 4, 0 1, 0 5, 3 圈是什么，能圈是什么，能 發(fā)送多少流？發(fā)送多少流？ 網(wǎng)絡(luò)單純形算法 27 沿圈發(fā)送流沿圈發(fā)送流 1 2 4 5 3 沿圈發(fā)送沿圈發(fā)送1 個(gè)單位的流個(gè)單位的流. T L U 3,0 4,2 4,2 3,2 2, 2 4, 0 1, 0 5, 3 下一個(gè)生成樹(shù)下一個(gè)生成樹(shù) 解是什么？解是什么？ 網(wǎng)絡(luò)單純

12、形算法 28 下一個(gè)生成樹(shù)解下一個(gè)生成樹(shù)解 1 2 4 5 3 這是更新的生成樹(shù)解這是更新的生成樹(shù)解 T L U 3,0 4,2 4,2 3,2 2, 2 4, 0 1, 0 5, 3 網(wǎng)絡(luò)單純形算法 29 更新的乘子更新的乘子 1 2 4 5 3 這是當(dāng)前乘子這是當(dāng)前乘子. T L U 0-4 0 2 2 0 2 0 0 2 1-4 3 我們?nèi)绾涡薷奈覀內(nèi)绾涡薷?乘子？乘子？ 網(wǎng)絡(luò)單純形算法 30 更新的乘子更新的乘子 1 2 4 5 3 這是更新的乘子這是更新的乘子. T L U 0 -4 + 0 2 2 0 2 0 0 2 1-4 3 應(yīng)該是什應(yīng)該是什 么值么值? 網(wǎng)絡(luò)單純形算法 31

13、更新的乘子更新的乘子 1 2 4 5 3 這是更新的乘子這是更新的乘子. T L U 0-6 -2 4 2 0 2 0 0 0 1-4 3 當(dāng)前生成樹(shù)解當(dāng)前生成樹(shù)解 是最優(yōu)的嗎？是最優(yōu)的嗎？ 網(wǎng)絡(luò)單純形算法 32 最優(yōu)解最優(yōu)解 1 2 4 5 3 這是最優(yōu)解這是最優(yōu)解. T L U 0-6 -2 4 2 0 2 0 0 0 1-4 3 沒(méi)有弧違反最沒(méi)有弧違反最 優(yōu)條件優(yōu)條件. 網(wǎng)絡(luò)單純形算法 33 尋找圈尋找圈 1 36 10 11 87 912 5 2 網(wǎng)絡(luò)單純形算法 34 使用深度和前驅(qū)使用深度和前驅(qū) 1 36 10 11 87 912 5 2 0 2 4 depth(5) = 4; de

14、pth(3) = 2; 用用 pred(5) 替換結(jié)點(diǎn)替換結(jié)點(diǎn)5 網(wǎng)絡(luò)單純形算法 35 使用深度和前驅(qū)使用深度和前驅(qū) 1 36 10 11 87 912 5 2 0 2 3 depth(9) = 3; depth(3) = 2; 用用 pred(9) 替換結(jié)點(diǎn)替換結(jié)點(diǎn)9 網(wǎng)絡(luò)單純形算法 36 使用深度和前驅(qū)使用深度和前驅(qū) 1 36 10 11 87 912 5 2 0 22 depth(2) = 2; depth(3) = 2; 用用 pred(2) 替換結(jié)點(diǎn)替換結(jié)點(diǎn)2; 用用 pred(3) 替換結(jié)點(diǎn)替換結(jié)點(diǎn)3 網(wǎng)絡(luò)單純形算法 37 使用深度和前驅(qū)使用深度和前驅(qū) 1 36 10 11 87

15、912 5 2 0 11 depth(8) = 1; depth(7) = 1; 用用 pred(8) 替換結(jié)點(diǎn)替換結(jié)點(diǎn)8; 用用 pred(1) 替換結(jié)點(diǎn)替換結(jié)點(diǎn)7 網(wǎng)絡(luò)單純形算法 38 使用深度和前驅(qū)使用深度和前驅(qū) 1 36 10 11 87 912 5 2 0 結(jié)點(diǎn)結(jié)點(diǎn)3和和5的的 最小共同祖最小共同祖 先被找到先被找到. 網(wǎng)絡(luò)單純形算法 39 更新乘子：使用線和深度更新乘子：使用線和深度 1 36 10 11 87 912 5 2 假設(shè)弧假設(shè)弧 (1,8) 將從樹(shù)中刪將從樹(shù)中刪 除除.以結(jié)點(diǎn)以結(jié)點(diǎn)8 為根的子樹(shù)為根的子樹(shù) 是什么？是什么？ 網(wǎng)絡(luò)單純形算法 40 跟隨從結(jié)點(diǎn)跟隨從結(jié)點(diǎn)8開(kāi)始的線開(kāi)始的線 1 36 10 11 87 912 5 2 什么是什么是 thread(8)? 網(wǎng)絡(luò)單純形算法 41 跟隨從結(jié)點(diǎn)跟隨從結(jié)點(diǎn)8開(kāi)始的線開(kāi)始的線 1 36 10 11 87