管理運籌學(xué)復(fù)習(xí)(編輯修改稿)
2025-05-14 08:21 本頁面
【文章內(nèi)容簡介】 ]，[V1，V3]}，并有S12=L1+C12=0+4=4 ； S13=L1+C13=0+18=18min(S12,S13)=S12=4給邊[V1，V2]中的未標號的點V2標以（4，1），表示從V1到V2的距離為4，并且在V1到V2的最短路徑上V2的前面的點為V1.③這時I={V1，V2},J={V3，V4，V5，V6,V7}，邊的集合{[Vi，Vj]︳Vi，Vj兩點中一點屬于I,而另一點屬于J}={[V1，V3]，[V2，V3]，[V2，V4]}，并有S23=L2+C23=4+12=16；S24=L2+C24=4+16=20；min(S23,S24,S13)=S23=16給邊[V2，V3]中的未標號的點V3標以（16，2）④這時I={V1，V2，V3},J={V4，V5，V6,V7}，邊的集合{[Vi，Vj]︳Vi，Vj兩點中一點屬于I,而另一點屬于J}={[V2，V4]，[V3，V4]，[V3，V5]}，并有S34=L3+C34=16+2=18；S35=L3+C35=16+6=22；S24=L2+C24=4+16=20min(S34,S35,S24)=S34=18給邊[V3，V4]中的未標號的點V4標以（18，3）⑤這時I={V1，V2，V3，V4},J={V5，V6,V7}，邊的集合{[Vi，Vj]︳Vi，Vj兩點中一點屬于I,而另一點屬于J}={[V4，V6]，[V4，V5]，[V3，V5]}，并有S46=L4+C46=18+7=25；S45=L4+C45=18+8=26；min(S46,S45,S35)=S35=24給邊[V3，V5]中的未標號的點V5標以（24，3）⑥這時I={V1，V2，V3，V4，V5},J={V6 ，V7}，邊的集合{[Vi，Vj]︳Vi，Vj兩點中一點屬于I,而另一點屬于J}={[V5，V7]，[V4，V6]}，并有S57=L5+C57=22+5=27；min(S57,S46)=S46=25給邊[V4，V6]中的未標號的點V6標以（25，4）⑦這時I={V1，V2，V3，V4，V5，V6},J={V7}，邊的集合{[Vi，Vj]︳Vi，Vj兩點中一點屬于I,而另一點屬于J}={[V5，V7]，[V6，V7]}，并有S67=L6+C67=25+6=31 ；min(S57,S67)=S57=27給邊[V5，V7]中的未標號的點V7標以（27，5）⑧此時I={V1，V2，V3 ，V4 ，V5 ，V6，V7},J=空集，邊集合{[Vi，Vj]︳Vi，Vj兩點中一點屬于I,而另一點屬于J}=空集，計算結(jié)束。⑨得到最短路。從V7的標號可知從V1到V7的最短時間為27分鐘。即：配送路線為：V1→V2→V3→V5→V7（14）最小生成樹問題某電力公司要沿道路為8個居民點架設(shè)輸電網(wǎng)絡(luò)，連接8個居民點的道路圖如圖所示，其中V1，……，V8表示8個居民點，圖中的邊表示可架設(shè)輸電網(wǎng)絡(luò)的道路，邊上的賦權(quán)數(shù)為這條道路的長度，單位為公里，請設(shè)計一個輸電網(wǎng)絡(luò)，聯(lián)通這8個居民點，并使總的輸電線路長度為最短9V25V643V12V723V342G26V55V47V8①在圖中找到一個圈（V1，V2，V5，V3）,并知在此圈上邊[V1，V2]和[V3，V5]的權(quán)數(shù)4為最大，在圖中去掉邊[V1，V2]；②在圖中找到一個圈（V3，V4，V8，V5，V3,V1），去掉其中權(quán)數(shù)最大的邊[V4，V8]；③在圖中找到一個圈（V3，V4，V5，V3），去掉其中權(quán)數(shù)最大的邊[V4，V5]；④在圖中找到一個圈（V5，V2，V6，V7，V5），去掉其中權(quán)數(shù)最大的邊[V2，V6]；⑤在圖中找到一個圈（V5，V7，V8，V5），去掉其中權(quán)數(shù)最大的邊[V5，V8]。⑥在圖中已找不到任何一個圈了，可知此即為圖G的最小生成樹。這個最小生成樹的所有邊的總權(quán)數(shù)為2+2+4+2+3+3+2=18（15）最大流問題某地區(qū)的公路網(wǎng)如圖所示，圖中V1，……，V6為地點，邊為公路，邊上所賦的權(quán)數(shù)為該段公路的流量（單位為千輛/小時），請求出V1到V6的最大流量。V28V5412V166V456V61065V3解：第一次迭代：選擇路為V1→V3→V6?。╒3，V6）的順流流量為5，決定了pf=5，改進的10網(wǎng)絡(luò)流量圖如圖所示：V280V504012V4V1V6105 00 56 06 0 6 00 55→ →5第一次迭代50650后的總流量V3第二次迭代：選擇路為V1→V2→V5→V6?。╒1，V2）的順流流量為6，決定了pf=6，改進的網(wǎng)絡(luò)流量圖如圖所示：V22806V5604012611→0V166000V4565006V6→115560第二次迭代后的總流量V3第三次迭代：選擇路為V1→V4→V6弧（V1，V4）的順流流量為6，決定了pf=6，改進的網(wǎng)絡(luò)流量圖如圖所示：V226V56406V417→V1065060506005066V617→第三次迭代560后的總流量V3第四次迭代：選擇路為V1→V3→V4→V2→V5→V6?。╒2，V5）的順流流量11為2，決定了pf=2，改進的網(wǎng)絡(luò)流量圖如圖所示：V20268V5602064V4V1V619→ 19→24 5 6800 6 0 62 05 53 45760第四次迭代后的總流量V3第五次迭代：選擇路為V1→V3→V4→V5→V6弧（V1，V3）的順流流量為3，決定了pf=3，改進的網(wǎng)絡(luò)流量圖如圖所示：V208V5V4V1V622→160
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1