《系統(tǒng)工程與運籌學(xué)》習(xí)題及答案 第3-11章

第三章

1.試用ISM技術(shù)研究本專業(yè)各門主要課程之間的關(guān)系（假定二元關(guān)系為“支

持”關(guān)系），建立你認(rèn)為比較合理的課程體系結(jié)構(gòu)。

2.某部門對其員工進(jìn)行年終考核，選用銷售目標(biāo)達(dá)成率、客戶檔案完整率、

新客戶開發(fā)數(shù)量、顧客滿意度等指標(biāo)。資料如下表，請幫助對各個員工進(jìn)行評價，

各指標(biāo)的權(quán)重采用AHP方法確定。

客戶檔案

銷售目標(biāo)達(dá)成新客戶開發(fā)數(shù)顧客滿意

員工完整率％

率％量（個）度

A1209015較好

B115859很好

C10510010較好

D1029811非常好

2.你的朋友想購買一輛新能源汽車，計劃支已不超過20萬元，現(xiàn)準(zhǔn)備在三

種品牌中選擇，三種車型數(shù)據(jù)如下，請用綜合評價法和AHP法幫助你的朋友選

購一輛理想的汽車，并比較兩種方法選擇的結(jié)果是否相同，如果不同請找出原因。

電池能量

充電時間樣式評

品牌價格（萬元）密度續(xù)航里程

（小時）分

（kW/kg）

A19.581604(M)85

/p>

C15.8714038080

3.如果你的朋友分別征求了10個同事的意見，10個同事對各車型的評價意

見見下表，請用模糊綜合評價法幫助你的朋友選擇一輛理想的轎車。

對A品牌評價的人數(shù)

電池能量

充電時間

評價價格（萬元）密度續(xù)航里程樣式評分

（小時）

（kW/kg）

好35416

中51243

差24451

對B品牌學(xué)價的人數(shù)

|評價價格（萬元）充電時間電池能量續(xù)航里程樣式評分

1

(小時)密度

(kW/kg)

好73285

中25424

基.I2401

對C品牌評價的人數(shù)

電池能量

充電時間

評價價格(萬元)密度續(xù)航里程樣式評分

(小時)

(kW/kg

好64545

中45454

差01111

答案：價格、充電時間、電池能量密度、續(xù)航里程、樣式等指標(biāo)權(quán)重由層次分析

法確定，權(quán)重確定過程略。

假定最終確定的價格、充電時間、電池能量密度、續(xù)航里程、樣式等指標(biāo)權(quán)

重為W=(0.3,0.1,().1,0.20.3)。

則A品牌綜合評價結(jié)果為

-().30.50.2

0.50.10.4

=WxR]=(0.30.10.10.20.3)0.40.20.4

0.10.40.5

0.60.30.1

=(0.380.350.27)

同理可得B品牌綜合評價結(jié)果B2=(0.570.310.12)

C品牌的綜合評價結(jié)果B3=(0.50.420.08)

設(shè)給評語集V二(好，中，差)依次賦予分值六(100,75,50),則

A綜合評價分值Ki=(0.380.350.27X1007550)=77.75(分)。

B綜合評價分值K]=(O570.310.12H1007550)=86.25(分)。

C綜合評價分值Ki=(0.50.420.08)*(1007550)=85.5(分)。

所以應(yīng)選擇品牌B.

4.某校舉行主持人大賽，分別從形象氣質(zhì)、臨場應(yīng)變、吐字清晰、親和力

等幾個方面進(jìn)行評價。有10位評委對4位參賽選手進(jìn)行了評價。10位評委對參

賽選手的評價意見見下表，請用模糊綜合評價法選出最佳主持人。

評價形象氣質(zhì)臨場應(yīng)變吐字清晰親和力現(xiàn)場效果

好64455

2

中45455

0

差0120

評委對參賽選手A的評價

評委對參賽選手B的評價

評價形象氣質(zhì)臨場應(yīng)變吐字清晰親和力現(xiàn)場效果

好810878

中20232

差00000

評委對參賽選手C的評價

