線性規(guī)劃圖與網(wǎng)絡(luò)分析

1、圖與網(wǎng)絡(luò)是專門研究圖的理論圖與網(wǎng)絡(luò)是專門研究圖的理論 圖論中的圖是用點(diǎn)和邊（?。﹣矸磮D論中的圖是用點(diǎn)和邊（弧）來反映系統(tǒng)中各對象之間相互關(guān)聯(lián)的關(guān)系，映系統(tǒng)中各對象之間相互關(guān)聯(lián)的關(guān)系，它與幾何圖、工程圖是不一樣的，圖中它與幾何圖、工程圖是不一樣的，圖中點(diǎn)的相對位置、點(diǎn)與點(diǎn)之間連線的長短點(diǎn)的相對位置、點(diǎn)與點(diǎn)之間連線的長短曲直，對于反映對象之間的關(guān)系并不是曲直，對于反映對象之間的關(guān)系并不是重要的。重要的。 簡單圖與多重圖例：5、路：簡單路（邊不同）；、路：簡單路（邊不同）； 初等路（點(diǎn)也不同）初等路（點(diǎn)也不同）. 圈（回路）：圈（回路）：連通圖與非連通圖連通圖與非連通圖（1）指邊或弧的有關(guān)數(shù)量指標(biāo)。

2、根據(jù)實(shí)指邊或弧的有關(guān)數(shù)量指標(biāo)。根據(jù)實(shí) 際背景可賦予不同含義，如距離、時間、際背景可賦予不同含義，如距離、時間、 費(fèi)用、容量等。費(fèi)用、容量等。（3）指定了指定了的的的的 。包括無向網(wǎng)絡(luò)、有向網(wǎng)絡(luò)、混合。包括無向網(wǎng)絡(luò)、有向網(wǎng)絡(luò)、混合 網(wǎng)絡(luò)。網(wǎng)絡(luò)。（2）圖圖G中點(diǎn)、邊中點(diǎn)、邊(弧弧) 以及邊（?。┥系囊约斑叄ɑ。┥系?權(quán)的總體，稱為賦權(quán)圖。權(quán)的總體，稱為賦權(quán)圖。(1) 、權(quán)矩陣(2)、關(guān)聯(lián)矩陣(3)、相鄰矩陣V3V4V6無向圖有向圖V4連通圖連通圖樹樹練習(xí)題練習(xí)題1：下圖中：下圖中1表示某生產(chǎn)隊(duì)的水源地，表示某生產(chǎn)隊(duì)的水源地，其它圖形表示水稻田，用堤埂分割為很多小其它圖形表示水稻田，用堤埂分割為很多

3、小塊。為了用水灌溉，需要挖開一些堤埂。問塊。為了用水灌溉，需要挖開一些堤埂。問最少挖開多少堤埂，才能使水澆灌到每小塊最少挖開多少堤埂，才能使水澆灌到每小塊稻田。稻田。 123456789101112將水源地及每小塊稻田各用一個點(diǎn)來表示，邊表示它們之間有堤埂相連，那么連接這些點(diǎn)的樹圖的邊數(shù)即為至少要挖開的堤埂數(shù)。在任一圖G=（V，E）中，當(dāng)點(diǎn)集V確定后，樹圖是G中邊數(shù)最少的連通圖。練習(xí)題2：如圖所示，有一菜園被田埂分割為6塊，現(xiàn)菜園各塊均灌溉了水，問至少需要打通多少田埂才能把所有的水排放掉？ 若將樹作為圖的一個子圖來考慮若將樹作為圖的一個子圖來考慮例：連通圖G支撐子圖1是一個樹支撐子圖2是一個樹

