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

1、主講人：制作：年月線性規(guī)劃的運(yùn)輸問題1在處理產(chǎn)、供、銷的經(jīng)濟(jì)活動(dòng)中，會(huì)經(jīng)常遇到物資調(diào)撥的運(yùn)輸問題。如糧棉油、煤炭、鋼鐵、水泥、化肥、木材等物資要由若干個(gè)產(chǎn)地調(diào)運(yùn)到若干個(gè)銷售地。問題是，怎樣制定合理的調(diào)用方案才能使總運(yùn)輸費(fèi)用最少？本章將專門討論這類特殊形式的線性規(guī)劃問題。導(dǎo)言第五章 運(yùn)輸問題2例 某食品公司經(jīng)銷的主要商品之一是糖果，它下面設(shè)有三個(gè)加工廠。某個(gè)的產(chǎn)量分別為A17t， A24t， A39t該公司把這些糖果分別運(yùn)往四個(gè)地區(qū)的門市部銷售，各地區(qū)每天的銷售量為： B13t， B26t， B35t， B46t 。已知從各個(gè)加工廠到各銷售部門每噸的運(yùn)價(jià)見下表：5.1 運(yùn)輸問題的數(shù)學(xué)模型3104

2、7A38291A2103113A1B4B3B2B1門市部加工廠單位：元/t問：該食品公司應(yīng)如何調(diào)運(yùn)，在滿足各部門銷售的情況下，使總的運(yùn)費(fèi)支出為最少？產(chǎn)銷平衡的運(yùn)輸問題3無論全國或一個(gè)地區(qū)，在各種生產(chǎn)或生活物資調(diào)運(yùn)中都可以提出入上述問題類似的例子?，F(xiàn)在把問題概括一下，在線性規(guī)劃中我們研究這樣一類運(yùn)輸問題：5.1 運(yùn)輸問題的數(shù)學(xué)模型產(chǎn)銷平衡的運(yùn)輸問題4 設(shè)有某種物資要從m個(gè)產(chǎn)地（或稱發(fā)點(diǎn)）Ai(i=1，2，m)運(yùn)往n個(gè)銷地（或稱收點(diǎn)）Bj(j=1，2，n) ，Ai的產(chǎn)量為ai，Bj的銷量為bj，把Ai運(yùn)到Bj的單位運(yùn)價(jià)設(shè)為cij，問怎樣編制調(diào)運(yùn)方案才能使總運(yùn)費(fèi)最少？ 假設(shè)從Ai運(yùn)到Bj的物資數(shù)量為

3、xij，總運(yùn)費(fèi)為S，總產(chǎn)量=總銷量。那么這個(gè)運(yùn)輸問題的數(shù)學(xué)模型是：5.1 運(yùn)輸問題的數(shù)學(xué)模型產(chǎn)銷平衡的運(yùn)輸問題5產(chǎn)銷平衡的運(yùn)輸問題5.1 運(yùn)輸問題的數(shù)學(xué)模型運(yùn)輸問題的數(shù)學(xué)模型是:產(chǎn)銷平衡表產(chǎn)量ai產(chǎn)地銷地銷量bi1 nmb1 b2 bna1a2amx11 x12 x1nx21 x22 x2nxm1 xm2 xmn產(chǎn)地銷地1 nmc11 c12 c1nc21 c22 c2ncm1 cm2 cmn單位運(yùn)價(jià)表6產(chǎn)銷平衡的運(yùn)輸問題5.1 運(yùn)輸問題的數(shù)學(xué)模型運(yùn)輸問題的數(shù)學(xué)模型是:7C=(c11，c12，c1n，c21，c22，c2n，cm1，cm2，cmn)B=（a1，a2，am，b1，b2，bn)TX

4、 =(x11，x12，x1n，x21，x22，x2n，xm1，xm2，xmn)T5.1 運(yùn)輸問題的數(shù)學(xué)模型其矩陣形式為產(chǎn)銷平衡的運(yùn)輸問題8（1）產(chǎn)量大于銷量的情形5.1 運(yùn)輸問題的數(shù)學(xué)模型產(chǎn)銷不平衡運(yùn)輸問題的轉(zhuǎn)化其運(yùn)輸問題的數(shù)學(xué)模型是9由于總量大于總銷量，所以多余物資應(yīng)儲(chǔ)存在產(chǎn)地。社某產(chǎn)地Ai的多余存儲(chǔ)量為xi,n+1，于是運(yùn)輸問題的約束條件方程組為：則5.1 運(yùn)輸問題的數(shù)學(xué)模型產(chǎn)銷不平衡運(yùn)輸問題的轉(zhuǎn)化105.1 運(yùn)輸問題的數(shù)學(xué)模型可將不平衡的運(yùn)輸問題（5.3）化為如下的平衡運(yùn)輸問題產(chǎn)銷不平衡運(yùn)輸問題的轉(zhuǎn)化令11（2）產(chǎn)量大于銷量的運(yùn)輸問題這時(shí)可增加一個(gè)設(shè)想的發(fā)點(diǎn)Am+1，發(fā)出量為并令該發(fā)點(diǎn)到

