运筹学基础-整数规划(3).ppt

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,三、,0-1,规划的应用举例,1,、,m,个约束条件只有,k,个起作用,m,个约束条件可表示为：,增加变量定义为：,又设,M,为任意大的数，则,表明：,m,个约束条件中有,m-k,个的右端项为,b,i,+M,y,i,，不起约束作用,【,实例,】,maxZ,=,3x,1,+5,x,2,x,1,8,2,x,2,12,三个约束中只有两个起作用,3x,1,+4,x,2,36,x,1,0,x,2,0,引入辅助变量,模型化为：,maxZ,=,3x,1,+5,x,2,x,1,8,+My,1,2,x,2,12,+My,2,3x,1,+4,x,2,36,+My,3,y,1,+y,2,+y,3,=1,x,1,0,x,2,0,y,i,只取,0,或,1,2,、约束条件的右端可能是,b,1,或,b,2,b,r,即：,引入变量定义为：,则原约束可表示为,【,例如,】,某约束为,2x,1,+5x,2,-x,3,2,或,3,引入辅助变量,y,1,y,2,约束化为,2x,1,+5x,2,-x,3,2,y,1,+3,y,2,y,1,+y,2,=1,y,1,y,2,只取,0,或,1,3,、两组条件满足其中一组,若,x1,4,则,x21,；否则（即,x14,时），,x2,3,引入变量定义为：,又,M,为任意大的数，则问题可表达为,4,、用以表示含固定费用的函数,用,x,j,代表产品,j,的生产量，其生产费用函数通常可表示为：,K,j,为与生产量无关的生产准备费用,解决方法：,设置一个逻辑变量,y,j,，,当,x,j,=0,时,，,y,i,=0,，,当,x,j,0,时,，,y,j,=1,可以看出当,xj,=0,时，,y,i,=0,为此引进一个特殊的约束条件，则模型设为,【,应用,1】,工厂的各种产品所需要的机时、人工工时、原材料的资源数量及可用资源的总量、产品的售价和各种资源的价格等因素。有关信息在下表中给出,。,产品,A,产品,B,资源总量资源价格（元单位）,机器（时）,6 8 120,人工（时）,10 5 100,20,原材料,(,公斤,)11 8 130 1,产品售价（元）,600 400,设,x1,x2,分别为产品,A,、,B,的生产量。,如果,生产产品,A,，工厂要花费,1000,元的固定成本，如果生产产品,B,，工厂要花费,800,元的固定成本。,假设其它情况不变，请你为该工厂设计一个使利润最大化的生产方案,。,再令,y1,y2,分别表示生产,A,、,B,和可能性（即,1,为生产，,0,为不生产）,例,2,东方大学计算机实验室聘用,4,名大学生（代号为,1,、,2,、,3,、,4,），两名研究生（代号为,5,、,6,）值班答疑，已经每人周一至周五每天最多可安排时间及每人每小时的报酬如下表：,学生代号,报酬,每天最多可安排的值班时间,周一,周二,周三,周四,周五,1,10,6,0,6,0,7,2,10,0,6,0,6,0,3,9.9,4,8,3,0,5,4,9.8,5,5,6,0,4,5,10.8,3,0,4,8,0,6,11.3,0,6,0,6,3,实验室开放时间为早,8,：,00,至晚,10,：,00,，值班时须有且仅须有一名学生值班，规定大学生每周值班不少于,8,小时，研究生每周值班不少于,7,小时，每名学生值班不超过,3,次，每次不少于,2,小时，每天安排值班不超过,3,人，且一名为研究生。试安排一张，使总报酬最低。,例,2,设：,xij,为学生,i,在周,j,值班时间，,aij,代表学生,i,在周,j,最多值班时间，,ci,代表学生,i,的报酬。,例,3,红星日用化工厂为发运产品，下一年度需,6,种不同容积的包装，每种包装的需求量及生产一个的可变费用如下表：,由于生产不同容积包装箱需进行专门准备、下料等，生产某一容积包装箱的固定费用为,1200,元，又若某一容积包装箱数量不够时，可用比它容积大的代替。试问化工厂应订做哪几种代号的包装箱各多少个，使费用最节省。,包装箱代号,1,2,3,4,5,6,容积（,m3,）,0.08,0.1,0.12,0.15,0.2,0.25,需求量（个,),500,550,700,900,450,400,可变费用（元,/,个）,5,8,10,12.1,16.3,18.2,设：,xj,为代号,j,包装箱的订做数量。,补充练习题：,1.,整数规划,maxZ,=3x,1,+2x,2,2x,1,+3x,2,14,2x,1,+x,2,9,x,1,0,x,2,0,x,1,x,2,整数,2.0,1,规划,minZ,=4x,1,+3x,2,+2x,3,2x,1,5x,2,+3x,3,4,4x,1,+x,2,+3x,3,3,+x,2,+x,3,1,x,1,x,2,x,3,=0,或,1,maxZ,=3x1,x2,3x1-2x2 3,5x1,4x2,10,2x1,x2 5,x1 0,x2 0,x1,x2,整数,补充练习题：,3.,指派问题,