物流運(yùn)籌學(xué) 習(xí)題 8題目-網(wǎng)絡(luò)分析

習(xí)題八8.1設(shè)有四個無向圖：G1={V1,E1},G2={V2,E2},G3={V3,E3},G4={V4,E4},其中：V1={v1,v2,v3,v4,v5,v6}E1={(v1,v2)(v1,v3)(v2,v3)(v2,v4)(v2,v5)(v3,v4)(v3,v5)(v4,v5)(v4,v6)(v5,v6)};V2={v1,v2,v3,v4,v5,v6}E2={(v1,v2)(v1,v3)(v2,v4)(v2,v5)(v3,v4)(v3,v5)(v4,v6)(v5,v6)};V3={v2,v4,v5,v6}E3={(v2,v4)(v2,v5)(v4,v5)(v4,v6)(v5,v6)};

V4={v1,v2,v3,v4,v5,v6}E4={(v1,v2)(v2,v5)(v3,v4)(v4,v6)};（1）試求這四個圖的圖解，判斷其是否連通。（2）試問G2,G3,G4是否為G1的真子圖和支撐子圖。（3）試問：在G1中，μ1=v1v2v3v4v5v6，μ2=v1v3v2v5v4v6，μ3=v3v4v6v5v2，μ4=v2v5v6v4v2，μ5=v2v3v1v2v5v4v2，μ6=v1v2v5v4v2v5v6，是否為開鏈，閉鏈，簡單鏈，初等鏈，圈，路，回路。8.2已知有向圖D=(V,A)，其中V={v1,v2,v3,v4,v5,},A={(v1,v2)(v1,v3)(v2,v4)(v2,v5)(v3,v2)(v4,v3)(v4,v5)}。(1)試求D與G(D)的圖解。(2)試問：μ1=v1v3v4v2v5，μ2=v2v5v4v3v2，μ3=v1v3v2v4v3v2v5，μ4=v3v2v4v3，μ5=v1v3v2v4v3，μ6=v1v3v2v4v5，是否為開鏈，閉鏈，簡單鏈，初等鏈，圈，路，回路。8.3試問：從8.1題的圖G1，G2的任一點(diǎn)出發(fā)，能否走遍該圖的各邊且僅過每邊一次而回到出發(fā)點(diǎn)，若能則找出這樣的路。8.4某工廠辦公室擬在三天內(nèi)舉行六項(xiàng)活動，每項(xiàng)活動各需半天時間。廠辦擬請十名廠級干部參加這些活動，如下表中√號所示。已知活動A須安排在第一天上午，活動F須安排在第三天下午，活動B只能安排在下午，而每名廠級干部都希望每天最多參加一項(xiàng)活動。廠辦應(yīng)如何安排這六項(xiàng)活動的日程。干部活動22345678910A√√√√√√B√√√√C√√√√√D√√√E√√√F√√√√√8.5分別用避圈法和破圈法求下列網(wǎng)絡(luò)的最小樹。55232223321423332786425191057143412752424（a）134655232223321423332786425191057143412752424（a）134675253783222746461314(b)123456788.6某市六個新建單位之間的交通線路的長度（公里）如下表所示。其中單位A距市煤氣供應(yīng)網(wǎng)最近，為1.5公里。ABCDEFA01.33.24.33.83.7B1.303.54.03.13.9C3.23.502.82.61.0D4.34.02.802.12.7E3.83.12.62.102.4F3.73.91.02.72.40為使這六個單位都能使用煤氣，現(xiàn)擬沿交通線鋪設(shè)地下管道，并且經(jīng)A與煤氣供應(yīng)網(wǎng)連通。應(yīng)如何鋪設(shè)煤氣管道使其總長最短。8.7在下列網(wǎng)絡(luò)中，求點(diǎn)s到各點(diǎn)的最短路。247t61S332247t61S332563447122437S123456t861(a)943182811675129163411427(b)25897178.8在下列網(wǎng)絡(luò)中，求各點(diǎn)間的最短路。710710218469296121235646(a)327322112356436(b)8.9在下面的網(wǎng)絡(luò)中，試求：①各點(diǎn)到點(diǎn)t的最短路;②點(diǎn)s到各點(diǎn)的最短路。-2-2215253s1234-24-3t448.10某公司正在研制一種有極好銷售潛力的新產(chǎn)品。當(dāng)研究工作接近完成時，公司獲悉一家競爭者正計(jì)劃生產(chǎn)這種產(chǎn)品。要突擊趕制出這種產(chǎn)品以參與競爭，還有四個互不重疊的階段。為了加快進(jìn)度，每個階段都可采取“優(yōu)先”或“應(yīng)急”的措施。不同的措施下每段工作所需要的時間（月）和費(fèi)用（百萬元）如小下表示?，F(xiàn)有一千萬元資金供這四個階段使用，則每段應(yīng)采取什么措施能使這種產(chǎn)品盡早上市。試將此問題化成最短路問題并求解。階段措施剩余研究試制工藝設(shè)計(jì)生產(chǎn)與調(diào)撥時間費(fèi)用時間費(fèi)用時間費(fèi)用時間費(fèi)用正常51優(yōu)先42325321應(yīng)急232334128.11已知七個村鎮(zhèn)之間的交通線路如下圖所示，點(diǎn)旁的數(shù)字為每個村的糧食產(chǎn)量，邊旁的數(shù)字為兩村間的路長。現(xiàn)要為這七個村建一個文化館和一個糧庫，試問：（1）文化館應(yīng)建在何村，使各村距其都較近。（2）糧庫應(yīng)建在何村，使總運(yùn)輸量為最小。2.52.532000810001.51.544323157462700003000100050004000621.88.12在右面的網(wǎng)絡(luò)中，弧旁的數(shù)字為其容量。試求：（1）所有截集及其截量；（2）最大流；（3）最小截集。1132425s12t338.13求下列網(wǎng)絡(luò)的最大流與最小截集?；∨缘臄?shù)字為其容量。6464157433332613s1234t(a)109554495613s12345t45(b)8.14有四根同一規(guī)格的軸A,B,C,D四個同一規(guī)格的齒輪Ⅰ，Ⅱ，Ⅲ，Ⅳ，現(xiàn)要將軸與齒輪配對使用。由于精度不高，不能任意匹配。已知A只能與Ⅱ配合，B能與Ⅰ，Ⅱ配合，C能與Ⅲ，Ⅳ配合，D能與Ⅱ，Ⅲ配合.應(yīng)如何匹配才能充分利用這些零件。試用網(wǎng)絡(luò)分析的方法求解。8.15某河流中有幾個島嶼，兩岸與各島以及各島之間的橋梁如下圖所示。在一次敵對的軍事行動中，至少應(yīng)炸斷幾座橋梁，才能完全切斷兩岸的交通。試用網(wǎng)絡(luò)分析的方法求解。112563489107111213AFBCDE8.16試建立下列問題的線性規(guī)劃模型：①例12；②例6。8.17求下列網(wǎng)絡(luò)的最小費(fèi)用最大流?；∨詳?shù)字為（）。(6,2)(3,10)(6,2)(3,10)(1,8)(2,5