運籌學ch3運輸問題ppt課件

1、人們在從事生產(chǎn)活動中，不可避免地要進行物資調(diào)運工作。如人們在從事生產(chǎn)活動中，不可避免地要進行物資調(diào)運工作。如某時期內(nèi)將生產(chǎn)基地的煤、鋼鐵、糧食等各類物資，分別運到某時期內(nèi)將生產(chǎn)基地的煤、鋼鐵、糧食等各類物資，分別運到需要這些物資的地區(qū)，根據(jù)各地的生產(chǎn)量和需要量及各地之間需要這些物資的地區(qū)，根據(jù)各地的生產(chǎn)量和需要量及各地之間的運輸費用，如何制定一個運輸方案，使總的運輸費用最小。的運輸費用，如何制定一個運輸方案，使總的運輸費用最小。這樣的問題稱為運輸問題。這樣的問題稱為運輸問題。n供給及需求單位：供給及需求單位：1卡車的量卡車的量n單位運輸成本：千元單位運輸成本：千元運價表運價表2321341s2

2、=27s3=19d1=22d2=13d3=12d4=13s1=14供應(yīng)量供應(yīng)地運價需求量需求地67538427591060 xxxxxxxxxxxx13xxx12xxx13xxx22xxx19xxxx27xxxx14xxxxs.t.x6x10 x9x5x7x2x4x8x3x5x7x6zmin343332312423222114131211342414332313322212312111343332312423222114131211343332312423222114131211供應(yīng)地約束需求地約束設(shè)設(shè)xij(i=1,2,3；j=1,2,3,4)為為i個工廠運往第個工廠運往第j個配送中心的運量

3、，個配送中心的運量，這樣得到下列運輸問題的數(shù)學模型：這樣得到下列運輸問題的數(shù)學模型：123467531x11x12x13x141484272x21x22x23x2427591063x31x32x33x341922131213知：知：m個產(chǎn)地記作個產(chǎn)地記作A1，A2，A3,Am），其產(chǎn)量分別為），其產(chǎn)量分別為a1,a2，am；n個銷地記作個銷地記作B1，B2，Bn），其需要量分別為），其需要量分別為b1,b2，bn；且產(chǎn)銷平衡，即；且產(chǎn)銷平衡，即 。從第從第i個產(chǎn)地到個產(chǎn)地到j(luò) 個銷地的單位運價為個銷地的單位運價為cij ，問：在滿足各地需要的前提下，求總運輸費用最小的調(diào)運方問：在滿足各地需要的

4、前提下，求總運輸費用最小的調(diào)運方案。案。 即即AiBj 的運量的運量xij 使使njjmiiba11njijijmixcz11minnjmiba11njmiba11求解的形式來這兩種情形都可以化為jiba產(chǎn)銷平衡問題模型1111 1,.1,.0 mnijijnijijmijjiijMin zaxxaimxbjnx 11112122111211112222 nnmmnmmmxxaxxaxxaxxxbxxx212 nnmnnbxxxb約束方程式中共mn個變量，m+n個約束。11 11 A= 111 1 1 1 1 1系數(shù)矩陣的特點:(1)約束條件的系數(shù)矩陣的元素只有兩個:0,1.(2)元素 xij

5、 對應(yīng)于每一個變量在前m個約束方程中(第i個方程中)出現(xiàn)一次,在后n個約束方程中(第m+j 個方程中)也出現(xiàn)一次.(3)產(chǎn)銷平衡問題為等式約束.(4)產(chǎn)銷平衡問題中各產(chǎn)地產(chǎn)量之和與各銷售地點的銷量之和相等.ijab3.m+n1個變量組構(gòu)成基變量的充要條件是它不個變量組構(gòu)成基變量的充要條件是它不包含任何閉回路。一條回路中的頂點數(shù)一定是偶數(shù)。包含任何閉回路。一條回路中的頂點數(shù)一定是偶數(shù)?！咀C】因為產(chǎn)銷平衡，即【證】因為產(chǎn)銷平衡，即 ，將前，將前m個約束方程兩邊相個約束方程兩邊相加得加得minjiiba11minjmiiijax111再將后再將后n個約束相加得個約束相加得njminjjijbx111

