(精選)《運(yùn)籌學(xué)》復(fù)習(xí)參考資料

1、運(yùn)籌學(xué)復(fù)習(xí)參考資料資料加工、整理人一一楊峰（函授總站高級(jí)講師）要求掌握的各部分知識(shí)點(diǎn)第一部分 線性規(guī)劃問(wèn)題的求解（相當(dāng)于教材的第一章）資一重要算法：?jiǎn)渭冃蔚?、?M法單純形迭代、表上作業(yè)法、匈牙利法第二部分 動(dòng)態(tài)規(guī)劃問(wèn)題的求解（相當(dāng)于教材的第三章）資一重要算法：圖上標(biāo)號(hào)法第三部分網(wǎng)絡(luò)分析問(wèn)題的求解（相當(dāng)于教材的第四章）資一重要算法：破圈法、TP標(biāo)號(hào)法、尋求網(wǎng)絡(luò)最大流的標(biāo)號(hào)法第 四部分 存儲(chǔ)論簡(jiǎn)介（相當(dāng)于教材的第七章）楊老師關(guān)于學(xué)習(xí)方法的提示：運(yùn)籌學(xué)屬于應(yīng)用數(shù)學(xué)的范疇，本門(mén)課程在管理類(lèi)本科生層次開(kāi)設(shè)時(shí)，又稱(chēng)“管理運(yùn)籌學(xué)”，是現(xiàn)代數(shù)學(xué)理論和計(jì)算機(jī)技術(shù)應(yīng)用于管理科學(xué)的新興學(xué)科。非應(yīng)用數(shù)學(xué)系（專(zhuān)業(yè)）

2、學(xué)生學(xué)習(xí)本門(mén)課程之前務(wù)必先具備“高數(shù)（線性代數(shù)、概率論與數(shù)理統(tǒng)計(jì)）的知識(shí)基礎(chǔ)。學(xué)員同志們通過(guò)學(xué)習(xí)，必須領(lǐng)會(huì)數(shù)學(xué)建模的思想、系統(tǒng)工程的思想。韭全口制學(xué)生學(xué)習(xí)時(shí),.反要求知道若干典型數(shù)學(xué)模型及其算法的操作即封須. 明白“怎樣做”，而不必去過(guò)問(wèn)“為什么”要這樣做。第一部分線性規(guī)劃問(wèn)題的求解一、兩個(gè)變量的線性規(guī)劃問(wèn)題的圖解法：概念準(zhǔn)備：定義：滿足所有約束條件的解為可行解；可行解的全體稱(chēng)為可行（解）域。定義：達(dá)到目標(biāo)的可行解為最優(yōu)解。圖解法：圖解法采用直角坐標(biāo)求解：X1橫軸；X2豎軸。1、將約束條件（取等號(hào)）用直線繪出；2、確定可行解域；3、繪出目標(biāo)函數(shù)的圖形（等值線），確定它向最優(yōu)解的移動(dòng)方向；注：求

3、極大值沿價(jià)值系數(shù)向量的正向移動(dòng)；求極小值沿價(jià)值系數(shù)向量的反向移動(dòng)。4、確定最優(yōu)解及目標(biāo)函數(shù)值。參考例題：（只要求下面這些有唯一最優(yōu)解的類(lèi)型）例1:某廠生產(chǎn)甲、乙兩種產(chǎn)品，這兩種產(chǎn)品均需在 A、B、C三種不同的設(shè)備上加工，每 種產(chǎn)品在不同設(shè)備上加工所需的工時(shí)不同，這些產(chǎn)品銷(xiāo)售后所能獲得利潤(rùn)以及這三種加工設(shè)備因各種條件限制所能使用的有效加工總時(shí)數(shù)如下表所示：消設(shè) 備ABC利潤(rùn)（萬(wàn)元）甲35970乙95330啟效總工時(shí)540450720問(wèn)：該廠應(yīng)如何組織生產(chǎn)，即生產(chǎn)多少甲、乙產(chǎn)品使得該廠的總利潤(rùn)為最大?（此題也可用“單純形法”或化“對(duì)偶問(wèn)題”用大M法求解）解：設(shè)XI、X2為生產(chǎn)甲、乙產(chǎn)品的數(shù)量s.t

