第四章運(yùn)輸問(wèn)題

1、 第四章第四章 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 Combinatorial Optimization Theory第四章第四章 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 運(yùn)輸問(wèn)題（運(yùn)輸問(wèn)題（Transportation Problem，簡(jiǎn)記為，簡(jiǎn)記為T(mén)P）是一類(lèi)常見(jiàn)而且極其特殊的線性規(guī)劃問(wèn)題是一類(lèi)常見(jiàn)而且極其特殊的線性規(guī)劃問(wèn)題. .它最早是從它最早是從物資調(diào)運(yùn)工作中提出來(lái)的，是物流優(yōu)化管理的重要的物資調(diào)運(yùn)工作中提出來(lái)的，是物流優(yōu)化管理的重要的內(nèi)容之一內(nèi)容之一 。 從理論上講，運(yùn)輸問(wèn)題也可用單純形法來(lái)求解，從理論上講，運(yùn)輸問(wèn)題也可用單純形法來(lái)求解，但是由于運(yùn)輸問(wèn)題數(shù)學(xué)模型具有特殊的結(jié)構(gòu)，存在一但是由于運(yùn)輸問(wèn)題數(shù)學(xué)模型具有特殊的結(jié)構(gòu)，

2、存在一種比單純形法更簡(jiǎn)便的計(jì)算方法種比單純形法更簡(jiǎn)便的計(jì)算方法 表上作業(yè)法，表上作業(yè)法，用表上作業(yè)法來(lái)求解運(yùn)輸問(wèn)題比用單純形法可節(jié)約計(jì)用表上作業(yè)法來(lái)求解運(yùn)輸問(wèn)題比用單純形法可節(jié)約計(jì)算時(shí)間與計(jì)算費(fèi)用算時(shí)間與計(jì)算費(fèi)用. .但表上作業(yè)法的實(shí)質(zhì)仍是單純形法但表上作業(yè)法的實(shí)質(zhì)仍是單純形法 加速物資流轉(zhuǎn)加速物資流轉(zhuǎn) 降低流通費(fèi)用降低流通費(fèi)用 1 運(yùn)輸問(wèn)題及其數(shù)學(xué)模型1 1 運(yùn)輸問(wèn)題及其數(shù)學(xué)模型運(yùn)輸問(wèn)題及其數(shù)學(xué)模型 設(shè)某種物資共有設(shè)某種物資共有 m 個(gè)產(chǎn)地個(gè)產(chǎn)地 A1，A2，Am，各各產(chǎn)地的產(chǎn)量分別是產(chǎn)地的產(chǎn)量分別是a1，a2 ，am；有有n 個(gè)銷(xiāo)地個(gè)銷(xiāo)地 B1，B2，Bn ，各銷(xiāo)地的銷(xiāo)量分別為各銷(xiāo)地的銷(xiāo)量

3、分別為b1，b2，bn . 假定從產(chǎn)地假定從產(chǎn)地Ai（i =1，2，m）向銷(xiāo)地向銷(xiāo)地Bj（j =1，2，n）運(yùn)輸單位物資的運(yùn)價(jià)是運(yùn)輸單位物資的運(yùn)價(jià)是cij，問(wèn)怎樣調(diào)運(yùn)才能，問(wèn)怎樣調(diào)運(yùn)才能使總運(yùn)費(fèi)最??？使總運(yùn)費(fèi)最??？一、一、運(yùn)輸問(wèn)題的數(shù)學(xué)模型運(yùn)輸問(wèn)題的數(shù)學(xué)模型0,0,0 (1,2,;1,2, )ijijabcim jn第四章第四章 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地 B1 B2 Bn產(chǎn)量產(chǎn)量 A1c11c21 c1n a1 A2c21c22 c2n a2 Amcm1cm2 cmn am銷(xiāo)量銷(xiāo)量 b1 b2 bn 運(yùn)輸表運(yùn)輸表1 1、產(chǎn)銷(xiāo)平衡問(wèn)題、產(chǎn)銷(xiāo)平衡問(wèn)題即即11mnijijab 設(shè)設(shè) xij

4、 表示產(chǎn)地表示產(chǎn)地 Ai 運(yùn)往銷(xiāo)地運(yùn)往銷(xiāo)地 Bj (i=1,2,m; j=1,2,n) 的運(yùn)量的運(yùn)量.11minmnijijijzc x1. .nijijstxa1,2,im1mijjixb1,2,jn01,2,;1,2,ijxim jn 銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地 B1 B2 Bn產(chǎn)量產(chǎn)量 A1 x11c11 x12c12 x1n c1n a1 A2 x21c21 x22c22 x2nc2n a2 Am xm1cm1 xm2cm2 xmncmn am銷(xiāo)量銷(xiāo)量 b1 b2 bnNote : cij 在左下在左下角角 xij 在右上角在右上角 1 運(yùn)輸問(wèn)題及其數(shù)學(xué)模型2 2、產(chǎn)銷(xiāo)不平衡問(wèn)題、產(chǎn)銷(xiāo)不平衡問(wèn)題

5、當(dāng)當(dāng)11mnijijab11minmnijijijzc x1. .nijijstxa1,2,im1mijjixb1,2,jn01,2,;1,2,ijxim jn當(dāng)當(dāng)11mnijijab11minmnijijijzc x1. .nijijstxa1,2,im1mijjixb1,2,jn01,2,;1,2,ijxim jn第四章第四章 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題二、運(yùn)輸問(wèn)題數(shù)學(xué)模型的特點(diǎn)二、運(yùn)輸問(wèn)題數(shù)學(xué)模型的特點(diǎn)討論產(chǎn)銷(xiāo)平衡問(wèn)題討論產(chǎn)銷(xiāo)平衡問(wèn)題定理定理 1 平衡運(yùn)輸平衡運(yùn)輸問(wèn)題必有可行解，也必有最優(yōu)解問(wèn)題必有可行解，也必有最優(yōu)解. . 證明證明定理定理 2 平衡運(yùn)輸問(wèn)題的約束方程系數(shù)矩陣平衡運(yùn)輸問(wèn)題的約束方

