运输问题的求解方法.ppt

4.1,线性规划及其单纯形求解方法,1.,线性规划的数学模型,线性规划之实例,线性规划的数学模型,*,第,3,节,运输问题的求解方法,表上作业法,产销平衡表与单位运价表,表上作业法,产销不平衡的运输问题的求解方法,一、产销平衡表与单位运价表,运输问题还可用,产销平衡表与单位运价表进行描述。,假设某种物资,有,m,个生产地点,A,i,（,i=1,，,2,，,，,m,），,其产量（供应量）分别为,a,i,（,i=1,，,2,，,，,m,），有,n,个销地,B,j,（,j,=1,，,2,，,，,n,），,其销量（需求量）分别,为,b,j,（,j,=1,，,2,，,，,n,）。从,A,i,到,B,j,运输单位物资的运价（单价）为,C,ij,。,将这些数据汇总可以得到产销平衡表和单位运价,表,5.3.1,。,销地,产地,产量,销量,表,5.3.1,产销平衡表与单位运价表,运输这一类特殊问题可用,更加简便的求解方法,表上作业法求解，实质仍是单纯形法，步骤如下：,（,1,）确定初始调运方案，即找出初始基可行解,在产销平衡表上给出,m,+,n,-1,个数字格,。,二、表上作业法,（,2,）求非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解：是否存在负的检验数？如果存在负的检验数，则初始调运方案不是最优方案；如果所有检验数都非负，则初始调运方案已经是最优方案了。如果已经得到最优调运方案，则停止计算，否则转入下一步。,（,3,）确定换入变量和换出变量，找出新的调运方案（新的基可行解），即在表上用闭回路法进行调整。,(,4,）重复（,1,）（,2,），直到求出最优解为止。,（一）,确定初始可行基的方法,最小元素法,从单位运价表中最小的运价开始确定供销关系，然后考虑运价次小的，一直到给出初始基可行解为止。,伏格尔法,采用最小元素法可能造成其他处的更多浪费，伏格尔法考虑最小运费与次小运费之间的差额，差额越大，就按次小运费调运。,（二）,最优解的判别,计算非基变量（空格）的检验数,当所有的检验数 时,，,为最优解。,求空格检验数的方法有：,闭回路法,以某一空格为起点找一条闭回路，用水平或垂直线向前划，每碰到一数字格转,90,0,后，继续前进，直到回到起始空格为止。,闭回路如图,5,.3.1,的（,a,）、（,b,）、（,c,）,等所示。,从每一个空格出发一定存在并且可以找到唯一的闭回路。,因为，,m,+,n,-,1,个数字格（基变量）对应的系数向量是一个基，任一空格（非基变量）对应的系数向量是这个基的线性组合。,图,5.3.1,闭回路示意图,举例说明：可表示为,而这些向量构成了闭回路见,图,位势法,一种较为简便的求检验数的方法。,设 是对应运输问题的,m,+,n,个约束条件的对偶变量。,B,是含有一个人工变量,X,a,的初始基矩阵。,X,a,在目标函数中的系数,C,a,，,由线性规划的对偶理论可知,而每一个决策变量,X,ij,的系数向量 ，所以,由单纯形法可知，所有基变量的检验数等于,0,，即,例,1,：假设某种物资共有,3,个产地，其日产量分别是：,A,1,为,7 t,，,A,2,为,4 t,，,A,3,为,9 t,；该种物资的,4,个销售地，其日销量分别：,B,1,为,3 t,，,B,2,为,6 t,，,B,3,为,5 t,，,B,4,为,6 t,；各产地到销售地的单位物资的运价如表,5.3.2,所示。在满足各销售点需要量的前提下，如何调运该种物资，才能使总运费达到最小？,销地,产地,B,1,B,2,B,3,B,4,A,1,A,2,A,3,3,1,7,11,9,4,3,2,10,10,8,5,表,5.3.2,下面用具体例子说明,表上作业法的计算步骤。,解：首先列出这一问题的产销平衡表，见表,5.3.3,。,表,5.3.3,某物资运输的产销平衡表,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,7,4,9,销量,3,6,5,6,用最小元素法求解,：,第,1,步，从表,5.3.4,中找出最小运价为,1,，表示应先将,A,2,的产品供应,B,1,。,在表,5.3.3,中（,A,2,B,1,）,的交叉格处填上,3,，得表,5.3.4,。将表,5.3.4,中的,B,1,列运价划去，得表,5.3.5,。,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,3,7,4,9,销量,3,6,5,6,表5.3.4,销地,产地,B,1,B,2,B,3,B,4,A,1,A,2,A,3,11,9,4,3,2,10,10,8,5,表5.3.5,第,2,步，在表,5.3.5,未划去的元素中再找出最小运价为,2,，确定,A,2,多余的,1 t,物资供应,B,3,。,得表,5.3.6,。将表,5.3.5,的行运价划去，得表,5.3.7,。,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,3,1,7,4,9,销量,3,6,5,6,表5.3.6,销地,产地,B,1,B,2,B,3,B,4,A,1,A,2,A,3,11,9,4,3,2,10,10,8,5,表5.3.7,第,3,步,，按照上述方法,直到单位运价表上的所有元素被划去为止。最后在产销平衡表上得到一个调运方案，即初始基可行解，见表,5.3.8,。,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,3,1,7,4,9,销量,3,6,5,6,表5.3.8,伏格尔法的步骤是：,第,1,步：在表,5.3.2,中分别计算出各行、各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行，见表,5.3.9,。,销地,产地,B,1,B,2,B,3,B,4,行差额,A,1,A,2,A,3,3,1,7,11,9,4,3,2,10,10,8,5,0,1,1,列差额,2,5,1,3,表5.3.9,第,2,步：从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表,5.3.9,中，可确定,A,3,的产品应首先供应,B,2,，,得表,5.3.10,。将单位运价表中的列的数字划去，得表,5.3.11,。,表5.3.10,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,6,7,4,9,销量,3,6,5,6,销地,产地,B,1,B,2,B,3,B,4,A,1,A,2,A,3,3,1,7,3,2,10,10,8,5,表5.3.11,第,3,步,对表,5.3.11,中余下的元素再分别计算出各行、各列的最小运费和次最小运费的差额，重复第,1,、第,2,步，直到给出初始基可行解为止。初始基可行解列于表,5.3.12,。,表,5.3.12,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,3,6,5,2,1,3,7,4,9,销量,3,6,5,6,伏格尔法给出的初始基可行解更接近最优解。本例中用伏格尔法给出的初始基可行解就是最优解。,用闭回路法判别检验,：,闭回路法计算检验数的经济解释为,在已给出初始基可行解的表中，可从任一空格出发，如（,A,1,B,1,），,若让,A,1,的产品调运,1 t,给,B,1,，,为了保持产销平衡，就要依次进行调整,就构成了以（,A,1,B,1,）,空格为起点，其他为数字格的闭回路，如表,5.3.13,中的虚线所示。闭回路各顶点所在格的右上角数字是单位运价。,表,5.3.13,调整的方案使运费增加,将“,1,”,填（,A,1,B,1,）,格中，这就是检验数。按上述办法，可找出所有空格的检验数，见表,5.3.14,。当检验数还有负数时，需要对原方案进行改造。,表,5.3.14,用位势法检验,:,第,1,步,按最小元素法给出表,5.3.8,的初始基可行解，作表,5.3.15,。在对应表,5.3.8,的数字格处填入单位运价。,销地,产地,B,1,B,2,B,3,B,4,A,1,A,2,A,3,1,4,3,2,10,5,表5.3.15,第,2,步,在上表增加一行一列，在列中填入 ，在行中填入 ，得表,5.3.16,。,销地,产地,B,1,B,2,B,3,B,4,A,1,A,2,A,3,1,4,3,2,10,5,0,-1,-5,2,9,3,10,表,5.3.16,首先令,u,1,=0,然后按 可确定所有和的数值。,第,3,步,按 计算所有空格的检验数，特设计计算表,5.3.17,。,表,5.3.17,改进的方法,闭回路调整法,:,在表,5.3.17,中，,(,A,2,B,4,),为调入格，以此格为出发点，作一闭回路,得表,5.3.18,。,表,5.3.18,格的调入量 是选择闭回路上具有（,-,1,）的数字格中的最小者即 ，然后，按闭回路上的正、负号，加、减此值得到调整方案，如表,5.3.19,所示。再用闭回路法或位势法求各空格的检验数，得表,5.3.20,。在表,5.3.20,中，因为所有检验数都非负，故得最优解，这时，得到最小运费为,85,（元）。,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,3,6,5,2,1,3,7,4,9,销量,3,6,5,6,销地,产地,B,1,B,2,B,3,B,4,A,1,A,2,A,3,0,9,2,2,1,12,表5.3.19,表5.3.20,三、产销不平衡的运输问题的求解方法,前面求解运输问题的表上作业法，是以产销平衡为前提的，即,实际情况需要把产销不平衡的问题化成产销平衡的问题。,当产大于销,运输问题的数学模型为求使,且满足,考虑多余的物资在哪一个产地就地储存的问题。设 是产地,A,i,的储存量，于是有,当 时，令,当 时，令,产销不平衡的运输问题就可以改写成：求,使,且满足,此时，,该问题变为产销平衡问题,，可用,表上作业法对其求解。,当销大于产时，只要在产销平衡表中增加一个假想的产地，让该地的产量为,并在单位运价表中令从假想的产地到各消费地的运价为 ，就可以将其转化为一个产销平衡的运输问题。然后可以用表上作业法对其求解,。,