6、顯然前顯然前m個約束方程之和等于后個約束方程之和等于后n個約束方程之和，個約束方程之和，m+n個約束個約束方程是相關(guān)的，系數(shù)矩陣方程是相關(guān)的，系數(shù)矩陣【定理【定理1】設(shè)有】設(shè)有m個產(chǎn)地個產(chǎn)地n個銷地且產(chǎn)銷平衡的運輸問題，則基變個銷地且產(chǎn)銷平衡的運輸問題，則基變量數(shù)為量數(shù)為m+n-1。中任意中任意m+n階子式等于零，取第一行到階子式等于零，取第一行到m+n1行與行與對應(yīng)的列共對應(yīng)的列共m+n-1列組成的列組成的m+n1階子式階子式1, 1121121,nmnnnxxxxxx，m 行行n 行行111212122212111111111111111111nnmmmnxxxxxxxxxA0111111

7、111故故r(A)=m+n1所以運輸問題有所以運輸問題有m+n1個基變量。個基變量。為了在為了在mn個變量中找出個變量中找出m+n1個變量作為一組基變量，就是個變量作為一組基變量，就是要在要在A中找出中找出m+n-1個線性無關(guān)的列向量，通常引用閉回路的概個線性無關(guān)的列向量，通常引用閉回路的概念尋找這些基變量。念尋找這些基變量。運輸單純形法也稱為表上作業(yè)法，是直接在運價表上求最優(yōu)解運輸單純形法也稱為表上作業(yè)法，是直接在運價表上求最優(yōu)解的一種方法，它的步驟是：的一種方法，它的步驟是： 第一步：求初始基行可行解初始調(diào)運方案）。第一步：求初始基行可行解初始調(diào)運方案）。 常用的方法有常用的方法有最小元素

8、法、元素差額法最小元素法、元素差額法Vogel近似法）、左上角法。近似法）、左上角法。 第二步：求檢驗數(shù)并判斷是否得到最優(yōu)解。常用求檢驗的方法第二步：求檢驗數(shù)并判斷是否得到最優(yōu)解。常用求檢驗的方法有閉回路法和位勢法，當非基變量的檢驗數(shù)有閉回路法和位勢法，當非基變量的檢驗數(shù)ij全都非負時得到最全都非負時得到最優(yōu)解，若存在檢驗數(shù)優(yōu)解，若存在檢驗數(shù)lk0，說明還沒有達到最優(yōu)，轉(zhuǎn)第三步。，說明還沒有達到最優(yōu)，轉(zhuǎn)第三步。 第三步：調(diào)整運量，即換基。選一個變量出基，對原運量進行第三步：調(diào)整運量，即換基。選一個變量出基，對原運量進行調(diào)整得到新的基可行解，轉(zhuǎn)入第二步。調(diào)整得到新的基可行解，轉(zhuǎn)入第二步。表表 上

9、上 作作 業(yè)業(yè) 法法左上角法左上角法(亦稱西北角法亦稱西北角法)是優(yōu)先從運價表的左上角的變量賦值，當行或列分是優(yōu)先從運價表的左上角的變量賦值，當行或列分配完畢后，再在表中余下部分的左上角賦值，依次類推，直到右下角元素分配完畢后，再在表中余下部分的左上角賦值，依次類推，直到右下角元素分配完畢當出現(xiàn)同時分配完一行和一列時，仍然應(yīng)在打配完畢當出現(xiàn)同時分配完一行和一列時，仍然應(yīng)在打“”的位置上選一的位置上選一個變量作基變量，以保證最后的基變量數(shù)等于個變量作基變量，以保證最后的基變量數(shù)等于m+n1 1 2 3 4 6 7 5 3 1 14 8 4 2 7 2 27 5 9 10 6 3 19 22 13

10、 12 13 813131466最小元素法的思想是優(yōu)先滿足單位運價最小的業(yè)務(wù)，即最最小元素法的思想是優(yōu)先滿足單位運價最小的業(yè)務(wù)，即最小運價小運價Cij 對應(yīng)的變量對應(yīng)的變量xij優(yōu)先賦值，優(yōu)先賦值，然后再在剩下的運價中取最小運價對應(yīng)的變量賦值并滿足然后再在剩下的運價中取最小運價對應(yīng)的變量賦值并滿足約束，依次下去，直到最后得到一個初始基可行解。約束，依次下去，直到最后得到一個初始基可行解。初始基礎(chǔ)可行解最小元素法jiijbax,min123467531148427212271559106319221312130初始基礎(chǔ)可行解最小元素法1）最小元素法2）1234675311314184272122