6、程系數(shù)矩陣 A 和增廣矩和增廣矩陣陣 的秩相等，且等于的秩相等，且等于 m+n-1 . 即即 A( )( )1R AR Amn定理定理2 說(shuō)明：說(shuō)明：基可行解包含基可行解包含m+n-1個(gè)基變量個(gè)基變量.定理定理 3 平衡運(yùn)輸問(wèn)題的約束方程系數(shù)矩陣平衡運(yùn)輸問(wèn)題的約束方程系數(shù)矩陣 A 的所有的所有各階子式只取各階子式只取 0，1 或或 -1 三個(gè)值三個(gè)值.定理定理 4 如果平衡運(yùn)輸問(wèn)題中的所有產(chǎn)量如果平衡運(yùn)輸問(wèn)題中的所有產(chǎn)量 ai 和銷(xiāo)量和銷(xiāo)量 bj都是整數(shù)，那么，它的任一基可行解都是整數(shù)解都是整數(shù)，那么，它的任一基可行解都是整數(shù)解. .證明證明noteGo on定理定理 1 1 的證明的證明Pr

7、oof :11mnijijabd設(shè)(1,2,;1,2, )ijijabxim jnd111(1,2,)nnnijiijjijjjabaxba imdd則取則取顯然有顯然有 ， 0ijx 又又111(1,2, )mmmijjijijiiiabbxabjndd所以所以 ，是問(wèn)題的一個(gè)可行解，是問(wèn)題的一個(gè)可行解. 0ijx 0 (1,2,;1,2, )ijcim jn 又因?yàn)橛忠驗(yàn)?，對(duì)于任一可行，對(duì)于任一可行解有目標(biāo)函數(shù)值解有目標(biāo)函數(shù)值 ，對(duì)于求極小化問(wèn)題，目標(biāo)函數(shù)，對(duì)于求極小化問(wèn)題，目標(biāo)函數(shù)值有下界，則必有最優(yōu)解值有下界，則必有最優(yōu)解. 0z 1 運(yùn)輸問(wèn)題及其數(shù)學(xué)模型Note : 平衡運(yùn)輸問(wèn)題有

8、平衡運(yùn)輸問(wèn)題有 個(gè)變量，個(gè)變量， 個(gè)約束個(gè)約束條件，規(guī)模很大。條件，規(guī)模很大。m nmn111111111111111111A111212122212nnmmmnxxxxxxxxxGo back( )1R Amn( )1R Amnmn1212111111111111111111mnaaaAbbb定理定理 4 的證明的證明Proof : 設(shè)設(shè) x 是是 Ax = b 的任一基可行解，的任一基可行解，1 12211,mnmni ji jijxxxB 為對(duì)應(yīng)的基矩陣，則為對(duì)應(yīng)的基矩陣，則det(1, 2,1)detttti jBxtmnB 其中其中 Bt 是用是用 b 中對(duì)應(yīng)的中對(duì)應(yīng)的 m+n-1元

9、素替換元素替換 B 的第的第t 列列元素得到的矩陣元素得到的矩陣.1212Tmnbaaabbb 顯然顯然，由定理，由定理 3 及及 ai 、 bj都是整數(shù)知，都是整數(shù)知，det Bt 是個(gè)是個(gè)整數(shù)，整數(shù)， det B= ，因此，因此，都是整數(shù)都是整數(shù).1(1, 2,1)tti jxtmn其基變量為其基變量為第四章第四章 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題定義定義 1 1凡是能排列成凡是能排列成1 11 22 22 31,s ssi ji ji ji ji ji jxxxxxx（其中（其中 互不相同，互不相同， 互不相同）互不相同）12, ,si ii12,sjjj形式的變量集合，稱(chēng)為一個(gè)閉回路，其中諸變量稱(chēng)為形

10、式的變量集合，稱(chēng)為一個(gè)閉回路，其中諸變量稱(chēng)為這個(gè)閉回路的頂點(diǎn)這個(gè)閉回路的頂點(diǎn). B1 B2 B3 B4 B5 A1 x11 x12 x13 x14 x15 A2 x21 x22 x23 x24 x25 A3 x31 x32 x33 x34 x35 A4 x41 x42 x43 x44 x45如：如： 變量集合變量集合111222243431,xxxxxx變量集合變量集合1114444535322221,xxxxxxxx2、每一行（或列）若有閉回路的頂點(diǎn)，則有兩個(gè)每一行（或列）若有閉回路的頂點(diǎn)，則有兩個(gè)頂點(diǎn)；頂點(diǎn)；3、每?jī)蓚€(gè)頂點(diǎn)格子的連線都是水平的或垂直的；每?jī)蓚€(gè)頂點(diǎn)格子的連線都是水平的或垂直的

11、；4、閉回路中頂點(diǎn)的個(gè)數(shù)必為偶數(shù)閉回路中頂點(diǎn)的個(gè)數(shù)必為偶數(shù). .閉回路的幾何特征：閉回路的幾何特征：1、每一個(gè)頂點(diǎn)格子都是每一個(gè)頂點(diǎn)格子都是 90轉(zhuǎn)角點(diǎn)；轉(zhuǎn)角點(diǎn)；1 運(yùn)輸問(wèn)題及其數(shù)學(xué)模型閉回路的代數(shù)性質(zhì)：閉回路的代數(shù)性質(zhì)：1 11 22 22 31,s ssi ji ji ji ji ji jxxxxxx性質(zhì)性質(zhì) 1 構(gòu)成閉回路的變量組對(duì)應(yīng)的列向量組構(gòu)成閉回路的變量組對(duì)應(yīng)的列向量組1 11 22 22 31,s ssi ji ji ji ji ji jpppppp必線性相關(guān)必線性相關(guān).證明證明性質(zhì)性質(zhì) 2 分組分組構(gòu)成閉回路，則該變量組對(duì)應(yīng)的列向量組構(gòu)成閉回路，則該變量組對(duì)應(yīng)的列向量組1 12

