物流運籌學復習題及答案

千里之行，始于足下讓知識帶有溫度。第第2頁/共2頁精品文檔推薦物流運籌學復習題及答案一、建立線性規(guī)劃模型

1．某工廠預備生產(chǎn)三種型號的洗衣機，每臺洗衣機所消耗的材料、所需要的人力及銷

材料供給天天3000公斤，而勞力天天最多有250小時，為使該工廠獲得最大利潤，天天應生產(chǎn)A、B、C三種型號的洗衣機各多少臺？

解：設天天應生產(chǎn)A、B、C三種型號的洗衣機分離為123,,xxx臺，用()fx表示工廠所獲利潤，由題意得到如下模型

123123123123

max()804030756250

..4050603000,,0fxxxxxxxstxxxxxx=++++≤??

++≤??≥?且為整數(shù)

2．某糕點廠生產(chǎn)面包、餅干、夾心餅和小甜餅四種產(chǎn)品，天天供給該廠的面粉、雞蛋、

糖和牛奶的數(shù)量如下表所示。配方和每種產(chǎn)品的利潤也列在表中。試制定一個最優(yōu)的生產(chǎn)方案。

解：設該糕點廠天天生產(chǎn)面包、餅干、夾心餅和小甜餅分離為1234,,,xxxx公斤，用()fx表示天天的利潤，由題意得如下模型

1234

123423412341231234max()0.60.70.91534.51.5250

460..0.251.50.218020.6125,,,0

fxxxxxxxxxxxxstxxxxxxxxxxx=++++++≤??++≤??+++≤??++≤??≥?

二、用單純形法求解線性規(guī)劃問題

1．

12

121212

max105349

..528,0zxxxxstxxxx=++≤??

+≤??≥?解：先化為標準形

12341231241234

max10500349..528,,,0zxxxxxxxstxxxxxxx=+++++=??++=??≥?

建立單純形表如下

故1217.5,1,3/2zxx*

===

2。12

121212max354212..3218,0

zxxxxstxxxx=+≤??≤??

+≤??≥?解：先化為標準形

12345132412512345max350004

212..3218,,,,0

zxxxxxxxxxstxxxxxxxx=+++++=??+=??

++=??≥?

建立單純形表如下

故1236,2,6zxx*

===

二、用表上作業(yè)法求解運輸問題

1、某建材公司所屬的三個水泥廠123,,AAA生產(chǎn)水泥運往四個銷售點1234,,,BBBB。已知各水泥廠的日產(chǎn)量（百噸），各銷售點的日銷售量（百噸）以及各工廠到各銷售點的單位運價（百元/百噸）如表所示，問該公司應如何調(diào)運產(chǎn)品，在滿足各銷售點銷量的前提下，使總運費為最??？

解：用伏格爾法得到初始計劃如下

用位勢法舉行檢驗令10u=由133uv+=得33v=；

由235uv+=得22u=；由224uv+=得22v=由241uv+=得41v=-；由322uv+=得30u=由314uv+=得14v=

計算各空格處的檢驗數(shù)

1112142133347(04)0;8(02)02(01)0;7(42)09(30)0;6(10)0

λλλλλλ=-+>=-+>=-+>=-+>=-+>=--+>故這時的計劃為最優(yōu)，這時的運輸計劃為

總運費為390百元。

2、某公司生產(chǎn)糖果，它有三個加工廠123,,AAA，每月產(chǎn)量分離為7噸，4噸，9噸。

該公司把這些產(chǎn)品分離運往四個銷售店1234,,,BBBB，每月的銷售量分離為3噸，6噸，5噸，6噸，已知從第i個加工廠到第j個銷售店的每噸糖果的運價如表所示，請確定在滿足各銷售店需求量的前提下，各加工廠到各銷售店的每月調(diào)運計劃，使該公司所花的總運費最小。

解：用伏格爾法得到初始計劃如下

用位勢法舉行檢驗令10u=由1211uv+=得211v=；

由224uv+=得27u=-；由133uv+=得33v=由1410uv+=得410v=；由348uv+=得32u=-由311uv+=得33u=計算各空格的檢驗數(shù)

1121232432333(30)0;010(73)0;5(710)09(112)0;2(32)0

λλλλλλ-+>=--+>=--+>=--==-->＝＝＝7-(-7+3)故得到的計劃為最優(yōu)。這時的最優(yōu)計劃為

總運費為104。

四、用匈牙利法求解最小指派問題

1、其損益矩陣如下48210397

29774

2759423510106

9

10??

???

?????

解：482103260814

79729775075536474

27552053342942357

20225210106

9

104

403422

2

3????????

??

???????→→?

??

??

????????

?

?????

舉行增零變換得到

47

3142342521????

?

???

?

????????

?

從而得到最優(yōu)指派計劃為

324310?

