运筹学期末练习题PPT课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,将下列线性规划转化为标准型,1,标准型为：,5,4,3,2,1,0,0,0,5,3,max,x,x,x,x,x,z,+,+,+,+,=,2,写出下列线性规划问题的对偶问题,3,对偶规划问题为,4,运输问题,1,、最小元素法,2,、伏格尔法,3,、闭回路检验法,4,、位势检验法,5,第三章 运输问题,第一节 运输问题及其数学模型,一、运算问题的数学模型,1,、运输问题的一般提法：某种物资有若干产地和销地，现在需要把这种物资从各个产地运到各个销地，产量总数等于销量总数。已知各产地的产量和各销地的销量以及各产地到各销地的单位运价（或运距），问应如何组织调运，才能使总运费（或总运输量）最省？,6,销地,产 地,B1,B2,B3,B4,产量,A1,16,A2,10,A3,22,销量,8,14,12,14,48,4,12,10,3,4,11,9,6,11,2,8,5,例题,1,：,某部门有,3,个生产同类产品的工厂（产地），生产的产品由,4,个销售点（销地）出售，各工厂的生产量、各销售点的销售量（假定单位均为,t,）以及各工厂到各销售点的单位运价（元,/t),示于表中,:,问题：,1,写出该问题的数学模型,2,如何调运才能使总运费最小？,（用最小元素法和伏格尔法）,7,解：由于总产量和总销量均为,48,，这是一个产销平衡运算问题。,用,x,ij,表示由第,i,个产地运往第,j,个销地的产品数量，即可写出该问题的数学模型：,8,9,销地,产地,B1,B2,B3,B4,产量,A,1,16,A,2,10,A,3,22,销量,8,14,12,14,48,8,2,4,5,10,12,11,4,6,3,9,11,8,14,2,10,6,8,10,最小元素法举例,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,8,2,10,14,6,8,11,方法,3,沃格尔法,例,3,用沃格尔法求解如下运输问题,：,产地,销地,B1,B2,B3,B4,销量,行罚数,A1,16,A2,10,A3,22,产量,8,14,12,14,48,列,罚,数,4,9,2,3,10,6,8,5,11,12,11,4,0,1,1,2,5,1,3,14,8,0,1,1,2,1,3,8,6,0,1,2,1,2,8,2,7,6,1,2,12,4,4,2,2,12,用伏格尔法得到的初始基可行解,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,4,8,14,8,12,2,目标函数值,用最小元素法,求出的目标函数,z=246,13,例题,2,某部门有,3,个生产同类产品的工厂,(,产地,),生产的产品由,4,个销售点,(,销地,),出售,各工厂的生产量、各销售点的销售量,(,假设单位均为,t),以及各工厂到各销售点的单位运价,(,元,/t),如下表,问如何调运产品才能使总运费最小？,（用最小元素法和伏格尔法）,14,最小元素法,解,(1),从最小元素开始,3,即,A,1,优先满足,B,3,3,个单位,B,3,已经满足,划去,B,3,列,-3,15,(2),再从最小元素开始,4,即,A,1,优先满足,B,4,1,个单位,A,1,已经满足,划去,A,1,行,.,-3,16,(3),再从最小元素开始,4.,即,A,2,优先满足,B,1,2,个单位,B,1,已经满足,划去,B,1,列,.,-3,17,(4),再从最小元素开始,4.,即,A,2,优先满足,B,2,4,个单位,B,2,A,2,已经满足,划去,B,2,列,A,2,行,.,-3,18,(5),最后把,A,3,满足,B,4,3,个单位,得到初始方案,.,19,(6),得到初始方案,:x,13,=3,x,14,=1,x,21,=2,x,22,=4,x,34,=3,总运费,=3*3+4*1+4*2+4*4+8*3=61(,元,),20,伏格尔法,解,(1),在运价表中分别计算出各行、各列的最小运费与次最小运费的差额,并填入该表的最右列和最下行,.,21,(2),从行或列差额中选出最大者,选择它所在行或列中的最小元素,.,22,(3),在新表中,计算新的差额数,.,按,(2),的方法确定一步方案,23,(4),在新表中,计算新的差额数,.,按,(2),的方法确定一步方案,24,(5),在新表中,计算新的差额数,.,按,(2),的方法确定一步方案,25,(6),在新的表中,计算新的差额数,.,按,(2),的方法确定一步方案,26,(7),在新的表中,计算新的差额数,.,按,(2),的方法确定一步方案,27,初始方案如下,:x,13,=3,x,14,=1,x,21,=2,x,22,=1,x,24,=3,x,32,=3,费用,=3*3+4*1+4*2+4*1+5*3+6*3=58(,元,),28,最小元素法,得到初始方案,:x,13,=3,x,14,=1,x,21,=2,x,22,=4,x,34,=3,总运费,=3*3+4*1+4*2+4*4+8*3=61(,元,),29,对最小元素法得出的解进行闭回路法检验,30,空格,x,ij,的检验数,=(,第奇数次拐角点运价之和减去第偶数次拐角点运价之和,),闭回路法,31,运用闭回路法检验是否为最优解？并进行解的调整,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,8,2,10,14,6,8,32,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,8,2,10,14,6,8,2,1,33,检验数表,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,8,2,10,14,6,8,2,1,1,-1,10,12,表中的解不是最优解。,34,第三步：解的调整,调整位置（,2,，,4,）非空，回路角上的格至少为空，且保证数字的非负性。,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,8,2,10,14,6,8,-1,（,-2,）,（,-2,）,（,+2,）,（,+2,）,35,调整后的解为：,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,8,2,12,14,4,8,2,2,0,9,1,12,此时的解为最优解。,36,用闭回路检验是否为最优解？,37,-1,38,-1,39,-2,40,-1,41,-5,42,-5,计算得到的初始基可行解不是最优解,(,33,0,),43,用位势法检验该运输成本是否为最优解？,44,指派问题,45,