5、收點(diǎn)B的運(yùn)價(jià)C.（，），同樣可將不平衡的運(yùn)輸問題轉(zhuǎn)化為平衡的運(yùn)輸問題。如無特別說明，本章僅限于對(duì)平衡問題的運(yùn)輸問題求解的討論。同一般的線性規(guī)劃問題一樣，運(yùn)輸問題的最優(yōu)解也一定能在它的基本可行解中找到。由于運(yùn)輸問題（.）的約束系數(shù)矩陣的前行之和恰好等于后行之和，即矩陣的行向量組線性相關(guān)，因此的秩必小于+5.1 運(yùn)輸問題的數(shù)學(xué)模型產(chǎn)銷不平衡運(yùn)輸問題的轉(zhuǎn)化125.1 運(yùn)輸問題的數(shù)學(xué)模型產(chǎn)銷不平衡運(yùn)輸問題的轉(zhuǎn)化13根據(jù)以上討論可知，運(yùn)輸問題（5.2）的基矩陣應(yīng)由m+n-1個(gè)線性無關(guān)的列向量組成，這些列向量是約束方程Ax=b中去掉多余方程后剩下的m+n-1個(gè)方程的系數(shù)列向量，因此在研究運(yùn)輸問題的基時(shí)只要

6、在A中找到m+n-1個(gè)線性無關(guān)的系數(shù)列向量就可以了。運(yùn)輸問題中的約束方程和變量個(gè)數(shù)一般比較多。例如m=25,n=500時(shí)，就有525個(gè)約束方程和12500個(gè)變量，這樣的問題即使使用電子計(jì)算機(jī)求解也很困難。但根據(jù)運(yùn)輸問題具有的特殊結(jié)構(gòu)，有專門為其設(shè)計(jì)的求解方法，這里不作介紹。對(duì)小規(guī)模的運(yùn)輸問題的求解，可通過表上作業(yè)法和圖上作業(yè)法去完成。 5.1 運(yùn)輸問題的數(shù)學(xué)模型因此秩（A）=m+n-1。同樣可得A的增廣矩陣 =（a,b）的秩也等于m+n-1。所以（5.2）式的m+n個(gè)等式約束中有一個(gè)是多余的，于是增廣矩陣 的任意一行都可用其余m+n-1行線性表出。這樣，運(yùn)輸問題（5.2）中去掉任一個(gè)等式約束后

7、就成為標(biāo)準(zhǔn)形式的線性規(guī)劃問題，便可用單純形或?qū)ε紗渭冃畏椒ㄇ蠼?。產(chǎn)銷不平衡運(yùn)輸問題的轉(zhuǎn)化145.2 運(yùn)輸問題的表上作業(yè)法對(duì)于小規(guī)模的運(yùn)輸問題其求解過程可以在表上進(jìn)行。155.2 運(yùn)輸問題的表上作業(yè)法表中共有mn個(gè)格子，每個(gè)格子對(duì)應(yīng)一個(gè)變量求解運(yùn)輸問題的首要任務(wù)是，在表上找到m+n-1個(gè)格子對(duì)應(yīng)的一組變量，是一組變量。為此，先引入以下概念和結(jié)論。16定義5.15.2 運(yùn)輸問題的表上作業(yè)法稱變量組的集合是一個(gè)閉回路。其中i1,i2,is互不相同，j1,j2,js互不相同,稱其中每個(gè)變量為閉回路的頂點(diǎn)。 例如，變量組 中的i1=4,i2=3,i3=1,j1=5,j2=1 ,j3=3 各互不相同，若在