12、 2,r ri ji ji jppp是線性相關(guān)的是線性相關(guān)的.推論推論 1 若變量組對(duì)應(yīng)的列向量組線性無(wú)關(guān)，則該變?nèi)糇兞拷M對(duì)應(yīng)的列向量組線性無(wú)關(guān)，則該變量組一定不包含閉回路量組一定不包含閉回路.若變量組若變量組 中有一個(gè)部中有一個(gè)部1 12 2*,( )r ri ji ji jxxxGo on性質(zhì)性質(zhì) 1 的證明的證明Proof :由直接計(jì)算可知由直接計(jì)算可知1 11 22 22 310s ssi ji ji ji ji ji jpppppp111111111111111111A111212122212nnmmmnxxxxxxxxx故該向量組線性相關(guān)故該向量組線性相關(guān).第四章第四章 運(yùn)輸問(wèn)題運(yùn)

13、輸問(wèn)題在變量組在變量組 中，若有某中，若有某1 12 2*,( )r ri ji ji jxxx一個(gè)變量一個(gè)變量 xij 是它所在的行（第是它所在的行（第 i 行）或列（第行）或列（第 j 列）列）中出現(xiàn)于中出現(xiàn)于（*）中的唯一變量，則稱(chēng)該變量中的唯一變量，則稱(chēng)該變量 xij 是該變量是該變量組的一個(gè)孤立點(diǎn)組的一個(gè)孤立點(diǎn).定義定義 21114444535322221,xxxxxxxx閉回路的特征閉回路的特征性質(zhì)性質(zhì) 3 沒(méi)有孤立點(diǎn)沒(méi)有孤立點(diǎn) 若一變量組中不包含任何閉回路，則該變量組若一變量組中不包含任何閉回路，則該變量組必有孤立點(diǎn)必有孤立點(diǎn).反證反證孤立點(diǎn)不會(huì)是孤立點(diǎn)不會(huì)是閉回路上的點(diǎn)閉回路上

14、的點(diǎn)定理定理 5 變量組變量組 對(duì)應(yīng)的列向量組線性無(wú)關(guān)的充要對(duì)應(yīng)的列向量組線性無(wú)關(guān)的充要*( )條件是該變量組中不包含任何閉回路條件是該變量組中不包含任何閉回路. .證明證明定理定理 5 的證明的證明Proof :用反證法用反證法設(shè)變量組設(shè)變量組（*）對(duì)應(yīng)的列向量）對(duì)應(yīng)的列向量組線性無(wú)關(guān)，但該變量組包含一個(gè)以其中某些變量為頂組線性無(wú)關(guān)，但該變量組包含一個(gè)以其中某些變量為頂點(diǎn)的閉回路，點(diǎn)的閉回路，則由性質(zhì)則由性質(zhì) 2 知，這些變量對(duì)應(yīng)的列向量必知，這些變量對(duì)應(yīng)的列向量必線性相關(guān)，與假設(shè)矛盾線性相關(guān)，與假設(shè)矛盾. .定理定理 5 變量組變量組 對(duì)應(yīng)的列向量組線性無(wú)關(guān)的充要對(duì)應(yīng)的列向量組線性無(wú)關(guān)的充

15、要*( )條件是該變量組中不包含任何閉回路條件是該變量組中不包含任何閉回路. .設(shè)有一組數(shù)設(shè)有一組數(shù) 使得使得12,rkkk1 122120(1)rri ji jri jk pk pk p 由于變量組由于變量組（* *）中不包含任何閉回路，由性質(zhì)中不包含任何閉回路，由性質(zhì) 3 可知其中必有孤立點(diǎn)，可知其中必有孤立點(diǎn)， 不妨設(shè)不妨設(shè) 為孤立點(diǎn)，為孤立點(diǎn)，1 1i jx又不妨設(shè)又不妨設(shè) 是（是（* *）在第）在第i1 1行上唯一的變量，這時(shí)由行上唯一的變量，這時(shí)由p pijij的特征，（的特征，（1 1）的左端第）的左端第i1個(gè)分量和為個(gè)分量和為k1，而右端為，而右端為0，1 1i jx在第在第

16、j1列上的唯列上的唯一變量如何？一變量如何？2 21200r ri jri jkk pk p，從而（1）變成（2）但但 仍不包含閉回路，其中還有孤立點(diǎn)仍不包含閉回路，其中還有孤立點(diǎn), ,2 23 3,r ri ji ji jxxx與前面類(lèi)似分析可證與前面類(lèi)似分析可證 k2= 0. 同理得同理得 k3 = k4 = kr = 0這就證明了向量組這就證明了向量組（* *）線性無(wú)關(guān)線性無(wú)關(guān).1 運(yùn)輸問(wèn)題及其數(shù)學(xué)模型推論推論 2 平衡運(yùn)輸問(wèn)題中的一組平衡運(yùn)輸問(wèn)題中的一組 m + n - 1 個(gè)變量個(gè)變量能構(gòu)成基變量的充要條件是它不包含任何閉回路能構(gòu)成基變量的充要條件是它不包含任何閉回路.1 122,(

17、1)ssi ji ji jxxxsmn 該推論給出了運(yùn)輸問(wèn)題的基可行解中基變量的一該推論給出了運(yùn)輸問(wèn)題的基可行解中基變量的一個(gè)基本特征：基變量組不含閉回路個(gè)基本特征：基變量組不含閉回路. . 這就是基可行解這就是基可行解在表上的一個(gè)表現(xiàn)，利用它來(lái)判斷在表上的一個(gè)表現(xiàn)，利用它來(lái)判斷 m + n 1 個(gè)變量個(gè)變量是否構(gòu)成基變量組，就看它是否包含閉回路是否構(gòu)成基變量組，就看它是否包含閉回路. . 這種方法簡(jiǎn)便易行，它比直接判斷這些變量對(duì)應(yīng)這種方法簡(jiǎn)便易行，它比直接判斷這些變量對(duì)應(yīng)的列向量是否線性無(wú)關(guān)要簡(jiǎn)便得多的列向量是否線性無(wú)關(guān)要簡(jiǎn)便得多. . 利用基變量的這個(gè)特征，將可以導(dǎo)出求平衡運(yùn)輸利用基變量的

