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

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