第3章运输问题

1、单击此处1111编辑母版标题样式,单击此处编辑母版文本样式单击此处编辑母版文本样式1、,11111111,运筹学,第三章运输问题,3.1 运输模型,例,1.1-3,表,1.2,B1,B2,B3,供应量,A1,15,21,18,200,A2,20,25,16,150,需求量,100,80,90,运输问题的数学描述,设某种物资有,m,个,发点,A,1,A,2,A,m,，,各发点的,发量,分别是,a,1,a,2,a,m,；,有,n,个,收点,B,1,B,2,B,n,，,各收点的,收量,分别为,b,1,b,2,b,n,。,已知从发点,A,i,(,i,=1,2,m,),向收点,B,j,(,j,=1,2,n,),运输单位物资的,运价,是,c,ij,，,问怎样调运这些物资才能使总运费最少？,收 点,发 点,B,1,B,2,B,n,发量,A,1,x,11,x,12,x,1,n,a,1,c,11,c,12,c,1,n,A,2,x,21,x,22,x,2,n,a,2,c,21,c,22,c,2,n,A,m,x,m,1,x,m,2,x,mn,a,m,c,m,1,c,m,2,c,mn,收量,b,1,b,2,b,n,定理,3.1,运输问题的任何一个基都由,m+n-1,个变量组成。,收 点,发 点,B,1,B,2,B,3,B,4,A,1,x,11,x,12,x,13,x,14,c,11,c,12,c,13,c,14,A,2,x,21,x,22,x,23,x,24,c,21,c,22,c,23,c,24,A,3,x,31,x,32,x,33,x,34,c,31,c,32,c,33,c,34,收 点,发 点,B,1,B,2,B,3,B,4,A,1,x,11,x,12,x,13,x,14,c,11,c,12,c,13,c,14,A,2,x,21,x,22,x,23,x,24,c,21,c,22,c,23,c,24,A,3,x,31,x,32,x,33,x,34,c,31,c,32,c,33,c,34,闭回路：,定理,3.2,运输问题中,m+n-1,个变量构成基的充分必要条件是它不包含闭回路。,收 点,发 点,B,1,B,2,B,3,B,4,A,1,x,11,x,12,x,13,x,14,c,11,c,12,c,13,c,14,A,2,x,21,x,22,x,23,x,24,c,21,c,22,c,23,c,24,A,3,x,31,x,32,x,33,x,34,c,31,c,32,c,33,c,34,收 点,发 点,B,1,B,2,B,3,B,4,A,1,x,11,x,12,x,13,x,14,c,11,c,12,c,13,c,14,A,2,x,21,x,22,x,23,x,24,c,21,c,22,c,23,c,24,A,3,x,31,x,32,x,33,x,34,c,31,c,32,c,33,c,34,3.2 初始基可行解的求法,3.2.1,最小元素法例,3.2-1,收 点,发 点,B,1,B,2,B,3,B,4,发量,A,1,9,9,18,1,10,A,2,10,11,6,8,18,A,3,6,14,12,2,16,收量,4,9,7,5,7,X,X,2,9,X,X,1,2,X,2,1,X,1,1,5,5,3.2.1,最小元素法例,3.2-1,收 点,发 点,B,1,B,2,B,3,B,4,发量,A,1,2,X,7,X,9,9,18,1,10,A,2,1,9,X,X,10,11,6,8,18,A,3,1,X,X,5,6,14,12,2,16,收量,4,9,7,5,例,3.2-2,收 点,发 点,B,1,B,2,B,3,发量,A,1,3,3,1,6,A,2,5,2,4,3,A,3,7,6,5,5,收量,5,3,7,3,X,X,0,5,X,0,0,X,7,0,0,例,3.2-2,收 点,发 点,B,1,B,2,B,3,发量,A,1,0,3,X,3,3,1,6,A,2,5,X,X,5,2,4,3,A,3,0,X,7,7,6,5,5,收量,5,3,7,定理,3.3,由最小元素法得到的各变量的值是运输问题的一个基可行解，而所有打圈处的变量正好构成一个基。,3.2.2,沃格尔近似法,收点,发点,B,1,B,2,B,3,B,4,发量,A,1,9,9,18,1,10,A,2,10,11,6,8,18,A,3,6,14,12,2,16,收量,4,9,7,5,行 差,列,差,10,2,8,6,1,6,2,6,X,X,X,1,2,8,8,7,12,2,9,X,1,3,8,8,7,2,5,X,4,3,8,7,2,1,X,3,11,9,2,1,3,3,3.2.2,沃格尔近似法,收点,发点,B,1,B,2,B,3,B,4,发量,A,1,3,X,1,5,9,9,18,1,10,A,2,1,9,X,X,10,11,6,8,18,A,3,X,X,6,X,6,14,12,2,16,收量,4,9,7,5,行 差,8,8,8,8,9,2,2,3,3,11,10,列,差,2,6,1,6,2,12,7,8,2,7,8,2,7,2,3.3 最优解的获得,1,、解的最优性检验位势法：,收 点,发 点,B,1,B,2,B,3,B,4,发量,v,1,v,2,v,3,v,4,A,1,2,7,9,u,1,9,18,1,10,A,2,1,9,10,u,2,11,6,8,18,A,3,1,5,6,u,3,14,12,2,16,收量,4,9,7,5,收 点,发 点,B,1,B,2,B,3,B,4,发量,v,1,v,2,v,3,v,4,A,1,2,7,9,u,1,9,18,1,10,A,2,1,9,10,u,2,11,6,8,18,A,3,1,5,6,u,3,14,12,2,16,收量,4,9,7,5,0,9,1,2,5,4,11,收 点,发 点,B,1,B,2,B,3,B,4,发量,9,4,1,11,A,1,2,7,9,0,9,18,1,10,A,2,1,9,10,2,11,6,8,18,A,3,1,5,6,5,14,12,2,16,收量,4,9,7,5,收 点,发 点,B,1,B,2,B,3,B,4,发量,9,4,1,11,A,1,2,-14,7,1,9,0,9,18,1,10,A,2,1,9,-5,-5,10,2,11,6,8,18,A,3,1,-3,4,5,6,5,14,12,2,16,收量,4,9,7,5,收 点,发 点,B,1,B,2,B,3,B,4,发量,9,4,1,11,A,1,2,-14,7,1,9,0,9,18,1,10,A,2,1,9,-5,-5,10,2,11,6,8,18,A,3,1,-3,4,5,6,5,14,12,2,16,收量,4,9,7,5,闭回路法求检验数示意：,收 点,发 点,B,1,B,2,B,3,B,4,发量,9,4,1,11,A,1,2,-14,7,1,9,0,9,18,1,10,A,2,1,9,-5,-5,10,2,11,6,8,18,A,3,1,-3,4,5,6,5,14,12,2,16,收量,4,9,7,5,2,、解的改进：,闭回路法：,收 点,发 点,B,1,B,2,B,3,B,4,发量,9,4,1,11,A,1,3,-14,6,1,9,0,9,18,1,10,A,2,1,9,-5,-5,10,2,11,6,8,18,A,3,-3,1,5,6,5,14,12,2,16,收量,4,9,7,5,2,、解的改进：,闭回路法：,收 点,发 点,B,1,B,2,B,3,B,4,发量,9,4,1,15,A,1,3,-14,6,1,9,0,9,18,1,10,A,2,1,9,-5,-5,10,2,11,6,8,18,A,3,-3,1,5,6,1,14,12,2,16,收量,4,9,7,5,2,、解的改进：,闭回路法：,收 点,发 点,B,1,B,2,B,3,B,4,发量,9,4,1,15,A,1,3,-14,6,5,9,0,9,18,1,10,A,2,1,9,-5,-1,10,2,11,6,8,18,A,3,-4,-7,1,5,6,1,14,12,2,16,收量,4,9,7,5,2,、解的改进：,闭回路法：,收 点,发 点,B,1,B,2,B,3,B,4,发量,9,4,1,15,A,1,3,-14,6,5,9,0,9,18,1,10,A,2,1,9,-5,-1,10,2,11,6,8,18,A,3,-4,-7,1,5,6,1,14,12,2,16,收量,4,9,7,5,2,、解的改进：,闭回路法：,收 点,发 点,B,1,B,2,B,3,B,4,发量,9,4,1,15,A,1,3,-14,1,5,9,0,9,18,1,10,A,2,1,9,-5,-1,10,2,11,6,8,18,A,3,-4,-7,6,6,1,14,12,2,16,收量,4,9,7,5,2,、解的改进：,闭回路法：,收 点,发 点,B,1,B,2,B,3,B,4,发量,9,4,1,10,A,1,3,-14,1,5,9,0,9,18,1,10,A,2,1,9,-5,-6,10,2,11,6,8,18,A,3,-4,-7,6,-5,6,1,14,12,2,16,收量,4,9,7,5,2,、解的改进：,闭回路法：,定理,3.4,在全体基变量中加入一个非基变量后，就一定存在一条，且只有唯一的一条闭回路。,定理,3.5,如果一个运输问题中的所有发量和所有收量都是整数，那么它的每一个基可行解中的所有变量也都取整数值。,3.4 不平衡运输问题,不平衡运输问题:,总发量不等于总收量的运输问题，即：,这时增加一个虚拟的收点,B,n,+1,，,它的收量为,b,n,+1,，,即,由于它实际上并不存在，所以从发点,A,i,(,i,=1,2,m,),调运到这个虚拟收点的物资数量,x,i,n,+1,，,实际上是就地储存在,A,i,的物资数量。就地储存的物资不经过运输，所以单位运价,c,i,n,+1,0(,i,=1,2,m,),。,例,3.4-1,B,1,B,2,B,3,B,4,发量,A,1,4,6,2,8,7,A,2,5,3,4,6,5,A,3,7,9,6,4,8,收量,3,6,4,2,B,1,B,2,B,3,B,4,B,5,发量,A,1,4,6,2,8,0,7,A,2,5,3,4,6,0,5,A,3,7,9,6,4,0,8,收量,3,6,4,2,5,20,这时增加一个虚拟的发点,A,m,+1,，,它的发量为,a,m,+1,，,即,由于它实际上并不存在，所以从它调运到各个收点,B,j,(,j,=1,2,n,),的物资数量,x,m,+1,j,，,实际上是各收点,B,j,所需物资的欠缺额。同样，这些欠缺的物资的单位运价,c,m,+1,j,0(,j,=1,2,n,),。,例,3.4-2,B,1,B,2,B,3,B,4,发量,A,1,6,5,7,3,6,A,2,2,4,5,6,5,A,3,8,5,7,4,5,收量,4,7,3,6,B,1,B,2,B,3,B,4,发量,A,1,6,5,7,3,6,A,2,2,4,5,6,5,A,3,8,5,7,4,5,A,4,0,0,0,0,4,收量,4,7,3,6,20,3.5 指派问题,例,3.5-1,B,1,B,2,B,3,B,4,A,1,3,4,5,2,A,2,8,5,7,6,A,3,9,6,4,5,A,4,5,3,6,6,指派问题的一般形式：,有,n,个人和,n,件事，已知第,i,个人做第,j,件事的效率为,c,ij,(,i,j,1,2,n,),，需要确定人和事之间的一一对应的指派方案，使完成这,n,件事的总效率最好。,事,人,B,j,A,i,x,ij,c,ij,事,1,事,2,事,n,人,1,人,2,人,n,解矩阵：,引入,n,2,个,0,1,变量：,若指派,A,i,做,B,j,若不指派,A,i,做,B,j,效率矩阵：,标准指派问题的特征：,人数和事数相等；,一人做一事；,优化目标为最小化，即为最小化指派问题。,标准指派问题的数学模型：,标准指派问题的数学模型：,定理,3.5,如果一个运输问题中的所有发量和所有收量都是整数，那么它的每一个基可行解中的所有变量也都取整数值。,运输问题的数学模型：,指派问题解的特点：,任何一个可行解由,n,2,个,x,ij,组成；,基变量为,2,n,-1,个；,n,个为,1,，其余为,0,；,n,个,1,位于解矩阵的不同行不同列上，对应的效率矩阵中的,n,个,c,ij,也位于不同行不同列上。,匈牙利解法,匈牙利解法是,库恩,于,1955,年利用匈牙利数学家,康尼格,的关于矩阵中独立,0,元素的定理，提出的一种算法，因而得名。,匈牙利解法的关键是利用了指派问题最优解的以下性质：,若从系数矩阵,C,的某行或某列各元素分别减去一个常数,k,，得到新矩阵,C,，则以,C,和,C,为系数矩阵的两个指派问题有相同的最优解。,匈牙利解法的步骤：,1,、变换效率矩阵，使每行每列至少有一个,0,元素。,方法：先对各行元素分别减去本行中的最小元素，再对各列元素分别减去本列中的最小元素。,-2,-5,-4,-3,-1,定理,3.7,覆盖所有,0,元素的最少直线数目等于独立,0,元素的个数。,2,、在变换得到的系数矩阵中确定独立,0,元素。,独立,0,元素,是指恰当地分布在不同行和不同列上的,0,元素。,方法：从,0,元素最少的行（或列）开始，圈出一个,0,元素，做一竖线（或横线）划去此,0,所在列（或行），考察剩余的行和列，直至所有的,0,都被划去。已经圈,0,的行和列不再圈,0,。,被圈出的,0,元素即为独立,0,元素。所划的直线为覆盖所有,0,元素的最少直线数目的直线集合。,若独立,0,元素的个数等于效率矩阵的阶数,n,，令解矩阵,X,中和独立,0,元素对应位置上的元素为,1,，其它为,0,，即得最优解矩阵，计算结束。若独立,0,元素的个数少于,n,，则继续下一步。,3,、 继续变换效率矩阵，使得未被直线覆盖的非,0,元素中出现新的,0,元素。然后返回步骤,2,。,方法：在未被直线覆盖的非,0,元素中找到最小元素，将未被直线覆盖的元素所在的行,(,或列,),中各元素都减去最小元素。对出现负元素的列,(,或行,),中各元素加上最小元素。,-1,-1,+1,非标准形式指派问题的解法,把非标准形式指派问题转化为标准形式，再用匈牙利解法求解。,1.,最大化指派问题,最大化指派问题和标准指派问题的唯一区别是：优化目标为最大化。,转化方法：,设最大化指派问题效率矩阵,C,(,c,ij,),n,n,，令矩阵,C,(,c,ij,),n,n,(,c,0,c,ij,),n,n,，其中,c,0,为,C,的最大元素或一足够大正数，求解以,C,为效率矩阵的最小化标准指派问题。,-1,-1,-5,-4,2,、人数和事数不等且一人做一事的指派问题,若人少事多，则添上一些虚拟的人，使人数和事数相等，虚拟的人做事的效率系数取为,0,；,若人多事少，则添上一些虚拟的事，使人数和事数相等，虚拟的事被各人做的效率系数取为,0,。,7,8,12,9,6,A,3,10,14,17,9,7,A,2,12,15,7,8,4,A,1,B,5,B,4,B,3,B,2,B,1,任务,人,c,ij,(,小时,),B,1,B,2,B,3,B,4,B,5,A,1,A,2,A,3,A,4,A,5,虚人,-4,-7,-6,+1,-1,-1,-1,-1,-1,-1,+1 +1,12,9,6,A,5,14,7,6,A,4,12,9,6,A,3,17,9,7,A,2,7,8,4,A,1,B,3,B,2,B,1,任务,人,c,ij,(,小时,),B,1,B,2,B,3,B,4,B,5,A,1,A,2,A,3,A,4,A,5,虚事,-4 -7 -7,-2,-2,-2,+2 +2,3.,一个人可以做几件事的指派问题,若某个人可以做,k,件事，将这个人化成相同的,k,个人来接受指派，使其转化为一人做一事的问题。这,k,个人做同一件事的效率是一样的。,7,8,12,9,6,A,3,10,14,17,9,7,A,2,12,15,7,8,4,A,1,B,5,B,4,B,3,B,2,B,1,任务,人,c,ij,(,小时,),每人最多可做2件事。,B,1,B,2,B,3,B,4,B,5,A,1,A,1,A,2,A,2,A,3,A,3,B,6,0,0,0,0,0,0,虚事,-4 -8 -7 -8 -7,-1,-1,+1,4,、 某事一定不能由某人做的指派问题,若某事一定不能由某人做，将效率矩阵中该人做该事相应的效率取作足够大的正数,M,，然后当作标准指派问题来解。,例,(,使雷达开机数量最少的指派问题,),某雷达团有,4,个雷达连，每个雷达连有数部雷达，现在需要搜索,4,批目标。已知各雷达连对各批目标进行成功搜索、发现并掌握情况所需的开机雷达数量，如表所示，问应指派哪个雷达连搜索哪一批目标，可使总的雷达开机数量最少？,2,4,1,3,4,连,X,X,3,2,3,连,3,X,1,3,2,连,4,3,1,2,1,连,目标,4,目标,3,目标,2,目标,1,目标,雷达连,开机雷达数,(,注：,X,表示超出雷达探测范围，不能发现目标,),-1,-1,-2,-1,-2 -1,END,