第四章--运输问题(共12页).doc

精选优质文档-倾情为你奉上第四章 运输问题主要内容：1、运输问题及其数学模型； 2、表上作业法； 3、运输问题的进一步讨论。重点与难点：表上作业法的原理、求解步骤，产销不平衡运输问题的求解方法。要 求：理解运输问题的基本概念及表上作业法的原理，掌握表上作业法确定初始可行解、最优解的判别与改进的方法。§1 运输问题及其数学模型一、运输问题引例，设有m个生产地，可供应（产量）分别为;有n个销地其需要量分别为。已知从到运输单位物资的运价（单价）为，试问如何调运物资才能使总费用最小？设用表示从到的运量，可将这些数据汇总于下表：产销平衡表 销地产地 产量销量 单价运价表销地产地 注：有时将两表合二为一。（1）若各产地的总产量等于各销地的总销量，即，则称之为产销平衡的运输问题（或平衡运输问题）；（2）若所有产地的总产量不等于所有销地的总销量，即，则称之为产销不平衡的运输问题（或不平衡的运输问题）；（3）若在运输途中，还存在中间转运点（转运点即是产地，又是销地），则称之为有转运的运输问题（或扩大的运输问题）。二、平衡运输问题的数学模型在产销平衡的条件下，要求得总运费最小，可建立以下数学模型：该运输问题也属于线性规划问题，包括：（1）个决策变量；（2）m+n个约束条件；由于有，所以模型只有m+n1个独立约束条件，基变量中含有m+n1个变量；（3）系数矩阵的秩（4）系数矩阵为阶矩阵，该系数矩阵中对应于变量的系数向量，其分量中除第i个和第m+j个为1以外，其余的都为零。§2 表上作业法求解步骤：（1）找出初始可行解，即在产销平衡表上给出个数字格；（2）求各非基变量的检验数，即在表上计算空格的检验数。判别是否达到最优解，如已是最优解，则停止计算；（3）确定换入变量和换出变量，找出新的基可行解，在表上用闭回路法调整；（4）重复（2）、（3）直至得到最优解为止。例1 某公司有三个工厂生产一种产品，每日的产量分别为7T、4T、9T。该公司把这些产品运往四个销点，各销点的日销量为-3T、-6T、-5T、-6T。已知从各工厂到各销售点的单位产品的运价见下表。问该公司应如何调运产品，在满足各销点需要量的前提下，使总运费最少？单位运价表 单位：元/T销地加工厂311310192874105（二） 确定初始基可行解（初始调运方案）（一）最小元素法思路：就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小，直到给出初始基可行解为止。以例1为例进行讨论：第一步：从单位运价表中找出最小运价为1，表示先将的产品供应给。因，除满足全部需要外，还多余1T产品。在与的交叉格处填上3，并将列的运价划去。第二步：在未划去的元素中再找出最小运价2，确定多余的1吨供应，并将行的运价划去。第三步：在未划去的元素中划出最小运价3，直到单位运价表上的所有元素都划去为止，最后在产销平衡表上得到一个调运方案，空格为非基变量。单位运价表 单位：T销地加工厂311310192874105产销平衡表 单位：T销地加工厂产量437314639销量3656注意：（1）在用最小元素法确定初始方案时，在产销平衡表上每填一个数，在单位运价表上划去一行或一列（当产大于销时；划去元素所在列；当产小于销时，划去元素所在行）。运价表中有行和列，需要划+条线，填最后一个数划去一行和一列，这样共填上个数。（2）当在产销平衡表上填上某个数时，行和列都平衡，需在单位运价表上划去一行和一列（这就出现了退化问题），为保持个基变量，需在行或列的任一空格处填上零，表示该基变量取值为零。（二）伏格尔法思路：一产地的产品，假如不能按最小运费就近供应，就考虑次小运费，这样就要有一差额。差额越大，说明不能按最小运费调运时，运费增加越多，因而对差额最大处，就采用最小运费调运。第一步：计算各行和各列的最小运费和次小运费的差额销地加工厂行差额311310019281741051列差额2513第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元素，在上表中，列是最大差额所在列，列中最小元素为4，可确定的产品先供应的需要，同时将运价表中的列数字划去。单位运价表销地产地311310192874105产销平衡表销地产地产量7469销量3656第三步：对表中未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，重复第一、二步，直到给出初始解为止。最后结果见下表。产销平衡表销地产地产量527314639销量3656注意：（1）伏格尔法与最小元素法除确定供求关系的原则不同外，其余相同；（2）伏格尔法给出的初始解更接近最优解。二、最优解的判别判别方法：计算空格检验数，当时，为最优解。下面介绍两种求空格检验数的方法：（一）闭回路法在给出调运方案的表上，从每一空格出发找一条闭回路。它是以某一空格为起点。用水平或垂直线向前划，每碰到一数字格转90度后，继续前进，直到回到开始空格为止。对用最小元素法确定的方案：销地加工厂产量4373114639销量3656不是最优解，需要调整。（二）位势法（对偶变量法）设是对应运输问题的对偶变量，其中-行位势，-列位势。检验数所有基变量的检验数 即由此求出，再计算。第一步：在按最小元素法给出的初始解的数字处填入单位运价销地产地310012145529310第二步：在表上增加一行一列，填入。对基变量有 第三步：计算空格的可直接在表上进行销地产地3113100121928111741055101229310三、调整-闭回路法当<0时，表明未得到最优解，选取<0中最小的所对应的变量为进基变量，以此格为出发点，作一闭回路，确定调整量（其原理与单纯形法中按规则确定换出变量相同），然后，按闭回路上的正、负号，加入或减去此值，得到新的调运方案。检验表：销地产地12111012新调运方案：销地产地产量72+_7522143-1+92963销量3656对上表求空格的检验数，见上表。因为所有>0，所以此解为最优解，总费用的最小值z=85注意：（1）若对某方案所有，且有某一个=0，则此问题有无穷多最优解，（两个最优解的组合，也一定是最优解）。（2）在用闭回路法调整时，若有两个具有“-”标记的数同时为最小值，把其中一个作为调出变量，另一个仍为基变量，其值为0；若有某个有“-”标记的数为0，调整量为零，把此格作为空格，原空格处填入零。如：13调整后变为041114调整后变为1400§3 产销不平衡问题1、若产大于销，需增加一个假想的销地，各产地到此的运价都为零，该地的销量为。2、若产小于销，需增加一个假想的产地，由此到各销地的运价都为零，该地的产量为。例2 设有三个化肥厂供应四个地区同一种化肥，其产、销量和运价如下表，试求出总的运费最节省的化肥调拨方案。运价单位：万元/万吨需求地区化肥厂IIIIIIIV产量（万吨）ABC1614191313202219231715506050最低需求（万吨）最高需求（万吨）3050707003010不限解： 产销平衡表和单位运价表：销地产地IIIIIIIIVIV产量ABCD161419M1614190131320M22192301715MM1715M050605050销量302070301050初始调拨方案：销地产地IIIIIIIIVIV产量A2M-225050B30201060C005050D203050销量302070301050判别：计算空格。最优方案：销地产地IIIIIIIIVIV产量A5050B20103060C3020050D302050销量302070301050专心-专注-专业