第四章运输问题1

1、第四章第四章 运输问题运输问题 1 1 运输问题的数学模型运输问题的数学模型 2 2 表上作业法表上作业法 2.1 2.1 确定初始基可行解确定初始基可行解 （一）最小元素法（一）最小元素法 （二）伏格尔法（二）伏格尔法 2.2 2.2 最优解的判别最优解的判别 （一）闭回路法（一）闭回路法 （二）、位势法（二）、位势法 2.3 2.3 改进的方法改进的方法闭回路调整法闭回路调整法 2.4 2.4 表上作业法计算中的问题表上作业法计算中的问题 3 3 产销不平衡问题产销不平衡问题内容与要求内容与要求 1、理解运输问题的数学模型： 产销平衡，产大于销和产小于销及其转化。 2、了解产销平衡的运输问

2、题模型的特点： 约束方程、系数矩阵、基变量个数及最优解的存在性。 3、掌握运输问题的求解（重点和难点）： 表上作业法（单纯形法）及其步骤； 初始基可行解的确定：最小元素法和伏格尔法。 检验数的计算方法：位势法和闭回路法及最优解的判别。 闭回路调整法。 4、掌握退化解的处理。 5、理解产销不平衡时的求解。 2 2 表上作业法表上作业法 （一）最小元素法（一）最小元素法 （二）伏格尔法（二）伏格尔法 1 1 运输问题的数学模型运输问题的数学模型 问题的提出问题的提出 一般的运输问题就是要解决把某种产品一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产从若干个产地调运到若干个销

3、地，在每个产地的供应量与每个销地的需求量已知，并知地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。一个使得总的运输费用最小的方案。 在经济建设中，经常碰到大宗物在经济建设中，经常碰到大宗物资调运问题。根据已有的交通网资调运问题。根据已有的交通网, ,应如何应如何制定调运方案，将这些物资从产地运往制定调运方案，将这些物资从产地运往销地，使总运费最小。销地，使总运费最小。1 1 运输问题的数学模型运输问题的数学模型 问题：问题： 已知有已知有m m个产地个产地A Ai i（i=1,2,i=1,2,m,

4、m）, ,可供应可供应某种物资（如土石方）某种物资（如土石方）, ,其供应量（产量，其供应量（产量，挖方）分别为挖方）分别为a ai i； 有有n n个销地个销地B Bj j（j=1,2,j=1,2,n,n）, ,其需要量其需要量（填方）分别为（填方）分别为b bj j。从。从A Ai i到到B Bj j运输单位物运输单位物资的运价（单价）为资的运价（单价）为c cijij，这些数据见表，这些数据见表 3-13-1，3-2 3-2 。若在产销平衡条件下，求总运。若在产销平衡条件下，求总运费最少的调运方案。费最少的调运方案。表表4-14-1： 产销产销平衡表平衡表 销地销地产地产地B B1 1

5、B B2 2 B Bn n产量产量A A1 1A A2 2A Am m a a1 1a a2 2a am m 销量销量b b1 1 b b2 2 b bn n表表4-24-2： 单位单位运价表运价表 销地销地产地产地B1 B2 BnA1A2Amc11 c12 c1nc21 c22 c2n cm1 cm2 cmn 销地销地产地产地B B1 1 B B2 2 B Bn n产量产量A A1 1A A2 2A Am m c c1111 c c12 12 c c1n1nc c21 21 c c22 22 c c2n2n c cm1 m1 c cm2 m2 c cmnmna a1 1a a2 2 a am

6、 m 销量销量b b1 1 b b2 2 b bn n平衡表及单位运价表平衡表及单位运价表运输问题建模运输问题建模 销地销地产地产地B B1 1 B B2 2 B Bn n产量产量A A1 1A A2 2A Am mX11 x12 x1nx21 x22 x2n xm1 xm2 xmna1a2 am 销量销量b1 b2 bn平衡运输问题数学模型平衡运输问题数学模型minjijijxcz11min x11+ x21+ + xm1=b1x12+ x22+ + xm2=b2X1n+ x2n+ + xmn=bnXij 0；i=1,2,m;j=1,nmiinjjab11x11+ x12+ + x1n=a1