4、支撐子圖3是一個樹支撐子圖4是一個樹支撐子圖5是一個樹TijwTWmin*)(步驟：步驟：1、先任取一個圈，從圈中去掉一條權(quán)最大的邊，若在同一個、先任取一個圈，從圈中去掉一條權(quán)最大的邊，若在同一個圈中有幾條都是權(quán)最大邊，則任選其中的一條邊去掉。圈中有幾條都是權(quán)最大邊，則任選其中的一條邊去掉。2、在余下的子圖中，重復(fù)上述步驟，直至沒有圈為止。、在余下的子圖中，重復(fù)上述步驟，直至沒有圈為止。避圈法：開始選一條最小權(quán)的邊，在以后的每一步中，避圈法：開始選一條最小權(quán)的邊，在以后的每一步中，總從未被選取的邊中選一條權(quán)最小的邊，并使之與已總從未被選取的邊中選一條權(quán)最小的邊，并使之與已選取的邊不構(gòu)成圈，如果

5、同時有幾條都是最小權(quán)的邊，選取的邊不構(gòu)成圈，如果同時有幾條都是最小權(quán)的邊，則可從中任選一條。則可從中任選一條。23464524練習(xí)練習(xí)1：上圖表示：上圖表示5個村莊的線路圖，每邊旁的數(shù)個村莊的線路圖，每邊旁的數(shù)字表示村莊之間線路的長度，現(xiàn)要求沿線路架設(shè)字表示村莊之間線路的長度，現(xiàn)要求沿線路架設(shè)有線廣播線，不僅使各村都能聽到有線廣播，而有線廣播線，不僅使各村都能聽到有線廣播，而且使廣播線總長度最短。且使廣播線總長度最短。v1331728541034v7v6v5v4v2v3224234423v1331723v7v6v5v4v2v3答案：答案：11，19PijwPWmin*)(管道鋪設(shè)、線路安排、管

6、道鋪設(shè)、線路安排、 廠區(qū)布局、設(shè)備更新等。廠區(qū)布局、設(shè)備更新等。網(wǎng)絡(luò)中所有的弧權(quán)均網(wǎng)絡(luò)中所有的弧權(quán)均 ，即，即 。0ijw ： 標(biāo)號標(biāo)號 P P（固定標(biāo)號或永久性標(biāo)號）（固定標(biāo)號或永久性標(biāo)號）從始點(diǎn)到該標(biāo)號點(diǎn)的最短路權(quán)。從始點(diǎn)到該標(biāo)號點(diǎn)的最短路權(quán)。 標(biāo)號標(biāo)號 T T（臨時性標(biāo)號）（臨時性標(biāo)號）從始點(diǎn)到該標(biāo)號點(diǎn)的最短路權(quán)從始點(diǎn)到該標(biāo)號點(diǎn)的最短路權(quán)。jjlvpvT11)(),(min jv s svj jv Avvj),(1 jv 第二步：考慮滿足條件第二步：考慮滿足條件 的所有點(diǎn)的所有點(diǎn) ； 具有具有T 標(biāo)號，即標(biāo)號，即 ， 為為T 標(biāo)號點(diǎn)集。標(biāo)號點(diǎn)集。 修改修改 的的T標(biāo)號為標(biāo)號為 ，并，并將

7、結(jié)果仍記為將結(jié)果仍記為T(vj)0)(1vp 第一步：始點(diǎn)標(biāo)上固定標(biāo)號第一步：始點(diǎn)標(biāo)上固定標(biāo)號 ,其余各其余各點(diǎn)標(biāo)臨時性標(biāo)號點(diǎn)標(biāo)臨時性標(biāo)號 T(vj)= , j 1;第三步：若網(wǎng)絡(luò)圖中已無第三步：若網(wǎng)絡(luò)圖中已無T標(biāo)號點(diǎn)，停止標(biāo)號點(diǎn)，停止計(jì)算。否則計(jì)算。否則,令令 , 然后將然后將 的的T 標(biāo)號改成標(biāo)號改成P 標(biāo)號標(biāo)號 ，轉(zhuǎn)入第，轉(zhuǎn)入第二步。二步。此時，要注意將第二步中的此時，要注意將第二步中的 改為改為 。 1v 0jv )()(min0jsvjvTvTj 0jv 1v 4v1v2v3v4v7v6v8456475541v59674v1v2v3v4v6v5v722561413412步驟步驟 考察

8、點(diǎn)考察點(diǎn) T標(biāo)號點(diǎn)集標(biāo)號點(diǎn)集 標(biāo)標(biāo) 號（號（ 表表P標(biāo)號）標(biāo)號）1v1v2，v7v1 v2 v3 v4 v5 v6 v7 0 - - - - - - 0+20+5 2 5 - - - - 23456v2v3v4v5v6v3，v7v4，v7v5，v6，v7v5，v72+22+42+6 4 6 8 - -4+14+3 5 8 7 - 5+45+1 5+4 8 6 96+2 8 8v78+18反向追蹤，得到最優(yōu)路線：反向追蹤，得到最優(yōu)路線：v1 v2 v3 v4 v6 v7v5若先把若先把v7的標(biāo)號改為永久性標(biāo)號，的標(biāo)號改為永久性標(biāo)號，該怎麼繼續(xù)作下去？該怎麼繼續(xù)作下去？56v6v7v5，v7v5v1 v2 v3 v4 v5 v6 v7 6+2 8 8 8+18 8 6 9 5127563425527313571練習(xí)1：求1275634231351(0)(2)(3)(4)(7)(8)(13)1275634223351(0)(2)(3)(4)(7)(8)(13)5273121344784