運(yùn)籌學(xué)-or課件運(yùn)輸1-底色修改

第三章運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題的數(shù)學(xué)模型1、運(yùn)輸問(wèn)題的一般提法

銷地產(chǎn)地B1B2B3B4B5產(chǎn)量

A1A2

A31.21.71.61.82.41.81.52.21.21.61.51.41.21.51.0

300040001000需求量1000500300015002000問(wèn)：如何合理調(diào)運(yùn)，才能使總運(yùn)費(fèi)最少？（產(chǎn)銷平衡）……2、運(yùn)輸模型的特點(diǎn)不是滿秩陣,r(A)=m+n-1基可行解只有m+n-1個(gè)變量3)對(duì)偶問(wèn)題二、表上作業(yè)法1、思路——同單純形法2、初始方案的確定1）西北角法銷地產(chǎn)地B1B2B3B4B5產(chǎn)量A11.21.71.61.82.43000A21.81.52.21.21.64000A31.51.41.21.51.01000銷量1000500300015002000100050015001500150010001000(Z=15120)空格：非基變量數(shù)字格：基變量2)最小元素法銷地產(chǎn)地B1B2B3B4B5產(chǎn)量A11.21.71.61.82.43000A21.81.52.21.21.64000A31.51.41.21.51.01000銷量1000500300015002000100010001500500200010001000(z=11750)3)差額法(z=11750)銷地產(chǎn)地B1

B2B3B4B5銷量A11.21.71.61.82.43000A21.81.52.21.21.64000A31.51.41.21.51.01000產(chǎn)量1000500300015002000差額差額0.40.30.20.30.10.40.30.610000.40.30.60.20.60.60.8100010000.40.320000.60.20.60.60.20.60.60.10.3150050010004)補(bǔ)零銷地產(chǎn)地B1B2B3B4產(chǎn)量A11087660

A2326150A3452960銷量503070202030601050補(bǔ)零位置：（1）所在行列上的最小元素；（2）不能形成所有頂點(diǎn)都為數(shù)字格的閉回路。03、檢驗(yàn)數(shù)的求法極小化問(wèn)題：所有δj≥0時(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è)格，由此形成的封閉折線稱為閉回路。銷地產(chǎn)地B1B2B3B4B5產(chǎn)量A11.21.71.61.82.43000A21.81.52.21.21.64000A31.51.41.21.51.01000銷量1000500300015002000100010001500500200010001000（2）閉回路的性質(zhì)以空格出發(fā)的閉回路存在且唯一；不存在所有頂點(diǎn)都為數(shù)字格的閉回路。2)用閉回路求檢驗(yàn)系數(shù)銷地產(chǎn)地B1B2B3B4B5產(chǎn)量A11.21.71.61.82.43000A21.81.52.21.21.64000A31.51.41.21.51.01000銷量1000500300015002000100010001500500200010001000+－+－δ12=1.7-1.6+2.2-1.5=0.8δ31=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可表示為：由空格所作出的閉回路中所有奇數(shù)格對(duì)應(yīng)的單位運(yùn)價(jià)之和減去所有

偶數(shù)格對(duì)應(yīng)的單位運(yùn)價(jià)之和的差。

ij1234510.81.21.42030.30.5-0.40.92)初等變換法（1）把對(duì)應(yīng)于數(shù)字格的運(yùn)費(fèi)加上括號(hào)銷產(chǎn)B1B2B3B4B5A11.21.71.61.82.4A21.81.52.21.21.6A31.51.41.21.51.0()()()()()()()銷產(chǎn)B1B2B3B4B5A1(1.2)1.7(1.6)1.82.4A21.2(0.9)(1.6)(0.6)(1.0)A31.51.41.21.5(1.0)銷產(chǎn)B1B2B3B4B5A1(0)0.8(0)1.21.4A20(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)系：銷產(chǎn)B1B2B3B4B5uiA11.21.71.61.82.4A21.81.52.21.21.6A31.51.41.21.51.0

vj()()()()()()()01.21.60.60.90.61.00