18、這個(gè)特征，將可以導(dǎo)出求平衡運(yùn)輸問(wèn)題的初始基可行解的一些簡(jiǎn)便方法問(wèn)題的初始基可行解的一些簡(jiǎn)便方法. .2 運(yùn)輸問(wèn)題的表上作業(yè)法2 2 運(yùn)輸問(wèn)題的表上作業(yè)法運(yùn)輸問(wèn)題的表上作業(yè)法 表上作業(yè)法（又稱(chēng)運(yùn)輸單純形法）是根據(jù)單純形表上作業(yè)法（又稱(chēng)運(yùn)輸單純形法）是根據(jù)單純形法的原理和運(yùn)輸問(wèn)題的特點(diǎn)，設(shè)計(jì)的一種在表上運(yùn)算法的原理和運(yùn)輸問(wèn)題的特點(diǎn)，設(shè)計(jì)的一種在表上運(yùn)算的求解運(yùn)輸問(wèn)題的簡(jiǎn)便而有效的方法的求解運(yùn)輸問(wèn)題的簡(jiǎn)便而有效的方法.主要步驟：主要步驟：1、求一個(gè)初始調(diào)運(yùn)方案（初始基可行解）；求一個(gè)初始調(diào)運(yùn)方案（初始基可行解）；2、判別當(dāng)前方案是否為最優(yōu)，若是則迭代停止，否則判別當(dāng)前方案是否為最優(yōu)，若是則迭代停止，

19、否則 轉(zhuǎn)下一步；轉(zhuǎn)下一步；3、改進(jìn)當(dāng)前方案，得到新的方案（新的基可行解），改進(jìn)當(dāng)前方案，得到新的方案（新的基可行解）， 再返回再返回 2 。第四章第四章 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題一、一、初始方案的確定初始方案的確定1、西北角法西北角法 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 15Ex. 1 50 已知某商品有三個(gè)產(chǎn)地已知某商品有三個(gè)產(chǎn)地A1、A2、A3和四個(gè)銷(xiāo)地和四個(gè)銷(xiāo)地B1、B2、B3、B4 ，產(chǎn)量、銷(xiāo)量及單位運(yùn)價(jià)如表，產(chǎn)量、銷(xiāo)量及單位運(yùn)價(jià)如表. .問(wèn)應(yīng)問(wèn)應(yīng)如何調(diào)運(yùn)，在滿(mǎn)足各銷(xiāo)地需要的情況下，

20、使總的運(yùn)費(fèi)如何調(diào)運(yùn)，在滿(mǎn)足各銷(xiāo)地需要的情況下，使總的運(yùn)費(fèi)支出為最少？支出為最少？ 解：解：51010205規(guī)則規(guī)則: :從運(yùn)輸表的西從運(yùn)輸表的西北角開(kāi)始北角開(kāi)始, ,優(yōu)先安排優(yōu)先安排編號(hào)小的產(chǎn)地和銷(xiāo)地編號(hào)小的產(chǎn)地和銷(xiāo)地的運(yùn)輸任務(wù)的運(yùn)輸任務(wù). .填了幾個(gè)數(shù)字？填了幾個(gè)數(shù)字？10505203 51 10254 10675z Note : 在填入一個(gè)數(shù)時(shí)，如果行和列同時(shí)飽和，在填入一個(gè)數(shù)時(shí)，如果行和列同時(shí)飽和， 規(guī)定只劃去一行或一列規(guī)定只劃去一行或一列 BjAi B1 B2 B3 B4 ai A110 5 2 3 50 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10

21、155002 運(yùn)輸問(wèn)題的表上作業(yè)法2、最小元素法最小元素法 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 15規(guī)則規(guī)則: :優(yōu)先安排單位運(yùn)價(jià)最小的產(chǎn)地與銷(xiāo)地之間的運(yùn)輸優(yōu)先安排單位運(yùn)價(jià)最小的產(chǎn)地與銷(xiāo)地之間的運(yùn)輸 任務(wù)任務(wù). .4010255101010405253 51 102 105 10620z Note : 在某行（或列）填入最后一個(gè)數(shù)時(shí)，如果行和在某行（或列）填入最后一個(gè)數(shù)時(shí)，如果行和列同時(shí)飽和，規(guī)定只劃去該行（或列）列同時(shí)飽和，規(guī)定只劃去該行（或列） BjAi B1 B2 B3 B4

22、ai A1 1 5 3 2 60 A2 4 1 2 3 20 A3 5 6 1 4 10 bj 50 20 10 100010102050填了幾個(gè)數(shù)字？填了幾個(gè)數(shù)字？第四章第四章 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題定理定理 6 用西北角法或最小元素法得到的初始解是用西北角法或最小元素法得到的初始解是平衡平衡運(yùn)輸問(wèn)題的基可行解，運(yùn)輸問(wèn)題的基可行解， m+n-1 個(gè)個(gè)填入數(shù)字的格子對(duì)應(yīng)的填入數(shù)字的格子對(duì)應(yīng)的是基變量是基變量.Proof : ijx首先，得到的初始解首先，得到的初始解 為可行解是顯然的為可行解是顯然的. . 其次，由于行列數(shù)共有其次，由于行列數(shù)共有 m+n ，而按填數(shù)字的方法，而按填數(shù)字的方法, ,除

23、填最后一個(gè)數(shù)時(shí)，劃去一行一列外，每填一個(gè)數(shù)劃去除填最后一個(gè)數(shù)時(shí)，劃去一行一列外，每填一個(gè)數(shù)劃去一行或一列一行或一列. 因此因此, , 共填共填 m+n-1 個(gè)數(shù)個(gè)數(shù). . 最后，證明所填最后，證明所填 m+n-1 個(gè)數(shù)對(duì)應(yīng)的變量組不含閉回路個(gè)數(shù)對(duì)應(yīng)的變量組不含閉回路.用反證法用反證法若含有閉回路若含有閉回路 不妨設(shè)此閉回路如右不妨設(shè)此閉回路如右（其他情形同理可證）（其他情形同理可證）1 1i jx4 4i jx3 3i jx2 2i jx 不妨設(shè)填不妨設(shè)填 后劃去行，故后劃去行，故 必須較必須較 先填，先填，且填后劃去的是列，從而且填后劃去的是列，從而 必須較必須較 先填，且填后劃先填，且填后