4、.max z=70x1+30X23X19x25405X15x24509X13x2720X1,x20、可行解域?yàn)閛abcd。，最優(yōu)解為b點(diǎn)由方程組解出 X1=75, X2=155xi 5X24509x1 3x2720* Xi.X= = (75, 15)X2. maX z =Z*= 70 x 75+30X 15=5700例3:用圖解法求解2x1乂210xi乂28乂27xi,乂20、s.t.max z = 6x 1+4x2max z = 6 X2+4X6=36解:可行解域?yàn)閛abcd。，最優(yōu)解為b點(diǎn)由方程組* Xi X二X22x1 x2 10 x1 x2 8(2, 6) T解出 Xi=2, X2=6

5、例5:用圖解法求解、min z = - 3必+先 s.t.x14x2 32x1 5x212x1 2x28x1, X20解:4由方程組x142x1 5x212解出xi=4,X2二一5* X二Xix24（4，5） .min z = -3X4+7= 11_55二、標(biāo)準(zhǔn)型線性規(guī)劃問(wèn)題的單純形解法：一般思路：1、用簡(jiǎn)單易行的方法獲得初始基本可行解；2、對(duì)上述解進(jìn)行檢驗(yàn)，檢驗(yàn)其是否為最優(yōu)解，若是，停止迭代，否則轉(zhuǎn)入3；3、根據(jù)0 l規(guī)則確定改進(jìn)解的方向；4、根據(jù)可能改進(jìn)的方向進(jìn)行迭代得到新的解；5、根據(jù)檢驗(yàn)規(guī)則對(duì)新解進(jìn)行檢驗(yàn)，若是最優(yōu)解，則停止迭代，否則轉(zhuǎn)入3，直至最優(yōu)解。具體做法（可化歸 標(biāo)準(zhǔn)型的情況）

6、：設(shè)已知s.t.a11x1a21 x1am1 x1max z = ca12 x2a22x2am2x2xj0， j對(duì)第 i 個(gè)方程加入松弛變量1X1+ c 2X2 + c nXna1n xna2nXnamnxn2，Xn+i ， i =1b1b2bmm得到a11x1a12 x2a1n xnxn 1b1a21 x1a22x2a2nxnxn 2b2am1 x1am2x2amnXnXn m bm列表計(jì)算，格式、算法如下：Xj0， j2，CbXbbC1X1C2X2Cn+mXn+me lCn+1Xn+1b1ana12a1 n+mC n+2 .Xn+2 .b2 .a21a22a2 n+m.Cn+m.Xn+m.

7、bnam1am2am n+mZ1Z2Zn+ma 1(T 2CT n+mm注： Zj =Cn+1 aij + c n+2 a2j + c n+m amj=cn i aij , (j=1 , 2,n + m)i 1(T j =Cj Zj ,當(dāng)(T j w 0時(shí)，當(dāng)前解最優(yōu)注：由max cn確定所對(duì)應(yīng)的行的變量為“入基變量”；由0 L=min曳鼠0確定所對(duì)應(yīng)的行的變量為“出基變量”，行、列交 i叉處為主元素，迭代時(shí)要求將主元素變?yōu)?,此列其余元素變?yōu)?。例1：用單純形法求解（本題即是本資料P2 “圖解法”例1的單純形解法；也可化”對(duì)偶 問(wèn)題”求解）max z =70X1+30X2s.t.3X1 9X

8、2 5405X1 5X24509xi 3X2720X1, x2 0解：加入松弛變量X3, X4, X5,得到等效的標(biāo)準(zhǔn)模型:max z =70x i+30X2+0 x 3+0 x 4+0 x 5s.t. max z =70 X 75+30X 15=57003xi 9x2 X35405x1 5x2x44509x1 3x2x5720xj 0,j 1,2,.,5列表計(jì)算如下*CbXbb70Xi30X20x3540390x4450550x5720(9)30070 T300x3300080x4500(10/3)70x18011/37070/3020/3 T0x31800030x2150170x17510

9、570070 030 0* . X= (75,15, 180,0,0)T000X3X4X5e l100540/3 =180010450/5 =90001720/9 =8000000010-1/3300/8 =37.501-5/950/10/3 =15001/980/1/3 =2400070/900-70/91 12/5103/10-1/60-1/101/60220/30-2-20/3例 2：用單純形法求解max z =7x 1+12x2s.t.9x1 4x2 3604x1 5x2 2003x1 10x2 300x1， x2 0解：加入松弛變量x3， x4， x5 ，得到等效的標(biāo)準(zhǔn)模型：max

10、z =7x 1+12x2+0 x3+0 x4+0 x5s.t.9x1 4x2 x3 3604x1 5x2x4 2003x1 10x2x5 300xj 0, j 1,2,.,5列表計(jì)算如下：QXbb7X112X20X30X40X5e l0X336094100360/4 =900X420045010200/5 =400X53003(10)001300/10 =3000000712T0000X324078/10010-2/5240/78/10 =2400/780X450(5/2)001-1/250/5/2 =2012X2303/101001/1030/3/10 =10018/512006/517/5

11、 T000 6/50X38400178/2529/257X1201002/5-1/512X2240103/254/28712034/2511/3542800034/25-11/35* . X= (20,24, 84，0, 0)T.max z =7 X20+12X 24=428三、非標(biāo)準(zhǔn)型線性規(guī)劃問(wèn)題的解法：1、一般地，對(duì)于約束條件組：若為“w”，則加松弛變量，使方程成為“=若為，則減松弛變量，使方程成為“= 我們?cè)谇懊鏄?biāo)準(zhǔn)型中是規(guī)定目標(biāo)函數(shù)求極大值。如果在實(shí)際問(wèn)題中遇到的是求極小值，則為非標(biāo)準(zhǔn)型?？勺魅缦绿幚恚河赡繕?biāo)函數(shù)min z=cjxj變成等價(jià)的目標(biāo)函數(shù) max( z) =( cjxj)j