??

?

??

?

???

2、有A、B、C、D四項任務需分派給甲、丙、丁四個人去做，這四個人都能擔當上述

四項任務，但完成任務所需要的時光如表所示，問應如何分派任務，可使完成四項任務的總工時最?。?/p>

解：

8171417096

992

91381517507953991716721090210579119024

222????????

????→→

?????

????????

從而得到最優(yōu)指派計劃為

88711???

???

??

五、用Dijkstra算法求解最短路問題

1、求①到⑦的最短路長與最短路徑

解：令(1)0,(),2,3,,7PTii==∞=以①為起點，舉行第一步迭代

121315(2)min{,(1)}min{,04}4(3)min{,(1)}min{,03}3(5)min{,(1)}min{,05}5

TPTTPTTPT=∞+=∞+==∞+=∞+==∞+=∞+=比較后，給③永遠性編號(3)3P=以③為起點，舉行其次步迭代

36(6)min{,(3)}min{,32}5TPT=∞+=∞+=

比較后，給②永遠性編號(2)4P=以②為起點，舉行第三步迭代

25(5)min{5,(2)}min{5,41}5TPT=+=+=

比較后，給⑤永遠性編號(5)5P=以⑤為起點，舉行第四步迭代

54(4)min{,(5)}min{,53}8TPT=∞+=∞+=56(6)min{5,(5)}min{5,51}5TPT=+=+=

比較后，給⑥永遠性編號(6)5P=以⑥為起點，舉行第五步迭代

6467(4)min{8,(6)}min{8,52}7(7)min{,(6)}min{,54}9

TPTTPT=+=+==∞+=∞+=

比較后，給④永遠性編號(4)7P=以④為起點，舉行第六步迭代

47(7)min{9,(4)}min{9,71}8TPT=+=+=

給⑦永遠性編號(7)8P=

至此，全部頂點都有了永遠性編號，從而得到從①到⑦的最短路長為8，最短路徑為

①③⑥④⑦

2、求①到⑥的最短路長與最短路徑

解：令(1)0,(),2,3,,6PTii==∞=以①為起點，舉行第一步迭代

1213(2)min{,(1)}min{,04}4(3)min{,(1)}min{,02}2

TPTTPT=∞+=∞+==∞+=∞+=

比較后，給③永遠性編號(3)2P=以③為起點，舉行其次步迭代

35(5)min{,(3)}min{,22}4TPT=∞+=∞+=

比較后，給②永遠性編號(2)4P=以②為起點，舉行第三步迭代

2524(5)min{4,(2)}min{4,41}4(4)min{,(2)}min{,43}7

TPTTPT=+=+==∞+=∞+=

比較后，給⑤永遠性編號(5)4P=以為起點，舉行第四步迭代

54(4)min{7,(5)}min{7,42}6TPT=+=+=56(6)min{,(5)}min{,43}7TPT=∞+=∞+=

比較后，給④永遠性編號(4)6P=以④為起點，舉行第五步迭代

46(6)min{7,(4)}min{7,63}7TPT=+=+=

給⑥永遠性編號(6)7P=

至此，全部頂點都有了永遠性編號，從而得到從①到⑥的最短路長為7，最短路徑為

①③⑤⑥

六、用動態(tài)規(guī)劃法求解資源分配問題1、

某市電信局有四套通訊設備，預備分給甲、乙、丙三個地區(qū)支局，事先調(diào)查了各地

區(qū)支局的經(jīng)營狀況，并對各種分配計劃作了經(jīng)濟效益的估量，如表所示，其中設備數(shù)為0時的收益，指已有的經(jīng)營收益，問如何分配這四套設備，使總的收益最大？

解：分三個階段1,2,3k=分離對應給甲、乙、丙三個地區(qū)支局分配設備，0,1,2,3,4ks=表

示在第k階段分配的設備套數(shù)，

()kkxs表示第k階段分配ks套設備所產(chǎn)生的收益

()kkfs表示將ks套設備分配給第k階段直到第3階段所產(chǎn)生的收益

用逆推法得到基本遞推方程

1144()max{()()},1,2,3

()0

kkkkkkfsxsfskfs++=+=??

=?當3k=時

33333(0)48,(1)64,(2)68,(3)78,(4)78fffff=====當2k=時

223(0)max{(0)(00)}max{4840}88fxf=+-=+=

23223(0)(1)6440(1)maxmax104(1)(0)4248xffxf++????

===????++????

2322323(0)(2)6840(2)max(1)(1)max64421085048(2)(0)xffxfxf++????

????

=+=+=????????

++????

2323

22323(0)(3)4078(1)(2)6842(3)maxmax118(2)(1)64506048(3)(0)xfxffxfxf++????

????++????===????++????????++????

