运输问题的线性规划

主讲人：主讲人：卫斌卫斌制作：制作：魏永牛魏永牛天水师范学院数理与信息科学学院数学系年月在处理产、供、销的经济活动中，在处理产、供、销的经济活动中，会经常遇到物资调拨的运输问题。如粮会经常遇到物资调拨的运输问题。如粮棉油、煤炭、钢铁、水泥、化肥、木材棉油、煤炭、钢铁、水泥、化肥、木材等物资要由若干个产地调运到若干个销等物资要由若干个产地调运到若干个销售地。问题是，怎样制定合理的调用方售地。问题是，怎样制定合理的调用方案才能使总运输费用最少？本章将专门案才能使总运输费用最少？本章将专门讨论这类特殊形式的线性规划问题。讨论这类特殊形式的线性规划问题。导导言言第五章 运输问题例例 某食品公司经销的主要商品之一是糖果，它下面设有三个加某食品公司经销的主要商品之一是糖果，它下面设有三个加工厂。某个的产量分别为工厂。某个的产量分别为A17t，A24t，A39t该公司把这些该公司把这些糖果分别运往四个地区的门市部销售，各地区每天的销售量为：糖果分别运往四个地区的门市部销售，各地区每天的销售量为：B13t，B26t，B35t，B46t。已知从各个加工厂到各销。已知从各个加工厂到各销售部门每吨的运价见下表：售部门每吨的运价见下表：5.1 运运输输问问题题的的数数学学模模型型31047A38291A2103113A1B4B3B2B1门市部加工厂单位：元/t问：该食品公司应如何调运，在满足各部门销售的情况下，问：该食品公司应如何调运，在满足各部门销售的情况下，使总的运费支出为最少？使总的运费支出为最少？产销平衡的运输问题产销平衡的运输问题无论全国或一个地区，在各种生产或生活物资无论全国或一个地区，在各种生产或生活物资调运中都可以提出入上述问题类似的例子。调运中都可以提出入上述问题类似的例子。现在把问题概括一下，在线性规划中我们研究现在把问题概括一下，在线性规划中我们研究这样一类运输问题：这样一类运输问题：5.1 运运输输问问题题的的数数学学模模型型产销平衡的运输问题产销平衡的运输问题 设有某种物资要从设有某种物资要从m m个产地（或称发点）个产地（或称发点）A Ai i(i(i=1=1，2 2，m)m)运往运往n n个销地（或称收点）个销地（或称收点）B Bj j(j(j=1=1，2 2，n)n)，A Ai i的产量为的产量为a ai i，B Bj j的销量为的销量为b bj j，把，把Ai运到运到Bj的单位运价设为的单位运价设为c cijij，问怎样编制调运，问怎样编制调运方案才能使总运费最少？方案才能使总运费最少？假设从假设从A Ai i运到运到B Bj j的物资数量为的物资数量为x xijij，总运，总运费为费为S S，总产量，总产量=总销量。那么这个运输问题总销量。那么这个运输问题的数学模型是：的数学模型是：5.1 运运输输问问题题的的数数学学模模型型产销平衡的运输问题产销平衡的运输问题产销平衡的运输问题产销平衡的运输问题5.1 运运输输问问题题的的数数学学模模型型运输问题的数学模型是运输问题的数学模型是:产销平衡表产销平衡表产量ai产地销地销量bi1 nmb1 b2 bna1a2amx11 x12 x1nx21 x22 x2nxm1 xm2 xmn产地销地1 nmc11 c12 c1nc21 c22 c2ncm1 cm2 cmn单位运价表单位运价表产销平衡的运输问题产销平衡的运输问题5.1 运运输输问问题题的的数数学学模模型型运输问题的数学模型是运输问题的数学模型是: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 运运输输问问题题的的数数学学模模型型其矩阵形式为其矩阵形式为产销平衡的运输问题产销平衡的运输问题（1 1）产量大于销量的情形）产量大于销量的情形5.1 运运输输问问题题的的数数学学模模型型产销不平衡运输问题的转化产销不平衡运输问题的转化其运输问题的数学模型是其运输问题的数学模型是由于总量大于总销量，所以多余物资应储存在产地。由于总量大于总销量，所以多余物资应储存在产地。社某产地社某产地Ai的多余存储量为的多余存储量为xi,n+1，于是运输问题的约束，于是运输问题的约束条件方程组为：条件方程组为：则5.1 运运输输问问题题的的数数学学模模型型产销不平衡运输问题的转化产销不平衡运输问题的转化5.1 运运输输问问题题的的数数学学模模型型可将不平衡的运输问题（5.3）化为如下的平衡运输问题产销不平衡运输问题的转化产销不平衡运输问题的转化令令（2）产量大于销量的运输问题这时可增加一个设想的发点这时可增加一个设想的发点Am+1，发出量为，发出量为并令该发点到收点并令该发点到收点B的运价的运价C.（，（，），），同样可将不平衡的运输问题转化为平衡的运输问题。同样可将不平衡的运输问题转化为平衡的运输问题。如无特别说明，本章仅限于对平衡问题的运输问题求解的讨论。如无特别说明，本章仅限于对平衡问题的运输问题求解的讨论。同一般的线性规划问题一样，运输问题的最优解也一定能在它同一般的线性规划问题一样，运输问题的最优解也一定能在它的基本可行解中找到。由于运输问题（的基本可行解中找到。由于运输问题（.）的约束系数矩阵）的约束系数矩阵的前行之和恰好等于后行之和，即矩阵的行向量组线性相关，的前行之和恰好等于后行之和，即矩阵的行向量组线性相关，因此的秩必小于因此的秩必小于+5.1 运运输输问问题题的的数数学学模模型型产销不平衡运输问题的转化产销不平衡运输问题的转化5.1 运运输输问问题题的的数数学学模模型型产销不平衡运输问题的转化产销不平衡运输问题的转化根据以上讨论可知，运输问题（根据以上讨论可知，运输问题（5.2）的基矩阵应由）的基矩阵应由m+n-1个线个线性无关的列向量组成，这些列向量是约束方程性无关的列向量组成，这些列向量是约束方程Ax=b中去掉多余方程中去掉多余方程后剩下的后剩下的m+n-1个方程的系数列向量，因此在研究运输问题的基时个方程的系数列向量，因此在研究运输问题的基时只要在只要在A中找到中找到m+n-1个线性无关的系数列向量就可以了。个线性无关的系数列向量就可以了。运输问题中的约束方程和变量个数一般比较多。例如运输问题中的约束方程和变量个数一般比较多。例如m=25,n=500时，时，就有就有525个约束方程和个约束方程和12500个变量，这样的问题即使使用电子计算个变量，这样的问题即使使用电子计算机求解也很困难。但根据运输问题具有的特殊结构，有专门为其设机求解也很困难。但根据运输问题具有的特殊结构，有专门为其设计的求解方法，这里不作介绍。对小规模的运输问题的求解，可通计的求解方法，这里不作介绍。对小规模的运输问题的求解，可通过表上作业法和图上作业法去完成。过表上作业法和图上作业法去完成。5.1 运运输输问问题题的的数数学学模模型型因此秩（因此秩（A）=m+n-1。同样可得。同样可得A的增广矩阵的增广矩阵 =（a,b）的秩也）的秩也等于等于m+n-1。所以（。所以（5.2）式的）式的m+n个等式约束中有一个是多余的，个等式约束中有一个是多余的，于是增广矩阵于是增广矩阵 的任意一行都可用其余的任意一行都可用其余m+n-1行线性表出。这样，运行线性表出。这样，运输问题（输问题（5.2）中去掉任一个等式约束后就成为标准形式的线性规划问）中去掉任一个等式约束后就成为标准形式的线性规划问题，便可用单纯形或对偶单纯形方法求解。题，便可用单纯形或对偶单纯形方法求解。产销不平衡运输问题的转化产销不平衡运输问题的转化B1BjBn发量A1 x11C11 xijCij x1nC1na1Aj xi1Ci1 xijCij xinCinaiAm xm1Cm1 xmjCmj xmnCmnam收量b1bjbn5.2 运运输输问问题题的的表表上上作作业业法法对于小规模的运输问题其求解过程可以在表上进对于小规模的运输问题其求解过程可以在表上进行。行。5.2 运运输输问问题题的的表表上上作作业业法法表中共有mn个格子，每个格子对应一个变量求解运输问题的首要任务是，在表上找到m+n-1个格子对应的一组变量，是一组变量。为此，先引入以下概念和结论。定义5.15.15.2 运运输输问问题题的的表表上上作作业业法法称变量组的集合称变量组的集合是一个闭回路。其中是一个闭回路。其中i1,i2,is互不相同，互不相同，j1,j2,js互不相同互不相同,称称其中每个变量为闭回路的顶点。其中每个变量为闭回路的顶点。例如，变量组例如，变量组 中的中的i1=4,i2=3,i3=1,j1=5,j2=1,j3=3 各互不相同，若在表格中把相邻两各互不相同，若在表格中把相邻两个顶点，第一个顶点与最后一个顶点用直线段连接起来，就可在下个顶点，第一个顶点与最后一个顶点用直线段连接起来，就可在下表表5.2中画出这个闭回路。中画出这个闭回路。B1B2B3B4B5A1A2A3A4X45X41X31X33X13X15定义5.15.15.2 运运输输问问题题的的表表上上作作业业法法B1B2B3B4B5A1A2A3A4X11但变量组x11,x12,x22,x24,x44,x42,x21不能构成一条闭回路，因为x42不是拐角点。X12X22X24X44X42X42 若变量组若变量组 是一个闭回路，则这个变量组对应矩阵是一个闭回路，则这个变量组对应矩阵A中的列向量组线中的列向量组线性相关。性相关。证明矩阵矩阵A中的每列只有两个元素为，其余都是。变量中的每列只有两个元素为，其余都是。变量xij对应中的列向量是对应中的列向量是5.2 运运输输问问题题的的表表上上作作业业法法定理5.15.1第i个分量第m+j个分量5.2 运运输输问问题题的的表表上上作作业业法法定理5.15.1通过计算闭回路中变量对应中的列向量，得这表明变量组对应矩阵中列向量组线性相关。变量组变量组 对应矩阵中列向量组对应矩阵中列向量组 根据以上结论，给出了从表格上判断运输问题的方根据以上结论，给出了从表格上判断运输问题的方法。法。m+n-1个变量是否为一组基变量就看表中个变量是否为一组基变量就看表中m+n-1个变量是否含有闭回路。于是可从表格上方便的个变量是否含有闭回路。于是可从表格上方便的求出运输问题的初始基本可行解来求出运输问题的初始基本可行解来.5.2 运运输输问问题题的的表表上上作作业业法法定理5.25.2线性无关的充要条件是该变量组不含有闭回路。线性无关的充要条件是该变量组不含有闭回路。求解运输问题的表上作业法可按以下步骤进行。求解运输问题的表上作业法可按以下步骤进行。一、编制初始调运方案方法一方法一 最小元素法最小元素法令令（1）若aibj，则取xij=bj,而xsj=0(s=1,2,i-1,i+1,m),将bj填入(i,j)格内。这时x1j+x2j+xij+xmj=xij=bj例例5.1用最小元素法求下列运输问题的初始调运方案用最小元素法求下列运输问题的初始调运方案 销地产地B1 B2 B3 B4 B5产量ai 销量bjB1 B2 B3 B4 B510 20 5 9 102 10 8 25 631 15 7 10 4平衡表运价表5.2 运运输输问问题题的的表表上上作作业业法法一、编制初始调运方案求解运输问题的表上作业法的步骤：求解运输问题的表上作业法的步骤：销地产地B1 B2 B3 B4 B5产量ai 销量bjB1 B2 B3 B4 B510 20 5 9 102 10 8 25 631 15 7 10 4平衡表运价表初始基本可行解为初始基本可行解为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,由此表上作业得初始调运方案的总运费为由此表上作业得初始调运方案的总运费为S=1x20+5x5+3x9+4x10+3x1+0 x15+5x4=135（元）（元）5.2 运运输输问问题题的的表表上上作作业业法法一、编制初始调运方案求解运输问题的表上作业法的步骤：求解运输问题的表上作业法的步骤：1534305解解15234415167方法二方法二 左上角法左上角法(也称西北角法）也称西北角法）令令（1）若）若a1b1，则取，则取x11=b1,则取则取x11=b1，而而xs1=0(s=2,3,m),将将b1填填入入(1,1)格内。这时格内。这时x11+x21+xm1=b15.2 运运输输问问题题的的表表上上作作业业法法一、编制初始调运方案求解运输问题的表上作业法的步骤：求解运输问题的表上作业法的步骤：例例5.2用左上角法求下列运输问题的初始调运方案用左上角法求下列运输问题的初始调运方案 销地产地B1 B2 B3 B4 B5产量ai9 销量bjB1 B2 B3 B4 B510 20 5 9 102 10 8 25 631 15 7 10 4平衡表运价表5.2 运运输输问问题题的的表表上上作作业业法法一、编制初始调运方案求解运输问题的表上作业法的步骤：求解运输问题的表上作业法的步骤：5.2 运运输输问问题题的的表表上上作作业业法法一、编制初始调运方案求解运输问题的表上作业法的步骤：求解运输问题的表上作业法的步骤：解解 销地产地B1 B2 B3 B4 B5产量ai9 销量bjB1 B2 B3 B4 B510 20 5 9 102 10 8 25 631 15 7 10 4平衡表运价表136251314445063575初始基本可行解为初始基本可行解为x11,x12,x13,x23,x33,x34,x35=3,5,1,4,0,3,5,相应运价为：相应运价为：c11,c12,c13,c23,c33,c34,c35=10,20,5,8,7,10,4,由此表上作业得初始调运方案的总运费为由此表上作业得初始调运方案的总运费为S=S=3x10+5x20+1x5+4x8+0 x7+3x10+5x4=217（元）（元）