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

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