第三章 运输问题讲义.ppt

第三章 运输问题,内容与要求,1、理解运输问题的数学模型： 产销平衡，产大于销和产小于销及其转化 2、了解产销平衡的运输问题模型的特点： 约束方程、系数矩阵、基变量个数及最优解的存在性 3、掌握运输问题的求解（重点和难点）： 表上作业法（单纯形法）及其步骤； 初始基可行解的确定：最小元素法和伏格尔法 检验数的计算方法：位势法和闭回路法及最优解的判别 闭回路调整法 4、掌握退化解的处理 5、理解产销不平衡时的求解§1 运输问题的数学模型,在经济建设中，经常碰到大宗物资调运问题根据已有的交通网,应如何制定调运方案，将这些物资从产地运往销地，使总运费最小这 样的问题可用以下数学语言描述：,已知有m个生产地点Ai,i=1,2,…,m.可供应某种物资（如土石方），其供应量（产量，挖方）分别为ai, i=1,2,…,m. 有n个销地Bj,j=1,2,…,n,其需要量（填方）分别为bj, j=1,2,…,n 从Ai到Bj运输单位物资的运价（单价）为cij， 这些数据可汇总于产销（平衡表）和单位运价表中，见表3-1，3-2,表3-1 运输平衡表,,表3-2 运价表,,,运 价表,运输问题建摸,运输问题要解决什么？ 什么叫一个运输方案？ 什么叫一个最优的运输方案？ 若用xij表示从Ai到Bj的运量，那么在产销平衡的条件下，求总运费最小的方案，,运输问题建模,可建立以下数学模型（产销平衡）,运输问题数学模型,x11+ x12+ …+ x1n=a1 x21+ x22+ …+ x2n=a2 … xm1+ xm2+ …+ xmn=am x11+ x21+ …+ xm1=b1 x12+ x22+ …+ xm2=b2 … X1n+ x2n+ …+ xmn=bn Xij ≥0,（产销不平衡）产大于销,x11+ x12+ …+ x1n≤a1 X21+ x22+ …+ x2n≤a2 … xm1+ xm2+ …+ xmn ≤ am x11+ x21+ …+ xm1=b1 x12+ x22+ …+ xm2=b2 … X1n+ x2n+ …+ xmn=bn Xij ≥0,（产销不平衡）销大于产,X11+ x12+ …+ x1n = a1 X21+ x22+ …+ x2n = a2 … Xm1+ xm2+ …+ xmn = am X11+ x21+ …+ xm1 ≤ b1 X12+ x22+ …+ xm2 ≤ b2 … X1n+ x2n+ …+ xmn ≤ bn Xij ≥0,这就是运输问题的数学模型。

它包含m×n个变量，m+n个约束方程其系数矩阵的结构比较松散且特殊x11 x12…x1n x21 x22 …x2n …xm1 xm2 …xmn,该系数矩阵中对应于xij的系数向量Pij,其分量中除第i个和第m+j个为1外，其余的都为零即 Pij=(0…0 1 0…0 1 0…0)T=ei+em+j 对产销平衡的运输问题，由于有以下关系式存在（总产量=总销量）,例,,所以模型最多只有m+n-1个独立约束方程即系数矩阵的秩≤m+n-1由于有以上特征，所以求解运输问题时，可用比较简便的计算方法习惯上称为表上作业法§2 表上作业法,表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法但具体计算和术语有所不同可归纳为： （1） 找出初始基可行解即在(m×n)产销平衡表上给出m+n-1个数字格 （2） 求各非基变量的检验数，即在表上计算空格的检验数判别是否达到最优解，如果是最优解，则停止计算，否则转入下一步 （3） 确定换入变量和换出变量，找出新的基可行解，在表上用闭回路法调整 重复（2），（3）直到得到最优解为止例1,某公司经销甲产品，它下设三个加工厂每日的产量分别为： A1——7吨，A2——4吨，A3——9吨。

该公司把这些产品分别运往四个销售点各销售点每日的销量为：B1——3吨，B2——6吨， B3——5吨，B4——6吨已知从各工厂到各销售点的单位产品的运价为表3-3所示，问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少解:先给出这问题的运价表和产销平衡表，见3-3(表3-4) ，3-4 表3-3 单位：元/吨,表3-4(3-3) 产销平衡表 单位：吨,2.1 确定初始基可行解,这与一般线性规划问题不同，产销平衡的运输问题总是存在可行解因有,必存在 0≤ xij,i=1,…,m,j=1,…,n 是可行解又因 0≤xij≤min(a1,bj) 故运输问题的可行解和最优解必存在 确定初始可行解的方法有很多，一般希望的方法即简便又尽可能接近最优解下面介绍两种方法：最小元素法和伏格尔（Vogel）法其它如西北角法等）,（一）最小元素法,这方法的基本思想是就近供应，即从单位运价表中最小的运价开始确定供应关系，然后次小一直到给出初始可行解为止以例1进行讨论运价表,第一步：从表3-3中找出最小运价为1，这表示先将A2的产品供应给B1,因a2b1,A2除满足B1的全部需要外，还可多余1吨产品。