12、 ij i令一z=z/,. min z= max z/2、等式約束一一大M法：通過(guò)加人工變量的方法，構(gòu)造人造基，從而產(chǎn)生初始可行基。人工變量的價(jià)值系數(shù)為-M M是很大的正數(shù)，從原理上理解又稱(chēng)為“懲罰系數(shù)”。(課本P29)類(lèi)型一:目標(biāo)函數(shù)仍為max z,約束條件組w與=。例 1: max z =3x 1+5x2s.t.x142x2 123x1 2x218x1, x20解：加入松弛變量x3, x4,得到等效的標(biāo)準(zhǔn)模型：max z =3x 1+5x2s.t.x x3 42x2x4 123x1 2x218xj 0,j 1,2,3,4其中第三個(gè)約束條件雖然是等式，但因無(wú)初始解，所以增加一個(gè)人工變量乂5,

13、得至上max z =3x1+5x2 Mx5Xi X342x2X4 12st3xi 2x2X5 18Xj0, j 1,2,5單純形表求解過(guò)程如下：CbXbb3X15X20X30X4MX5e l0X34(1)01004/1 =40X41202010-MX5183200118/3 =6-3M-2M00-M3M+ 3T5+2M0003Xi4101000X4120201012/2 =6-MX560(2)-3016/2 =33-2M3+3M0-M05T-3-3M003Xi4101004/1 =40X4600(3)1-16/3 =25X2301 3/201/23/( 2/3)=9/2一35 9/205/20

14、09/2 T0-M- 5/23Xi2100-1/31/305x3x2260011/3-1/30101/20363503/210003/2-M-1X*= (2, 6, 2, 0) T. max z =3 x 2+5X6=36類(lèi)型二:目標(biāo)函數(shù)min z,約束條件組與=例2:用單純形法求解min z =4x 1+3x2s.t.2xi 4x2 163xi 2x2 12x1, x2 0解：減去松弛變量x3, x4,并化為等效的標(biāo)準(zhǔn)模型: max z/ = - 4xi 3x2s.t.2x1 4x2 x3 163xi 2x2x4 12xj 0,j 1,2,3,4增加人工變量乂5、x6,得到：max z/ =

15、 4xi 3x2 MxMxs.t9義旦義寸單純形表求解過(guò)程如下:CbXbb一 40X30X4-MX5-MX6e lX1X2MX5162(4)-101016/4=4-MX612320-10112/2=65M6MMM-M-M5M- 46M- 3TMM00-3X241/21-1/401/404/1/2=8-MX64(2)01/2-11/214/2=22Mk 3/2-33/4 M/2MM/2-3/4一 M2Mk 5/2 T0M/2- 3/4一 M3/4 3M/20-3X2301 3/81/43/81/4一 4X12101/4-1/21/41/2一 4-31/85/41/8-5/4-1700-1/8-5