24、劃去的是行，而這又說(shuō)明去的是行，而這又說(shuō)明 必須較必須較 先填，且填后劃先填，且填后劃去的是列，這又得到去的是列，這又得到 必須較必須較 先填，且填后劃去的先填，且填后劃去的是行，這樣就得到了矛盾，所以，填數(shù)的是行，這樣就得到了矛盾，所以，填數(shù)的 m+nm+n-1 -1 個(gè)格個(gè)格子對(duì)應(yīng)的變量組不含閉回路，從而，證得了本定理子對(duì)應(yīng)的變量組不含閉回路，從而，證得了本定理. . 1 1i jx4 4i jx2 2i jx3 3i jx1 1i jx2 2i jx4 4i jx3 3i jx1 1i jx2 運(yùn)輸問(wèn)題的表上作業(yè)法關(guān)鍵關(guān)鍵1、填一個(gè)數(shù)字劃去一行或一列填一個(gè)數(shù)字劃去一行或一列 不產(chǎn)生閉回路

25、；不產(chǎn)生閉回路； 2、填一個(gè)數(shù)字填一個(gè)數(shù)字只只劃去一行或一列劃去一行或一列 填滿(mǎn)填滿(mǎn)m+n-1-1個(gè)數(shù)個(gè)數(shù). . BjAi B1 B2 ai A1 8 2 5 A2 3 1 4 bj 6 3 差額差額 6 2 差額差額 5 1315 BjAi B1 B2 ai A1 8 2 5 A2 3 1 4 bj 6 3 8 53 1 1 346z 按最小元素法按最小元素法3423、Vogel 法法 ( (元素差額法元素差額法) )規(guī)則：計(jì)算各行各列的最小元素與次小元素的差額，規(guī)則：計(jì)算各行各列的最小元素與次小元素的差額，優(yōu)先安排差額最大的所優(yōu)先安排差額最大的所在行或列的單位運(yùn)價(jià)最在行或列的單位運(yùn)價(jià)最小的

26、產(chǎn)地與銷(xiāo)地之間的小的產(chǎn)地與銷(xiāo)地之間的運(yùn)輸任務(wù)運(yùn)輸任務(wù)8 23 42 334Vz 這是最優(yōu)解這是最優(yōu)解.110 405 52 103 153 205 10600VExz 第四章第四章 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題二、二、最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn) BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 1540102551010定理定理 7 設(shè)設(shè) 是平衡運(yùn)輸問(wèn)題的是平衡運(yùn)輸問(wèn)題的一組基變量，一組基變量， 是非基變量，則在變量組是非基變量，則在變量組 中存在唯一的閉回路中存在唯一的閉回路.1 12 2,(1)s si ji

27、ji jxxxsmn1 12 20,s si ji ji jx xxx0 x1、閉回路法閉回路法+1-1+1-121423 105 檢驗(yàn)數(shù)檢驗(yàn)數(shù) BjAi B1 B2 B3 B4 A1 A2 A3檢驗(yàn)數(shù)表檢驗(yàn)數(shù)表-5-10 6 6 6ijijijcc奇頂點(diǎn)偶頂點(diǎn)2 運(yùn)輸問(wèn)題的表上作業(yè)法2、位勢(shì)法（對(duì)偶變量法）位勢(shì)法（對(duì)偶變量法）求檢驗(yàn)數(shù)的求檢驗(yàn)數(shù)的方法方法11minmnijijijzc x1. .nijijstxa1,2,im1mijjixb1,2,jn01,2,1,2,ijximjn11minmnijijijzc x1nijijxa2,3,im1mijjixb1,2,jn01,2,1,2,i

28、jximjn111211nxxxa. .st0 x00a x約束方程的系數(shù)矩陣的秩為約束方程的系數(shù)矩陣的秩為m+n -1x0必為基變必為基變量量, x0= 0約束方程的系數(shù)矩陣的秩為約束方程的系數(shù)矩陣的秩為m+n對(duì)任意的對(duì)任意的 a0， 與原問(wèn)題等價(jià)與原問(wèn)題等價(jià)1212,mnyu uuv vv11maxmniijjijaub v10. .1,2,1,2,ijijijstuvcimuajnu v無(wú)符號(hào)限制由于由于01010ijipmj ijijijcyp1212,ijmnijcu uuv vvpijijcuv001au010000pxj 的檢驗(yàn)數(shù)的檢驗(yàn)數(shù) 1jjBjjjcc Bpcyp1 12

29、2,(1)s si ji ji jxxxsmn設(shè)：為基變量，由于基變量設(shè)：為基變量，由于基變量的檢驗(yàn)數(shù)等于零的檢驗(yàn)數(shù)等于零111 1222 210sss siji jiji jiji juvcuvcuvcua一定有解，不唯一一定有解，不唯一（a0 0可任?。┛扇稳。﹗i 稱(chēng)為行位勢(shì)稱(chēng)為行位勢(shì)，vj 稱(chēng)為列位勢(shì)稱(chēng)為列位勢(shì)第四章第四章 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題ijijcuv BjAi B1 B2 B3 B4 ui A1 4010 25 5 2 5 3 A2 4 3 10 1 10 2 A3 10 5 6 3 4 vj BjAi B1 B2 B3 B4 A1 A2 A3檢驗(yàn)數(shù)表檢驗(yàn)數(shù)表-5-10 6 6 6

30、-2-120273見(jiàn)見(jiàn) Ex. 1 最小元素法得到的初始基可行解最小元素法得到的初始基可行解2121241411cccc21241411cuvuvuv2121cuv4275 3333333( 2)( 1)6cuv 10053-12-5323232cuv6( 5)56 若若 ，則此時(shí)的運(yùn)輸方案為最優(yōu)的，則此時(shí)的運(yùn)輸方案為最優(yōu)的0ijijijijcuv2 運(yùn)輸問(wèn)題的表上作業(yè)法三、三、基可行解的改進(jìn)基可行解的改進(jìn) BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 1540102551010 BjAi B

