運輸問題的線性規(guī)劃

主講人：衛(wèi)斌制作：魏永牛天水師范學院數(shù)理與信息科學學院數(shù)學系２００４年５月線性規(guī)劃的運輸問題第一頁，共二十八頁。在處理產、供、銷的經(jīng)濟活動中，會經(jīng)常遇到物資調撥的運輸問題。如糧棉油、煤炭、鋼鐵、水泥、化肥、木材等物資要由若干個產地調運到若干個銷售地。問題是，怎樣制定合理的調用方案才能使總運輸費用最少？本章將專門討論這類特殊形式的線性規(guī)劃問題。導言第五章運輸問題第二頁，共二十八頁。例某食品公司經(jīng)銷的主要商品之一是糖果，它下面設有三個加工廠。某個的產量分別為A1—7t，A2—4t，A3—9t該公司把這些糖果分別運往四個地區(qū)的門市部銷售，各地區(qū)每天的銷售量為：B1—3t，B2—6t，B3—5t，B4—6t。已知從各個加工廠到各銷售部門每噸的運價見下表：5.1運輸問題的數(shù)學模型31047A38291A2103113A1B4B3B2B1

門市部加工廠單位：元/t問：該食品公司應如何調運，在滿足各部門銷售的情況下，使總的運費支出為最少？產銷平衡的運輸問題第三頁，共二十八頁。無論全國或一個地區(qū)，在各種生產或生活物資調運中都可以提出入上述問題類似的例子?，F(xiàn)在把問題概括一下，在線性規(guī)劃中我們研究這樣一類運輸問題：5.1運輸問題的數(shù)學模型產銷平衡的運輸問題第四頁，共二十八頁。設有某種物資要從m個產地（或稱發(fā)點）Ai(i=1，2，…，m)運往n個銷地（或稱收點）Bj(j=1，2，…n)，Ai的產量為ai，Bj的銷量為bj，把Ai運到Bj的單位運價設為cij，問怎樣編制調運方案才能使總運費最少？假設從Ai運到Bj的物資數(shù)量為xij，總運費為S，總產量=總銷量。那么這個運輸問題的數(shù)學模型是：5.1運輸問題的數(shù)學模型產銷平衡的運輸問題第五頁，共二十八頁。產銷平衡的運輸問題5.1運輸問題的數(shù)學模型運輸問題的數(shù)學模型是:產銷平衡表產量ai產地銷地銷量bi1２…n１２mb1b2…bna1a2amx11x12…x1nx21x22…x2nxm1xm2…xmn產地銷地1２…n１２mc11c12…c1nc21c22…c2ncm1cm2…cmn單位運價表第六頁，共二十八頁。產銷平衡的運輸問題5.1運輸問題的數(shù)學模型運輸問題的數(shù)學模型是:第七頁，共二十八頁。C=(c11，c12，…，c1n，c21，c22，c2n，…，cm1，cm2，…cmn)B=（a1，a2，…，am，b1，b2，…bn)TX=(x11，x12，…，x1n，x21，x22，x2n，…，xm1，xm2，…xmn)T5.1運輸問題的數(shù)學模型其矩陣形式為產銷平衡的運輸問題第八頁，共二十八頁。（1）產量大于銷量的情形5.1運輸問題的數(shù)學模型產銷不平衡運輸問題的轉化其運輸問題的數(shù)學模型是第九頁，共二十八頁。由于總量大于總銷量，所以多余物資應儲存在產地。社某產地Ai的多余存儲量為xi,n+1，于是運輸問題的約束條件方程組為：