評價形象氣質(zhì)臨場應(yīng)變吐字清晰親和力現(xiàn)場效果

L

好9878i

中1122

差0110

評委對?參賽選手D的評價

評價形象氣質(zhì)臨場應(yīng)變吐字清晰親和力現(xiàn)場效果

好97897

中12212

差()1()01

答案：形象氣質(zhì)、臨場應(yīng)變、吐字清晰、親和力等指標(biāo)權(quán)重由層次分析法確定,

權(quán)重確定過程略，假定最終確定的形象氣質(zhì)、臨場應(yīng)變、吐字清晰、親和力、現(xiàn)

場效果等指標(biāo)權(quán)重為W=(0.2,030.2,0).10.2)。

則參賽選手A的綜合評價結(jié)果為

-0.60.40

0.40.50.1

=WxR[=(0.20.30.20.10.2)0.40.40.2

().5().50

0.50.50

=(0.470.460.07)

參賽選手B的綜合評價結(jié)果為

3

'0600900、

表4：Z=955200X=,其中：銷地內(nèi)缺貨1500單位

、35005(X)0>

。50000、

3.Z=4950X=010(0400,其中：產(chǎn)地由存儲150單位，產(chǎn)地由存儲150單位

<0040050,

"050000、

4.Z=6bOUX=25560100，其中：銷地力胡貨2。單位

<0600070,

5.(1)唯一最優(yōu)解X*=⑵5),z*=19（2）無界解

(3)無窮多解X*=(15,7.5),Z*=1200(4)無可行解

6.

(I)X*=(2,5),Z*=19(2)無界解(3)X*=(15,7.5),Z*=1200

(4)X*=(4,2),Z*=14(5)X*=(200,600),Z*=2600

(6)X*=(3.6,0,16.8),Z*=-44.4

7.(I)X*=(3,4,0),Z*=26(2)X*=(0.8,1.8,0),Z*=7(3)無可行解

(4)無界解(5)無可行解(6)X*=(3,0,1),Z*=6

8.

MaxW=3y+21y2+2

MinW=4y+14y2-5y3f+2y2上力與3

2M+2為+0=2一2y一3)，2-)”2

一凹+3%_/<3<3x+5%+2為=-7

jpy2>0,y3<04力-6%一必=4

y\<0,y320，K無約束

McixW=10y+8J2+6y3MinW=25y}-60y2+30y3-5y4+10)1

K+2y223M+2y2+2%41

—3.+2%之T

(3)(4)

-3y,+2y2+y3<-4一2y-7%-4為=5

.Vi+2.v+.v.+y=-7

y.-y2+.%=i25

>,(20，必?zé)o約束%無約束,為、

9.

ABCDEFGH

-324-22310

IJKLMN0P

5-53/204515

5

10.

MinZ=3內(nèi)+2X2

McixW=20)[+6y2+6y3

%+2x1<20

力+2%+%6

(1)2X1-x>6

2-2^-^+^<2

%+x2>6

7i?。,、2，力20

%,x2>0

X*=(4,2)Z*=16

Y*=(0,1/3,7/3)W*=16

112

（3）最優(yōu)基4=02-1

0I1

-11/3-5/3-

最優(yōu)基的逆方|=01/31/3

0-1/32/3

11.

(1)X*=(2,24),Z*=1440(2)X*=(2,2,2),Z*=72

12.最優(yōu)解：X*=(0,100,200),Z*=1300(千元)

(1)X*=(100,175,0),Z*=1375(千元)；CK17/4千元時原最優(yōu)生產(chǎn)方案不變;

(2)X*=(0,0,300),Z*=1800；當(dāng)-15/4/C3W5時，原最優(yōu)生產(chǎn)方案不變；

(3)X*=(0,175,100),Z*=I275；設(shè)備B有效應(yīng)滿足10Gowb2W4000/3：

(4)X*=(50,100,200),Z*=1350；

(5)值得投產(chǎn)，X*=(0,0,280,40),Z*=132O;

(6)不能保持;X*=(0,220,40),Z*=1260o

13.(1)0,-0.4,-10；X*=(180,40),Z*=13000；

MinW=300y+400)、+120)、