31、1 B2 B3 B4 A1 A2 A3檢驗(yàn)數(shù)表檢驗(yàn)數(shù)表-5-10 6 6 6選擇進(jìn)基變量選擇進(jìn)基變量min0,1,1stijijimjn 則取非基變量則取非基變量 xst 為進(jìn)基變量為進(jìn)基變量確定出基變量確定出基變量調(diào)整量調(diào)整量 minijklxx閉回路上偶頂點(diǎn)則基變量則基變量 xkl 出基（運(yùn)量擦去）出基（運(yùn)量擦去）調(diào)整方法：在該閉回路上，奇點(diǎn)運(yùn)量加調(diào)整方法：在該閉回路上，奇點(diǎn)運(yùn)量加 ，偶點(diǎn)減去，偶點(diǎn)減去 能轉(zhuǎn)運(yùn)多少？能轉(zhuǎn)運(yùn)多少？153010 6 5 4 2010 1-5 6 520 6 6 4 5 6 因?yàn)橐驗(yàn)?，所以此運(yùn)輸方案為最優(yōu)，所以此運(yùn)輸方案為最優(yōu)方案方案0ijNote : 若在閉

32、回路上有幾個(gè)偶點(diǎn)處的運(yùn)量等于若在閉回路上有幾個(gè)偶點(diǎn)處的運(yùn)量等于 ，則，則可任取其中一個(gè)作為出基變量（運(yùn)量擦去），其余幾可任取其中一個(gè)作為出基變量（運(yùn)量擦去），其余幾個(gè)點(diǎn)的值調(diào)整后變?yōu)閭€(gè)點(diǎn)的值調(diào)整后變?yōu)?. (0. (但應(yīng)填入，說(shuō)明這些變量還但應(yīng)填入，說(shuō)明這些變量還在基內(nèi)，這時(shí)就出現(xiàn)了退化在基內(nèi)，這時(shí)就出現(xiàn)了退化) )620-50-50=520問(wèn)：?jiǎn)枺簭膹腁2到到B4的單位運(yùn)價(jià)的單位運(yùn)價(jià)c24在什么范圍變化時(shí)，所得在什么范圍變化時(shí)，所得最優(yōu)調(diào)運(yùn)方案不變最優(yōu)調(diào)運(yùn)方案不變. . c12在什么范圍變化呢？在什么范圍變化呢？第四章第四章 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題補(bǔ)充：運(yùn)輸問(wèn)題的圖上作業(yè)法補(bǔ)充：運(yùn)輸問(wèn)題的圖上作業(yè)

33、法 圖上作業(yè)法是在交通圖上進(jìn)行物資調(diào)運(yùn)方案編制和圖上作業(yè)法是在交通圖上進(jìn)行物資調(diào)運(yùn)方案編制和調(diào)整的一種科學(xué)方法。在鐵路特別是公路運(yùn)輸中使用很調(diào)整的一種科學(xué)方法。在鐵路特別是公路運(yùn)輸中使用很多且有很好的效果。多且有很好的效果。 在交通圖中，用在交通圖中，用表示表示產(chǎn)地（發(fā)點(diǎn)），并將產(chǎn)量記產(chǎn)地（發(fā)點(diǎn)），并將產(chǎn)量記在圓圈內(nèi)；用在圓圈內(nèi)；用表示銷(xiāo)地表示銷(xiāo)地（收點(diǎn)），并將銷(xiāo)量記在方（收點(diǎn)），并將銷(xiāo)量記在方框內(nèi)?？騼?nèi)。206040402463目標(biāo)：噸公里數(shù)目標(biāo)：噸公里數(shù)( (費(fèi)用費(fèi)用) )最小的調(diào)運(yùn)方案最小的調(diào)運(yùn)方案 . . 物資調(diào)運(yùn)的流向用與交通線平行的箭線表示，規(guī)定物資調(diào)運(yùn)的流向用與交通線平行的箭線表

34、示，規(guī)定畫(huà)在前進(jìn)方向的右邊，調(diào)運(yùn)量加括號(hào)記在箭線的右邊。畫(huà)在前進(jìn)方向的右邊，調(diào)運(yùn)量加括號(hào)記在箭線的右邊。(20)(20)(40)補(bǔ)充：運(yùn)輸問(wèn)題的圖上作業(yè)法20303020243對(duì)流：物資在同一線路上往返運(yùn)輸對(duì)流：物資在同一線路上往返運(yùn)輸.(20)(20)(30)(30)(10)這是對(duì)流這是對(duì)流20303020243(20)(20)(30)(30)106030(10)(20)1、無(wú)圈無(wú)圈的交通的交通圖圖2020502010 對(duì)于無(wú)圈圖，每條對(duì)于無(wú)圈圖，每條邊都是割邊，去掉它網(wǎng)邊都是割邊，去掉它網(wǎng)絡(luò)將不連通，所以，每絡(luò)將不連通，所以，每條邊上的運(yùn)量是不得不條邊上的運(yùn)量是不得不只要每條邊上不產(chǎn)生對(duì)流

35、，即為最優(yōu)方案只要每條邊上不產(chǎn)生對(duì)流，即為最優(yōu)方案第四章第四章 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題206040402463(20)(20)(40)2、有一個(gè)圈的交通圖有一個(gè)圈的交通圖圈長(zhǎng)：圈上每一條邊的長(zhǎng)度之和（記為圈長(zhǎng)：圈上每一條邊的長(zhǎng)度之和（記為 l）l =15 先用先用“丟邊破圈丟邊破圈”方法，得到無(wú)圈圖，再產(chǎn)生一方法，得到無(wú)圈圖，再產(chǎn)生一個(gè)個(gè)沒(méi)有對(duì)流的方案。沒(méi)有對(duì)流的方案。內(nèi)圈長(zhǎng)內(nèi)圈長(zhǎng) l內(nèi)內(nèi)：流向在圈內(nèi)的邊的長(zhǎng)度之和：流向在圈內(nèi)的邊的長(zhǎng)度之和l內(nèi)內(nèi)= 8外圈長(zhǎng)外圈長(zhǎng) l外外：流向在圈外的邊：流向在圈外的邊的長(zhǎng)度之和的長(zhǎng)度之和l外外= 4是最優(yōu)解嗎？是最優(yōu)解嗎？8,2ll 內(nèi)不是最優(yōu)的.稱(chēng)為迂回稱(chēng)為迂回

