第五章运输问题及解法课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章 运输问题,一.运输问题的一般提法,在经济建设中，经常碰到物资调拨中的运输问题。,例如,煤、钢材、粮食、木材等物资，在全国都有若干生产基地，分别将这些物资调到各消费基地去，应如何制定调运方案，使总的运输费用最少？,第五章 运输问题一.运输问题的一般提法,1,运输问题的一般提法是：,1.,产销平衡问题,运输问题的一般提法是：1.产销平衡问题,2,2.产销不平衡问题,此时分为两种情形来考虑：,供不应求,：即产量小于销量时有,供过于求,：即产量大于销量时有,2.产销不平衡问题此时分为两种情形来考虑：,3,二.运输问题的模型,产销平衡问题模型,二.运输问题的模型产销平衡问题模型,4,将约束方程式展开可得,约束方程式中共mn个变量，m+n个约束。,将约束方程式展开可得约束方程式中共mn个变量，m+n个约束。,5,第五章运输问题及解法课件,6,第五章运输问题及解法课件,7,2.m+n,个约束中有一个是多余的（因为其间含有一个平衡关系式 ）,所以,R(A)=m+n-1,，即解的,mn个变量中基变量,为m+n-1个。,2.m+n个约束中有一个是多余的（因为其间含有一个平衡关系式,8,三.运输问题的解法,运输问题仍然是线性规划问题，可以用线性规划法中的单纯形法来解决。但是：,1.运输问题所涉及的,变量多，造成单纯 形表太大；,2.,若把技术系数矩阵A中的0迭代成非0，会使问题更加复杂。,以上两个原因使得我们不得不利用运输问题的特点设计出它的特殊解法,表上作业法,。,三.运输问题的解法 运输问题仍然是线性规划问题，可以用线,9,表上作业法，实质上还是单纯形法。其步骤如下：,1.,确定一个初始可行调运方案。,可以通过最小元素法、Vogel 法来完成；,2.,检验当前可行方案是否最优,，常用的方法有闭回路法和位势法，用这两种方法计算出检验数，从而判别方案是否最优；,3.,方案调整,，从当前方案出发寻找更好方案，常采用闭回路法。,表上作业法，实质上还是单纯形法。其步骤如下：1.确定一个初始,10,（）运输问题的常用解法：,最小元素法,（确定初始方案）,闭回路法,（检验当前方案）,闭回路法,（方案调整）,以下面例题说明这种方法的具体步骤：,例12,：某食品公司下设3个加工厂A,1,，,A,2,，A,3,，和4个门市部B,1,，,B,2,，B,3,，B,4,。各加工厂每天的产量、各门市部每天的销售量以及从各加工厂到各门市部的运价如下表所示。,问：该公司应如何调运，在满足各门市部销售需要的情况下，使得运费支出为最少？,（）运输问题的常用解法：例12：某食品公司下设3个加工厂A,11,运输问题一般用表上作业法求解，需建立表格模型：,单位运价表,产销平衡表,用线性规划法处理此问题。设由产地i到销地j的运量为x,ij,，模型为：,min z=3x,11,+11x,12,+3x,13,+10 x,14,+x,21,+9x,22,+2x,23,+8x,24,+7x,31,+4x,32,+10 x,33,+5x,34,x,11,+x,12,+x,13,+x,14,=7,x,21,+x,22,+x,23,+x,24,=4,x,31,+x,32,+x,33,+x,34,=9,x,11,+x,21,+x,31,=3,x,12,+x,22,+x,32,=6,x,13,+x,23,+x,33,=5,x,14,+x,24,+x,34,=6,x,ij,0 (i=1,2,3;j=1,2,3,4),运输问题一般用表上作业法求解，需建立表格模型：单位运,12,给出初始调运方案最常用的方法,最小元素法,3,1,4,6,3,3,初始方案运费Z,0,=31+64+43+12+310+35=86(元),给出初始调运方案最常用的方法314633初始方案运费Z0=3,13,表上作业法要求，调运方案的数字格必须为m+n-1个，且所有数字格不构成闭回路。一般，用最小元素法给出的方案符合这一要求。,闭回路:从方案中某一始格出发，沿同行或同列前进，当遇到一个数字格时可以可转90度或继续前进，按此方法进行，直到回到始点的一个封闭曲线。同行或同列最多有两个点。,表上作业法要求，调运方案的数字格必须为m+n-,14,最小元素法中的退化情况,3,6,0,5,4,2,出现退化时，要在同时被划去的行列中任选一个空格填0，此格作为有数字格。,最小元素法中的退化情况360542 出现退化时，要在,15,找出任意空格的闭回路除此空格外，其余顶点均为有数格。如可找,（,A,1,B,1,）（,A,1,B,3,）（,A,2,B,3,）（,A,2,B,1,）；,2.检验,（闭回路法:计算空格的检验数）,计算出空格的检验数等于闭回路上由此空格起奇数顶点运价与偶数顶点运价的,代数和,。如,11,c,11,-,c,13,+,c,23,-,c,21,=1,3,1,4,6,3,3,找出任意空格的闭回路除此空格外，其余顶点均为有数格。如,16,计算出此空格的检验数,ij,若,ij,，则该方案为最优方案，否则转；,注：检验数的经济意义，以,11,为例，空格表示原方案中,X,11,=0,即A,1,B,1,的运输量为,0,。若试着运1单位，则这样所引起的总费用的变化恰是,11,，,可见检验数,ij,的意义是：,A,i,B,j,增运,单位所引起的总费用的增量。,ij,，说明若增运一单位则在总运输量不变情况下，总运费会增加。此时不应在,A,i,B,j,上增运。,计算出此空格的检验数ij,若ij，则该方案为最优方,17,3.调整:从,ij,为最大正值的空格出发.对其闭回路上的奇数顶点运量增加,偶数顶点的运量减少,(,这才能保证新的平衡,)，,其中,为该空格闭回路中偶数顶点的最小值。,24,=-10，,从（,A,2,B,4,）,出发其闭回路上,=1,，调整后得到一个新方案（如下表），运量为,=1,的,（,A,2,B,3,）变空格，得到新方案后再转,2。,11,=1，,12,=2,22,=1，,24,=-1,31,=10，,33,=12,3,1,4,6,3,3,3.调整:从ij 为最大正值的空格出发.对其闭回路上的奇数,18,经再计算新方案的检验数全部大于0。所以，该新方案为最优方案，可计算得总运费为85元。,注：若闭回路的偶数顶点中同时有两个格以上运量为,，,则调整后其中一个变空格，其余填0。（保证基变量个数不变）,3,6,1,3,2,5,经再计算新方案的检验数全部大于0。所以，该新方案为最优方案，,19,2.确定初始方案的方法之二伏格尔法（Vogel法）,求各行各列运价最小与次小之差额，选其中最大的行或列中最小运价进行供应；,如果某一行或某一列按照这种方法已被供应满，则划去该行或该列，在剩下的行列中重复这种方法，即得最优方案。,2.确定初始方案的方法之二伏格尔法（Vogel法）求各行,20,3,6,3,5,1,2,2,7,6,2,3635122762,21,3.求空格检验数的方法之二位势法,原理：设有运输问题,的对偶问题为,3.求空格检验数的方法之二位势法原理：设有运输问题的对偶问,22,3,1,4,6,3,3,3,10,1,2,4,5,仍以例一为例：对偶变量表面上是7个，实际上只有6个。有一个是自由变量。,3146333101245仍以例一为例：对偶变量表面上是,23,当找出,ij,0,的格后，调整方法仍用闭回路法。,位势法步骤：,由有数格c,ij,=,u,i,+v,j,求得,u,i,和v,j,（先令,u,1,=0,），,原有数格（基变量）的检验数,ij,=0,；空格,ij,=c,ij,(u,i,+v,j,)；,由此可得检验数表。,当找出ij0的格后，调整方法仍用闭回路法。位势法步骤：,24,（）产销不平衡的运输问题,1.产大于销的情况：,添加松弛变量,x,i,n+1,x,in+1,的定义：由A,i,向B,n+1,的运量，而B,n+1,并不存在，相当于增加了一个虚设的销地A,i,自己的仓库里，自己往自己的地方运，运费c,in+1,显然为0。实际上x,in+1,即A,i,的剩余量。,（）产销不平衡的运输问题1.产大于销的情况：添加松弛变量x,25,A,1,A,m,B,1,B,n,B,n+1,C,11,0,0,C,1n,C,m1,C,mn,产大于销的单位运价表,产大于销的产销量表,A,1,A,m,a,1,a,m,B,1,B,n,B,n+1,b,1,b,n,A1AmB1Bn Bn+1C1100C1n,26,2.,销大于产的情况：,添加松弛变量,x,m,+1j,同理，此时x,m+1j,的意义为销售短缺的量，同样，A,m+1,不存在，c,m+1j,为0。,2.销大于产的情况：添加松弛变量xm+1j同理，此时xm+1,27,销大于产的产销量表,A,1,A,m,a,1,a,m,B,1,B,n,b,1,b,n,A,m+1,A,1,A,m,B,1,B,n,C,11,0,0,C,1n,C,m1,C,mn,销大于产的单位运价表,A,m+1,销大于产的产销量表A1Ama1amB1Bnb1bnA,28,四 应 用 举 例,由于在变量个数相等的情况下，表上作业法的计算远比单纯形法简单得多。所以在解决实际问题时，人们常常尽可能把某些线性规划的问题化为运输问题的数学模型。下面介绍几个典型的例子。,四 应 用 举 例由于在变量个数相等的情况下，表上作业法的,29,例,3,某厂按合同规定须于当年每个季度末分别提供,10,，,15,，,25,，,20,台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表,3-29,所示。又如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护等费用,0.15,万元。要求在完成合同的情况下，作出使该厂全年生产,(,包括储存、维护,),费用最小的决策,。,例3 某厂按合同规定须于当年每个季度末分别提供10，15，,30,解 由于每个季度生产出来的柴油机不一定当季交货，所以设,x,ij,为第,i,季度生产的用于第,j,季度交货的柴油机数。根据合同要求，必须满足,解 由于每个季度生产出来的柴油机不一定当季交货，所以设xi,31,又每季度生产的用于当季和以后各季交货的柴油机数不可能超过该季度的生产能力，故又有：,又每季度生产的用于当季和以后各季交货的柴油机数不可能超过该季,32,第i季度生产的用于,j,季度交货的每台柴油机的实际成本,c,ij,应该是该季度单位成本加上储存、维护等费用。,c,ij,的具体数值见表3-30。,第i季度生产的用于j季度交货的每台柴油机的实际成本cij应该,33,设用,a,i,表示该厂第i季度的生产能力，,b,j,表示第i季度的合同供应量，则问题可写成：,设用ai表示该厂第i季度的生产能力，bj表示第i季度的合同供,34,显然，这是一个产大于销的运输问题模型。注意到这个问题中当,i,j,时，,x,ij,=0，所以应令对应的,c,ij,=,M,，再加上一个假想的需求,D,，就可以把这个问题变成产销平衡的运输模型，并写出产销平衡表和单位运价表(合在一起，见表3-31)。,显然，这是一个产大于销的运输问题模型。注意到这个问题中当i,35,经用表上作业法求解，可得多个最优方案，表3-32中列出最优方案之一。即第季度生产25台，10台当季交货，15台季度交货；季度生产5台，用于季度交货；季度生产30台，其中20台于当季交货，10台于季度交货。季度生产10台，于当季交货。按此方案生产，该厂总的生产(包括储存、维护)的费用为773万元。,经用表上作业法求解，可得多个最优方案，表3-32中列出最优方,36,例4 某航运公司承担六个港口城市A、B、C、D、E、F的四条固定航线的物资运输任务。已知各条航线的起点、终点城市及每天航班数见表3-33。,例4 某航运公司承担六个港口城市A、B、C、D、E、F的四,37,假定各条航线使用相同型号的船只，又各城市间的航程天数见表3-34。,假定各条航线使用相同型号的船只，又各城市间的航