第6章 網(wǎng)絡(luò)模型圖6426.1如圖642所示，建立求最小部分樹的01整數(shù)規(guī)劃數(shù)學(xué)模型?！窘狻窟卛，j的長度記為cij，設(shè)數(shù)學(xué)模型為：圖6436.2如圖643所示，建立求v1到v6的最短路問題的01整數(shù)規(guī)劃數(shù)學(xué)模型?！窘狻炕?i，j)的長度記為cij，設(shè)數(shù)學(xué)模型為：6.3如圖643所示，建立求v1到v6的最大流問題的線性規(guī)劃數(shù)學(xué)模型?！窘狻?設(shè)xij為?。╥,j）的流量，數(shù)學(xué)模型為6.4求圖641的最小部分樹。圖6-41（a）用破圈法,圖6-41（b）用加邊法。圖644【解】圖6-44（a），該題有4個解，最小樹長為22，其中一個解如下圖所示。圖6-44（b），最小樹長為20。最小樹如下圖所示。6.5 某鄉(xiāng)政府計劃未來3年內(nèi)，對所管轄的10個村要達(dá)到村與村之間都有水泥公路相通的目標(biāo)。根據(jù)勘測，10個村之間修建公路的費(fèi)用如表6-20所示。鄉(xiāng)鎮(zhèn)府如何選擇修建公路的路線使總成本最低。表6-20兩村莊之間修建公路的費(fèi)用(萬元)123456789101234567891012.810.59.68.57.713.812.713.112.611.413.911.28.67.58.314.815.78.59.68.98.013.212.410.59.38.812.714.812.713.615.89.88.211.713.69.78.910.513.414.69.110.512.68.98.8【解】屬于最小樹問題。用加邊法，得到下圖所示的方案。最低總成本74.3萬元。6.6在圖645中，求A到H、I的最短路及最短路長，并對圖(a)和(b)的結(jié)果進(jìn)行比較。 圖645【解】圖645(a):A到H的最短路PAH=A,B,F,H,A,C,F,H最短路長22；A到I的最短路PAI=A,B,F,I,A,C,F,I最短路長21。對于圖645(b)：A到H的最短路PAH=A,C,G,F,H,最短路長21；A到I的最短路PAI=A,C,G,F,I,最短路長20；結(jié)果顯示有向圖與無向圖的結(jié)果可能不一樣。6.7已知某設(shè)備可繼續(xù)使用5年，也可以在每年年末賣掉重新購置新設(shè)備。已知5年年初購置新設(shè)備的價格分別為3.5、3.8、4.0、4.2和4.5萬元。使用時間在15年內(nèi)的維護(hù)費(fèi)用分別為0.4、0.9、1.4、2.3和3萬元。試確定一個設(shè)備更新策略，使5年的設(shè)備購置和維護(hù)總費(fèi)用最小?！窘狻吭O(shè)點(diǎn)vj為第j年年初購置新設(shè)備的狀態(tài)，（i，j）為第i年年初購置新設(shè)備使用到第j年年初，弧的權(quán)為對應(yīng)的費(fèi)用（購置費(fèi)維護(hù)費(fèi)），繪制網(wǎng)絡(luò)圖并計算，結(jié)果見下圖所示?？傎M(fèi)用最小的設(shè)備更新方案為：第一種方案，第1年購置一臺設(shè)備使用到第5年年末；第二種方案，第1年購置一臺設(shè)備使用到第2年年末，第3年年初更新后使用到第5年年末?？傎M(fèi)用為11.5萬元。圖6466.8圖646是世界某6大城市之間的航線，邊上的數(shù)字為票價（百美元），用Floyd算法設(shè)計任意兩城市之間票價最便宜的路線表?！窘狻拷處熆衫媚０迩蠼猓篸atachpt6ch6.xlsL1v1v2v3v4v5v6v108.895.686v28.801051004v3910034.814v45.653012100v581004.81209v6641410090L2v1v2v3v4v5v6v108.88.65.686v28.8085134v38.68034.814v45.65307.89v58134.87.809v66414990L3v1v2v3v4v5v6v108.88.65.686v28.8085134v38.68034.812v45.65307.89v58134.87.809v66412990最優(yōu)票價表：v1v2v3v4v5v6v108.88.65.686v2085134v3034.812v407.89v509v60v1、v2、v6到各點(diǎn)的最優(yōu)路線圖分別為： 6.9 設(shè)圖646是某汽車公司的6個零配件加工廠，邊上的數(shù)字為兩點(diǎn)間的距離(km)?，F(xiàn)要在6個工廠中選一個建裝配車間。（1）應(yīng)選那個工廠使零配件的運(yùn)輸最方便。（2）裝配一輛汽車6個零配件加工廠所提供零件重量分別是0.5、0.6、0.8、1.3、1.6和1.7噸，運(yùn)價為2元/噸公里。應(yīng)選那個工廠使總運(yùn)費(fèi)最小?！窘狻?1)利用習(xí)題6.8表L3的結(jié)果v1v2v3v4v5v6Maxv108.88.65.6868.8v28.808513412.8v38.68034.81212v45.65307.899v58134.87.80912.8v6641299012選第1個工廠最好。(2)計算單件產(chǎn)品的運(yùn)價，見下表最后一行。計算單件產(chǎn)品的運(yùn)費(fèi)，見下表最后一列。v1v2v3v4v5v6單件產(chǎn)品運(yùn)費(fèi)v108.88.65.68684.88v28.808513489.16v38.68034.81282.16v45.65307.8971.96v58134.87.80981.92v6641299082.2運(yùn)價11.21.62.63.23.4選第4個工廠最好。圖6476.10 如圖647，（1）求v1到v10的最大流及最大流量；（2）求最小割集和最小割量。【解】給出初始流如下第一輪標(biāo)號：得到一條增廣鏈，調(diào)整量等于5，如下圖所示調(diào)整流量。第二輪標(biāo)號：得到一條增廣鏈，調(diào)整量等于2，如下圖所示調(diào)整流量。第三輪標(biāo)號：得到一條增廣鏈，調(diào)整量等于3，如下圖所示調(diào)整流量。第四輪標(biāo)號：不存在增廣鏈，最大流量等于45，如下圖所示取 ，最小截集(3,7),(4,7),(6,9),(8,10)，最小截量等于45。6.11 將3個天然氣田A1、A2、A3的天然氣輸送到2個地區(qū)C1、C2，中途有2個加壓站B1、B2，天然氣管線如圖648所示。輸氣管道單位時間的最大通過量cij及單位流量的費(fèi)用dij標(biāo)在弧上(cij, dij)。求(1)流量為22的最小費(fèi)用流；（2）最小費(fèi)用最大流。圖648【解】虛擬一個發(fā)點(diǎn)和一個收點(diǎn)T6.111得到流量v22的最小費(fèi)用流，最小費(fèi)用為271。求解過程參看習(xí)題部分答案PPT文檔。T6.1113最小費(fèi)用最大流如下圖，最大流量等于27，總費(fèi)用等于351。6.12如圖646所示，（1）求解旅行售貨員問題；（2）求解中國郵路問題。圖6-46【解】（1）旅行售貨員問題。距離表C12345618.895.68628.81054391034.81445.65312584.8129664149在C中行列分別減除對應(yīng)行列中的最小數(shù)，得到距離表C1。距離表C112345613.23.400.60.422.8610347001140.6207.251.207.29600103.2由距離表C1，v1到v4， H1= v1, v4 ,v3 ,v5 ,v6 ,v2 ,v1, C(H1)=5.6+3+4.8+9+4+8.8=35.2去掉第1行第四列，d41=，得到距離表C2。得到距離表C21235622.8603470114207.251.209600103.2距離表C2的每行每列都有零，H2= H1= v1, v4 ,v3 ,v5 ,v6 ,v2 ,v1就是總距離最小的Hamilton回路，C(H1) =35.2。(2)中國郵路問題。虛擬一條邊取回路H1v1，v3，v4，C(H1)=9+5+3=17,C(v1，v3)=9> C(H1)/2，調(diào)整回路。所有回路滿足最短回路的準(zhǔn)則，上圖是最短的歐拉回路，其中邊(v1, v4)和(v4, v3)各重復(fù)一次。6.13 思考與簡答題（1）運(yùn)籌學(xué)研究的圖有哪些特征。（2）什么是樹形圖。（3）簡述求有向圖最短路的Dijkstra算法的基本步驟。（4）Dijkstra算法在求有向圖與無向圖最短路時有什么不同。（5）什么是網(wǎng)絡(luò)最大流問題？最大流與最大流量有何區(qū)別。（6）簡述最大流問題Ford-Fulkerson標(biāo)號算法的基本思路。（7）求最小樹有哪幾種方法，分別簡述各種方法的求解思路。（8）簡述增廣鏈的含義。（9）什么是最小割集，最小割集的經(jīng)濟(jì)含義是什么。返回頂部教學(xué)#類別