16、/4_M 1/8-M+ 5/4* .X= (2, 3, 0, 0) .min z = max Z = (17) =17四、對(duì)偶問(wèn)題的解法：什么是對(duì)偶問(wèn)題？1、在資源一定的條件下，作出最大的貢獻(xiàn)；2、完成給定的工作，所消耗的資源最少。引例（與本資料P2例1 “圖解法”、P7例1 “單純形法”同）：某工廠生產(chǎn)甲、乙兩種 產(chǎn)品，這些產(chǎn)品均需在 A、B、C三種不同的設(shè)備上加工，每種產(chǎn)品在不同設(shè)備 上加工時(shí)需要不同的工時(shí)，這些產(chǎn)品售后所能獲得的利潤(rùn)值以及這三種加工設(shè) 備因各種條件下所能使用的有效總工時(shí)數(shù)如下表：設(shè)ABC利潤(rùn)（萬(wàn)元）消、備耗m甲35970乙95330啟效總工時(shí)540450720問(wèn)：該廠應(yīng)如

17、何組織生產(chǎn)，即生產(chǎn)多少甲、乙產(chǎn)品使得該廠的總利潤(rùn)為最大?解:原問(wèn)題一一設(shè)Xi、X2為生產(chǎn)甲、乙產(chǎn)品的數(shù)量max z = 70x i+30X2s.t.3xi 9X25405xi 5X24509x1 3x2720X1, x20將這個(gè)原問(wèn)題化為它的對(duì)偶問(wèn)題設(shè)yi、y2、y2分別為設(shè)備A、B、C單位工時(shí)數(shù)的加工費(fèi)。min w = 540y 1+450y2 +720y3s.t.3y1 5y2 9y3 709y1 5y2 3y3 30yi 0， i 1，2，3用大M法，先化為等效的標(biāo)準(zhǔn)模型：max w/ = 540y1 450y2 720y3s.t.3y1 5y2 9y3 y4709y1 5y2 3y3y

18、5 30yj 0,j 1,2,.,5增加人工變量y6、 y7 ，得到：max z/ = 540y1 450y2 720y3 My6 My7s.t3y1 5y2 9y3 y4y6 709y1 5y2 3y3y5y7 30yj 0, j 1,2,.,5大M法單純形表求解過(guò)程如下： 540450-72000-M-MCbXbbe lyiy2y3y4y乎yMy670359-101070/330/9=10/-My730(9)530-1013-12M-10M -12M MM-M-M12m 540 T10Mk 450 12M- 720- M M00-My660010/3(8)-11/311/360/8=2.5

19、10/3/1/3 540y110/315/91/30-1/901/9=10-300+10/3M-8M-180 M M/3+60 MM/3 600-150+10/3M 8M-540 TMM/3600- M/3+6015/2/5/1 720y315/205/1211/81/241/81/242=185/6/5/12 540yi5/61(5/12)01/24-1/8-1/241/8=2 540 572- 720 -135/2 475/12-135/2 75/20125 T0135/2 -475/12 135/2 M 75/2M 720y320/3-1011/61/61/6-1/6 450y2212/

20、5101/103/10-1/103/10 360450-72075157515 5700-18000-751575-M 15 M.該對(duì)偶問(wèn)題的最優(yōu)解是y= (0, 2,20 ，0) T最優(yōu)目標(biāo)函數(shù)值 min w = ( 5700) =5700五、運(yùn)輸規(guī)劃問(wèn)題:運(yùn)輸規(guī)劃問(wèn)題的特殊解法一一“表上作業(yè)法”解題步驟:1、找出初始調(diào)運(yùn)方案。即在（mx n）產(chǎn)銷(xiāo)平衡表上給出m+n-1個(gè)數(shù)字格。（最小元素法）2、（對(duì)空格）求檢驗(yàn)數(shù)。判別是否達(dá)到最優(yōu)解。如已是最優(yōu)解，則停止計(jì)算，否則轉(zhuǎn)到下一步。（閉回路法）3、對(duì)方案進(jìn)行改善，找出新的調(diào)運(yùn)方案。（根據(jù)檢驗(yàn)結(jié)果選擇入基變量，用 表上閉回路法調(diào) 整一一即迭代計(jì)算，

