運(yùn)籌運(yùn)輸問(wèn)題

1、 第三章 運(yùn)輸問(wèn)題 運(yùn)輸問(wèn)題的數(shù)學(xué)模型1、運(yùn)輸問(wèn)題的一般提法 銷(xiāo)地產(chǎn)地 B1 B2 B3 B4 B5 產(chǎn) 量 A1 A2 A31.2 1.7 1.6 1.8 2.41.8 1.5 2.2 1.2 1.61.5 1.4 1.2 1.5 1.0 3000 4000 1000 需求量1000 500 3000 1500 2000問(wèn)：如何合理調(diào)運(yùn)，才能使總運(yùn)費(fèi)最少？（產(chǎn)銷(xiāo)平衡）2、運(yùn)輸模型的特點(diǎn)不是滿秩陣, r(A)=m+n-1 基可行解只有m+n-1個(gè)變量3) 對(duì)偶問(wèn)題二、表上作業(yè)法1、思路同單純形法2、初始方案的確定1）西北角法 銷(xiāo)地產(chǎn)地B1B2B3B4B5產(chǎn) 量A11.21.71.61.82.4

2、3000A21.81.52.21.21.64000A31.51.41.21.51.01000 銷(xiāo) 量1000500300015002000100050015001500150010001000(Z=15120)空格：非基變量數(shù)字格：基變量2) 最小元素法 銷(xiāo)地產(chǎn)地B1B2B3B4B5產(chǎn) 量A11.21.71.61.82.43000A21.81.52.21.21.64000A31.51.41.21.51.01000 銷(xiāo) 量1000500300015002000100010001500500200010001000(z=11750)3) 差額法(z=11750) 銷(xiāo)地產(chǎn)地B1 B2B3B4B5銷(xiāo)量

3、A11.21.71.61.82.43000A21.81.52.21.21.64000A31.51.41.21.51.01000 產(chǎn) 量1000 500300015002000差 額差 額0.40.30.2 0.3 0.1 0.40.3 0.610000.40.30.60.20.60.60.8100010000.40.320000.60.20.60.60.20.60.60.10.3150050010004) 補(bǔ)零 銷(xiāo)地產(chǎn)地B1B2B3B4產(chǎn) 量A110876 60 A2326150A3452960 銷(xiāo) 量503070202030601050補(bǔ)零位置：（1）所在行列上的最小元素；（2）不能形成所有

4、頂點(diǎn)都為數(shù)字格的閉回路。0 產(chǎn)地銷(xiāo)地123 產(chǎn) 量121012231114344銷(xiāo) 量91011Z=49P98/3.2(1)3、檢驗(yàn)數(shù)的求法極小化問(wèn)題：所有j0時(shí)為最優(yōu)。1）閉回路法 閉回路從調(diào)運(yùn)方案的某一空格出發(fā)，沿水平或垂直的 方向前進(jìn)，遇到一個(gè)適當(dāng)?shù)臄?shù)字格便按與前進(jìn) 方向垂直的路徑前進(jìn)。經(jīng)過(guò)若干次后，再回到 原來(lái)出發(fā)的那個(gè)格，由此形成的封閉折線稱為 閉回路。 銷(xiāo)地產(chǎn)地B1B2B3B4B5產(chǎn) 量A11.21.71.61.82.43000A21.81.52.21.21.64000A31.51.41.21.51.01000 銷(xiāo) 量10005003000150020001000100015005

5、00200010001000（2）閉回路的性質(zhì) 以空格出發(fā)的閉回路存在且唯一； 不存在所有頂點(diǎn)都為數(shù)字格的閉回路。2) 用閉回路求檢驗(yàn)系數(shù) 銷(xiāo)地產(chǎn)地B1B2B3B4B5產(chǎn) 量A11.21.71.61.82.43000A21.81.52.21.21.64000A31.51.41.21.51.01000 銷(xiāo) 量1000500300015002000100010001500500200010001000+12 = 1.7-1.6+2.2-1.5=0.831 =1.5-1.0+1.6-2.2+1.6-1.2=0.3(1)(2)(3)(4)結(jié)論：空格（i,j)的檢驗(yàn)系數(shù)ij可表示為：由空格所作出的 閉