X+2)”50

(2)Y*=(30,10,0)；

<3Y+%+)’32120

(3)值得，X*=(170,60),Z*=14500-50*25=13250；o

14.云騰公司擬在華東、華南、華北三個區(qū)域建立銷售中心，共有8個地點可供選擇,，見

表13,共有投資資金6380千元。要求：（1）華東區(qū)至多選2個；（2）華南區(qū)、華北區(qū)至少

選1個。問應(yīng)選擇哪幾個地點建立銷售中心才能使利潤最大？

表13投資與利潤表

區(qū)域地點預(yù)計利潤（千元）投資額（千元）

華東A116001050

6

A21400980

A31300970

華南A41250975

A51000890

A61250950

華北A71080850

A8990870

答案：選擇在A1A2A4A5A6A7建立銷售中心，利潤為7580千元。

15.某公司在A城經(jīng)營一家年生產(chǎn)量30000件產(chǎn)品的工廠。產(chǎn)品被運輸?shù)郊住⒁?、丙三個

地區(qū)的分銷中心。由于預(yù)期將有需求增長，某公司計劃在B、C、D、E中一個或多個城市

建立新工廠以增加生產(chǎn)力。建立新工廠的年固定成本和年生產(chǎn)能力見表14,對三個分銷中

心的年需求量預(yù)測見表15o單件產(chǎn)品從每個工廠到每個分銷中心的運費見表16。

表14新建工廠的固定成本和生產(chǎn)能力

目標(biāo)工廠年固定成本（元）年生產(chǎn)能力（件）

/p>

C30()0002000()

D37500030000

E50000030000

表15分銷中心的年需求量預(yù)測

分銷中心年需求量（件）

甲30000

乙20000

丙20000

表16分銷系統(tǒng)的單位運輸成本

分銷中心

生產(chǎn)地

甲乙丙

A843

B523

C434

D975

E1042

問安排在哪些城市建立新工廠，使得總的建造成本和運輸成本為最低。

答案：應(yīng)在B、D建廠，總的建造成本和運輸成本為最低為940000。

16.某車間有五種生產(chǎn)設(shè)備，分別可以加工五種零件，每種零件在不同設(shè)備上加工所消

耗的時間見表17,要求：一種零件只能由一個設(shè)備加工，一個設(shè)備上只能加工一種零件。

問，如何安排生產(chǎn)，使加工五種零件所消耗的時間最短。

7

表17零件在設(shè)備上的加工時間

備

零件^\ABCDE

1127979

289666

371712149

415146610

34107109

答案：最優(yōu)安排為1-A,2-C;3-E;4-D;5A,花費時間為32.

17.有4名翻譯人員A、B、C、D,均精通英語?、法語、德語和俄語。現(xiàn)需翻譯一部書稿,

要求一名翻譯人員只能翻譯一種語言，一種語言只能由一位翻譯人員翻譯，需要時間見表

18。問如何指派工作，才能使翻譯總時間最短。

表18翻譯人員消耗的翻譯時間

翻譯和、英語法語德語俄語

A781012

BII9129

C810913

DII12911

答案；最優(yōu)安排為1-B,2-D;3-A;4-C,花費時間為34.

18.某機(jī)械設(shè)備公司準(zhǔn)備將4種設(shè)備A、B、C、D分別出租給4個公司，要求一種設(shè)備只

能出租給?個公司，?個公司只能租借?種設(shè)備，所得收費價格見表19。問如何安排出租，

才能使公司收益最大。

Ji?司

公司1公司2公司3公司4

設(shè)

A17181922

B21192220

C18202321

8

D21222425表19設(shè)備出

租給公司的收費價格

答案：最優(yōu)安排為1-D.2-A;3-C;4-B,最大收費為88.

19.某公司準(zhǔn)備將4位工程師A、B、C、D分別派往4個項目，要求一位工程師只能去往

一個項目，一個項目只能有一位工程師，所得收益見表20。問如何安排指派，才能使公司

收益最高。

表20工程師在項目上的收益

項目