8、表格中把相鄰兩個(gè)頂點(diǎn)，第一個(gè)頂點(diǎn)與最后一個(gè)頂點(diǎn)用直線段連接起來，就可在下表5.2中畫出這個(gè)閉回路。 X45X41X31X33X13X1517定義5.15.2 運(yùn)輸問題的表上作業(yè)法X11但變量組x11,x12,x22,x24,x44,x42,x21不能構(gòu)成一條閉回路，因?yàn)閤42不是拐角點(diǎn)。X12X22X24X44X42X4218 若變量組 是一個(gè)閉回路，則這個(gè)變量組對(duì)應(yīng)矩陣A中的列向量組線性相關(guān)。證明矩陣A中的每列只有兩個(gè)元素為，其余都是。變量xij對(duì)應(yīng)中的列向量是5.2 運(yùn)輸問題的表上作業(yè)法定理5.1第i個(gè)分量第m+j個(gè)分量195.2 運(yùn)輸問題的表上作業(yè)法定理5.1通過計(jì)算閉回路中變量對(duì)應(yīng)中的

9、列向量，得這表明變量組對(duì)應(yīng)矩陣中列向量組線性相關(guān)。20變量組 對(duì)應(yīng)矩陣中列向量組 根據(jù)以上結(jié)論，給出了從表格上判斷運(yùn)輸問題的方法。m+n-1個(gè)變量是否為一組基變量就看表中m+n-1個(gè)變量是否含有閉回路。于是可從表格上方便的求出運(yùn)輸問題的初始基本可行解來.5.2 運(yùn)輸問題的表上作業(yè)法定理5.2線性無關(guān)的充要條件是該變量組不含有閉回路。求解運(yùn)輸問題的表上作業(yè)法可按以下步驟進(jìn)行。21一 、編制初始調(diào)運(yùn)方案方法一 最小元素法令（1）若aibj，則取xij=bj,而xsj=0(s=1,2,i-1,i+1,m),將bj填入(i,j)格內(nèi)。這時(shí)x1j+x2j+xij+xmj=xij=bj例5.1用最小元素法

10、求下列運(yùn)輸問題的初始調(diào)運(yùn)方案 銷地產(chǎn)地B1 B2 B3 B4 B5產(chǎn)量ai 銷量bjB1 B2 B3 B4 B510 20 5 9 10 10 8 25 61 15 7 10 4平衡表運(yùn)價(jià)表5.2 運(yùn)輸問題的表上作業(yè)法一 、編制初始調(diào)運(yùn)方案求解運(yùn)輸問題的表上作業(yè)法的步驟：23 銷地產(chǎn)地B1 B2 B3 B4 B5產(chǎn)量ai 銷量bjB1 B2 B3 B4 B510 20 5 9 10 10 8 25 61 15 7 10 4平衡表運(yùn)價(jià)表初始基本可行解為x12,x13,x14,x22,x31,x32,x35=1,5,3,4,3,0,5,相應(yīng)運(yùn)價(jià)為：c12,c13,c14,c22,c31,c32,c

11、35=20,5,9,10,1,15,4,由此表上作業(yè)得初始調(diào)運(yùn)方案的總運(yùn)費(fèi)為S=1x20+5x5+3x9+4x10+3x1+0 x15+5x4=135（元）5.2 運(yùn)輸問題的表上作業(yè)法一 、編制初始調(diào)運(yùn)方案求解運(yùn)輸問題的表上作業(yè)法的步驟：1534305解1523441516724方法二 左上角法(也稱西北角法）令（1）若a1b1，則取x11=b1,則取x11=b1 ，而xs1=0(s=2,3,m),將b1填入(1,1)格內(nèi)。這時(shí)x11+x21+xm1=b15.2 運(yùn)輸問題的表上作業(yè)法一 、編制初始調(diào)運(yùn)方案求解運(yùn)輸問題的表上作業(yè)法的步驟：25例5.2用左上角法求下列運(yùn)輸問題的初始調(diào)運(yùn)方案 銷地產(chǎn)地B1 B2 B3 B4 B5產(chǎn)量ai9 銷量bjB1 B2 B3 B4 B510 20 5 9 10 10 8 25 61 15 7 10 4平衡表運(yùn)價(jià)表5.2 運(yùn)輸問題的表上作業(yè)法一 、編制初始調(diào)運(yùn)方案求解運(yùn)輸問題的表上作業(yè)法的步驟：265.2 運(yùn)輸問題的表上作業(yè)法一 、編制初始調(diào)運(yùn)方案求解運(yùn)輸問題的表上作業(yè)法的步驟：解 銷地產(chǎn)地B1 B2 B3 B4 B5產(chǎn)量ai9 銷量bjB1 B2 B3 B4 B510 20 5 9 10 10 8 25 61 15 7 10 4平衡表