第四章运输问题1.

第四章运输问题•§1运输问题的数学模型•§2表上作业法•2.1确定初始基可行解•（一）最小元素法•（二）伏格尔法•2.2最优解的判别•（一）闭回路法•（二）、位势法•2.3改进的方法——闭回路调整法•2.4表上作业法计算中的问题•§3产销不平衡问题内容与要求•1、理解运输问题的数学模型：–产销平衡，产大于销和产小于销及其转化。•2、了解产销平衡的运输问题模型的特点：–约束方程、系数矩阵、基变量个数及最优解的存在性。•3、掌握运输问题的求解（重点和难点）：–表上作业法（单纯形法）及其步骤；–初始基可行解的确定：最小元素法和伏格尔法。–检验数的计算方法：位势法和闭回路法及最优解的判别。–闭回路调整法。•4、掌握退化解的处理。•5、理解产销不平衡时的求解。•2表上作业法•（一）最小元素法•（二）伏格尔法§1运输问题的数学模型•问题的提出一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。在经济建设中，经常碰到大宗物资调运问题。根据已有的交通网,应如何制定调运方案，将这些物资从产地运往销地，使总运费最小。§1运输问题的数学模型•问题：已知有m个产地Ai（i=1,2,…,m）,可供应某种物资（如土石方）,其供应量（产量，挖方）分别为ai；有n个销地Bj（j=1,2,…,n）,其需要量（填方）分别为bj。从Ai到Bj运输单位物资的运价（单价）为cij，这些数据见表3-1，3-2。若在产销平衡条件下，求总运费最少的调运方案。表4-1：产销平衡表销地产地B1B2…Bn产量A1A2…Ama1a2…am销量b1b2…bn表4-2：单位运价表销地产地B1B2…BnA1A2…Amc11c12…c1nc21c22…c2n…………cm1cm2…cmn销地产地B1B2…Bn产量A1A2…Amc11c12…c1nc21c22…c2n…………cm1cm2…cmna1a2…am销量b1b2…bn平衡表及单位运价表运输问题建模销地产地B1B2…Bn产量A1A2…AmX11x12…x1nx21x22…x2n…………xm1xm2…xmna1a2…am销量b1b2…bn平衡运输问题数学模型minjijijxcz11minx11+x21+…+xm1=b1x12+x22+…+xm2=b2…X1n+x2n+…+xmn=bnXij≥0；i=1,2,…,m;j=1,…,nmiinjjab11x11+x12+…+x1n=a1x21+x22+…+x2n=a2…xm1+xm2+…+xmn=am•数学模型（产销平衡）minjijijxcz11minnjmixnjbxmiaxijjmiijinjij...1;...1;0)2.3(,,2,1,)1.3(,,2,1,11njjmiiba11•容易看出系数矩阵A有如下的特征：•1）A有m*n列；每列有m+n个元素，其中只有两个元素为1，其余均为零。即xij的系数列向量为：•Pij=(0…010…010…0)T=ei+em+jx11x12…x1nx21x22…x2n…xm1xm2…xmnA=111111111111111111nm21212）A有m+n行。前m行：每行有n个1，且这些1是连在一起的，其余为零；而后n行每行有m个1，且分散排列，其余为零。miinjmiijminjijmijaxxb111111•所以模型最多只有m+n-1个独立约束方程。•即系数矩阵的秩:R(A)≤m+n-1。•经证明：R(A)=m+n-1•由于有以上特征，所以求解运输问题时，可用比较简便的计算方法，习惯上称为表上作业法。§2表上作业法•表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法。但具体计算和术语有所不同。可归纳为：•（1）找出初始基可行解。即在(m×n)产销平衡表上给出m+n-1个数字格。（2）求各非基变量的检验数，即在表上计算空格的检验数。判别是否达到最优解，如果是最优解，则停止计算，否则转入下一步。•（3）确定换入变量和换出变量，找出新的基可行解，在表上用闭回路法调整。•重复（2），（3）直到得到最优解为止。2.1确定初始基可行解这与一般线性规划问题不同，产销平衡的运输问题总是存在可行解。因有：dabmiinjj11必存在xij≥0,i=1,…,m,j=1,…,n是可行解。又因0≤xij≤min(ai,bj)故运输问题的可行解和最优解必存在。确定初始可行解的方法有很多，一般希望的方法即简便又尽可能接近最优解。下面介绍两种方法：最小元素法和伏格尔（Vogel）法。（其它如西北角法等）（一）最小元素法1.基本思想:就近供应；即从单位运价表中最小的运价开始确定供应关系，然后次小。直到求出初始可行解为止。2.举例：P94例1•某公司经销甲产品，它下设三个加工厂。每日的产量分别为：•A1——7吨，A2——4吨，A3——9吨。该公司把这些产品分别运往四个销售点。各销售点每日的销量为：B1——3吨，B2——6吨，B3——5吨，B4——6吨。已知从各工厂到各销售点的单位产品的运价为表3-3所示，问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少。销地加工厂B1B2B3B4产量A1A2A3317119432101085749销量3656表4-3：单位：元/吨表4-4:产销平衡表单位：吨销地加工厂B1B2B3B4产量A1A2A3749销量3656解:先给出这问题的运价表和产销平衡表销地加工厂B1B2B3B4A1A2A3317119432101085单位运价表单位：元/吨销地加工厂B1B2B3B4产量A1A2A33749销量3656销地加工厂B1B2B3B4A1A2A3317119432101085第一步：从表4-3中找出最小运价为1，这表示先将A2的产品供应给B1。因a2＞b1，A2除满足B1的全部需要外，还可多余1吨产品。在表3-4的(A2，B1)的交叉格处填上3。得表4-5。并将表3-3的B1列运价划去。得表4-6。第二步：在表4-6未划去的元素中再找出最小运价2，确定A2多余的1吨供应B3，并给出表4-7，表4-8。销地加工厂B1B2B3B4产量A1A2A331749销量3656销地加工厂B1B2B3B4A1A2A3317119432101085（二）伏格尔法•最小元素法的缺点是：为了节省一处的费用，有时造成在其它处要多花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应就考虑次小运费，这就有一个差额，差额越大，说明如果不按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小运费。伏格尔法的步骤第一步：在单位运价中分别计算出各行和各列的最小运费和次小运费的差额，并填入该表的最右列和最下行。第二步：从行或列差额中选出最大者，由其对应的最小元素确定供应关系。第三步：重复第一，第二，直到求出初始可行解为止表4-10伏格尔法销地加工厂B1B2B3B4行差额A1A2A317119432101085011列差额2513表4-13：伏格尔法求得的解销地加工厂B1B2B3B4产量A1A2A3365213749销量3656•从以上可见：伏格尔法同最小元素法除在确定供求关系的原则上不同外，其余步骤相同。伏格尔法给出的初始解比用最小元素法给出的初始解更接近最优解。•实际上本例用伏格尔法给出的初始解就是最优解。2.2最优解的判别•因运输问题的目标函数是要求实现最小化，故：当所有的cij-CBB-1Pij≥0时，为最优解。下面介绍两种求检验数的方法。方法：是计算空格（非基变量）的检验数cij-CBB-1Pij,i,j∈N.（一）闭回路法•闭回路：由某空格和有关（相关）数字格为顶点所组成的一个封闭的多边形。•它是以该空格为起点，用水平或垂直线向前划,每碰到一相关数字格转900后（中间可以跳过某数字)，继续前进，直到回到起始空格为止。结论：每一空格一定存在唯一的闭回路。空格检验数：就是当某一空格调入单位运输量时，经平衡调整后，使目标函数值增加（减少）的改变值。表4-14销地加工厂B1B2B3B4产量A1A2A33316431233749销量3656++--•如果规定该空格为第1个顶点，闭回路的其他顶点依次为第2个顶点、第3个顶点……，那么就有：ij=(闭回路上的奇数次顶点单位运价之和)–(闭回路上的偶数次顶点单位运价之和)其中ij为非基变量（空格）的下角指标•按以上所述，可找出所有空格的检验数，见表3-15。当检验数还存在负数时，说明原方案不是最优解，改进方法见2.3。闭回路表4-15空格闭回路检验数11122224313311-13-23-21-1112-14-34-32-1222-23-13-14-34-32-2224-23-33-14-2431-34-14-13-23-21-3133-34-14-13-33121-11012（二）、位势法•用闭回路法求检验数时，需给每一空格找一闭回路。当产销点很多时，这种方法很繁。下面介绍较为简便的方法——位势法。•设u1,u2,…,um;v1,v2,…,vn是对应运输问题的m+n个约束条件的对偶变量。由线性规划的对偶理论可知：•CBB-1=Y=(u1,u2,…,um,v1,v2,…,vn)•又已知运输问题的每个变量xij的系数列向量Pij=ei+em+j,•所以有：CBB-1Pij=ui+vj•于是检验数：•σij=cij-CBB-1Pij=cij-(ui+vj)•由单纯形法知:•所有基变量的检验数等于零。•即：cij-(ui+vj)=0,i=1,2,…m,j=1,2,…,n.(m+n-1个方程，m+n个未知数）•x13c13-(u1+v3)=0即3-（u1+v3）=0•x14c14-(u1+v4)=0即10-（u1+v4）=0•x21c21-(u2+v1)=0即1-（u2+v1）=0•x23c23-(u2+v3)=0即8-（u2+v3）=0•x32c32-(u3+v2)=0即4-（u3+v2）=0•x34c34-(u3+v4)=0即5-（u3+v4）=0•基变量检验数•例如：在例1的用最小元素法得到的初始解中x24,x34,x21,x32,x13,x14是基变量，这时对应的检验数是：位势法•从以上6个方程7个未知数可知：该方程组有无穷个解。•令u1=0,可得：u2=-1,u3=-5,•v1=2,v2=9,v3=3,v4=10•因非基变量的检验数•σij=cij-(ui+vj)i,j∈N•所以由已知的ui,vj就可求得。这些计算可在表格中进行。以例1说明。先令u1=0，然后按基变量的检验数为0，可确定出各ui，vj.再按：σij=cij−(ui+vj),i,j∈N计算所有空格的检验数如下表3-18：销地产地B1B2B3B4uiA131=3-(0+2)112=11-(0+9)30=3-(0+3)100=10-(0+10)0A210=1-(-1+2)91=9-(-1+9)20=2-(-1+3)8-1=8-(-1+10)-1A3710=7-(-5+2)40=4-(-5+9)1012=10-(-5+3)50=5-(-5+10)-5vj29310•由于还有负的检验数。说明未得到最优解，还可以改进。2.3改进的方法——闭回路调整法•当在表中空格处出现负检验数时，表明未得最优解。若有两个和两个以上的负检验数时，一般选其中最小的负检验数，以它对应的空格为调入格。即以它对应的非基变量为换入变量。由表4-18得(2，4)为调入格。以此格为出发点，作一闭回路，如表4-19所示。销地产地B1B2B3B4产量A1A2A3364(+1)1(-1)3(-1)(+1)3749销量3656调整后如表4-20：销地产地B1B2B3B4产量A1A2A3365213749销量3656再用