項目1項目2項目3項目4

工程師

A67114

B5498

C43610

D5986

答案：最優(yōu)安排為l-C,2-A;3-D;4-B,最大收費為35.

20.某大學(xué)為運籌學(xué)專業(yè)研究生開設(shè)的課程如表所示。某些課程要求必須先選擇先修課程。

由于每門課程屬于不同的類別，因此考慮到學(xué)科間的互補(bǔ)，要求必須選擇兩門數(shù)學(xué)類課程、

兩門運籌學(xué)類課程和兩門計算機(jī)類課程，見表21。計算一個學(xué)生至少要選擇幾門課程才能

滿足上述要求？

課程所屬類別先修課程

運籌學(xué)數(shù)學(xué)類、運籌學(xué)類—

微積分?jǐn)?shù)學(xué)類—

計算機(jī)程序設(shè)計計算機(jī)類—

數(shù)據(jù)結(jié)構(gòu)數(shù)學(xué)類、計算機(jī)類i-算機(jī)程序設(shè)計

9

微積分表課程信息

管理統(tǒng)計數(shù)學(xué)類、運籌學(xué)類21

表

計算機(jī)模擬計算機(jī)類、運籌學(xué)類十算機(jī)程序設(shè)計

預(yù)測數(shù)學(xué)類、運籌學(xué)類管理統(tǒng)計

解答：至少選擇4門課才能滿足要求，分別是微積分、計算機(jī)程序設(shè)計、管理統(tǒng)計、計算機(jī)

模擬。

21.某物流公司擬在5個候選地點中建立若干個配送中心，用以滿足6個批發(fā)商對商品

的需求。若選中某地建立配送中心，則需支付一筆固定投資，沒被選中的地點則不用支付該

投資。每個批發(fā)商所需商品只能由建好的配送中心負(fù)責(zé)運輸。每個地點建立配送中心所需的

固定投資、每個建好的配送中心的配送能力、每個批發(fā)商的需求量以及批發(fā)商到配送中心的

單位運價（萬元/千噸）見表21。該物流公司如何確定商品運輸方案才能使得總成本最小？

總成本包括固定投資和運費兩部分。

表21配送能力、需求量以及批發(fā)商到配送中心的單位運價（萬元/千噸）

ABCDEF所需固定投資/萬元配送能刀/千噸

10.80.50.60.40.50.351

20.70.60.40.60.50.282

30.90.80.90.650.50.461.5

40.80.50.80.70.850.6102.5

50.70.90.80.60.70.4154

需求量/千噸0.80.90.711.20.6

10

答案：選擇在3、5構(gòu)建配送中心，使總成本最低為24.34。

22.某大學(xué)計算機(jī)機(jī)房聘用三名大學(xué)生（代號1,2,3,4）和3名研究生（代號5,6）值班。

已知每人從周一至周五每天最多可安排的值班時間及每人每小時的報酬見表22。

表23值班人員報酬表

報酬每天最多可安排的值班時間（h）

學(xué)生代號

(TU/h)周一周二周三周四周五

11260607

21206060

31148305

41()55604

51130480

61306063

該實驗室開放時間為上午8：00至晚上10：00,開放時間內(nèi)須有且僅須一名學(xué)生值班，

規(guī)定大學(xué)生每周值班不少于8小時，研究生每周不少于7小時，每名學(xué)生每周值班不超過3

次，每次值班不少于2小時，每天安排值班的學(xué)生不超過3人，且其中必須有一名研究生。

試建立數(shù)學(xué)模型并求解,為該實驗室安排一張人員的值班表，使總支付的報酬為最少。

最優(yōu)安排為見下表，最低投酬為794。

報酬每天最多可安排的值班時間（h）

學(xué)生代號

(%/h)周一周二周三周四周五

1126040

21202060

31108005

41050604

51130480

61304003

23.某公司現(xiàn)有一筆300萬元的資金，考慮今后三年內(nèi)用于下列四個項目的投資。

（1）三年內(nèi)的每年年初均可投資，每年獲利為投資額的20%,其本利可一起用于下一年的

投資。

