第6章網(wǎng)絡(luò)模型

1、.第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。最小樹如下

2、圖所示。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.

3、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年年初購置新

4、設(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é)果見下圖所示。精品.總費(fèi)用最小的設(shè)備更新方案為：第一種方案，第1年購置一臺設(shè)備使用到第5年年末；第二種方案，第1年購置一臺設(shè)備使用到第2年年末，第3年年初更新后使用到第5年年末?？傎M(fèi)用為11.5萬元。圖6466.8圖646是世界某6大城市之間的航線，邊上的數(shù)

5、字為票價（百美元），用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.6530

6、7.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é)果v1v2v3v4v5v6m

7、axv108.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 如圖64

8、7，（1）求v1到v10的最大流及最大流量；（2）求最小割集和最小割量?！窘狻拷o出初始流如下第一輪標(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)用d

9、ij標(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。距離表c11

10、2345613.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算法在求有向圖與