21、得新的基本可行解）4、重復(fù)2、3,再檢驗(yàn)、再迭代，直到求得最優(yōu)調(diào)運(yùn)方案。類(lèi)型一:供求平衡的運(yùn)輸規(guī)劃問(wèn)題（又稱(chēng)“供需平衡”、“產(chǎn)銷(xiāo)平衡”）引例：某鋼鐵公司有三個(gè)鐵礦和四個(gè)煉鐵廠， 鐵礦的年產(chǎn)礦石量分別為100萬(wàn)噸、80萬(wàn)噸和50萬(wàn)噸，煉鐵廠年需礦石量分別為 50萬(wàn)噸、70萬(wàn)噸、80萬(wàn)噸解：用“表上作業(yè)法”求解先用最低費(fèi)用法（最小元素法）求此問(wèn)題的初始基礎(chǔ)可行解:費(fèi)銷(xiāo)地BiB2BbRSAi152067330-6510020X80xA2708144420803020X30A125332033251050x50xx銷(xiāo)量dj50708030230 230 初始方案:A350Z=15X 20+3X 80+

22、70x 30+8X 20+20X 30+3X 50=3550 （噸.公里）對(duì)的初始可行解進(jìn)行迭代 （表上閉回路法），求最優(yōu)解：費(fèi)銷(xiāo)BiB2BbR產(chǎn)量SAl1520143301210020X80XA70-53814一 92080X50X30A12320202510503020Xx銷(xiāo)量dj50708030230230 最優(yōu)方案:用表上閉回路法調(diào)整后，從上表可看出，所有檢驗(yàn)數(shù)0,已得最優(yōu)解Z=15X 20+3X 80+8x 50+20X 30+12X 30+3X 20=1960 （噸.公里）解法分析：如何求檢驗(yàn)數(shù)并由此確定入基變量？有數(shù)字的空格稱(chēng)為“基格”、打x的空格稱(chēng)為“空格”，標(biāo)號(hào)為偶數(shù)的頂點(diǎn)稱(chēng)

23、為偶點(diǎn)、標(biāo)號(hào)為奇數(shù)的頂點(diǎn)稱(chēng)為奇點(diǎn)，出發(fā)點(diǎn)算0故為偶點(diǎn)。找出所有空格的閉回路后計(jì)算它們的檢驗(yàn)數(shù) ij Cj Cj,必須j00,才得到最優(yōu)奇點(diǎn) 偶點(diǎn)解。否則，應(yīng)選所有中正的最大者對(duì)應(yīng)的變量Xj為入基變量進(jìn)行迭代（調(diào)整）。檢驗(yàn)后調(diào)整運(yùn)輸方案的辦法是：在空格的閉回路中所有的偶點(diǎn)均加上奇點(diǎn)中的最小運(yùn)量，所有的奇 點(diǎn)均減去奇點(diǎn)中的最小運(yùn)量。重復(fù)以上兩步，再檢驗(yàn)、再調(diào)整，直到求得最優(yōu)運(yùn)輸方案。類(lèi)型二:供求不平衡的運(yùn)輸規(guī)劃問(wèn)題sidj ,則是供大于求（供過(guò)于求）問(wèn)題，可設(shè)一虛銷(xiāo)地段+1,令i1j1mnmnci,n+1 =0， dn+1=sidj ，轉(zhuǎn)化為產(chǎn)銷(xiāo)平衡問(wèn)題。若sidj ，則是供小i1j1i1j1nm

24、于求（供不應(yīng)求）問(wèn)題，可設(shè)一虛產(chǎn)地Am+1,令Cm+1,j=。，Sm+1=dj 與，j1i1轉(zhuǎn)化為產(chǎn)銷(xiāo)平衡問(wèn)題。（,2,，簿,2,，n）六、工作指派問(wèn)題：工作指派問(wèn)題的數(shù)學(xué)模型假定有 n 項(xiàng)工作需要完成，恰好有n 個(gè)人每人可去完成其中一項(xiàng)工作，效果要好。工作指派問(wèn)題的特殊解法“ 匈牙利法 ” （ 考！ ！ ） 解題步驟：1、使系數(shù)矩陣（效率矩陣）各行、各列出現(xiàn)零元素。作法：行約簡(jiǎn)一系數(shù)矩陣各行元素減去所在行的最小元素，列約簡(jiǎn)一再?gòu)乃镁仃?的各列減去所在列最小元素。2、試求最優(yōu)解。如能找出n 個(gè)位于不同行不同列的零元素，令對(duì)應(yīng)的xij = 1，其余xij = 0，得最優(yōu)解，結(jié)束；否則下一步。作