（2）只允許每一年初投稿，于第二年末收回，本利合計為投資額的150%,但投資限額130

萬元。

（3）允許于第二年初投入，于第三年末收回，木利合計為投資額的160%,但投資限額200

萬元。

11

（4）允許于第三年初投入，年末收回，可獲得40%,但投資限額100萬元。

為該公司確定一個使第三年末本利和為最大的投資組合方案。

答案：建立連續(xù)投資的線性規(guī)劃模型，求得第三年末本利和為最大，579.6萬元。

24.某建筑公司有5個施工項目準(zhǔn)備開工，該公司有兩個金屬構(gòu)件生產(chǎn)車間，有兩個倉

庫，內(nèi)存3種規(guī)格鋼材，1種規(guī)格塑鋼門窗.（成套使用）。倉庫的鋼材品種及擁有量見表24,

構(gòu)件車間生產(chǎn)的單位構(gòu)件材料消耗、工時消耗、生產(chǎn)能力和生產(chǎn)成本見表25-28,各項目構(gòu)

件和鋼材需求量見表29,由構(gòu)件車間向各項目和由倉庫向各項目運送物資的單位運費見表

30。試建立并求解模型，編制各車間的產(chǎn)品生產(chǎn)計劃、由構(gòu)件車間向各項目和由倉庫向各項

目、各車間的物資調(diào)運計劃，使總成本為最小。

表24倉庫的鋼材品種、塑鋼擁有量

甲倉庫乙倉庫

A型鋼材（噸）60004800

B型鋼材（噸）50006200

C型鋼材（噸）65007200

塑鋼門窗（套）400320

表25單位構(gòu)件材料消耗量單位：噸/件

A型鋼材B型鋼材C型鋼材

鋼梁91323

鋼架111520

表26車間構(gòu)件生產(chǎn)工時消耗表

鋼梁（小時/件）鋼架（個時/件）工時擁有量（小時）

一車間304014000

二車間403510000

表27車間生產(chǎn)能力表單位：件

鋼梁鋼架

一車間260120

二車間200240

表28車間生產(chǎn)成本表單位：元/件

鋼梁鋼架

一車間320300

二車間280360

表29各項目鋼梁、鋼架、鋼材、塑鋼門窗需求量表

鋼梁鋼架A型鋼材B型鋼材C型鋼材塑鋼門

（件）曲（噸）㈣（噸）窗（套）

項目15040702070120

項目2305050106580

12

項目39080308085180

項目470100709060180

項目56020806040100

合計30()29030()26()320660

表30單位物資運價表單位：元融.公里元/套.公里元/件.公里

一車間二車間項目1項目2項目3項目4項目5

一車間—一6070140908()

二車間-一—40601207060

甲倉庫90603020304030

乙倉庫705()2025251540

答案：建立并求解模型，編制各車間的產(chǎn)品生產(chǎn)計劃、由構(gòu)件車間向各項目和由

色庫向各項目、各車間的物資調(diào)運計劃，使總成本為最小，目標(biāo)函數(shù)值為1536765

兀o

25.某構(gòu)件公司有四個構(gòu)件廠，現(xiàn)接受五個企業(yè)預(yù)應(yīng)力梁和預(yù)制樁的訂貨，訂貨量分別為

2200件和3200件，單價分別是1萬元和0.8萬元。各構(gòu)件廠生產(chǎn)能力、單位成本、材料單

耗等資料見表31,各構(gòu)件廠擁有的材料見表32,訂貨企業(yè)與各構(gòu)件廠的距離見表33,預(yù)應(yīng)

力梁單件重5噸，預(yù)制樁單件重3噸，每噸公里運費0.1元，按公司利潤最大建立并求解模

型。

答案：以公司利潤最大建立并求解模型，求得最大收益，目標(biāo)函數(shù)值為11362680

TIJO

第五章

1.設(shè)中心混凝土攪拌站的位置為(x,y),則攪拌站距離各工點的位置為：

4一%I+1-y|(仁1,2,3,4)

建立該問題的數(shù)學(xué)模型為：

44