36、調(diào)整方案：調(diào)整方案：對(duì)內(nèi)圈各流量中最小調(diào)運(yùn)量，進(jìn)行反向調(diào)運(yùn)對(duì)內(nèi)圈各流量中最小調(diào)運(yùn)量，進(jìn)行反向調(diào)運(yùn)(40)(20)(20)結(jié)論：結(jié)論：內(nèi)外圈長(zhǎng)都小于圈長(zhǎng)的一半的無(wú)對(duì)流的調(diào)運(yùn)方案內(nèi)外圈長(zhǎng)都小于圈長(zhǎng)的一半的無(wú)對(duì)流的調(diào)運(yùn)方案 為最優(yōu)方案為最優(yōu)方案67.22llll外內(nèi)此時(shí)為最優(yōu)調(diào)運(yùn)方案補(bǔ)充：運(yùn)輸問(wèn)題的圖上作業(yè)法3、有多個(gè)、有多個(gè)圈圈的交通的交通圖圖106030202050203020有幾個(gè)圈？ 如有一個(gè)圈的情形，對(duì)每一個(gè)圈先用如有一個(gè)圈的情形，對(duì)每一個(gè)圈先用“丟邊破圈丟邊破圈”方方法，得到無(wú)圈圖，再產(chǎn)生一個(gè)沒(méi)有對(duì)流的方案。再進(jìn)行法，得到無(wú)圈圖，再產(chǎn)生一個(gè)沒(méi)有對(duì)流的方案。再進(jìn)行檢查、調(diào)整。檢查、調(diào)整。只

37、需檢查13個(gè)圈嗎？會(huì)循環(huán)嗎？ 一般不夠！因?yàn)閷?duì)一個(gè)圈進(jìn)行調(diào)整后，會(huì)對(duì)已檢一般不夠！因?yàn)閷?duì)一個(gè)圈進(jìn)行調(diào)整后，會(huì)對(duì)已檢查的圈有影響查的圈有影響. 不會(huì)！因?yàn)槊看文繕?biāo)不會(huì)！因?yàn)槊看文繕?biāo)函數(shù)下降值大于一個(gè)固定函數(shù)下降值大于一個(gè)固定值（如值（如 1）第四章第四章 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題四、四、產(chǎn)銷(xiāo)不平衡運(yùn)輸問(wèn)題產(chǎn)銷(xiāo)不平衡運(yùn)輸問(wèn)題當(dāng)當(dāng)11mnijijab111minmnijijijzc x1. .nijijstxa1,2,1im m11mijjixb1,2,jn01,2,1;1,2,ijxim mjnNote : 通常建立運(yùn)輸模通常建立運(yùn)輸模型指的是平衡運(yùn)輸模型型指的是平衡運(yùn)輸模型可以虛設(shè)一個(gè)產(chǎn)地可以虛設(shè)一個(gè)產(chǎn)

38、地 Am+1, 其產(chǎn)量為其產(chǎn)量為111nmmjijiaba 并假設(shè)產(chǎn)地并假設(shè)產(chǎn)地 Am+1 運(yùn)往各銷(xiāo)地的單運(yùn)往各銷(xiāo)地的單位運(yùn)價(jià)為位運(yùn)價(jià)為 cm+1, j = 0 ( j = 1 , 2 , , n ) . 則原問(wèn)題可轉(zhuǎn)則原問(wèn)題可轉(zhuǎn)化為平衡運(yùn)輸問(wèn)題：化為平衡運(yùn)輸問(wèn)題： 產(chǎn)大于銷(xiāo)，可通產(chǎn)大于銷(xiāo)，可通過(guò)虛設(shè)銷(xiāo)地，類(lèi)似過(guò)虛設(shè)銷(xiāo)地，類(lèi)似建立平衡運(yùn)輸模型建立平衡運(yùn)輸模型2 運(yùn)輸問(wèn)題的表上作業(yè)法Ex. 2已知運(yùn)輸問(wèn)題由表給出，試建立運(yùn)輸模型已知運(yùn)輸問(wèn)題由表給出，試建立運(yùn)輸模型 . Bj Ai B1 B2 B3 ai A14 25 10 A2638 15 bj 8 7 14解解: Bj Ai B1 B2 B3

39、 ai A14 25 10 A2638 15 A3000 4 bj 8 7 14本題產(chǎn)量為本題產(chǎn)量為25，銷(xiāo)量為，銷(xiāo)量為29，是銷(xiāo)大于產(chǎn)問(wèn)題，是銷(xiāo)大于產(chǎn)問(wèn)題 虛設(shè)一個(gè)產(chǎn)地虛設(shè)一個(gè)產(chǎn)地 A3，由于并沒(méi)有生產(chǎn)，所以運(yùn)價(jià)為，由于并沒(méi)有生產(chǎn)，所以運(yùn)價(jià)為零，得運(yùn)輸模型零，得運(yùn)輸模型. . 如果各銷(xiāo)地不滿(mǎn)足時(shí)，單位缺貨費(fèi)為如果各銷(xiāo)地不滿(mǎn)足時(shí)，單位缺貨費(fèi)為 4，3，7，則，則運(yùn)輸模型為運(yùn)輸模型為437第四章第四章 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 BjAi B1 B2 B3 ai A14 23 10 A2564 15 A3345 20 最低最低需求量需求量 10 10 10Ex. 3 已知運(yùn)輸問(wèn)題由表給出，如果產(chǎn)地已知運(yùn)輸

40、問(wèn)題由表給出，如果產(chǎn)地 Ai 的產(chǎn)量的產(chǎn)量必須運(yùn)走必須運(yùn)走，試建立運(yùn)輸模型試建立運(yùn)輸模型 . BjAi B1 B2 B3 B4 ai A14 23 10 A2564 15 A3345 20 bj 10 10 10 15解解:這是一個(gè)產(chǎn)大于銷(xiāo)的運(yùn)輸問(wèn)題這是一個(gè)產(chǎn)大于銷(xiāo)的運(yùn)輸問(wèn)題. .234虛設(shè)一銷(xiāo)地虛設(shè)一銷(xiāo)地 B4 ,銷(xiāo)量銷(xiāo)量 b4 = 15 . BjAi B1 B2 B3 ai A14 23 10 A2564 15 A3345 20 最低最低需求量需求量 10 10 10 最高最高需求量需求量 20 10不限不限 BjAi B1 B2 B3 ai A14 23 10 A2564 15 A334

