第6章 網(wǎng)絡(luò)模型【教學(xué)試題】

《第6章 網(wǎng)絡(luò)模型【教學(xué)試題】》由會(huì)員分享，可在線閱讀，更多相關(guān)《第6章 網(wǎng)絡(luò)模型【教學(xué)試題】（12頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 第6章 網(wǎng)絡(luò)模型 圖6－42 6.1如圖6－42所示，建立求最小部分樹的0－1整數(shù)規(guī)劃數(shù)學(xué)模型。 【解】邊[i，j]的長(zhǎng)度記為cij，設(shè) 數(shù)學(xué)模型為： 圖6－43 6.2如圖6－43所示，建立求v1到v6的最短路問題的0－1整數(shù)規(guī)劃數(shù)學(xué)模型。 【解】弧(i，j)的長(zhǎng)度記為cij，設(shè) 數(shù)學(xué)模型為： 6.3如圖6－43所示，建立求v1到v6的最大流問題的線性規(guī)劃數(shù)學(xué)模型。 【解】 設(shè)xij為?。╥,j）的流量，數(shù)學(xué)模型為 6.4求圖6－41的最小部分樹。圖6-41（a）用破圈法,圖6-41（b）用加邊法。 圖6－44 【解】

2、圖6-44（a），該題有4個(gè)解，最小樹長(zhǎng)為22，其中一個(gè)解如下圖所示。 圖6-44（b），最小樹長(zhǎng)為20。最小樹如下圖所示。 6.5 某鄉(xiāng)政府計(jì)劃未來3年內(nèi)，對(duì)所管轄的10個(gè)村要達(dá)到村與村之間都有水泥公路相通的目標(biāo)。根據(jù)勘測(cè)，10個(gè)村之間修建公路的費(fèi)用如表6-20所示。鄉(xiāng)鎮(zhèn)府如何選擇修建公路的路線使總成本最低。 表6-20 兩村莊之間修建公路的費(fèi)用(萬元) 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 12.8 10.5 9.6 8.5 7.7 13.8 12.7

3、 13.1 12.6 11.4 13.9 11.2 8.6 7.5 8.3 14.8 15.7 8.5 9.6 8.9 8.0 13.2 12.4 10.5 9.3 8.8 12.7 14.8 12.7 13.6 15.8 9.8 8.2 11.7 13.6 9.7 8.9 10.5 13.4 14.6 9.1 10.5 12.6 8.9 8.8 【解】屬于最小樹問題。用加邊法，得到下圖所示的方案。 最低總成本74.3萬元。 6.6在圖6－45中，求A到H、I的最短路及最短路長(zhǎng)，并

4、對(duì)圖(a)和(b)的結(jié)果進(jìn)行比較。 圖6－45 【解】圖6－45(a): A到H的最短路PAH={A,B,F,H},{A,C,F,H}最短路長(zhǎng)22；A到I的最短路PAI={A,B,F,I},{A,C,F,I}最短路長(zhǎng)21。 對(duì)于圖6－45(b)： A到H的最短路PAH={A,C,G,F,H},最短路長(zhǎng)21；A到I的最短路PAI={A,C,G,F,I},最短路長(zhǎng)20； 結(jié)果顯示有向圖與無向圖的結(jié)果可能不一樣。 6.7已知某設(shè)備可繼續(xù)使用5年，也可以在每年年末賣掉重新購置新設(shè)備。已知5年年初購置新設(shè)備的價(jià)格分別為3.5、3.8、4.0、4.2和4.5萬元。使用時(shí)間