6、回路中所有奇數(shù)格對(duì)應(yīng)的單位運(yùn)價(jià)之和減去所有 偶數(shù)格對(duì)應(yīng)的單位運(yùn)價(jià)之和的差。 i j1234510.81.21.42030.30.5-0.40.92) 初等變換法（1）把對(duì)應(yīng)于數(shù)字格的運(yùn)費(fèi)加上括號(hào) 銷(xiāo)產(chǎn)B1B2B3B4B5 A11.21.71.61.82.4 A21.81.52.21.21.6 A31.51.41.21.51.0( )( )( )( )( )( )( ) 銷(xiāo)產(chǎn)B1B2B3B4B5 A1(1.2)1.7(1.6)1.82.4 A21.2(0.9)(1.6)(0.6)(1.0) A31.51.41.21.5(1.0) 銷(xiāo)產(chǎn)B1B2B3B4B5 A1( 0 )0.8( 0 )1.21.

7、4 A20( 0 )( 0 )( 0 )( 0 ) A30.30.5-0.40.9( 0 )（2）作行的初等變化，使每列中加括號(hào)的數(shù)都相等-0.6(3)各列分別減去本列中加括號(hào)的數(shù)3) 位勢(shì)法對(duì)應(yīng)于基變量存在如下關(guān)系： 銷(xiāo)產(chǎn)B1B2B3B4B5 ui A11.21.71.61.82.4 A21.81.52.21.21.6 A31.51.41.21.51.0 vj( )( )( )( )( )( )( ) 01.21.60.60.9 0.6 1.0 0 i j12345123 0.8 1.2 1.4 0 0.3 0.5 -0.4 0.94、方案的調(diào)整過(guò)格(k,l)作閉回路，在閉回路上作盡可能大的

8、調(diào)整，調(diào)整量y為偶數(shù)格上的最小調(diào)運(yùn)量。(最小規(guī)則) 最小元素法 銷(xiāo)地產(chǎn)地B1B2B3B4B5產(chǎn) 量A11.21.71.61.82.43000A21.81.52.21.21.64000A31.51.41.21.51.01000 銷(xiāo) 量1000500300015002000100010001500500200010001000(z=11750)+_+_調(diào)整量 y=1000，x23出基 銷(xiāo)地產(chǎn)地B1B2B3B4B5產(chǎn) 量A11.21.71.61.82.43000A21.81.52.21.21.64000A31.51.41.21.51.01000 銷(xiāo) 量100050030001500200010001

9、50050020001000 02000 銷(xiāo)產(chǎn)B1B2B3B4B5 ui A11.21.71.61.82.4 A21.81.52.21.21.6 A31.51.41.21.51.0 vj( )( )( )( )( )( )( ) 01.21.60.21.3 1.0 1.4- 0.4 i j1234510.40.81.020.40.430.70.50.9 銷(xiāo)地產(chǎn)地甲乙丙丁產(chǎn) 量13764 5 224322343853 銷(xiāo) 量332221 32 2 0Z1=36uivj0 3 6-1 4 5-2 銷(xiāo)地產(chǎn)地甲乙丙丁產(chǎn) 量137645 224322343853 銷(xiāo) 量33223 32 0 0Z2=36