7、x21+ x22+ + x2n=a2xm1+ xm2+ + xmn=am 数学模型数学模型（产销平衡）（产销平衡）minjijijxcz11minnjmixnjbxmiaxijjmiijinjij.1;.1; 0) 2 . 3 (, 2 , 1,) 1 . 3 (, 2 , 1,11njjmiiba11 容易看出系数矩阵容易看出系数矩阵A A有如下的特征有如下的特征： 1 1）A A有有m m* *n n列列；每列有；每列有m+nm+n个元素，其中只有两个个元素，其中只有两个元素为元素为1 1，其余均为零。即，其余均为零。即x xijij的系数列向量为：的系数列向量为： P Pijij=(0=

8、(00 1 00 1 00 1 00 1 00)0)T T=e=ei i+e+em+jm+j x11 x12x1n x21 x22 x2n xm1 xm2 xmn A=111111111111111111nm21212 2）A A有有m+nm+n行。行。前前m m行：每行有行：每行有n n个个1 1，且这，且这些些1 1是连在一起的，其余为零；而后是连在一起的，其余为零；而后n n行行每行有每行有m m个个1 1，且分散排列，其余为零。，且分散排列，其余为零。 miinjmiijminjijmijaxxb111111 所以模型最多只有所以模型最多只有m+n-1m+n-1个独立约束个独立约束方程

9、。方程。 即系数矩阵的秩即系数矩阵的秩:R(A)m+n-1:R(A)m+n-1。 经证明：经证明： R(A)= m+n-1R(A)= m+n-1由于有以上特征，所以求解运输问由于有以上特征，所以求解运输问题时，可用比较简便的计算方法，题时，可用比较简便的计算方法，习惯上称为表上作业法。习惯上称为表上作业法。 2 2 表上作业法表上作业法 表上作业法是单纯形法在求解运输问题时的表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法。但具体一种简化方法，其实质是单纯形法。但具体计算和术语有所不同。可归纳为：计算和术语有所不同。可归纳为：（1 1） 找出初始基可行解。即在找出初始基可行

10、解。即在(m(mn)n)产销平衡产销平衡表上给出表上给出m+n-1m+n-1个个数字格数字格。（2 2） 求各非基变量的检验数，即在表上计算求各非基变量的检验数，即在表上计算空格空格的检验数。判别是否达到最优解，如果是的检验数。判别是否达到最优解，如果是最优解，则停止计算，否则转入下一步。最优解，则停止计算，否则转入下一步。（3 3） 确定换入变量和换出变量，找出新的基确定换入变量和换出变量，找出新的基可行解，在表上用闭回路法调整。可行解，在表上用闭回路法调整。重复（重复（2 2），（），（3 3）直到得到最优解为止）直到得到最优解为止。2.1 2.1 确定初始基可行解确定初始基可行解这与一般

11、线性规划问题不同，产销平这与一般线性规划问题不同，产销平衡的运输问题衡的运输问题总是存在可行解总是存在可行解。 因有：因有： dabmiinjj11必存在必存在x xijij0 ,i=1,0 ,i=1,m,j=1,m,j=1,n,n是可行解。又因是可行解。又因0 x0 xijijmin(amin(ai i,b,bj j) ) 故运输问题的可行解和最优解必存在故运输问题的可行解和最优解必存在。 确定初始可行解的方法有很多，一般希望确定初始可行解的方法有很多，一般希望的方法即简便又尽可能接近最优解。下的方法即简便又尽可能接近最优解。下面介绍两种方法：面介绍两种方法：最小元素法和伏格尔最小元素法和伏

12、格尔（VogelVogel）法）法。（其它如西北角法等）（其它如西北角法等） （一）最小元素法（一）最小元素法1.基本思想基本思想:就近供应；就近供应；即从单位运价表中最小即从单位运价表中最小的运价开始确定供应关系，然后次的运价开始确定供应关系，然后次小。直到求出初始可行解为止。小。直到求出初始可行解为止。2.举例：举例：P94 例例1 某公司经销甲产品，它下设三个加工某公司经销甲产品，它下设三个加工厂。每日的产量分别为：厂。每日的产量分别为： A A1 17 7吨吨，A A2 24 4吨，吨，A A3 39 9吨吨。该公司把这些产品分别运往四个销售该公司把这些产品分别运往四个销售点。各销售点

13、每日的销量为：点。各销售点每日的销量为：B B1 13 3吨，吨，B B2 26 6吨，吨，B B3 35 5吨，吨，B B4 46 6吨。已知从各工厂到各销售点的单位吨。已知从各工厂到各销售点的单位产品的运价为表产品的运价为表3-33-3所示，问该公司应所示，问该公司应如何调运产品，在满足各销点的需要如何调运产品，在满足各销点的需要量的前提下，使总运费为最少量的前提下，使总运费为最少。 销地销地加工厂加工厂B B1 1B B2 2B B3 3B B4 4产量产量A A1 1A A2 2A A3 3 3 31 17 711119 94 43 32 2101010108 85 57 74 49

14、9 销量销量3 36 65 56 6表表4-34-3：单位：元单位：元/ /吨吨表表4-4: 4-4: 产销平衡表产销平衡表 单位：吨单位：吨 销地销地加工厂加工厂B B1 1B B2 2B B3 3B B4 4产量产量A A1 1A A2 2A A3 3 7 74 49 9 销量销量3 36 65 56 6解解: :先给出这问题的运价表和产销平衡表先给出这问题的运价表和产销平衡表 销地销地加工厂加工厂B B1 1B B2 2B B3 3B B4 4A A1 1A A2 2A A3 3 3 31 17 711119 94 43 32 2101010108 85 5 单位运价表单位运价表 单位：

15、元单位：元/ /吨吨第一步：从表第一步：从表4-34-3中找出最小运价为中找出最小运价为1 1，这表示，这表示先将先将A A2 2的产品供应给的产品供应给B B1 1。因。因a a2 2b b1 1，A A2 2除满足除满足B B1 1的全部需要外，还可多余的全部需要外，还可多余1 1吨产品。在表吨产品。在表3-43-4的的( (A A2 2，B B1 1) )的交叉格处填上的交叉格处填上3 3。得表。得表4-54-5。并将表。并将表3-33-3的的B B1 1列运价划去。得表列运价划去。得表4-64-6。第二步：在表第二步：在表4-64-6未划去的元素中再找出最未划去的元素中再找出最小运价小

16、运价2 2，确定，确定A A2 2多余的多余的1 1吨供应吨供应B B3 3，并给，并给出表出表4-74-7，表，表4-84-8。销 地 加工厂 B1 B2 B3 B4 A1 A2 A3 3 1 7 11 9 4 3 2 10 10 8 5 （二）伏格尔法（二）伏格尔法 最小元素法的缺点是：为了节省一处最小元素法的缺点是：为了节省一处的费用，有时造成在其它处要多花几的费用，有时造成在其它处要多花几倍的运费。伏格尔法考虑到，一产地倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应的产品假如不能按最小运费就近供应就考虑次小运费，这就有一个差额，就考虑次小运费，这就有一个差额，差额越大

17、，说明如果不按最小运费调差额越大，说明如果不按最小运费调运时，运费增加越多。因而对差额最运时，运费增加越多。因而对差额最大处，就应当采用最小运费大处，就应当采用最小运费。 伏格尔法的步骤伏格尔法的步骤 第一步第一步：在单位运价中分别计算出各：在单位运价中分别计算出各行和各列的最小运费和次小运费的差行和各列的最小运费和次小运费的差额，并填入该表的最右列和最下行。额，并填入该表的最右列和最下行。第二步第二步：从行或列差额中选出最大者，从行或列差额中选出最大者，由其对应的最小元素确定供应关系由其对应的最小元素确定供应关系。第三步第三步：重复：重复第一，第二，第一，第二，直到求出直到求出初始可行解为止

18、初始可行解为止表表4-10 伏格尔法伏格尔法 销地销地加工厂加工厂B1B2B3B4行差额行差额A1A2A317119432101085011 列差额列差额2513表表4-13：伏格尔法求得的解伏格尔法求得的解 销地销地加工厂加工厂 B B1 1B B2 2B B3 3B B4 4产量产量A A1 1A A2 2A A3 33 36 65 52 21 13 37 74 49 9销量销量3 36 65 56 6 从以上可见：伏格尔法同最小元从以上可见：伏格尔法同最小元素法除在确定供求关系的原则上素法除在确定供求关系的原则上不同外，其余步骤相同。不同外，其余步骤相同。伏格尔伏格尔法给出的初始解比用最

19、小元素法法给出的初始解比用最小元素法给出的初始解更接近最优解。给出的初始解更接近最优解。实际上本例用伏格尔法给出的实际上本例用伏格尔法给出的初始解就是最优解。初始解就是最优解。 2.2 2.2 最优解的判别最优解的判别因运输问题的目标函数是要求实现因运输问题的目标函数是要求实现最小化，故：最小化，故：当所有的当所有的c cijij-C-CB BB B-1-1P Pijij00时时，为最优解为最优解。下面介绍两种求检验数的方法下面介绍两种求检验数的方法。方法方法：是计算空格（非基变量）的：是计算空格（非基变量）的检验数检验数c cijij-C-CB BB B-1-1P Pij ij , i,jN

20、., i,jN.（一）闭回路法（一）闭回路法 闭回路：闭回路：由某空格和有关（相关）数字由某空格和有关（相关）数字格为顶点所组成的一个封闭的多边形。格为顶点所组成的一个封闭的多边形。 它是以该空格为起点，用水平或垂直线它是以该空格为起点，用水平或垂直线向前划向前划, ,每碰到一每碰到一相关相关数字格转数字格转90900 0后后（中间可以跳过某数字（中间可以跳过某数字) )，继续前进，继续前进，直到回到起始空格为止。直到回到起始空格为止。结论结论：每一空格：每一空格一定存在唯一一定存在唯一的闭回路。的闭回路。空格空格检验数：检验数：就是当某一空格调入单位运就是当某一空格调入单位运输量时，经平衡调

