运筹学(第三章)ppt课件

.,第三章,运输问题,主要内容：,第一节运输问题及数学模型第二节用表上作业法求解运输问题第三节运输问题的进一步讨论第四节运输问题的应用举例,.,第一节,运输问题及其数学模型,.,一、运输问题的一般提法,的单位运,.,二、运输问题的数学模型,s.t,约束方程即为：,.,三、运输问题数学模型的特点,1.平衡条件下的运输问题一定有最优解。2.运输问题的系数矩阵,系数矩阵的特点：（1）约束条件系数矩阵的元素为0或1；（2）约束条件系数矩阵的每一列有两个1元素，对于变量xij在第i个约束方程中出现一次，在第m+j个方程中出现第二次；（3）系数矩阵的秩为m+n-1。,.,第二节,用表上作业法求解运输问题,基本思路：（1）找出基本可行解；（2）检验是否为最优解。是，则停止，否，转入（3）；（3）解的调整。得到一个新的基本可行解，重新回到步骤二。,所有步骤都在表上进行操作,运输表,.,例子：,某部门有3个生产同类产品的工厂，生产的产品由4个销售点出售，各工厂的生产量、各销售点的销售量（假定单位均为吨）以及各工厂到各销售点的单位运价（元/吨）如下表，要求研究产品如何调运才能使总运费最小。,.,一、找出初始基可行解,1.西北角法2.最小元素法3.沃格尔法（差值法）,较差,较好,更好,.,8,8,6,4,8,14,84+812+610+43+811+146=372（元）,西北角法每次找最左上角对应的元素,.,14,8,2,10,8,6,82+145+104+23+611+86=246（元）,最小元素法每次找最小元素,.,14,8,2,12,8,82+145+124+411+29+86=244（元）,行罚数,列罚数,2,5,1,3,0,1,1,0,1,2,2,2,1,2,7,6,4,沃格尔法每次找行罚数和列罚数中最大值所对应的行或列中最小的元素,.,二、解的最优性检验,1.闭回路法2.对偶变量法（位势法）,.,（14）,（8）,（2）,（10）,（8）,（6）,闭回路法：,.,（14）,（8）,（2）,（10）,（8）,（6）,1,1,-1,2,10,12,存在小于0的检验数，故此基可行解不是最优解。,.,在运输问题中通常目标函数是求最小值，所以当所有的检验数为正值时，得到最优解。,注意：,对于每一个非基变量，在运输表中唯一对应一条这样的闭回路。,.,对偶变量法（位势法）：,.,基变量的检验数为0，得到m+n-1个方程，这些方程中共包含m+n个对偶变量，因此解的个数不唯一。,把用这m+n-1个方程求得的对偶变量的解带入到其它m*n-(m+n-1)个式子中，求出非基变量的检验数。当所有的检验数都0时，得到最优解。,.,（14）,（8）,（2）,（10）,（8）,（6）,1,1,-1,2,10,12,ui,vj,u1,v4,v3,v2,v1,u2,u3,(4),(11),(0),(-5),(-1),(3),(10),存在小于0的检验数，故此基可行解不是最优解。,.,三、解的改进,闭回路法,（14）,（8）,（2）,（10）,（8）,（6）,+2,+2,-2,-2,.,（14）,（8）,（12）,（8）,（4）,（2）,.,四、重新进行最优性检验,（14）,（8）,（12）,（8）,（4）,0,2,（2）,2,9,12,1,不存在小于0的检验数，故此基可行解是最优解，得到最优运输方案。(存在无穷多最优调运方案),.,第三节,运输问题的进一步讨论,.,一、产销不平衡的运输问题,表上作业法是以产销平衡为前提的。当实际问题是产销不平衡的问题时，需要转化为产销平衡的运输问题。,.,s.t,),.,2,1,(,1,m,i,a,x,i,n,j,ij,=,=,1、产大于销，即,此时增加一个假想的销地n+1，该销地的销量为，而各产地到假想销地的单位运价定为0，就转化成产销平衡的运输问题。,.,2、销大于产，即,s.t,),.,2,1,(,1,n,j,b,x,j,m,i,ij,=,=,此时增加一个假想的产地m+1，该产地的产量为，而假想产地到各销地的单位运价定为0，就转化成产销平衡的运输问题。,.,例1：,某市有三个造纸厂A1,A2和A3，其纸的产量分别为8，5和9个单位。由各造纸厂到各用户的单位运价如表所示，请确定总运费最少的调运方案。,.,.,例2：,有三个产地A1,A2,A3，生产同一种物品，使用者分别为B1,B2,B3，各产地到各使用者的单位运价示与下表。这三个使用者的需求量分别为10、4和6个单位。由于销售需要和客观条件的限制，产地A1至少要发出6个单位的产品，但它最多只能生产11个单位的产品；A2必须发出7个单位的产品；A3至少要发出4个单位的产品。试根据以上条件用表上作业法求解该运输问题的最优运输方案。,.,A3最多可能送出的产品数量：(10+4+6)-(6+7)=7,.,在以上讨论中，假定物品由产地直接运送到销售目的地，不经中间转运。但是，常常会遇到这种情形：需先将物品由产地运列某个中间转运站(可能是另外的产地、销地或中间转运仓库)，然后再转运到销售目的地。有时，经转运比直接运到目的地更为经济(如下页图)。因此，在决定运输方案时有必要把转运也考虑进去。,二、有转运的运输问题,.,A,B,C,30,10,10,20,10,4,2,2,1,1,.,建立一般意义上的数学模型，设：ai：第i个产地的产量(净供应量)；bj：第j个销地的销量(净需要量)；xij：由第i个发送地运到第j个接收地的物品数量；cij：由第i个发送地到第j个接收地的单位运价，ti：第i个地点转运物品的数量；ci：第i个地点转运单位物品的费用。将产地和销地统一编号，并把产地排在前面。销地排在后面，则有：,.,令：,建立数学模型：,.,注：所有i=j，cij=-ci,.,例：如图所示是一个运输系统，它包括二个产地（1和2）、二个销地(4和5)及一个中间转运站(3)，各产地的产量和各销地的销量用相应节点处箭线旁的数字表示，节点联线上的数字表示其间的运输单价，节点旁的数字为该地的转运单价，试确定最优运输方案。,该运输问题的运输表,该运输问题的最优调运方案,总运费：10*2+20*2+20*4+20*5+（50-30）*3=300,.,第四节,运输问题的应用举例,例1：某厂按合同规定须于当年每个季度末分别提供15、20、25、20台同一规格的设备。已知该厂各季度的生产能力及生产每台设备的成本如下表。又知如果生产出来的设备当季度不交货，每台每季度的存储维护费为0.1万元。试安排全年生产计划，使总费用最低。,解：设xij（n=1,2,4；n=1,2,4）表示第i季生产第j季销售的设备数量，xi5表示第i季度实际生产数量与该季度生产能力之间的差值。列出如下产销平衡运输表。,季度,季度,1,2,3,4,5,(,虚销地,),产,量,12.0,12,.1,12.2,12.3,0,1,0,20,25,M,11.0,11.1,11.2,0,2,0,20,10,3,5,M,M,1,1.5,11.6,0,3,15,20,30,M,M,M,12.5,0,4,15,20,销量,15,20,2,5,20,30,110,所有检验数都大于等于0，因此该解为最优解。,求初始生产计划方案并进行检验：,10,ui,vj,12.0,12.1,0,-1.1,0,12.2,-0.7,12.3,（0）,（0）,（M-10.9）,（0）,（1.1）,（0.7）,（0.2）,（注：其余空格检验数显然大于0，省略未写）,例2:某航运公司承担六个港口城市A,B,C,D,E,F间四条航线的货物运输任务。已知（1）各航线的起点、终点、日航班数（下表左）；（2）各城市间的航行时间（下表右）；（3）所有航线都使用同一种船只，每次装船和卸船时间均为1天。,问该公司至少应配备多少条船才能满足所有航线运输的需要？,解：,所需船只分成两部分,(1)载货航行需要的船只数：,3*19+2*5+9+15=91条.,(2)各港口间调度需要的船只数.,各港口每天船只的余缺数为:,调度需要船只：2+13+5+17+3=40,至,从,A,B,E,产量,2,3,5,C,1,1,0,2,14,13,17,D,（-2）,2,2,7,8,3,F,1,1,销量,1,1,3,（0）,（7）,（7）,（2）,（0）,（7）,（9）,(1)运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有唯一最优解，有无穷多最优解，无界解，无可行解。(2)在运输问题中，只要任意给出一组含（m+n-1）个