11、715591063192213121300最小元素法3）123467531131418427213122725910631922131213000最小元素法4）1234675311314184272131227259106319190221312133000最小元素法5）12346753111314084272131227259106319190221312132000最小元素法6）123467531113140842722131227059106319190221312130000初始基礎(chǔ)可行解元素差額法（Vogel近似法）求初始基本可行解的步驟是：求初始基本可行解的步驟是： 第一步：求出每

12、行次小運價與最小運價之差，記為第一步：求出每行次小運價與最小運價之差，記為ui，i=1,2,m ；同時求出每列次小運價與最小運價之差，記為；同時求出每列次小運價與最小運價之差，記為vj，j=1，2，n ； 第二步：找出所有行、列差額的最大值，即第二步：找出所有行、列差額的最大值，即L=maxui，vi，差，差額額L對應(yīng)行或列的最小運價處優(yōu)先調(diào)運；對應(yīng)行或列的最小運價處優(yōu)先調(diào)運； 第三步：這時必有一列或一行調(diào)運完畢，在剩下的運價中再求第三步：這時必有一列或一行調(diào)運完畢，在剩下的運價中再求最大差額，進行第二次調(diào)運，依次進行下去，直到最后全部調(diào)運最大差額，進行第二次調(diào)運，依次進行下去，直到最后全部調(diào)

13、運完畢，就得到一個初始調(diào)運方案。完畢，就得到一個初始調(diào)運方案。 用元素差額法求得的基本可行解更接近最優(yōu)解，所以也稱為近用元素差額法求得的基本可行解更接近最優(yōu)解，所以也稱為近似方案。似方案?！纠坑迷夭铑~法求下表運輸問題的初始基本可行解?！纠坑迷夭铑~法求下表運輸問題的初始基本可行解?！窘狻俊窘狻?求行差額求行差額 ui, i=1,2,3及列差額及列差額vj,j=1,2,3,4.計算公式為計算公式為 ui= i行次小運價行次小運價i行最小運價行最小運價 vj= j列次小運價列次小運價j例最小運價例最小運價【 】520【 】0除去除去B3列，重新計算差額列，重新計算差額200【 】10205求

14、出一組基可行解后，判斷是否為最優(yōu)解，仍然是用檢驗數(shù)來判求出一組基可行解后，判斷是否為最優(yōu)解，仍然是用檢驗數(shù)來判斷，記斷，記xij的檢驗數(shù)為的檢驗數(shù)為ij由第一章知，求最小值的運輸問題的最優(yōu)由第一章知，求最小值的運輸問題的最優(yōu)判別準則是：判別準則是：所有非基變量的檢驗數(shù)都非負，則運輸方案最優(yōu)即為最優(yōu)解）。所有非基變量的檢驗數(shù)都非負，則運輸方案最優(yōu)即為最優(yōu)解）。求檢驗數(shù)的方法有兩種，閉回路法和位勢法。求檢驗數(shù)的方法有兩種，閉回路法和位勢法。1閉回路法求檢驗數(shù)閉回路法求檢驗數(shù) 求某一非基變量的檢驗數(shù)的方法是：在基求某一非基變量的檢驗數(shù)的方法是：在基本可行解矩陣中，以該非基變量為起點，以基變量為其它頂

15、點，本可行解矩陣中，以該非基變量為起點，以基變量為其它頂點，找一條閉回路，由起點開始，分別在頂點上交替標上代數(shù)符號找一條閉回路，由起點開始，分別在頂點上交替標上代數(shù)符號+、-、+、-、，以這些符號分別乘以相應(yīng)的運價，其代數(shù)和就是，以這些符號分別乘以相應(yīng)的運價，其代數(shù)和就是這個非基變量的檢驗數(shù)。這個非基變量的檢驗數(shù)。第二步，求檢驗數(shù)，判優(yōu)第二步，求檢驗數(shù)，判優(yōu)12346753114148427281362759106361319221312135非基變量xij的檢驗數(shù)cij-zij閉回路法(1)12=c12-z12=c12- (c11-c21+c22) =7-6+8-4=512346753114

