[管理学]第三章运输问题.ppt

第三章 特殊的线性规划运输问题,模型及其特点 求解思路及相关理论 求解方法表上作业法 运输问题的推广 产销不平衡的运输问题 转运问题,3.1 运输问题模型与性质 一、运输问题的数学模型 1、 运输问题的一般提法：人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的生产量和需要量及各地之间的运输费用，如何制定一个运输方案，使总的运输费用最小。这样的问题称为运输问题。,单位根据具体问题选择确定。,表3-1 有关信息,2、运输问题的数学模型,【例1】如图3-1所示的网络图，有A1，A2，A3三个产粮区，可供应粮食分别为10，8，5（万吨），现将粮食运往B1，B2，B3，B4四个地区，其需要量分别为5，7，8，3（万吨）。产粮地到需求地（销地）的运价（元/吨）如表3-2所示，问如何安排一个运输计划，使总的运输费用最少。,表3-2产销平衡表,图3-1,【解】设xij (i=1,2,3；j=1,2,3,4)为i个产粮地运往第j个需求地的运量(万吨)，这样得到下列运输问题的数学模型：,(1)使总的运输费用最小，则目标函数为,实际总运费等于Z乘以10000。,（2）各产粮地的供给量与运出量的平衡方程,（3）供给各需求地的供给量与需要量的平衡方程,（4）粮食的运量应大于或等于零（非负要求），即,有些问题表面上与运输问题没有多大关系，其模型的数学 结构与例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-3 产销平衡表,表3-4 单位运价表,【解】设xij为从产地Ai运往销地Bj的物资数量（i=1，m；j=1，n），由于从Ai运出的物资总量应等于Ai的产量ai，因此xij应满足：,同理，运到Bj的物资总量应该等于Bj的销量bj，所以xij还应满足： 总运费为：,运输问题的数学模型,（3-1）,二、运输问题的特点 1约束方程组的系数矩阵具有特殊的结构 写出式（3-1）的系数矩阵A，形式如下：, 矩阵的元素均为1或0； 每一列只有两个元素为1，其余元素均为0； 列向量Pij =(0,，0，1，0，,0,1,0,0)T，其中两个元素1分别处于第i行和第m+j行。 将该矩阵分块，特点是：前m行构成m个mn阶矩阵，而且第k个矩阵只有第k行元素全为1，其余元素全为0（k=1，m）；后n行构成m个n阶单位阵。,i,m+j,其中,2.运输问题的基变量总数是m + n -1 写出增广矩阵,证明系数矩阵A及其增广矩阵的秩都是m+n-1,前m行相加之和减去后n行相加之和结果是零向量，说明m+n个行向量线性相关，因此 的秩小于m+n； ？,因此 的秩恰好等于m+n-1，又D本身就含于A中，故A的秩也等于m+n-1,由 的第二至m+n行和前n列及 对应的列交叉处元素构成m+n-1阶方阵D 非奇异； ？,可以证明：m+n个约束方程中的任意m+n-1个都是线性无关的。,三、运输问题的求解方法,(1)、单纯形法（为什么？） (2)、表上作业法 由于问题的特殊形式而采用的更简洁、更方便的方法,一、运输问题的表上作业法,1.表上作业法的基本思想是:先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案 (表上作业法和单纯形法的求解思想完全一致，但是具体作法更加简捷)。,2.表上作业法求解步聚,(1)找出初始基本可行解(初始调运方案).常用的方法有最小元素法、元素差额法（Vogel近似法）、左上角法。 (2)求检验数并判断是否得到最优解，常用求检验的方法有闭回路法和位势法，假设目标函数取最小，当非基变量的检验数ij全都非负时得到最优解（对于max Z有ij0时最优），若存在检验数lk0，说明还没有达到最优，转第三步。 (3)确定换入变量和换出变量,找到新的基本可行解.在表上用闭回路法调整(运量). (4)重复(2),(3),直到得到最优解为止.,表上作业法是单纯形法在求解运输问题的一种简便方法。 单纯形法与表上作业法的关系： （1）找出初始基可行解 （2）求各非基变量的检验数 （3）判断是否最优解,换基：,（4）确定换入变量和换出变量找出新的基可行解。 （5）重复（2）、（3）直至求出最优解。,停止,3.举例. 例2.,某公司经销甲产品.它下设三个加工厂.每日的产量分别是:A1为7吨,A2为4吨,A3为9吨.该公司把这些产品分别运往四个销售点.各销售点每日销量为:B1为3吨,B2为6吨,B3为5吨,B4为6吨.已知从各工厂到各销售点的单位产品的运价见表3-5所示.问该公司应如何调运产品,在满足各销售点的需要量的前提下,使总运费最少.,表3-5信息表,解:(1)建立数学模型 设xij为从Ai到Bj的运量,i=1,2,3,j=1,2,3,4.根据已知信息,求得该问题的数学模型如下:,(2)确定初始基本可行解（最小元素法）.,最小元素法: 最小元素法的思想是就近优先运送， 即最小运价Cij对应的变量xij优先赋值,然后再在剩下的运价中取最小运价对应的变量赋值并满足约束， 依次下去，直到最后得到一个初始基可行解。,最小元素法确定初始基本可行解:,第一步:从信息表中找出最小运价,比较最小运价所在的行对应 的产量与所在列对应的销量.选择一个xij,令,对照信息表将xij具体的数字填入最小运价所在的格子中,比较产量与销量,当产大于销,划去该元素所在的列,当产小于销,划去该元素所在的行. 第二步：从划去的元素表中再找最小运价（或从原始信息表中找次小运价），同样确定填入数值，并划去相应的行或列,并修改日产量或日销量。 第三步:从划去的元素表中再找最小运价（或从原始信息表中找次次小运价），同样确定填入数值，并划去相应的行或列,并修改日产量或日销量。依次类推,直至将表中所有的元素划去为止,最后在产销平衡表中得到一个调运方案。,最小元素法举例,20,6,5,6,3,9,4,7,3,2,1,4,3,2,1,A,A,A,B,B,B,B,销量,产量,销地,产地,3,1,1,0,4,4,0,3,6,3,3,3,0,0,0,0,3,0,20,6,5,6,3,9,4,7,3,2,1,4,3,2,1,A,A,A,B,B,B,B,销量,产量,销地,产地,3,1,4,6,3,3,最后得到一个调运方案：该方案的运费为：z0 ,结论： 在产销平衡表中共得到m+n-1个数，即给出了（m+n-1)个基变量的值，且该（m+n-1)个基变量对应的系数列向量是线性独立的,(2)确定初始基本可行解（采用伏格尔法）,(又称)元素差额法：由于最小元素法只考虑了局部运输费用 最小，对整个产销系统的总运输费用来说可能离最优值较远， 有时为了节省某一处的运费，而在其它处可能运费很大。 元素差额法对最小元素法进行了改进，考虑到产地到销地的最小 运价和次小运价之间的差额，如果差额很大，就选最小运价处先 调运，否则会增加总运费。,基于此，采用伏格尔法确定初始基本可行解，仍以例为例 第一步：在运价表中计算出各行最小运费和次最小运费的差额， 行差额记为ui，i=1,2,m；同时求出每列次小运价与最小运价 之差，记为vj，j=1,2,n；填入表中的最右列和最下行,第二步：从行或列差额中选出最大者，选择它所在行或列中 的最小运价即L=maxui，vi，差额L对应行或列的最小运价处优先调运； 第三步：这时必有一列或一行调运完毕，在剩下的运价中再求最大差额，进行第二次调运，依次进行下去，直到最后全部调运完毕，就得到一个初始调运方案。,结合例2说明这种方法。,20,6,5,6,3,9,4,7,3,2,1,4,3,2,1,A,A,A,B,B,B,B,行差额,0,3-3=0,第一次,结合例2说明这种方法。,20,6,5,6,3,9,4,7,3,2,1,4,3,2,1,A,A,A,B,B,B,B,1,2-1=1,第一次,结合例2说明这种方法。,20,6,5,6,3,9,4,7,3,2,1,4,3,2,1,A,A,A,B,B,B,B,销量,产量,销地,产地,1,第一次,结合例2说明这种方法。,20,6,5,6,3,9,4,7,3,2,1,4,3,2,1,A,A,A,B,B,B,B,3,11,1,7,4,3,2,8,5,10,10,9,销量,产量,销地,产地,1,3-1=2,2,1,5,3,第一次,结合例2说明这种方法。,20,6,5,6,3,9,4,7,3,2,1,4,3,2,1,A,A,A,B,B,B,B,3,11,1,7,4,3,2,8,5,10,10,9,销量,产量,销地,产地,6,3,0,优先安排销地 ，否则运价会更高,下次不考虑该列,第一次,第二次,结合例2说明这种方法。,优先安排销地 ，否则运价会更高,3,20,6,5,6,3,9,4,7,3,2,1,4,3,2,1,A,A,A,B,B,B,B,6,0,0,3,下次不考虑该行,结合例2说明这种方法。,20,6,5,6,3,9,4,7,3,2,1,4,3,2,1,A,A,A,B,B,B,B,销量,产量,销地,产地,3,下次不考虑该列,3,0,1,第三次,结合例2说明这种方法。,20,6,5,6,3,9,4,7,3,2,1,4,3,2,1,A,A,A,B,B,B,B,3,2,5,0,下次不考虑该列,第四次,结合例2说明这种方法。,2,1,20,6,5,6,3,9,4,7,3,2,1,4,3,2,1,A,A,A,B,B,B,B,销量,产量,产地,3,0,0,0,第五次,例2用伏格尔法得到的初始基可行解,20,6,5,6,3,9,4,7,3,2,1,4,3,2,1,A,A,A,B,B,B,B,3,11,1,7,4,3,2,8,5,10,10,9,销量,产量,销地,产地,目标函数值,用最小元素法 求出的目标函数z=86,一般说来，伏格尔法得出的初始解的质量最好，常用来作为运输问题最优解的近似解。,结论： 伏格尔法同最小元素法在确定供求关系的原则上不同外，其余步骤相同同时伏格尔法给出的初始解比用最小元素法给出的初始解更接近最优解 （本例已得到最优解）,课间讨论:判断下表中给出的调运方案能否作为用表上作业法求解时的初始解?为什么?,作业:P97:3.2题(只作表3-44),(3)最优解判别,求最小值的运输问题的最优判别准则是：判断初始调运方案表中所有非基变量的检验数(空格的检验数)cij-CBB-1Pij是否都非负，是,则运输方案最优（即为最优解）。 求检验数的方法有两种，闭回路法和位势法。,定义3.1 凡是能排成 (3-4) 或 (3-5) 形式的变量集合称为一个闭回路,并称式中变量为该闭回路的顶点；其中 互不相同, 互不相同。,1)闭回路法,什么是闭回路?,例 设m=3，n=4，决策变量xij表示从产地Ai到销地Bj的调运量，列表如下，给出闭回路 在表中的表示法用折线连接起来的顶点变量。,练习 请给出闭回路 和 在表中的表示法。,练习 下面的折线构成的封闭曲线连接的顶点变量哪些不可能是闭回路？为什么？, 表中的折线构成一条封闭曲线，且所有的边都是水平或垂直的；为什么？ 表中的每一行和每一列由折线相连的闭回路的顶点只有两个；为什么？,从每一空格出发一定存在和可以找到唯一的闭回路.,证明:因(m-n-1)个数字格(基变量)对应的系数向量是一个基.任一空格(非基变量)对应的系数向量是这个基的线性组合.如Pij,可表示为: Pij=ei+em+j=ei+em+k-em+k+el-el+em+s-em+s+eu-eu+em+j =(ei+em+k)-(el+em+k)+(el+em+s)-(eu+em+s)+(eu+em+j) =Pik-Plk+Pls-Pus+Puj 其中Pik,Plk,Pls,Pus,Puj基矩阵B中的向量. 为什么是唯一的呢?假设存在另一个闭回路,则在Pij某一行或某一列存在两个非基变量,那么这些非基变量可自行组成闭回路,注意:列向量Pij =(0,0,1,0,0,1,0,0)T中两个元素1 分别处于第i行和第m+j行，直接计算即可得到结果。,闭回路法求检验数求某一非基变量的检验数的方法： 在基本可行解矩阵中，以该非基变量为起点，以基变量为其它顶点，找一条闭回路，由起点开始，分别在顶点上交替标上代数符号、，以这些符号分别乘以相应的运价，其代数和就是这个非基变量的检验数。,该闭回路的特点是：除了起始顶点是非基变量外，其他顶点 均为基变量（对应着填上数值的格）。,可以证明，如果对闭回路的方向不加区别，对于每一个非基变 量而言，以其为起点的闭回路存在且唯一。,现在，在用最小元素法确定例2初始调运方案的基础上，计算非基变量X11,X12,X22,X24,X31,X33的检验数 ：,闭回路法求检验数经济含义：在保持产销平衡的条件下，该非基变量增加一个单位运量而成为基变量时目标函数值的变化量。,3,11,1,7,4,3,2,8,5,10,10,9,20,6,5,6,3,9,4,7,3,2,1,4,3,2,1,A,A,A,B,B,B,B,销量,产量,销地,产地,从初始表分析：,要保证产销平衡，则,称为闭回路,+1,-1,+1,-1,20,6,5,6,3,9,4,7,3,2,1,4,3,2,1,A,A,A,B,B,B,B,销量,产量,销地,产地,2,1,计算所有非基变量的检验数,非基变量X11的检验数为: 11=c11-c13+c23-c21=3-3+2-1=1 非基变量X11的检验数为: 12=c12-c14+c33-c32=11-10=+5-4=2 同理可找出其它非基变量的闭回路,然后计算其检验数分别为: 22=c22-c23+c13-c14+c34-c32=9-2+3-10+5-4=1 24=c24-c23+c13-c14=-1 31=c31-c34+c14-c13+c23-c21 =10 33=c33-c34+c14-c13=12 当所有的非基变量的检验数都计算出来之后,就可以判断原方案是不是最优解.,检验数表,20,6,5,6,3,9,4,7,3,2,1,4,3,2,1,A,A,A,B,B,B,B,2,1,1,-1,10,12,表中的解不是最优解。,2)位势法(对偶变量法,dual variable method),位势法: 位势法求检验数是根据对偶理论推导出来的一种方法。 产销平衡运输模型: 若用u1,u2,um分别表示前m个约束等式相应的对偶变量;用v1,v2,vn表示后n个等式约束的对偶变量.,则有对偶变量向量Y=(u1,u2,um, v1,v2, vn) 这时可得运输问题的对偶问题 线性规则决策变量的检验数,书上:设u1,u2,um;v1,v2,vn是对应运输问题的m+n个约束条件 的对偶变量. B是含有人工变量xa的（m+n)(m+n)初始基矩阵 (为什么含有一个人工变量)人工变量xa在目标函数中的系数 ca=0，从线性规划的对偶理论可知 -（ u1,u2,um;v1,v2,vn)而每个决策变量xij的 系数向量Pij=ei+em+j,所以-Pij=ui+vj. 则检验数ij=cij-CBB-1Pij=cij- (ui+vj) 由单纯形法可知：所有基变量的检验数等于，即 cij -(ui+vj)=0,i,j属于B,现在根据位势法来计算非基变量的检验数 由于基变量的检验数等于，故有,解得：u1=0,u2=-1,u3=-5，v1=2,v2=9,v3=3,v4=10 非基变量的检验数 ij=cij - (ui+vj), i,j属于,检验数：目标函数的系数减去对偶变量之和,10,3,9,2,-5,-1,0,3,2,1,4,3,2,1,A,A,A,B,B,B,B,vj,ui,销地,产地,设计表格,10,3,9,2,-5,-1,0,3,2,1,4,3,2,1,A,A,A,B,B,B,B,vj,ui,销地,产地,0,0,0,0,0,0,1,11=c11 - (u1+v1)=3-0-2=1 12=c12 - (u1+v2)=11-0-9=2 ,2,1,-1,10,12,上表检验数还存在负数，故没有得到最优解,（）调整运量（闭回路调整法） 当某个检验数小于零时，基可行解不是最优解，总运费还可以下降，这时需调整运输量，改进原运输方案，改进运输方案的步骤是： 第一步：确定进基变量， 进基； 第二步：确定出基变量，在进基变量Xlk的闭回路中，标有负号的最小运量作为调整量，对应的基变量为出基变量，并打上“”以示作为非基变量。 第三步：调整运量，在进基变量的闭回路中标有正号的变量加上调整量，标有负号的变量减去调整量，其余变量不变，得到一组新的基可行解，然后求所有非基变量的检验数重新检验。,3,11,1,7,4,3,2,8,5,10,10,9,20,6,5,6,3,9,4,7,3,2,1,4,3,2,1,A,A,A,B,B,B,B,销量,产量,销地,产地,（-1）,（-1）,（+1）,（+1）,解的调整,调整后的解为：,3,11,1,7,4,3,2,8,5,10,10,9,20,6,5,6,3,9,4,7,3,2,1,4,3,2,1,A,A,A,B,B,B,B,销量,产量,销地,产地,1,调整后计算非基变量的检验数（位势法）：,10,3,9,3,-5,-2,0,3,2,1,4,3,2,1,A,A,A,B,B,B,B,vj,ui,销地,产地,3,6,2,3,5,0,2,2,9,12,1,1,此时的解为最优解。,几点说明：,当检验数为的负的变量超过两个，选择最小者对应的变量换入； 在最优解的表中，若有非基变量检验数=0，则该运输问题有无穷多最优解； 迭代过程中，若某一格填数时需同时划去一行和一列，此时出现退化。为保证m+n-1个非空格，需在上述的行或列中填入数字0。 在第二步确定出基变量时，当出现两个或两个以上最小运量，在其中任选一个作为非基变量，其它对应的变量仍作为基变量，运量为零，得到退化基本可行解,四 产销不平衡的运输问题及其求解方法,当总产量与总销量不相等时,称为不平衡运输问题。这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题求解。 (1) 产大于销时,即有,数学模型为,由于总产量大于总销量，必有部分产地的产量不能全部 运送完，必须就地库存，即在每个产地虚设一个仓库，库存量 为Xi,n+1（i=1，2，m），总的库存量为,bn+1作为一个虚设的销地Bn+1的销量。各产地Ai到Bn+1的 运价为零，即Ci,n+1=0,（i=1，m）。则平衡问题的 数学模型为,具体求解时,只在运价表右端增加一列Bn+1，运价为零, 销量为bn+1即可。,决策变量 表示由 到 的物品数量。,注意：用最小元素法求初始调运方案时，最后一列的零运价最后考虑。,（2）当销大于产时,即,数学模型为,由