10、-4=32uivj203 4-15-2 4 銷(xiāo)地產(chǎn)地甲乙丙丁產(chǎn) 量13764 5 224322343853 銷(xiāo) 量33223 32 0Z3=32uivj203 4 0-2 6 5-3三、運(yùn)輸問(wèn)題的進(jìn)一步討論（一）產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題1、供大于求解決問(wèn)題的思路：產(chǎn)銷(xiāo)不平衡產(chǎn)銷(xiāo)平衡 銷(xiāo)地產(chǎn)地B1B2B3B4B5產(chǎn) 量A121347A2103595A378127 銷(xiāo) 量23460 0 0 4 3 4 2 3 2 1 42 、供不應(yīng)求（二）無(wú)運(yùn)輸通路如：至無(wú)運(yùn)輸通路（三）目標(biāo)函數(shù)極大化型1、最大元素法2、最大減次大練習(xí)題 銷(xiāo)地產(chǎn)地 B1 B2 B3 B4 B5 產(chǎn) 量A1A2A3A4 5 7 3 4

11、4 6 8 6 9 7 3 5 7 2 5 8 4 5 7 3 7005008001000需求量420 490 510 530 550 已知某運(yùn)輸問(wèn)題的單位收益表如下：1、求出最佳運(yùn)輸方案；2、若A4產(chǎn)地因倉(cāng)庫(kù)容量限制，1000單位貨物必須全部運(yùn)出去則應(yīng)如何確定最佳運(yùn)輸方案。 差額法 銷(xiāo)地產(chǎn)地B1 B2B3B4B5B6銷(xiāo)量A1573440700A2686970500A3357250800A48457301000 產(chǎn) 量420 490510530550500差 額差 額21 21 2 1 1 2 24901 2 2 1500 3 2 3 1 420 1 2 2 30 1 2 2510290210

12、 50500Z=17510 產(chǎn)地銷(xiāo)地B1B2B3B4B5B6產(chǎn) 量A1573440700A2686970500A3357250800A48457301000銷(xiāo) 量4204905105305505005004204905103029021050500uivj0 7 4 1-1 6 8 91 1Z=17610 產(chǎn)地銷(xiāo)地B1B2B3B4B5B6產(chǎn) 量A1573440700A2686970500A3357250800A48457301000銷(xiāo) 量42049051053055050045042049051080290210500uivjZ=1761050 0 7 4 3 1 6 6 1 7-1+-+-+

13、- 產(chǎn)地銷(xiāo)地B1B2B3B4B5B6產(chǎn) 量A1573440700A2686970500A3357250800A48457301000銷(xiāo) 量420490510530550500240420490510290290210290uivjZ=17820260 0 70 0 8 72 5 0 7 產(chǎn)地銷(xiāo)地B1B2B3B4B5B6產(chǎn) 量A1573440700A2686970500A3357250800A48457301000銷(xiāo) 量420490510530550500240420490510290290210290uivjZ=17820260-M 0 7 0-M7 + M2-M5 + M8 + M-M7 +

14、 M +-+-+- 產(chǎn)地銷(xiāo)地B1B2B3B4B5B6產(chǎn) 量A1573440700A2686970500A3357250800A484573-M1000銷(xiāo) 量420490510530550500420250510530290 450 50uivj260 0 7 0-M240 1 67+M 8+M-1 8+-+- 產(chǎn)地銷(xiāo)地B1B2B3B4B5B6產(chǎn) 量A1573440700A2686970500A3357250800A484573-M1000銷(xiāo) 量420490510530550500420200510530290 500uivj260 0 7 0240 1 650Z=17430-3 11 10-1

15、 8+-+-+- 產(chǎn)地銷(xiāo)地B1B2B3B4B5B6產(chǎn) 量A1573440700A2686970500A3357250800A484573-M1000銷(xiāo) 量42049051053055050042044051053050 260uivj500 0 7 050Z=17670240-30 7 5 11 10 2+-+-+- 產(chǎn)地銷(xiāo)地B1B2B3B4B5B6產(chǎn) 量A1573440700A2686970500A3357250800A484573-M1000銷(xiāo) 量42049051053055050042049046053050 210uivj500 0 7 0Z=177202900 7 5 250-2 10 9 銷(xiāo)地產(chǎn)地甲乙丙產(chǎn) 量A151822 400 B212516 450 銷(xiāo) 量320250350 C 701521M290300甲22M1627080M0丙3、書(shū)上P100/（1）； （2）若C22變?yōu)?