《运筹学》胡运权第4版第三章运输问题.ppt

第三章运输问题,2,本章内容,运输问题及其数学模型用表上作业法求解运输问题运输问题的进一步讨论应用问题举例,问题的提出：一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。,1运输问题及其数学模型,1运输问题及其数学模型,1.经典运输问题单一品种物资的运输调度问题,1运输问题及其数学模型,网络表示：,5,000,2,500,6,000,如果运输问题的总产量等于其总销量，即有则称该运输问题为产销平衡运输问题；反之，称产销不平衡运输问题。,产销平衡运输问题的数学模型可表示如下：,1运输问题及其数学模型,二、运输问题数学模型的特点：运输问题一定有最优解；基变量的个数=m+n-1运输问题约束条件的系数矩阵：,1运输问题及其数学模型,运输问题具有下述特点：(1)约束条件系数矩阵的元素等于0或1；(2)约束条件系数矩阵的每一列有两个非零元素，这对应于每一个变量在前m个约束方程中出现一次，在后n个约束方程中也出现一次。,1运输问题及其数学模型,对产销平衡运输问题，除上述两个特点外，还有以下特点：(1)所有结构约束条件都是等式约束；(2)各产地产量之和等于各销地销量之和。,1运输问题及其数学模型,例1某部门有3个生产同类产品的工厂(产地)，生产的产品由4个销售点(销地)出售，各工厂的生产量、各销售点的销售量(假定单位均为t)以及各工厂到各销售点的单位运价(元t)示于表3-2中，要求研究产品如何调运才能使总运费最小?,表3-2,4,2,8,12,5,4,10,11,3,9,6,11,1运输问题及其数学模型,该问题的数学模型：,1运输问题及其数学模型,12,本章内容,运输问题及其数学模型用表上作业法求解运输问题运输问题的进一步讨论应用问题举例,一、表上作业法的基本思想和步骤：1.基本思想：同单纯形法的基本思想,2用表上作业法求解运输问题,二、表上作业法的步骤（1）寻找初始基可行解；最小元素法、西北角法、沃格尔法（2）求出非基变量检验数（空格检验数），判断是否为最优解；闭回路法、位势法（3）换基改进，找到新的基可行解闭回路调整法（4）重复（2）（3）,2用表上作业法求解运输问题,1.最小元素法从运价最小的格开始，在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。,寻找初始基可行解,4,2,8,5,10,11,12,3,4,6,9,11,1.最小元素法,总费用z=104+611+82+23+145+86=246,寻找初始基可行解,2.西北角法从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。,寻找初始基可行解,2.西北角法,总费用z=84+812+610+43+811+146=372,寻找初始基可行解,3.沃格尔法罚数=次小费用-最小费用找出最大的罚数行或列所对应的最小费用优先安排。重复计算步骤1和2,寻找初始基可行解,3.沃格尔法,4,10,12,11,3,4,6,9,11,2,8,5,2,0,1,5,1,3,2,2,1,0,1,1,3,2,1,14,8,8,1,0,2,总费用z=244,寻找初始基可行解,最优性检验就是检查所得到的方案是不是最优方案。检查的方法与单纯形方法中的原理相同，即计算检验数。由于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案；否则就不是最优，需要进行调整。下面介绍两种求检验数的方法：闭回路法和对偶变量法。,解的最优性检验,1.闭回路法闭回路：从空格出发，遇到数字格可以旋转90度，最后回到空格所构成的回路；原理：利用检验数的经济含义；检验数：非基变量增加一个单位引起的成本变化量。当所有非基变量的检验数均大于或等于零时，现行的调运方案就是最优方案，因为此时对现行方案作任何调整都将导致总的运输费用增加。闭回路法的主要缺点是：当变量个数较多时，寻找闭回路以及计算两方面都会产生困难。,解的最优性检验,1.闭回路法（结合最小元素法的初始解）,解的最优性检验,8,14,10,2,6,8,检验数11=c11-c21+c23-c13=4-2+3-4=124=c24-c14+c13-c23=9-11+4-3=-10,故知该最小元素法的解不是最优解,位势：设对应基变量xij的m+n-1个i、j，存在ui,vj满足ui+vj=cij,i=1,2,.,m;j=1,2,n称这些ui,vj为该基本可行解对应的位势。,解的最优性检验,2.对偶变量法（位势法）,解的最优性检验,2.对偶变量法（位势法）,设对偶变量向量为,解的最优性检验,对偶规划为,解的最优性检验,检验数：目标函数的系数减去对偶变量之和,原问题检验数：ij=cij-(ui+vj),特别对于m+n-1个基变量，有ij=0,j=Cj-CBB-1Pj=Cj-YPjij=Cij-CBB-1Pij=Cij-YPij=Cij-(u1,u2,um,v1,v2,vn)Pij=Cij-(ui+vj)当xij为基变量时ij=Cij-(ui+vj)=0由此，任选一个对偶变量为0，可求出其余所有的ui，vj。再根据ij=Cij-(ui+vj)求出所有非基变量的检验数。,解的最优性检验,解的最优性检验,表3-9,1.增加一位势列和位势行并计算位势,其中,解的最优性检验,2.计算检验数,（+2）,4.解的改进闭回路调整法,解的最优性检验,改进的方法是在运输表中找出这个空格对应的闭回路Lij，在满足所有约束条件的前提下，使xij尽量增大并相应调整此闭回路上其他顶点的运输量，以得到另一个更好的基可行解。,（-2）,（+2）,（-2）,5、需要注意的问题（一）多个空格（非基变量）的检验数为负，任一个都可作为换入变量。一般ij0中最小的对应变量作为换入变量。（二）最优解时，如果有某非基变量的检验数为0，则说明该运输问题有无穷多最有解。（三）退化解。,解的最优性检验,本章内容,运输问题及其数学模型用表上作业法求解运输问题运输问题的进一步讨论应用问题举例,3运输问题进一步讨论,产销不平衡的运输问题有转运的运输问题,1.当产大于销时，即,产销不平衡问题,平衡后的数学模型为：,加入假想销地（假想仓库），销量为，由于实际并不运送，它们的运费为=0；,产销不平衡问题,2.当销大于产时，即,加入一个虚设的产地去生产不足的物资；它的产量为,产销不平衡问题,有转运的运输问题,表3-15有转运输问题的运输表,有转运的运输问题,有转运的运输问题,表3-16有转运输问题的运价表,例5,有转运的运输问题,图3-3示出了一个运输系统，它包括两个产地(和)、两个销地(和)及一个中间转运站()，各产地的产量和各销地的