23232232323(0)(4)4078(1)(3)4278(4)max(2)(2)max68501246064(3)(1)6648(4)(0)xfxffxfxfxf++????????++????????

=+=+=????????++????+????+????

當1k=時

112(0)max{(0)(0)}max{3888}126fxf=+=+=12112(1)(0)4188(1)maxmax140(0)(1)38102xffxf++????

===????++????

1211212(2)(0)4888(2)max(1)(1)max4110414638108(0)(2)xffxfxf++????

????

=+=+=????????

++????

1212

11212(3)(0)6088(2)(1)48104(3)maxmax156(1)(2)4110838118(0)(3)xfxffxfxf++????

????++????===????++????????++????

12121121212(4)(0)6688(3)(1)60104(4)max(2)(2)max4810816441118(1)(3)38124(0)(4)xfxffxfxfxf++????????++????????

=+=+=????????++????+?+???????

故最大收益為162，詳細分配計劃為甲3套，乙0套，丙1套。

2、某物流公司有12支巡邏隊負責4個倉庫的巡邏。按規(guī)定對每個倉庫可分離派2～4支隊

伍巡邏。因為所派隊伍數(shù)量上的差別，各倉庫一年內(nèi)預期發(fā)生事故的次數(shù)如表所示。試確定

派往各倉庫的巡邏隊數(shù)，使預期事故的總次數(shù)最少。

把往四個倉庫派巡邏隊劃分為4,3,2,1k=四個階段，狀態(tài)變量ks為k階段初擁有的未派出的巡邏隊數(shù)，決策變量kx為k階段派出的巡邏隊數(shù)，狀態(tài)轉(zhuǎn)移方程為1kkkssx+=-，

()kkPx為k階段派出kx個巡邏隊時預期發(fā)生的事故數(shù)，()kkfs為k階段派出kx個巡邏隊

至四階段時預期發(fā)生的事故數(shù)，用逆推法得到遞推公式

1155()min{()()}

()0

kkkkkkfsPxfsfs++=+??

=?當4k=時

444(2)34,(3)31,(4)25fff===

當3k=時

334(4)min{(2)(2)}min{1434}48fPf=+=+=34334(2)(3)1431(5)minmin45(3)(2)1234PffPf++????

===????++????

3433434(2)(4)1425(6)min(3)(3)min1231391134(4)(2)PffPfPf++????????

=+=+=????????

++????

34334(4)(3)1225(7)minmin37(3)(4)1131PffPf++????

===????++????

334(8)min{(4)(4)}min{1125}36fPf=+=+=

當2k=時

223(6)min{(2)(4)}384886fPf=+=+=23223(2)(5)3845(7)minmin83(3)(4)3648PffPf++????

===????++????

2322323(2)(6)3839(8)min(3)(5)min3645773048(4)(4)PffPfPf++????????

=+=+=????????

++????

2322323(2)(7)3837(9)min(3)(6)min3639753045(4)(5)PffPfPf++????

????

=+=+=????????

++????

2322323(2)(8)3836(10)min(3)(7)min3637693039(4)(6)PffPfPf++????

????

=+=+=????????

++????

當1k=時

112(8)min{(2)(6)}1886104fPf=+=+=

12112(2)(7)1883(9)minmin101(3)(6)1686PffPf++??

??===????++????

12112

12(2)(8)1877(10)min(3)(7)min1683951286(4)(6)PffPfPf++????????

=+=+=????????

++????12112

12(2)(9)1875(11)min(3)(8)min1677931283(4)(7)PffPfPf++??

??????

=+=+=????????

++????1211212(2)(10)1869(12)min(3)(9)min1675871277(4)(8)PffPfPf++??

??????

=+=+=????????

++????

故最優(yōu)計劃為：

甲倉庫2支乙倉庫4支丙倉庫2支丁倉庫4支預期發(fā)生的事故數(shù)為87。

七、求解網(wǎng)絡規(guī)劃問題

1．某項工程的工序名稱、工序時光以及工序之間的規(guī)律關(guān)系如表所示，繪制該工程的網(wǎng)絡

列出全部路線共五條

①②④⑥⑦長29

①②④⑤⑦長25

①③④⑥⑦長27

①③④⑤⑦長25

①③⑤⑦長16

故關(guān)鍵路線為

①②④⑥⑦總工期為29

2．某項工程各工序的工序時光及所需要的人數(shù)如表所示，現(xiàn)有人數(shù)為14人，試確定工程完

列出全部路線共四條

①⑥需4天

①④⑤⑥需9天

①②③⑤⑥需11天

①③⑤⑥需9天

故關(guān)鍵路線為

①②③⑤⑥需11天

詳細時光－資源的最優(yōu)支配為

0～2天做工序C需8人同時做工序D需6人

2～4天做工序B需5人同時做工序F需9人

4～7天做工序E需10人同時做工序G需4人