在3-4的（A2,B1）的交叉处填上3得表3-5并将表3-3的B1列运价划去得表3-6表3-5,表3-6,第二步：在表3-6未划去的元素中在找出最小运价2，确定A2多余的1吨供应B3,并给出表3-7，表3-8,表3-7,表3-8,第三步：在表3-8未划去的元素中再找出运价3，这样一步步地进行下去，直到单位运价表中的所有元素划去为止最后在产销平衡表中得到一个调运方案，见表3-9，这方案的总费用为86元表3-9,用最小元素法给出的初始解是运输问题的基可行解但又可能在产销平衡表上填入一个数字后，在单位运价表上同时划去一行和一列这时就会出现退化，关于退化时的处理将在2.4中讲述二）伏格尔法,最小元素法的缺点是：为了节省一处的费用，有时造成在其它处要多花几倍的运费伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应就考虑次小运费，这就由一个差额，差额越大，说明按最小运费调运时，运费增加越多因而对差额最大处，就应当采用最小运费伏格尔法的步骤是：,第一步：在表3-3中分别计算出各行和各列的最小运费和次小运费的差额，并填入该表的最右列和最下行，见表3-10,表3-10 伏格尔法,从行或列差额中选出最大者，选择它所在行或列的最小元素。

在表3-10中B2列是最大差额所在列B2列中最小元素为4，可确定A3的产品先供应B2的需要得表3-11表3-11,同时将运价表中的B2列数字划去如表3-12所示第三步：对表3-12中未划去的元素在分别计算出各行、各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行重复第一、二步，直到给出初始解为止用此法给出例1的初始解列于表3-13表3-13,从以上可见：伏格尔法同最小元素法除在确定供求关系的原则上不同外，其余步骤相同伏格尔法给出的初始解比用最小元素法给出的初始解更接近最优解 实际上本例用伏格尔法给出的初始解就是最优解2.2 最优解的判别,判别的方法是计算空格（非基变量）的检验数cij-CBB-1Pij,i,j∈N.因运输问题的目标函数是要求实现最小化，故当所有的cij-CBB-1Pij≥0时，为最优解下面介绍两种求检验数的方法一）闭回路法,在给出初始调运方按的计算表上，如表3-13，从每一空格出发找一条闭回路它是以该一空格为起点，用水平或垂直线向前划,每碰到一数字格转900后（中间可以跳过某数字)，继续前进，直到回到起始空格为止实际上从每一空格出发一定存在和可以找到唯一的闭回路。

表3-14,,,,,,,,,,,,+,+,-,-,,,,,可见这调整的方案使运费增加 （+1）×3+（-1）×3+（+1）×2+（-1）×1=1（元） 这表明若这样调整运量将增加运费，将这个数填入（1，1）格，这就是检验数按以上所述，可找出所有空格的检验数，见表3-15当检验数还存在负数时，说明原方案不是最优解，改进方法见2.3表3-15,（二）、位势法,用闭回路法求检验数时，需给每一空格找一闭回路当产销点很多时，这种方法很繁下面介绍较为简便的方法——位势法 设u1,u2,…,um;v1,v2,…,vn是对应运输问题的m+n个约束条件的对偶变量B是含有一个人工变量xa的（m+n）×(m+n)初始基矩阵，人工变量xa在目标函数中的系数ca=0,,从线性规划的对偶理论可知： CBB-1=(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个方程， m+n个未知数）,例如：在例1的有最小元素法得到的初始解中x24,x34,x21,x32,x13,x14是基变量，xa为人工变量，这时对应的检验数是： 基变量 检验数 xa ca-u1=0 因ca=0所以u1=0 x24 c24-(u2+v4)=0即8-（u2+v4）=0 x34 c34-(u3+v4)=0即5-（u3+v4）=0 x21 c21-(u2+v1)=0即1-（u2+v1）=0 x32 c32-(u3+v2)=0即4-（u3+v2）=0 x13 c13-(u1+v3)=0即3-（u1+v3）=0 x14 c14-(u1+v4)=0即10-（u1+v4）=0,从以上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说明第一步,按最小元素法给出表3-9的初始解，作表3-16在对应表3-9的数字格处填如单位运价，见表3-16,表3-16,第二步：在表3-16上增加一行一列，在列中填入ui，在行中填入ui,得表3-17先令u1=0，然后按基变量的检验数cij- ui+vj=0相继地确定ui，vj.由表3-18可见由于还有负的检验数说明未得到最优解，还可以改进2.3 改进的方法——闭回路­调整法,选最小的检验数对应的空格为调入格(进基变量），以此格为出发点，作一闭回路然后进行调整如表3-19,表3-19,,,,,-,-,+,+,调整后如表3-20：,,在用闭回路法或位势法求（非基变量的）检验数如表3-21,2.4 表上作业法计算中的问题,（1） 无穷多最优解 当最优表中非基变量的检验数有零时，则有无穷多最优解 （2） 退化 当基可行解中有基变量为零时，则称该基可行解为退化(基可行)解; 1） 求初始解时，当在中间同时划去一行和一列时 2） 闭回路调整法调整时-1角上有两个以上达到最小值时. 3)出现退化解时特别注意:在相应的单元格中要填上数字0,表示它为基变量.,例：求初始解时，当在中间同时划去一行和一列时,最小元素法求初始基可行解,§3 产销不平衡问题,1、 产大于销（相当于虚设一个销地） 2、 产小于销（相当于虚设一个产地）,1、 产大于销（相当于虚设一个销地）,X11+ x12+ …+ x1n + x1n+1 =a1 X21+ x22+ …+ x2n + x2n+1 =a2 … Xm1+ xm2+ …+ xmn + xmn+1 =am X11+ x21+ …+ xm1=b1 X12+ x22+ …+ xm2=b2 … X1n+ x2n+ …+ xmn=bn X1n+1+ x2n+1+ …+ xmn+1=bn+1= Xij ≥0,2、销大于产（相当于虚设一个产地）,X11+ x12+ …+ x1n =a1 … Xm1+ xm2+ …+ xmn =am Xm。