ij123451230.81.21.400.30.5-0.40.94、方案的調(diào)整過(guò)格(k,l)作閉回路，在閉回路上作盡可能大的調(diào)整，調(diào)整量y為偶數(shù)格上的最小調(diào)運(yùn)量。(最小θ規(guī)則)最小元素法銷地產(chǎn)地B1B2B3B4B5產(chǎn)量A11.21.71.61.82.43000A21.81.52.21.21.64000A31.51.41.21.51.01000銷量1000500300015002000100010001500500200010001000(z=11750)+_+_調(diào)整量y=1000，x23出基銷地產(chǎn)地B1B2B3B4B5產(chǎn)量A11.21.71.61.82.43000A21.81.52.21.21.64000A31.51.41.21.51.01000銷量1000500300015002000100015005002000100002000銷產(chǎn)B1B2B3B4B5uiA11.21.71.61.82.4A21.81.52.21.21.6A31.51.41.21.51.0

vj()()()()()()()01.21.60.21.31.01.4-0.4

ij1234510.40.81.020.40.430.70.50.9銷地產(chǎn)地甲乙丙丁產(chǎn)量137645

224322343853銷量332221

32

2

0Z1=36uivj03

6-1

4

5-2銷地產(chǎn)地甲乙丙丁產(chǎn)量137645

224322343853銷量33223

32

0

0Z2=36-4=32uivj203

4-15-2

4銷地產(chǎn)地甲乙丙丁產(chǎn)量137645

224322343853銷量33223

32

0Z3=32uivj203

40-2

6

5-3三、運(yùn)輸問(wèn)題的進(jìn)一步討論（一）產(chǎn)銷不平衡的運(yùn)輸問(wèn)題1、供大于求解決問(wèn)題的思路：產(chǎn)銷不平衡→產(chǎn)銷平衡

銷地產(chǎn)地B1B2B3B4B5產(chǎn)量A121347A2103595A378127

銷量23460

0

04342

3

2142、供不應(yīng)求（二）無(wú)運(yùn)輸通路如：Ａ２至Ｂ３無(wú)運(yùn)輸通路（三）目標(biāo)函數(shù)極大化型1、最大元素法2、最大減次大練習(xí)題

銷地產(chǎn)地B1B2B3B4B5

產(chǎn)量A1A2A3A4573446869735725845737005008001000需求量420490510530550已知某運(yùn)輸問(wèn)題的單位收益表如下：1、求出最佳運(yùn)輸方案；2、若A4產(chǎn)地因倉(cāng)庫(kù)容量限制，1000單位貨物必須全部運(yùn)出去則應(yīng)如何確定最佳運(yùn)輸方案。差額法銷地產(chǎn)地B1

B2B3B4B5B6銷量A1573440700A2686970500A3357250800A48457301000產(chǎn)量420490510530550500差額差額212121122490122150032314201223012251029021050500Z=17510

產(chǎn)地銷地B1B2B3B4B5B6產(chǎn)量A1573440700A2686970500A3357250800A48457301000銷量4204905105305505005004204905103029021050500uivj0741-168911Z=17610

產(chǎn)地銷地B1B2B3B4B5B6產(chǎn)量A1573440700A2686970500A3357250800A48457301000銷量42049051053055050045042049051080290210500uivjZ=1761050074316617-1+-+-+-

產(chǎn)地銷地B1B2B3B4B5B6產(chǎn)量A1573440700A2686970500A3357250800A48457301000銷量420490510530550500240420490510290290210290uivjZ=178202600700872507

產(chǎn)地銷地B1B2B3B4B5B6產(chǎn)量A1573440700A2686970500A3357250800A48457301000銷量420490510530550500240420490510290290210290uivjZ=17820260-M070-M7+M2-M5+M8+M-M7+M+-+-+-

產(chǎn)地銷地B1B2B3B4B5B6產(chǎn)量A1573440700A2686970500A3357250800A484573-M1000銷量42049051053055050042025051053029045050uivj260070-M240167+M8+M-18+-+-

產(chǎn)地銷地