16、148427281362759106361319221312135閉回路法(2)13=c13-z13=c13- c11+c21-c23) =5-6+8-2=5512346753114148427281362759106361319221312135閉回路法(3)14=c14-z14=c14-(c11-c21+ c21 - c23 + c33 -c34)-=3- (6-8+2-10+6)=77512346753114148427281362759106361319221312135閉回路法(4)c24-z24=c24 -(c23-c33+ c34)=7 -(2-10+6)=99571234675

17、3114148427281362759106361319221312135閉回路法(5)c31-z31=c31- (c21-c23+ c33) =5 -(8-2+10)=-11-1157912346753114148427281362759106361319221312135閉回路法(6)c32-z32=c32-( c22-c23+ c33) =9 -(4-2+10)=-3-3579-11這里31和 320,得到最優(yōu)解。Min z=61+3 13+8 2+4 13+2 12+5 19=1421155482 產(chǎn)銷平衡表 單位：噸 單位運價表 單位：元/噸以此類推，得到一初始方案如下圖）：X21=

18、3，X32=6，X13=4，X23=1，X14=3，X34=3有數(shù)格）X11=X31=X12=X22=X33=X24=0空格）注：（）有數(shù)格是基變量，共m+n-1=3+4-1=6個?？崭袷欠腔兞?，共劃去m+n=7條線；（）如果填上一個運量之后能同時劃去兩條線一行與一列），就須在所劃去的該行或該列填一個0，此0格當有數(shù)個對待。初始方案運費Z0=31+64+43+12+310+35=86(元)每一個空格的檢驗數(shù)每一個空格的檢驗數(shù)=奇頂點運費之和奇頂點運費之和 偶頂點運費之和。偶頂點運費之和。(+1)*3+ (-1)*3+(+1)*2+(-1)*1=1空格檢驗數(shù)空格檢驗數(shù)24=(+1)*8+(-1

19、)*2+(+1)*3+(-1)*10=-1+-從ij 為最小負值的空格出發(fā).對其閉回路上的奇數(shù)頂點運量增加,偶數(shù)頂點的運量減少(這才能保證新的平衡)，其中為該空格閉回路中偶數(shù)頂點的最小值。 240，從A2 B4） 出發(fā)其閉回路上=1，調(diào)整后得到一個新方案如下表），運量為=1的A2 B3變空格，得到新方案后再轉(zhuǎn) 2。經(jīng)再計算新方案的檢驗數(shù)全部大于0。所以，該新方案為最優(yōu)方案，可計算得總運費為85元。注：若閉回路的偶數(shù)頂點中同時有兩個格以上運量為，則調(diào)整后其中一個變空格，其余填0。（保證基變量個數(shù)不變）3B1B3A2A1A4B2B3.調(diào)整調(diào)整:12921124表上作業(yè)法須注意的問題：表上作業(yè)法須注

20、意的問題： i) 在最終調(diào)運表中，若有某個空格非基變量的檢驗在最終調(diào)運表中，若有某個空格非基變量的檢驗數(shù)為數(shù)為0時，則表明該運輸問題有多重調(diào)運方案；時，則表明該運輸問題有多重調(diào)運方案； ii) 在確定初始方案時，若某一行的產(chǎn)量與某一列的需求在確定初始方案時，若某一行的產(chǎn)量與某一列的需求量同時滿足，這時也只能劃去一行或一列絕對不能同時量同時滿足，這時也只能劃去一行或一列絕對不能同時把行、列劃去，否則就不滿足圈格把行、列劃去，否則就不滿足圈格=m+n1個的要求，即個的要求，即基變量的個數(shù)永遠要保持為基變量的個數(shù)永遠要保持為m+n1個）；個）； iii) 在用閉回路法調(diào)整時，當閉回路上奇頂點有幾個相