21、整后，使目标函数值增输量时，经平衡调整后，使目标函数值增加（减少）的改变值。加（减少）的改变值。表表4-14 销地销地加工厂加工厂B1B2B3B4产量产量A1A2A3 33 1 64 31 233749销量销量3656+- 如果规定该空格为第如果规定该空格为第1 1个顶点，闭回路的个顶点，闭回路的其他顶点依次为第其他顶点依次为第2 2个顶点、第个顶点、第3 3个顶个顶点点，那么就有：，那么就有： ijij = ( = (闭回路上的奇数次顶点单位运价之和闭回路上的奇数次顶点单位运价之和) ) ( (闭回路上的偶数次顶点单位运价之和闭回路上的偶数次顶点单位运价之和) ) 其中其中 ijij 为非基

22、变量（空格）的下角指为非基变量（空格）的下角指标标 按以上所述，可找出所有空格的检验数，按以上所述，可找出所有空格的检验数，见表见表3-153-15。当检验数还存在负数时，说明当检验数还存在负数时，说明原方案不是最优解原方案不是最优解，改进方法见，改进方法见2.32.3。 闭回路闭回路表表4-15 空格空格闭回路闭回路检验数检验数11111212222224243131333311-13-23-21-1111-13-23-21-1112-14-34-32-1212-14-34-32-1222-23-13-14-34-32-2222-23-13-14-34-32-2224-23-33-14-24