41、5 20 bj 10 10 10 443B3B15351015A4M100MM0 三個(gè)銷(xiāo)地的最低需求為三個(gè)銷(xiāo)地的最低需求為 30，最高需求不限最高需求不限. . 根據(jù)根據(jù)現(xiàn)有產(chǎn)量，現(xiàn)有產(chǎn)量，B3 至多能得到至多能得到 25. 建立運(yùn)輸模型建立運(yùn)輸模型 .2說(shuō)明什么？說(shuō)明什么？第四章第四章 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題3 運(yùn)輸問(wèn)題應(yīng)用舉例運(yùn)輸問(wèn)題應(yīng)用舉例Ex. 4 (生產(chǎn)調(diào)度問(wèn)題生產(chǎn)調(diào)度問(wèn)題) 某制冰廠每年某制冰廠每年1 4 季度必須供季度必須供應(yīng)冰塊應(yīng)冰塊 15、20、25、10（千噸）（千噸）. .已知該廠各季度冰已知該廠各季度冰 塊的生產(chǎn)能力及冰塊的單位成本如表塊的生產(chǎn)能力及冰塊的單位成本如表. .

42、如果生產(chǎn)出來(lái)如果生產(chǎn)出來(lái)的冰塊不在當(dāng)季度使用，每千噸冰塊存儲(chǔ)一個(gè)季度的冰塊不在當(dāng)季度使用，每千噸冰塊存儲(chǔ)一個(gè)季度費(fèi)用為費(fèi)用為4（千元）（千元）. .又設(shè)該制冰廠每年第又設(shè)該制冰廠每年第3季度末對(duì)貯季度末對(duì)貯冰庫(kù)進(jìn)行清庫(kù)維修冰庫(kù)進(jìn)行清庫(kù)維修. .問(wèn)應(yīng)如何安排冰塊的生產(chǎn)，可使問(wèn)應(yīng)如何安排冰塊的生產(chǎn)，可使該廠全年生產(chǎn)、該廠全年生產(chǎn)、存儲(chǔ)費(fèi)用最少？存儲(chǔ)費(fèi)用最少？季季 度度 生產(chǎn)能力（千噸）生產(chǎn)能力（千噸） 單位成本（千元）單位成本（千元） 1 25 5 2 18 7 3 16 8 4 15 53 運(yùn)輸問(wèn)題應(yīng)用舉例季季 度度 生產(chǎn)能力（千噸）生產(chǎn)能力（千噸） 單位成本（千元）單位成本（千元） 1 25

43、5 2 18 7 3 16 8 4 15 5 Bj Ai B1 B2 B3 B4 ai A1 25 A2 18 A3 16 A4 15 bj 15 20 25 10 解：解：5B54913M0MMMMM0005118179137第四章第四章 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題Ex. 5 ( (運(yùn)量有界的運(yùn)輸問(wèn)題運(yùn)量有界的運(yùn)輸問(wèn)題) ) 6 5 7 bj 10762 A2 84 53 A1 ai B3 B2 B1 BjAi表表 1 1 5 2 4 A2 3 3 4 A1 B3 B2 B1 dij表表 2 2 表表1 給出一個(gè)運(yùn)輸問(wèn)題給出一個(gè)運(yùn)輸問(wèn)題. .現(xiàn)在規(guī)定產(chǎn)地現(xiàn)在規(guī)定產(chǎn)地 Ai 至銷(xiāo)地至銷(xiāo)地 Bj 的運(yùn)量不

44、能超過(guò)的運(yùn)量不能超過(guò) dij , , 由表由表 2 2 給定給定. . 試建立運(yùn)輸問(wèn)題試建立運(yùn)輸問(wèn)題 . .解解： 虛設(shè)虛設(shè) Dij (i=1,2; j=1,2,3) 6 6個(gè)點(diǎn)，個(gè)點(diǎn)，Dij 既作產(chǎn)地，既作產(chǎn)地，又作銷(xiāo)地，其產(chǎn)量、銷(xiāo)量都為又作銷(xiāo)地，其產(chǎn)量、銷(xiāo)量都為 dij . . 產(chǎn)地產(chǎn)地 Ai 的物資只可的物資只可運(yùn)送給運(yùn)送給 Dij , 而而 Dij 的物資只可運(yùn)送給的物資只可運(yùn)送給 Bj ,或送給自身或送給自身.3 運(yùn)輸問(wèn)題應(yīng)用舉例 BjAi D11 D12 D13 D21 D22 D23 B1 B2 B3 ai A1 D11 D12 D13 A2 D21 D22 D23 bj 6 5

45、 7 bj 10762 A2 84 53 A1 ai B3 B2 B1 BjAi表表 1 1 5 2 4 A2 3 3 4 A1 B3 B2 B1 dij表表 2 2 8 104330000305040000206074334254257563321303124244214第四章第四章 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題Ex. 6 ( (空車(chē)調(diào)度問(wèn)題空車(chē)調(diào)度問(wèn)題) ) 某航運(yùn)公司承擔(dān)六個(gè)港口城市某航運(yùn)公司承擔(dān)六個(gè)港口城市 A、B、C、D、E、F 的四條固定航線的物資運(yùn)輸任的四條固定航線的物資運(yùn)輸任務(wù)務(wù). . 已知各條航線的起點(diǎn)、終點(diǎn)城市及每天航班數(shù)見(jiàn)已知各條航線的起點(diǎn)、終點(diǎn)城市及每天航班數(shù)見(jiàn)表表1，假定各條航線使用相同型號(hào)的船只，又各城市間，假定各條航線使用相同型號(hào)的船只，又各城市間的航程天數(shù)見(jiàn)表的航程天數(shù)見(jiàn)表2. 又知每條船只每次裝卸貨的時(shí)間各又知每條船只每次裝卸貨的時(shí)間各需一天，則該航運(yùn)公司至少應(yīng)配備多少條船，才能滿(mǎn)足需一天，則該航運(yùn)公司至少應(yīng)配備多少條船，才能滿(mǎn)足所有航線的運(yùn)貨需求？所有航線的運(yùn)貨需求？航航線線起點(diǎn)起點(diǎn)城市城市終點(diǎn)終點(diǎn)城市城市每天航班每天航班數(shù)數(shù)1ED32BC23AF14DB1表表1 1 到到從從ABCDEFA0121477B1031388C23015557851703F7852030表