21、同在用閉回路法調(diào)整時，當閉回路上奇頂點有幾個相同的最小值時，調(diào)整后只能有一個空格，其余均要保留數(shù)的最小值時，調(diào)整后只能有一個空格，其余均要保留數(shù)“0”，以保證圈格，以保證圈格=m+n1個的需要。個的需要。 iv) 用最小元素法所得到的初始方案可以不唯一。用最小元素法所得到的初始方案可以不唯一。1 0nijijijjiijMin ZCXxaxbx添加松弛變量xin+111 0nijijijjiijMin ZCXxaxbxxin+1的定義：由Ai向Bn+1的運量，而Bn+1并不存在，相當于增加了一個虛設(shè)的銷地Ai自己的倉庫里，自己往自己的地方運，運費cin+1顯然為0。實際上xin+1即剩余量就地

22、庫存產(chǎn)大于銷的產(chǎn)銷量表A1Ama1amB1Bnb1bnBn+1A1AmB1BnC1100C1nCm1Cmn產(chǎn)大于銷的單位運價表Bn+1jinbab11 0mijjiijiijMin ZCXxbxax添加松弛變量xm+1j11 0mijjiijiijMin ZCXxbxax同理，此時xm+1j的意義為銷售短缺的量，同樣，Am+1不存在， cm+1j為0。銷大于產(chǎn)的產(chǎn)銷量表A1Ama1amB1Bnb1bnAm+11jiabamA1AmB1BnC1100C1nCm1Cmn銷大于產(chǎn)的單位運價表Amjjiba因為有：因為有：【例】求下列表中極小化運輸問題的最優(yōu)解?！纠壳笙铝斜?/p>

23、中極小化運輸問題的最優(yōu)解。 所以是一個產(chǎn)大于銷的運輸問題。所以是一個產(chǎn)大于銷的運輸問題。表中表中A2不可達不可達B1，用一個很大的正數(shù)，用一個很大的正數(shù)M表示運價表示運價C21。虛設(shè)。虛設(shè)一個銷量為一個銷量為b5=180160=20的銷地的銷地B5，Ci5=0，i=1，2，3，4。表的右邊增添一列表的右邊增添一列 這樣可得新的運價表：這樣可得新的運價表：下表為計算結(jié)果?？煽闯觯寒a(chǎn)地下表為計算結(jié)果。可看出：產(chǎn)地A4還有還有20個單位沒個單位沒有運出。有運出。上例中，假定上例中，假定B1的需要量是的需要量是20到到60之間，之間，B2的需要量是的需要量是50到到70，試求極小化問題的最優(yōu)解。試求極

24、小化問題的最優(yōu)解。需求量不確定的運輸問題需求量不確定的運輸問題（1總產(chǎn)量為總產(chǎn)量為180，B1，B4的最低需求量的最低需求量 20+50+35+45=150，這時屬產(chǎn)大于銷；，這時屬產(chǎn)大于銷；（2B1，B4的最高需求是的最高需求是60+70+35+45=210，這時屬銷大于產(chǎn)，這時屬銷大于產(chǎn)（3虛設(shè)一個產(chǎn)地虛設(shè)一個產(chǎn)地A5，產(chǎn)量是，產(chǎn)量是210180=30，A5的產(chǎn)量只能供的產(chǎn)量只能供應(yīng)應(yīng)B1或或B2。（4將將B1與與B2各分成兩部分各分成兩部分 的需求量是的需求量是20， 的需求量是的需求量是40， 的需求量分別是的需求量分別是50與與20，因此，因此 必須由必須由A1，A4供應(yīng)，供應(yīng)， 可

25、由可由 A1、A5供應(yīng)。供應(yīng)。1122122111BBBBB，、及、21B2212BB 與1211BB 、2221BB 、（5上述上述A5不能供應(yīng)某需求地的運價用大不能供應(yīng)某需求地的運價用大M表示，表示，A5到到 、 的運價為零。得到下表的產(chǎn)銷平衡表。的運價為零。得到下表的產(chǎn)銷平衡表。先作如下分析：先作如下分析：11B21B12B22B得到這樣的平衡表后，計算得到最優(yōu)方案表得到這樣的平衡表后，計算得到最優(yōu)方案表5-29。產(chǎn)銷平衡表產(chǎn)銷平衡表 B3B4aiA1 352560A2 40 40A30 10 2030A42030 50A5 10 20 30bj204050203545210 11B21B12B22B表中：表中：x131=0