25、法：由獨(dú)立0 元素的行（列）開(kāi)始，獨(dú)立0 元素處畫(huà) （ ） 標(biāo)記 ，在有 （ ） 的行列中劃去 （也可打 *） 其它 0元素； 再在剩余的 0 元素中重復(fù)此做法， 直至不能標(biāo)記（ ） 為止。3、作能覆蓋所有0 元素的最少數(shù)直線集合。作法：對(duì)沒(méi)有（）的行打，號(hào)；對(duì)已打，號(hào)的行中所有0元素的所在列打，號(hào)；再對(duì)打有，號(hào)的列中0元素的所在行打，號(hào)；重復(fù)、直到得不出新的打，號(hào)的行（列） 為止；對(duì)沒(méi)有打，號(hào)的行畫(huà)一橫線，對(duì)打，號(hào)的列畫(huà)一縱線，這就得到覆蓋所有0元素的最少直線數(shù)。未被直線覆蓋的最小元素為Cij ,在未被直線覆蓋處減去Cij，在直線交叉處加上 Cij 。4、重復(fù)2、 3，直到求得最優(yōu)解。類(lèi)型一

26、:求極小值的匈牙利法：（重點(diǎn)掌握這種基本問(wèn)題）例1:有甲、乙、丙、丁四個(gè)人，要派去完成 A B C D四項(xiàng)工作，他們解：用“匈牙利法”求解已知條件可用系數(shù)矩陣（效率矩陣）表不為:(cij61078123148131213124141610行約簡(jiǎn)27008070996401192列約簡(jiǎn)27008070552001192標(biāo)號(hào)27(0)*08(0)7*0(0)119(0)使總工時(shí)為最少的分配任務(wù)方案為:甲fD,乙-B,丙A, 丁 C此時(shí)總工時(shí)數(shù)W=4+3+7+12=26 例2:求效率矩陣109758754623487的最優(yōu)解。551097解：587546234875530102 03 202121列

27、約簡(jiǎn)20330102 03 202120102標(biāo)號(hào)*32(0)0(0)321_1(0)20*所畫(huà)()0元素少于n,未*0122得到最優(yōu)解，需要繼續(xù)變換矩陣(求能覆蓋所有0元素的最少數(shù)直線集合)32(0)31(0)*01*(0)021V*20未被直線覆蓋的最小元素為Cj=1 ,在未被直線覆蓋處減去1,在直線交叉處加上標(biāo)號(hào)*、42(0)042000210202000111。0010100000010100類(lèi)型二:求極大值的匈牙利法:min z= max ( z)*(0)210*，、202(0)* , 、0(0)11(Cj ) 一 (W Cj ) = (bj ), (Gj )中最大的元素為max z

28、=cijxij =(Mcj)xji ji j(M Cij )xij -Cij xiji ji j第一部分到此結(jié)束第二部分動(dòng)態(tài)規(guī)劃只要求掌握動(dòng)態(tài)規(guī)劃的最短路問(wèn)題一一用“圖上標(biāo)號(hào)法”解決：具體解題步 驟請(qǐng)參看教材P103 （這是本套資料少見(jiàn)的與教材完全相同的算法類(lèi)型之一，務(wù) 必看書(shū)掌握）學(xué)員們只有完全理解了這種作法（思路： 逆向追蹤）才有可能做題，考試時(shí)數(shù)字無(wú)論如 何變化都能作出正確求解！第二部分到此結(jié)束第三部分網(wǎng)絡(luò)分析一、求最小生成樹(shù)（最小支撐樹(shù)、最小樹(shù)）問(wèn)題：破圈法一一任取一個(gè)圈，從圈中去掉一條權(quán)最大的邊（如果有兩條或兩條以上的邊都是權(quán)最大的邊，則任意去掉其中一條）。在余下的圖中，重復(fù)這個(gè)步 驟，直到得到一個(gè)不含圈的圖為止，這時(shí)的圖便是最小樹(shù)。參考例題：例：求下圖的最小生成樹(shù)：解：用“破圈法”求得最小生成樹(shù)為:V3V5已得最小樹(shù)，此時(shí)權(quán) w=1+2+4