5、在1～5年內(nèi)的維護(hù)費(fèi)用分別為0.4、0.9、1.4、2.3和3萬元。試確定一個(gè)設(shè)備更新策略，使5年的設(shè)備購置和維護(hù)總費(fèi)用最小。 【解】設(shè)點(diǎn)vj為第j年年初購置新設(shè)備的狀態(tài)，（i，j）為第i年年初購置新設(shè)備使用到第j年年初，弧的權(quán)為對(duì)應(yīng)的費(fèi)用（購置費(fèi)＋維護(hù)費(fèi)），繪制網(wǎng)絡(luò)圖并計(jì)算，結(jié)果見下圖所示。 總費(fèi)用最小的設(shè)備更新方案為：第一種方案，第1年購置一臺(tái)設(shè)備使用到第5年年末；第二種方案，第1年購置一臺(tái)設(shè)備使用到第2年年末，第3年年初更新后使用到第5年年末?？傎M(fèi)用為11.5萬元。 圖6－46 6.8圖6－46是世界某6大城市之間的航線，邊上的數(shù)字為票價(jià)（百美元），用Floyd算法設(shè)計(jì)任

6、意兩城市之間票價(jià)最便宜的路線表。 【解】教師可利用模板求解：data\chpt6\ch6.xls L1 　 v1 v2 v3 v4 v5 v6 v1 0 8.8 9 5.6 8 6 v2 8.8 0 10 5 100 4 v3 9 10 0 3 4.8 14 v4 5.6 5 3 0 12 100 v5 8 100 4.8 12 0 9 v6 6 4 14 100 9 0 L2 　 v1 v2 v3 v4 v5 v6 v1 0 8.8 8.6 5.6 8 6 v

7、2 8.8 0 8 5 13 4 v3 8.6 8 0 3 4.8 14 v4 5.6 5 3 0 7.8 9 v5 8 13 4.8 7.8 0 9 v6 6 4 14 9 9 0 L3 　 v1 v2 v3 v4 v5 v6 v1 0 8.8 8.6 5.6 8 6 v2 8.8 0 8 5 13 4 v3 8.6 8 0 3 4.8 12 v4 5.6 5 3 0 7.8 9 v5 8 13 4.8 7.8 0 9 v6 6 4

8、 12 9 9 0 最優(yōu)票價(jià)表： 　 v1 v2 v3 v4 v5 v6 v1 0 8.8 8.6 5.6 8 6 v2 0 8 5 13 4 v3 0 3 4.8 12 v4 0 7.8 9 v5 0 9 v6 0 v1、v2、…、v6到各點(diǎn)的最優(yōu)路線圖分別為： 6.9 設(shè)圖6－46是某汽車公司的6個(gè)零配件加工廠，邊上的數(shù)字為兩點(diǎn)間的距離(km)?，F(xiàn)要在6個(gè)工廠中選一個(gè)建裝配車間。

9、 （1）應(yīng)選那個(gè)工廠使零配件的運(yùn)輸最方便。 （2）裝配一輛汽車6個(gè)零配件加工廠所提供零件重量分別是0.5、0.6、0.8、1.3、1.6和1.7噸，運(yùn)價(jià)為2元/噸公里。應(yīng)選那個(gè)工廠使總運(yùn)費(fèi)最小。 【解】(1)利用習(xí)題6.8表L3的結(jié)果 　 v1 v2 v3 v4 v5 v6 Max v1 0 8.8 8.6 5.6 8 6 8.8 v2 8.8 0 8 5 13 4 12.8 v3 8.6 8 0 3 4.8 12 12 v4 5.6 5 3 0 7.8 9 9 v5 8 13

10、4.8 7.8 0 9 12.8 v6 6 4 12 9 9 0 12 選第1個(gè)工廠最好。 (2)計(jì)算單件產(chǎn)品的運(yùn)價(jià)，見下表最后一行。計(jì)算單件產(chǎn)品的運(yùn)費(fèi)，見下表最后一列。 　 v1 v2 v3 v4 v5 v6 單件產(chǎn)品運(yùn)費(fèi) v1 0 8.8 8.6 5.6 8 6 84.88 v2 8.8 0 8 5 13 4 89.16 v3 8.6 8 0 3 4.8 12 82.16 v4 5.6 5 3 0 7.8 9 71.96 v5 8 13 4.8 7.8 0 9

