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

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

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

3、xij，總運費為S，總產(chǎn)量=總銷量。那么這個運輸問題的數(shù)學(xué)模型是：5.1 運輸問題的數(shù)學(xué)模型產(chǎn)銷平衡的運輸問題5產(chǎn)銷平衡的運輸問題5.1 運輸問題的數(shù)學(xué)模型運輸問題的數(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單位運價表6產(chǎn)銷平衡的運輸問題5.1 運輸問題的數(shù)學(xué)模型運輸問題的數(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 運輸問題的數(shù)學(xué)模型其矩陣形式為產(chǎn)銷平衡的運輸問題8（1）產(chǎn)量大于銷量的情形5.1 運輸問題的數(shù)學(xué)模型產(chǎn)銷不平衡運輸問題的轉(zhuǎn)化其運輸問題的數(shù)學(xué)模型是9由于總量大于總銷量，所以多余物資應(yīng)儲存在產(chǎn)地。社某產(chǎn)地Ai的多余存儲量為xi,n+1，于是運輸問題的約束條件方程組為：則5.1 運輸問題的數(shù)學(xué)模型產(chǎn)銷不平衡運輸問題的轉(zhuǎn)化105.1 運輸問題的數(shù)學(xué)模型可將不平衡的運輸問題（5.3）化為如下的平衡運輸問題產(chǎn)銷不平衡運輸問題的轉(zhuǎn)化令11（2）產(chǎn)量大于銷量的運輸問題這時可增加一個設(shè)想的發(fā)點Am+1，發(fā)出量為并令該發(fā)點到

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

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

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

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

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

10、求下列運輸問題的初始調(diào)運方案 銷地產(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平衡表運價表5.2 運輸問題的表上作業(yè)法一 、編制初始調(diào)運方案求解運輸問題的表上作業(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平衡表運價表初始基本可行解為x12,x13,x14,x22,x31,x32,x35=1,5,3,4,3,0,5,相應(yīng)運價為：c12,c13,c14,c22,c31,c32,c

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