运筹学-运输问题课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,2024/11/12,1,运筹学,OPERATIONS RESEARCH,2024/11/12,2,第三章 运输问题,运输问题的数学模型,表上作业法,产销不平衡的运输问题及应用,2024/11/12,3,1 运输问题的典例及数学模型,一、引例,某公司从三个产地 ，将产品运往四个销地 ，,，各产地的产量，各销地的销量，及各产地往各销,地的运费单价如表所示。应如何调运可使运费最小？,销地,运费单价,产地,B,1,B,2,B,3,B,4,产量（吨）,A,1,3,11,3,10,7,A,2,1,9,2,8,4,A,3,7,4,10,5,9,销量（吨）,3,6,5,6,2024/11/12,4,解：,从表中可知：总产量,=,总销量。这是一个产销平衡的,运输问题。假设 表示从产地 运往销地 的产,品数量，建立如下表格：,于是可建立如下的数学模型,：,销地,运费单价,产地,B,1,B,2,B,3,B,4,产量（吨）,A,1,3,11,3,10,7,A,2,1,9,2,8,4,A,3,7,4,10,5,9,销量（吨）,3,6,5,6,2024/11/12,5,目标函数,：,约束条件：,产量约束,销量约束,20,20,2024/11/12,6,设有,m,个产地，分别为,;,n,个销地，分别是 ；,从产地 运往销地 的单位运价是 ，运量,是产地 的产量；是销地 的销量。,二、,一般运输问题数学模型,则该运输问题的模型如下：,2024/11/12,7,说明,：当 时，称其为产销平衡的运输问题，,否则产销不平衡。,2024/11/12,8,说明,：从上述模型可以看出：,（,1,）这是一个线性规划的模型；,（,2,）变量有,m,n,个；,（,3,）约束条件有,m+n,个；,（,4,）,系数矩阵非常稀疏；系数矩阵的秩一般为（,m+n-1),而非,m+n,。,若直接用单纯形法求解，显然单纯形表比较庞大，于是在,单纯形法的基础上创建了表上作业法求解运输问题这一特,殊的线性规划问题,2024/11/12,9,从第一节的运输问题的数学模型可知，运输问题实际上,也属于线性规划，但由,于,运输问题的特殊性（变量个数较多，,系数矩阵的特点），如果用单纯形表格方法迭代，计算量很,大。今天介绍的,“,表上作业法,”,，是针对运输问题的特殊求解,方法，实质还是单纯形法，但减少了计算量。,表上作业法,适用于求解产销平衡的运输问题。（产销不平,衡的问题可转化为平衡问题）,2,运输问题的表上作业法,2024/11/12,10,表上作业法,一般步骤,：,1,、找出初始基本可行解；,2,、检查各非基变量的检验数，是否达到最优性条件，若达到，则得最优解；否则 转第三步；,3,、确定出基变量、进基变量，用闭回路方法进行调整，得到新的基可 行解；,4,、重复第二、第三步，直至得到最优解。,2024/11/12,11,一、确定初始基本可行解：,对于有,m,个产地,n,个销地的产销平衡问题，有,m,个关于产量,的约束方程和,n,个关于销量的约束方程。表面上，共有,m+n,个,约束方程。,但由于产销平衡，其模型最多只有,m+n-1,个独立的约束方,程，所以运输问题实际上有,m+n-1,个基变量,。在,mn,的产销,平衡表上给出,m+n-1,个数字格，其相对应的调运量的值即为,基变量的值。,2024/11/12,12,销地,运费单价,产地,B,1,B,2,B,3,B,4,产量（吨）,A,1,3,11,3,10,7,A,2,1,9,2,8,4,A,3,7,4,10,5,9,销量（吨）,3,6,5,6,那么在该例中，应有,3+4-1=6,个基变量。,2024/11/12,13,1.最小元素法,最小元素法的思想是就近供应，即对单位运价最小的变量分配运输量。,在表上找到单位运价最小的x,21,，并使x,21,取尽可能大,的值，即x,21,=3,把A,1,的产量改为1，B,1,的销量改为0，并,把B,1,列划去。在剩下的33矩阵中再找最小运价，同,理可得其他的基本可行解。,销地,运费单价,产地,B,1,B,2,B,3,B,4,产量（吨）,A,1,3,11,3,10,7,A,2,1,9,2,8,4,A,3,7,4,10,5,9,销量（吨）,3,6,5,6,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,4,3,7 3 0,A,2,3,1,4 1 0,A,3,6,3,9 3 0,销量,3,0,6,0,5,4,0,6,3,0,20,20,3,11,3,10,8,5,10,2,9,4,7,1,2024/11/12,15,表中填,有数字的格,对应于,基变量,(取值即为格中数字），而,空格,对应的是,非基变量,（取值为零）.,在求初始基本可行解时要,注意,的一个问题：,当我们取定x,ij,的值之后，会出现A,i,的产量与B,j,的销量都改为零的情况，这时只能划去A,i,行或B,j,列，但不能同时划去A,i,行与B,j,列。,（或者在同时划去A,i,行与B,j,列时，在该行或该列的任意空格处填加一个0。）,这样可以保证填过数或零的格为m+n-1个，即保证基变量的个数为m+n-1个。,2024/11/12,16,2.Vogel,法,Vogel,法的思想是,:,一地的产品如果不能按照最小运费就近供应，就考虑次小运费，这就有差额，差额越大，说明不能按最小运费调运时，运费增加得越多。因而差额越大处，就应当采用最小运费调运。,销地,运费单价,产地,B,1,B,2,B,3,B,4,产量（吨）,A,1,3,11,3,10,7,A,2,1,9,2,8,4,A,3,7,4,10,5,9,销量（吨）,3,6,5,6,2024/11/12,17,销地,产地,B,1,B,2,B,3,B,4,A,1,5,2,0 0 0 7,A,2,3,1,1 1 1 6,A,3,6,3,1 2,2,2,2,5,1,1,1,1,3,3,2,2,20,20,3,11,3,10,2,9,4,7,1,10,8,5,2024/11/12,18,二,、最优解的判别,判别解的最优性需要：,计算检验数。,方法有两种,闭回路：,是在已给出的调运方案的运输表上从一个代表非基变量的空格出发，沿水平或垂直方向前进，遇到代表基变量的填入数字的格可转,90,度（当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做,闭回路,。,一个空格存在唯一的闭回路。,1,.,闭回路法,因为任意非基向量均可表示为基向量的唯一线性组合，因此对于任意空格都,能够找到、并且只能找到唯一的,一条闭回路。,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,4,3,7,A,2,3,1,4,A,3,6,3,9,销量,3,6,5,6,10,8,5,3,11,3,10,2,9,4,7,1,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,（+）,1,4（-）,3,7,A,2,（-）3,1（+）,4,A,3,6,3,9,销量,3,6,5,6,10,8,5,3,11,3,10,2,9,4,7,1,2024/11/12,20,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,（+）,1,4（-）,3,7,A,2,（-）3,1（+）,4,A,3,6,3,9,销量,3,6,5,6,10,8,5,3,11,3,10,2,9,4,7,1,从非基变量 出发，找到一个闭回路如上表所示。回路有四个顶点，除,外，其余都为基变量。,调整调运量：，运费增加了,3,元；，运费减少,3,元,，运费增加,2,元；，运费减少,1,元,调整后，,总运费增加,：,3-3+2-1=1,元。,说明如果让 为基变量，运费就会增加，其增加值,1,作为 的,检验数,，,2024/11/12,21,闭回路法计算检验数：,就是对于代表非基变量的空格（其调运量为零），把它的调运量调整为,1,，由于产销平衡的要求,必须对这个空格的闭回路中的各顶点的调运量加上或减少,1,。最后计算出由这些变化给整个运输方案的总运输费带来的变化。以这个变化的数值，作为各空格（非基变量）的检验数。,判别最优解准则：,如果所有代表非基变量的空格的检验数都大于等于零，则已求得最优解；否则继续改进找出最优解。,2024/11/12,22,2.,位势法,（,1,）对运输表上的每一行赋予一个数值 ，对每一列赋予一个数值 ，称为行（列,),位势。,（,2,）行（列,),位势的数值是由基变量的检验数所决定的，即,基变量,要满足：,非基变量,的检验数就可以用公式,求出。,销地,产地,B,1,B,2,B,3,B,4,u,i,A,1,1,2,4,3,0,A,2,3,1,1,-1,-1,A,3,10,6,12,3,-5,v,j,2,9,3,10,3,11,3,10,8,5,10,2,9,4,7,1,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,4,3,7,A,2,3,1,4,A,3,6,3,9,销量,3,6,5,6,10,8,5,3,11,3,10,2,9,4,7,1,2024/11/12,24,我们先给u,1,赋个任意数值，不妨设u,1,=0，则从基变量x,11,的检验数求得 v,3,=c,13,-u,1,=3-0=3 。,同理可以求得 v,4,=10，u,2,=-1，等等见上表。,检验数的求法，即用公式 ，,如,。,销地,产地,B,1,B,2,B,3,B,4,u,i,A,1,1,2,4,3,0,A,2,3,1,1,-1,-1,A,3,10,6,12,3,-5,v,j,2,9,3,10,3,11,3,10,8,5,10,2,9,4,7,1,2024/11/12,25,位势法计算检验数：,检验数：,又因为基变量的检验数为,0,，于是由（,m+n-1),个基变 量的检验数,可解出 ，进而计算其他非基变量的检验数。,其中,第,i,个分量,第,m+j,个分量,2024/11/12,26,三、改进运输方案的办法,闭回路调整法,当表中的某个检验数小于零时，方案不为最优，需要调整。方法是：选取所有负检验数中最小的非基变量作为入基变量，以求尽快实现最优。,（,1,）,确定调整量,：例：取 ，表明增加一个单位的,运输量，可使得总运费减少,1,。在以 为出发点的闭回路中，找出所有偶数顶点的调运量：，,则调整量,（,2,）,调整方法,：把所有闭回路上为偶数顶点的运输量都减少这个值，奇数顶点的运输量都增加这个值,(,见下表,),。,2024/11/12,27,销地,产地,B,1,B,2,B,3,B,4,u,i,A,1,1,2,4,3,0,A,2,3,1,1,-1,-1,A,3,10,6,12,3,-5,v,j,2,9,3,10,3,11,3,10,8,5,10,2,9,4,7,1,销地,产地,B,1,B,2,B,3,B,4,u,i,A,1,4,(+1),3,(-1),0,A,2,3,1,(-1),+1,-1,A,3,6,3,-5,v,j,2,9,3,10,3,11,3,10,8,5,10,2,9,4,7,1,调整运量后的新方案：,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,5,2,7,A,2,3,1,4,A,3,6,3,9,销量,3,6,5,6,2024/11/12,29,销地,产地,B,1,B,2,B,3,B,4,u,i,A,1,0,2,5,2,0,A,2,3,2,1,1,-2,A,3,9,6,12,3,-5,v,j,3,9,3,10,3,11,3,10,8,5,10,2,9,4,7,1,对上表用位势法进行检验如下表，可知已达最优解。,2024/11/12,30,表上作业法,的一般步骤：,1,、用最小元素法或,Vogel,法确定初始基可行解；,2,、判断是否为最优：用闭回路法或位势法计算空格检验数，若所有检验数均非负，则已得到最优解；否则进入第