則5.1運輸問題的數(shù)學模型產銷不平衡運輸問題的轉化第十頁，共二十八頁。5.1運輸問題的數(shù)學模型可將不平衡的運輸問題（5.3）化為如下的平衡運輸問題產銷不平衡運輸問題的轉化令第十一頁，共二十八頁。（2）產量大于銷量的運輸問題這時可增加一個設想的發(fā)點Am+1，發(fā)出量為并令該發(fā)點到收點Bｊ的運價Cｍ＋１.ｊ＝０（ｊ＝１，２，…，ｎ），同樣可將不平衡的運輸問題轉化為平衡的運輸問題。如無特別說明，本章僅限于對平衡問題的運輸問題求解的討論。同一般的線性規(guī)劃問題一樣，運輸問題的最優(yōu)解也一定能在它的基本可行解中找到。由于運輸問題（５.２）的約束系數(shù)矩陣Ａ的前ｍ行之和恰好等于后ｎ行之和，即矩陣Ａ的行向量組線性相關，因此Ａ的秩必小于ｍ+ｎ．5.1運輸問題的數(shù)學模型產銷不平衡運輸問題的轉化第十二頁，共二十八頁。5.1運輸問題的數(shù)學模型產銷不平衡運輸問題的轉化第十三頁，共二十八頁。根據(jù)以上討論可知，運輸問題（5.2）的基矩陣應由m+n-1個線性無關的列向量組成，這些列向量是約束方程Ax=b中去掉多余方程后剩下的m+n-1個方程的系數(shù)列向量，因此在研究運輸問題的基時只要在A中找到m+n-1個線性無關的系數(shù)列向量就可以了。運輸問題中的約束方程和變量個數(shù)一般比較多。例如m=25,n=500時，就有525個約束方程和12500個變量，這樣的問題即使使用電子計算機求解也很困難。但根據(jù)運輸問題具有的特殊結構，有專門為其設計的求解方法，這里不作介紹。對小規(guī)模的運輸問題的求解，可通過表上作業(yè)法和圖上作業(yè)法去完成。5.1運輸問題的數(shù)學模型因此秩（A）=m+n-1。同樣可得A的增廣矩陣=（a,b）的秩也等于m+n-1。所以（5.2）式的m+n個等式約束中有一個是多余的，于是增廣矩陣的任意一行都可用其余m+n-1行線性表出。這樣，運輸問題（5.2）中去掉任一個等式約束后就成為標準形式的線性規(guī)劃問題，便可用單純形或對偶單純形方法求解。產銷不平衡運輸問題的轉化第十四頁，共二十八頁。B1…Bj…Bn發(fā)量A1x11C11…xijCij…x1nC1na1…………………Ajxi1Ci1…xijCij…xinCinai…………………Amxm1Cm1…xmjCmj…xmnCmnam收量b1…bj…bn5.2運輸問題的表上作業(yè)法對于小規(guī)模的運輸問題其求解過程可以在表上進行。第十五頁，共二十八頁。5.2運輸問題的表上作業(yè)法表中共有mn個格子，每個格子對應一個變量求解運輸問題的首要任務是，在表上找到m+n-1個格子對應的一組變量，是一組變量。為此，先引入以下概念和結論。第十六頁，共二十八頁。定義5.15.2運輸問題的表上作業(yè)法稱變量組的集合是一個閉回路。其中i1,i2,…,is互不相同，j1,j2,…,js互不相同,稱其中每個變量為閉回路的頂點。例如，變量組中的i1=4,i2=3,i3=1,j1=5,j2=1,j3=3各互不相同，若在表格中把相鄰兩個頂點，第一個頂點與最后一個頂點用直線段連接起來，就可在下表5.2中畫出這個閉回路。B1B2B3B4B5A1A2A3A4X45X41X31X33X13X15第十七頁，共二十八頁。定義5.15.2運輸問題的表上作業(yè)法B1B2B3B4B5A1A2A3A4X11但變量組{x11,x12,x22,x24,x44,x42,x21}不能構成一條閉回路，因為x42不是拐角點。X12X22X24X44X42X42第十八頁，共二十八頁。若變量組是一個閉回路，則這個變量組對應矩陣A中的列向量組線性相關。證明矩陣A中的每列只有兩個元素為１，其余都是０。變量xij對應Ａ中的列向量是5.2運輸問題的表上作業(yè)法定理5.1第i個分量第m+j個分量第十九頁，共二十八頁。5.2運輸問題的表上作業(yè)法定理5.1通過計算閉回路中變量對應Ａ中的列向量，得這表明變量組對應矩陣Ａ中列向量組線性相關。第二十頁，共二十八頁。變量組對應矩陣Ａ中列向量組根據(jù)以上結論，給出了從表格上判斷運輸問題的方法。m+n-1個變量是否為一組基變量就看表中m+n-1個變量是否含有閉回路。于是可從表格上方便的求出運輸問題的初始基本可行解來.5.2運輸問題的表上作業(yè)法定理5.2線性無關的充要條件是該變量組不含有閉回路。求解運輸問題的表上作業(yè)法可按以下步驟進行。第二十一頁，共二十八頁。一、編制初始調運方案方法一最小元素法令（1）若ai<bj，則取xij=ai,而xik=0(k=1,2,…,j-1,j+1,…,n),將ai填入(i,j)格內。這時xi1+xi2+…+xi,j-1+xij+xi,j+1+…+xin=xij=ai5.2運輸問題的表上作業(yè)法求解運輸問題的表上作業(yè)法的步驟：編制初始調運方案就是求運輸問題的初始基本可行解，方法有兩種第二十二頁，共二十八頁。（2）若ai>bj，則取xij=bj,而xsj=0(s=1,2,…,i-1,i+1,…,m),將bj填入(i,j)格內。這時x1j+x2j+…+xij+…+xmj=xij=bj例5.1用最小元素法求下列運輸問題的初始調運方案銷地產地B1B2B3B4B5Ａ１Ａ２Ａ３產量ai９４８３５５３５銷量bj２１B1B2B3B4B5102059101082561157104平衡表運價表5.2運輸問題的表上作業(yè)法一、編制初始調運方案求解運輸問題的表上作業(yè)法的步驟：第二十三頁，共二十八頁。銷地產地B1B2B3B4B5Ａ１Ａ２Ａ３產量ai９４８３５５３５銷量bj２１B1B2B3B4B5102059101082561157104平衡表運價表初始基本可行解為{x12,x13,x14,x22,x31,x32,x35}={1,5,3,4,3,0,5},相應運價為：{c12,c13,c14,c22,c31,c32,c35}={20,5,9,10,1,15,4},由此表上作業(yè)得初始調運方案的總運費為S=1x20+5x5+3x9+4x10+3x1+0x15+5x4=135（元）5.2運輸問題的表上作業(yè)法一、編制初始調運方案求解運輸問題的表上作業(yè)法的步驟：1534305二十四頁，共二十八頁。方法二左上角法(也稱西北角法）令（1）若a1<b1，則取x11=a1,而x1k=0(k=2,3,…,n),將a1填入(1,1)格內。這時x11+x12+…+x1n=x11=a1（2）若a1>b1，則取x11=b1,則取x11=b1，而xs1=0(s=2,3,…,m),將b1填入(1,1)格內。這時x11+x21+…+xm1=b15.2運輸問題的表上作業(yè)法一、編制初始調運方案求解運輸問題的表上作業(yè)法的步驟：第二十五頁，共二十八頁。例5.2用左上角法求下列運輸問題的初始調運方案

銷地產地B1B2B3B4B5Ａ１Ａ２Ａ３產量ai9４

８３５５３５銷量bj２１B1B2B3B4B5102059101082561157104平衡表運價表5.2運輸問題的表上作業(yè)法一、編制初始調運方案求解運輸問題的表上作業(yè)法的步驟：第二十六頁，共二十八頁。5.2運輸問題的表上作業(yè)法一、編制初始調運方案求解運輸問題的表上作業(yè)法的步驟：解

銷地產地B1B2B3B4B5Ａ１Ａ２Ａ３產量ai9４

８３５５３５銷量bj２１B1B2B3B4B510205