23、24-23-33-14-2431-34-14-13-23-21-3131-34-14-13-23-21-3133-34-14-13-3333-34-14-13-331 12 21 1-1-110101212（二）、位势（二）、位势法法 用闭回路法求检验数时，需给每一空格用闭回路法求检验数时，需给每一空格找一闭回路。当产销点很多时，这种方找一闭回路。当产销点很多时，这种方法很繁。下面介绍较为简便的方法法很繁。下面介绍较为简便的方法位势法位势法。 设设u u1 1,u,u2 2, ,u,um m;v;v1 1,v,v2 2, ,v,vn n是对应运输问是对应运输问题的题的m+nm+n个约束条件的对

24、偶变量。由线性个约束条件的对偶变量。由线性规划的对偶理论可知：规划的对偶理论可知： C CB BB B-1-1 =Y=(u =Y=(u1 1,u,u2 2, ,u,um m,v,v1 1,v,v2 2, ,v,vn n) ) 又已知运输问题的每个变量又已知运输问题的每个变量x xijij的系数列的系数列向量向量P Pijij=e=ei i+e+em+jm+j , , 所以有：所以有： C CB BB B-1-1P Pijij=u=ui i+v+vj j 于是检验数：于是检验数： ijij=c=cijij-C-CB BB B-1-1P Pijij=c=cijij-( u-( ui i+v+vj

25、j) ) 由单纯形法知由单纯形法知: : 所有基变量的检验数等于零。所有基变量的检验数等于零。 即：即：c cijij-(u-(ui i+v+vj j)=0)=0, , i=1,2, i=1,2,m,j=1,2,m,j=1,2,n.(m+n-1,n.(m+n-1个方程，个方程，m+nm+n个未知数）个未知数） x13 c13-(u1+v3)=0 即即 3-（u1+v3）=0 x14 c14-(u1+v4)=0 即即 10-（u1+v4）=0 x21 c21-(u2+v1)=0 即即 1-（u2+v1）=0 x23 c23-(u2+v3)=0 即即 8-（u2+v3）=0 x32 c32-(u3

26、+v2)=0 即即 4-（u3+v2）=0 x34 c34-(u3+v4)=0 即即 5-（u3+v4）=0基变量基变量 检验数检验数例如：在例例如：在例1 1的用最小元素法得到的初始解的用最小元素法得到的初始解中中x x2424,x,x3434,x,x2121,x,x3232,x,x1313,x,x1414是基变量，这时对应是基变量，这时对应的检验数是：的检验数是：位势法位势法 从以上从以上6 6个方程个方程7 7个未知数可知：该方程个未知数可知：该方程组有无穷个解。组有无穷个解。 令令u u1 1= 0,= 0,可得：可得：u u2 2= -1, u= -1, u3 3= -5,= -5,

27、 v v1 1=2, v=2, v2 2=9, v=9, v3 3=3, v=3, v4 4=10=10 因非基变量的检验数因非基变量的检验数 ijij= c= cijij-( u-( ui i+v+vj j) i,jN) i,jN 所以由已知所以由已知的的u ui i, v, vj j就可求得。这些计就可求得。这些计算可在表格中进行。以例算可在表格中进行。以例1 1说明。说明。 先令先令u u1 1=0=0，然后按基变量的检验数为，然后按基变量的检验数为0 0，可，可确定出各确定出各u ui i，v vj j. .再按：再按： ijij= =c cijij ( (u ui i+ +v vj

28、j),), i i, ,j jN N 计算所有空格的检验数如下表计算所有空格的检验数如下表3-183-18： 由于还有负的检验数。说明未得由于还有负的检验数。说明未得到最优解，还可以改进。到最优解，还可以改进。2.3 2.3 改进的方法改进的方法闭回路调整法闭回路调整法 当在表中空格处出现负检验数时，表明未得最优解。当在表中空格处出现负检验数时，表明未得最优解。若有两个和两个以上的负检验数时，一般选其中最小若有两个和两个以上的负检验数时，一般选其中最小的负检验数，以它对应的空格为调入格。即以它对应的负检验数，以它对应的空格为调入格。即以它对应的非基变量为换入变量。由表的非基变量为换入变量。由表

29、4-184-18得得(2(2，4)4)为调入格。为调入格。以此格为出发点，作一闭回路，如表以此格为出发点，作一闭回路，如表4-194-19所示。所示。调整后如表调整后如表4-204-20： 销地销地产地产地B1B2B3B4产量产量A1A2A33 65213749销量销量3656再用闭回路法或位势法求（非基再用闭回路法或位势法求（非基变量的）检验数如表变量的）检验数如表4-214-21 销地销地产地产地B1B2B3B4A1A2A30922112因表因表3-213-21中所有检验数都中所有检验数都00，所，所以表以表3-203-20中的方案为最优方案。中的方案为最优方案。2.4 2.4 表上作业法

30、计算中的问题表上作业法计算中的问题（2 2） 退化退化当基可行解中有基变量为零时，则称该基可行当基可行解中有基变量为零时，则称该基可行解为退化解为退化( (基可行基可行) )解解; ;1 1） 求初始解时求初始解时; ; 例例P P1031032 2） 闭回路调整法调整时闭回路调整法调整时. . 见补例见补例 出现退化解时出现退化解时特别注意特别注意: :在相应的单元格中在相应的单元格中要填上数字要填上数字0,0,表示它为基变量表示它为基变量. .（1 1） 无穷多最优解无穷多最优解当最优表中非基变量的检验数有零时，则有当最优表中非基变量的检验数有零时，则有无穷多最优解。无穷多最优解。例例P1

31、03P103：求初始解时，当在中：求初始解时，当在中间同时划去一行和一列时间同时划去一行和一列时 销地销地加工厂加工厂B1B2B3B4产量产量A1A2A3 37111724310586749 销量销量3656 退化补例退化补例销销厂厂B B1 1B B2 2B B3 3B B4 4产量产量A A1 13 33 31 17 7A A2 23 33 3A A3 33 36 69 9销量销量3 36 64 46 6销销厂厂B1B2B3B4A1000-2A2-1-10-3A3110140 检验数表：检验数表：方案表：方案表：3 3 产销不平衡问题产销不平衡问题 1 1、 产大于销（相当于虚设一个销地）

32、产大于销（相当于虚设一个销地） 2 2、 产小于销（相当于虚设一个产地产小于销（相当于虚设一个产地） 1 1、产大于销、产大于销njjmiiba11minjijijxcZ11minx11+ x12+ + x1na1 x21+ x22+ + x2na2 xm1+ xm2+ + xmn am x11+ x21+ + xm1=b1x12+ x22+ + xm2=b2x1n+ x2n+ + xmn=bnxij 0数学模型数学模型：1、 产大于销的转换（相当于虚设一个销地）产大于销的转换（相当于虚设一个销地）x11+ x12+ + x1n + x1n+1 =a1x21+ x22+ + x2n + x2n

33、+1 =a2xm1+ xm2+ + xmn + xmn+1 =am x11+ x21+ + xm1=b1x12+ x22+ + xm2=b2x1n+ x2n+ + xmn=bnx1n+1+ x2n+1+ + xmn+1=bn+1= xij 0 minjijijxc11minnjjmiiba11产大于销的产大于销的表格模型表格模型转换转换 销地销地产地产地B B1 1 B B2 2 B Bn n B Bn+1n+1 产量产量A A1 1A A2 2A Am mc c11 11 c c12 12 c c1n 1n 0 0c c21 21 c c22 22 c c2n 2n 0 0 0 0 c cm

34、1 m1 c cm2 m2 c cmnmn 0 0a a1 1a a1 1a am m销量销量b b1 1 b b2 2 bn bn b bn+1n+1销大于产销大于产miinjjab11minjijijxcZ11minx11+ x12+ + x1n = a1x21+ x22+ + x2n = a2xm1+ xm2+ + xmn = am x11+ x21+ + xm1 b1x12+ x22+ + xm2 b2x1n+ x2n+ + xmn bnxij 0数学模型数学模型：2 2、销大于产的转换、销大于产的转换 minjijijxc11minx11+ x12+ + x1n =a1 xm1+ x

35、m2+ + xmn =amxm+11+ xm+12+ + xm+1n =am+1= x11+ x21+ + xm1 + xm+11 =b1 x1n+ x2n+ + xmn + xm+1n =bn xij 0miinjjab11销大于产的表格模型转换销大于产的表格模型转换 销地销地产地产地B B1 1 B B2 2 B Bn n产量产量A1A2AmAm+1c11 c12 c1nc21 c22 c2n cm1 cm2 cmn 0 0 0a a1 1a a1 1a am ma am+1m+1销量销量例例: : 产大于销产大于销 销地销地产地产地 B1B2B3B4产量产量A1A2A3 2107 113

36、8351492757 销量销量23461915例：例： 产大于销产大于销 销地销地加工厂加工厂B1B2B3B4产量产量A1A2A3 317 1194321010852049 销量销量3656解解 化为产销平衡的问题化为产销平衡的问题 销地销地加工厂加工厂B1B2B3B4B5产量产量A1A2A3 317 1194321010850002049 销量销量365613例：例： 销大于产销大于产 销地销地加工厂加工厂B1B2B3B4产量产量A1A2A3 317 119432101085749 销量销量31656解：化为产销平衡的问题解：化为产销平衡的问题 销地销地加工厂加工厂B B1 1B B2 2B

37、 B3 3B B4 4产量产量A A1 1A A2 2A A3 3 A A4 43 31 17 7 0 011119 94 40 03 32 210100 010108 85 50 07 74 49 9 1010销量销量3 316165 56 6例例2 2 设有三个化肥厂设有三个化肥厂(A(A，B B，C)C)供应四个地供应四个地区区(，)的农用化肥。假定等量的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂的化肥在这些地区使用效果相同。各化肥厂年产量，各地区年需要量及从各化肥厂到各年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价如表地区运送单位化肥的运价如表4-254-2

38、5所示。试所示。试求出总的运费最节省的化肥调拨方案。求出总的运费最节省的化肥调拨方案。例例2 解：解：这是一个产销不平衡的运输问题，总产量为这是一个产销不平衡的运输问题，总产量为160160万吨，四个地区的最低需求为万吨，四个地区的最低需求为110110万吨，最高需求为万吨，最高需求为无限。根据现有产量，第无限。根据现有产量，第个地区每年最多能分配到个地区每年最多能分配到6060万吨，这样最高需求为万吨，这样最高需求为210210万吨，大于产量。为了万吨，大于产量。为了求得平衡，在产销平衡表中增加一个假想的化肥厂求得平衡，在产销平衡表中增加一个假想的化肥厂D D，其年产量为其年产量为5050万

39、吨。由于各地区的需要量包含两部分，万吨。由于各地区的需要量包含两部分，如地区如地区，其中，其中3030万吨是最低需求，故不能由假想化万吨是最低需求，故不能由假想化肥厂肥厂D D供给，令相应运价为供给，令相应运价为M(M(任意大正数任意大正数) )，而另一部，而另一部分分2020万吨满足或不满足均可以，因此可以由假想化肥万吨满足或不满足均可以，因此可以由假想化肥厂厂D D供给，按前面讲的，令相应运价为供给，按前面讲的，令相应运价为0 0。对凡是需求。对凡是需求分两种情况的地区，实际上可按照两个地区看待。这分两种情况的地区，实际上可按照两个地区看待。这样可以写出这个问题的产销平衡表样可以写出这个问题的产销平衡表( (表表4-26)4-26)和单位运和单位运价表价表( (表表4-27)4-