minf=min=minZ(卜一引十“一)")嗎

Mr-l

2.r=0.43,0*=346,T(rJ=1601386o

3.t=0.56，Q=56O

13

4.r=0.96,Z*=26,0'=96。

>：

5.f=27.2,Z*=45,e=189.7,r,=15,r2=21.4,r3=23.14<>

6.(1)凹函數(shù)(2)嚴(yán)格凸函數(shù)(3)非凹非凸函數(shù)(4)嚴(yán)格凸函數(shù)

7.4=0.538,7(4)=1.751。

8.4=0.527,/(4)=1.751。

9.4=2.022,/(4)=0.978。

10.其KKT條件為

2(x—4)—4+4=0

4(i)=0

—6)=0

4>o,/U>()

最優(yōu)解為：r=4,此時4=4=0,/(z)=0o

11.其KKT條件為

4^1—4xo—8+4+4，，=0

~4^1+8X7—5+4+X,=0

?4(5+w-3)=0

4(4七+.々-9)=0

4>0,2,>0

rr

12.**=*：,芯［=(0,1)/，當(dāng)何=1時，X*=(x1\x；)=(0,-)；當(dāng)"=10時,

2

X*=(x；,x；)T=(*兒

13.(1)V=0.5,/(V)=0。

(2)X*=(T，E)T=(0,8.79)丁，/(X")=0。

14.(1)x=0，/")=1。

(2)X*=(1，E)7'=(l,0)J/(X*)=4/3o

14

第六章習(xí)題答案

I.求圖I中各圖的最小部分樹和最大部分樹。

2.某奶站在VI處辦公，每天送奶員需要給居住在各個街區(qū)的用戶送牛奶,問送奶員應(yīng)

如何安排路線，使其給所有用戶送完牛奶返回奶站，所走的路程最短。

答案：圖2應(yīng)該重復(fù);走vl-v2,v3-v4-v6,重復(fù):路長為22,所走總路程為128；

3.列表找出圖3的所有S到T的割集，確定其容晟，并找出該圖的最大流量，見下表所示。

VsGr割集割集容量

SV.,V2,V3,V4,T(SM)(SY)24

SYV2,V3,v%r(5,V2)(VI,V4)(VI,V3)28

s,v2(S-W)26

15

S,V3V1,V2,V4,7,(S,V|)(S,V2)(V3,T)39

SN4VlYN"(S,VI)(S,V2)(V4,T)(V4,V3)42

s,vhv2v3,V4,r(VhV3)(V2,V4)(V1,V4)30

S,V|,V3V3,V4,T(S,V2)(V1,V4)(V3,T)36

s,vhv4v2,v3,r(5,V2)(V,,V3)(V4,T)32

S,V|,V2,V3V4J(V3,T)(VhV4)(V2,V4)38

T27

5,V,,V2,V3,V4(V3,T)(V4,T)

5,V|,V3,V4V2,r(5,V2)(V3,T)(V4,T)40

s,vI,v2,v4V3J(VI,V3)(V4,V3)(V4,T)40

S,V2,V3V|,V4,T(S,VI)(V2,V4)(V3,T)41

)

5,V2,V4Vhv3,r(S,V!(V4,V3)(V4,T)29

SY,V3MV1,T(S.VI)(V3,T)(V4,T)38

s,v3,v4Vi,v2,r(S,VI)(S,V2)(V3J)(V4,T)51

4.用Dijkstra算法求出圖4中S到T的最短路徑。

答案:最短路徑為：S-vl-v3-T,路長26

5.采用福特法求圖5中S到各點的最短路徑。

答案見下表。

f(o)(1)f(3)

l//⑵

SV|V2肉V4V5sjSJ

S0710co0080000

V\-30148877(S-1)7(S-1)7(S-i)

V1CO00081100108(S-l-2)8(S-l-2)8(S-l-2)

V38-2oc00013COll(S-l-3)ll(S-l-3)ll(S-l-3)

V4800-6605815(S-l-4)15(S-l-4)15(S-l-4)

V5800CO800080020(S-1-4-5)20(S-1-4-5)

16

6.圖6為一網(wǎng)絡(luò)最大流問題，其中弧上的數(shù)字為容量，括號內(nèi)的數(shù)字為流量。

（1）在空白的括號內(nèi)填上數(shù)字，使之構(gòu)成一個可行流。

（2）對可行流進(jìn)行判斷、調(diào)整，求該圖的最大流。

7.如圖7所示，從三個生產(chǎn)基地經(jīng)公路將貨物運至兩個經(jīng)銷中心，中間要經(jīng)過四個中轉(zhuǎn)

站。圖中弧旁數(shù)字為各條公路的最大運輸能力（單位為噸/小時），求從生產(chǎn)基地每小時能運

送到經(jīng)銷中心的最大流量。

生產(chǎn)基地每小時能運送到經(jīng)銷中心的最大流量為205.運送過程見圖7a所示。

8.圖8所求為一最小費用最大流問題，弧上第一個數(shù)字表示單位物資運費(dij),第二個數(shù)

字表示該路的允許流量(Cj),求該圖的最小費用最大流。

9.某工地值班人員每天需對所管轄的范圍進(jìn)行巡視，其巡視路線如圖9所示，如何確定最

優(yōu)巡視路線？

答案：最優(yōu)巡視路線為重復(fù)走v2-v3-v6,v4-v7-v8,重復(fù)路長為15,所走總路程為68;

10.某工地道路網(wǎng)如圖9所示，工地值班員準(zhǔn)備從口點出發(fā)去口點，怎樣走，距離最近呢?

答案：路線為vl-v2-v3-v6-v9,最短距離為16.

11.采用福特法求圖10中S到各點的最短路徑。

S到各點的最短路徑見下表

/⑴)/⑴/⑵

V1V2V3V4V5%SJ%

VI0-15-100000

V20002003-1-1(1-2)-1(1-2)

V3-100000151(1-2-3)1(1-2-3)

V434802-1-1(1-4)-1(1-4)

作0000800081(1-4-5)1(1-4-5)

12.圖II為一網(wǎng)絡(luò)最大流問題，其中弧上的數(shù)字為容量，用標(biāo)記法找出S-T的最大流。

答案：流量見圖11a所示。最大流量為24.

13.某塑鋼廠S與建筑工地T間道路的容許流量為單位運價為46,力，塑鋼廠S與

18

建筑工地T之間的網(wǎng)絡(luò)如圖12所示（弧中左邊的數(shù)字為運輸物資的單位費用4G,力，右面

的數(shù)字為線路容量CG,j）,現(xiàn)需確定怎樣運輸才能使塑綱廠S運到建筑工地T的塑鋼最多

且運費最省。

答案：實際運量見圖12a所示。最大運量11,最小費用58.

14.有六臺機(jī)床，用xl,x2,…，x6表示，現(xiàn)有六個零件需要加工，用yl,y2，…，y6表示。其

中機(jī)床xl可加工零件yl；機(jī)床x2可加工零件yl、y2；機(jī)床x3可加工零件yl、y2、y3；

機(jī)床x4可加工零件y2；機(jī)床x5可加工零件y2、y3、y4；機(jī)床x6可加工零件y2、y5、y6。

現(xiàn)要求制定加工方案，使一臺機(jī)床只加工一個零件，一個零件只在一臺機(jī)床上加工，要求盡

可能多地安排零件的加工。試將該問題化為網(wǎng)絡(luò)最大流問題，求出能滿足上述條件的加工方

案。

答案：最多加工5個零件。機(jī)床xl-yl；機(jī)床x2-y2；機(jī)床x3-y3；機(jī)床x4不加工零件;

19

機(jī)床x5-y4；機(jī)床x6-y6o

15.某建筑公司一季度需完成四項施工任務(wù)，其中第一項任務(wù)工期為1月?2月份共兩個月，

總計需2000元；第二項任務(wù)工期為I月?3月份共三個月，總計需1500元；第三項任務(wù)工

期為2月?3月，共兩個月，總計需3000元；第四項任務(wù)工期為1月?3月，共三個月，總

計需2500元。該公