物流運(yùn)籌學(xué)復(fù)習(xí)題及答案

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

1．某工廠預(yù)備生產(chǎn)三種型號(hào)的洗衣機(jī)，每臺(tái)洗衣機(jī)所消耗的材料、所需要的人力及銷

材料供給天天3000公斤，而勞力天天最多有250小時(shí)，為使該工廠獲得最大利潤(rùn)，天天應(yīng)生產(chǎn)A、B、C三種型號(hào)的洗衣機(jī)各多少臺(tái)？

解：設(shè)天天應(yīng)生產(chǎn)A、B、C三種型號(hào)的洗衣機(jī)分離為123,,xxx臺(tái)，用()fx表示工廠所獲利潤(rùn)，由題意得到如下模型

123123123123

max()804030756250

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

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

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

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

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

1234

123423412341231234max()0.60.70.91534.51.5250

460..0.251.50.218020.6125,,,0

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

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

1．

12

121212

max105349

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

+≤??≥?解：先化為標(biāo)準(zhǔn)形

12341231241234

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

建立單純形表如下

故1217.5,1,3/2zxx*

===

2。12

121212max354212..3218,0

zxxxxstxxxx=+≤??≤??

+≤??≥?解：先化為標(biāo)準(zhǔn)形

12345132412512345max350004

212..3218,,,,0

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

++=??≥?

建立單純形表如下

故1236,2,6zxx*

===

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

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

解：用伏格爾法得到初始計(jì)劃如下

用位勢(shì)法舉行檢驗(yàn)令10u=由133uv+=得33v=；

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

計(jì)算各空格處的檢驗(yàn)數(shù)

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

λλλλλλ=-+>=-+>=-+>=-+>=-+>=--+>故這時(shí)的計(jì)劃為最優(yōu)，這時(shí)的運(yùn)輸計(jì)劃為

總運(yùn)費(fèi)為390百元。

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

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

解：用伏格爾法得到初始計(jì)劃如下

用位勢(shì)法舉行檢驗(yàn)令10u=由1211uv+=得211v=；

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

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

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

總運(yùn)費(fèi)為104。

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

1、其損益矩陣如下48210397

29774

2759423510106

9

10??

???

?????

解：482103260814

79729775075536474

27552053342942357

20225210106

9

104

403422

2

3????????

??

???????→→?

??

??

????????

?

?????

舉行增零變換得到

47

3142342521????

?

???

?

????????

?

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

324310?

??

?

??

?

???

2、有A、B、C、D四項(xiàng)任務(wù)需分派給甲、丙、丁四個(gè)人去做，這四個(gè)人都能擔(dān)當(dāng)上述

四項(xiàng)任務(wù)，但完成任務(wù)所需要的時(shí)光如表所示，問應(yīng)如何分派任務(wù)，可使完成四項(xiàng)任務(wù)的總工時(shí)最?。?/p>

解：

8171417096

992

91381517507953991716721090210579119024

222????????

????→→

?????

????????

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

88711???

???

??

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

1、求①到⑦的最短路長(zhǎng)與最短路徑

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

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

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

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

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

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

比較后，給⑤永遠(yuǎn)性編號(hào)(5)5P=以⑤為起點(diǎn)，舉行第四步迭代

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

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

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

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

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

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

給⑦永遠(yuǎn)性編號(hào)(7)8P=

至此，全部頂點(diǎn)都有了永遠(yuǎn)性編號(hào)，從而得到從①到⑦的最短路長(zhǎng)為8，最短路徑為

①③⑥④⑦

2、求①到⑥的最短路長(zhǎng)與最短路徑

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

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

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

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

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

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

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

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

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

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

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

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

給⑥永遠(yuǎn)性編號(hào)(6)7P=

至此，全部頂點(diǎn)都有了永遠(yuǎn)性編號(hào)，從而得到從①到⑥的最短路長(zhǎng)為7，最短路徑為

①③⑤⑥

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

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

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

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

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

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

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

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

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

()0

kkkkkkfsxsfskfs++=+=??

=?當(dāng)3k=時(shí)

33333(0)48,(1)64,(2)68,(3)78,(4)78fffff=====當(dāng)2k=時(shí)

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++????????++????????

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

當(dāng)1k=時(shí)

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，詳細(xì)分配計(jì)劃為甲3套，乙0套，丙1套。

2、某物流公司有12支巡邏隊(duì)負(fù)責(zé)4個(gè)倉(cāng)庫(kù)的巡邏。按規(guī)定對(duì)每個(gè)倉(cāng)庫(kù)可分離派2～4支隊(duì)

伍巡邏。因?yàn)樗申?duì)伍數(shù)量上的差別，各倉(cāng)庫(kù)一年內(nèi)預(yù)期發(fā)生事故的次數(shù)如表所示。試確定

派往各倉(cāng)庫(kù)的巡邏隊(duì)數(shù)，使預(yù)期事故的總次數(shù)最少。

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

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

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

1155()min{()()}

()0

kkkkkkfsPxfsfs++=+??

=?當(dāng)4k=時(shí)

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

當(dāng)3k=時(shí)

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=+=+=

當(dāng)2k=時(shí)

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++????

????

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

++????

當(dāng)1k=時(shí)

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)計(jì)劃為：

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

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

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

列出全部路線共五條

①②④⑥⑦長(zhǎng)29

①②④⑤⑦長(zhǎng)25

①③④⑥⑦長(zhǎng)27

①③④⑤⑦長(zhǎng)25

①③⑤⑦長(zhǎng)16

故關(guān)鍵路線為

①②④⑥⑦總工期為29

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

列出全部路線共四條

①⑥需4天

①④⑤⑥需9天

①②③⑤⑥需11天

①③⑤⑥需9天

故關(guān)鍵路線為

①②③⑤⑥需11天

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

0～2天做工序C需8人同時(shí)做工序D需6人

2～4天做工序B需5人同時(shí)做工序F需9人

4～7天做工序E需10人同時(shí)做工序G需4人