11、 81.92 v6 6 4 12 9 9 0 82.2 運(yùn)價(jià) 1 1.2 1.6 2.6 3.2 3.4 選第4個(gè)工廠最好。 圖6－47 6.10 如圖6－47，（1）求v1到v10的最大流及最大流量；（2）求最小割集和最小割量。 【解】給出初始流如下 第一輪標(biāo)號(hào)：得到一條增廣鏈，調(diào)整量等于5，如下圖所示 調(diào)整流量。 第二輪標(biāo)號(hào)：得到一條增廣鏈，調(diào)整量等于2，如下圖所示 調(diào)整流量。 第三輪標(biāo)號(hào)：得到一條增廣鏈，調(diào)整量等于3，如下圖所示 調(diào)整流量。 第四輪標(biāo)號(hào)：不存在增廣鏈，最大流量等于45，如下圖所示

12、 取 ，最小截集{(3,7),(4,7),(6,9),(8,10)，最小截量等于45。 6.11 將3個(gè)天然氣田A1、A2、A3的天然氣輸送到2個(gè)地區(qū)C1、C2，中途有2個(gè)加壓站B1、B2，天然氣管線如圖6－48所示。輸氣管道單位時(shí)間的最大通過量cij及單位流量的費(fèi)用dij標(biāo)在弧上(cij, dij)。求(1)流量為22的最小費(fèi)用流；（2）最小費(fèi)用最大流。 圖6－48 【解】虛擬一個(gè)發(fā)點(diǎn)和一個(gè)收點(diǎn) T6.11－1 得到流量v＝22的最小費(fèi)用流，最小費(fèi)用為271。求解過程參看習(xí)題部分答案PPT文檔。 T6.11－13 最小費(fèi)用最大流如下圖，最大流量等于2

13、7，總費(fèi)用等于351。 6.12如圖6－46所示，（1）求解旅行售貨員問題；（2）求解中國郵路問題。 圖6-46 【解】（1）旅行售貨員問題。 距離表C 　 1 2 3 4 5 6 1 ∞ 8.8 9 5.6 8 6 2 8.8 ∞ 10 5 ∞ 4 3 9 10 ∞ 3 4.8 14 4 5.6 5 3 ∞ 12 ∞ 5 8 ∞ 4.8 12 ∞ 9 6 6 4 14 ∞ 9 ∞ 在C中行列分別減除對(duì)應(yīng)行列中的最小數(shù)，得到距離表C1。 距離表C1 　 1 2

14、3 4 5 6 1 ∞ 3.2 3.4 0 0.6 0.4 2 2.8 ∞ 6 1 ∞ 0 3 4 7 ∞ 0 0 11 4 0.6 2 0 ∞ 7.2 ∞ 5 1.2 ∞ 0 7.2 ∞ 9 6 0 0 10 ∞ 3.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。 得到距離表C2 　 1 2 3 5 6 2 2.8 ∞

15、 6 ∞ 0 3 4 7 ∞ 0 11 4 ∞ 2 0 7.2 ∞ 5 1.2 ∞ 0 ∞ 9 6 0 0 10 3.2 ∞ 距離表C2的每行每列都有零，H2= H1={ v1, v4 ,v3 ,v5 ,v6 ,v2 ,v1}就是總距離最小的Hamilton回路，C(H1) =35.2。 (2)中國郵路問題。虛擬一條邊 取回路H1＝{v1，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 思考與簡(jiǎn)答題 （1）運(yùn)籌學(xué)研究的圖有哪些特征。 （2）什么是樹形圖。 （3）簡(jiǎn)述求有向圖最短路的Dijkstra算法的基本步驟。 （4）Dijkstra算法在求有向圖與無向圖最短路時(shí)有什么不同。 （5）什么是網(wǎng)絡(luò)最大流問題？最大流與最大流量有何區(qū)別。 （6）簡(jiǎn)述最大流問題Ford-Fulkerson標(biāo)號(hào)算法的基本思路。 （7）求最小樹有哪幾種方法，分別簡(jiǎn)述各種方法的求解思路。 （8）簡(jiǎn)述增廣鏈的含義。 （9）什么是最小割集，最小割集的經(jīng)濟(jì)含義是什么。 返回頂部 教學(xué)#類別