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

《运筹学基础-整数规划(3)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、三、0-1规划的应用举例1、m个约束条件只有k个起作用m个约束条件可表示为：增加变量定义为：又设M为任意大的数，则表明：m个约束条件中有m-k个的右端项为bi+Myi，不起约束作用【实例】maxZ=3x1+5x2x1≤82x2≤12三个约束中只有两个起作用3x1+4x2≤36x1≥0,x2≥0引入辅助变量模型化为：maxZ=3x1+5x2x1≤8+My12x2≤12+My23x1+4x2≤36+My3y1+y2+y3=1x1≥0,x2≥0,yi只取0或12、约束条件的右端可能是b1或b2…br即：引入变量定义

2、为：则原约束可表示为【例如】某约束为2x1+5x2-x3≤2或3引入辅助变量y1,y2,约束化为2x1+5x2-x3≤2y1+3y2y1+y2=1y1,y2只取0或13、两组条件满足其中一组若x1≤4,则x2≥1；否则（即x1>4时），x2≤3引入变量定义为：又M为任意大的数，则问题可表达为4、用以表示含固定费用的函数用xj代表产品j的生产量，其生产费用函数通常可表示为：Kj为与生产量无关的生产准备费用解决方法：设置一个逻辑变量yj，当xj=0时，yi=0，当xj>0时，yj=1可以看出当xj=0时，yi=0为此引进一

3、个特殊的约束条件，则模型设为【应用1】工厂的各种产品所需要的机时、人工工时、原材料的资源数量及可用资源的总量、产品的售价和各种资源的价格等因素。有关信息在下表中给出。产品A产品B资源总量　资源价格（元／单位）机器（时）68120５人工（时）10510020原材料(公斤)1181301产品售价（元）600400设x1,x2分别为产品A、B的生产量。如果生产产品A，工厂要花费1000元的固定成本，如果生产产品B，工厂要花费800元的固定成本。假设其它情况不变，请你为该工厂设计一个使利润最大化的生产方案。再令y1,y2分别表

4、示生产A、B和可能性（即1为生产，0为不生产）例2东方大学计算机实验室聘用4名大学生（代号为1、2、3、4），两名研究生（代号为5、6）值班答疑，已经每人周一至周五每天最多可安排时间及每人每小时的报酬如下表：学生代号报酬每天最多可安排的值班时间周一周二周三周四周五110606072100606039.94830549.855604510.830480611.306063实验室开放时间为早8：00至晚10：00，值班时须有且仅须有一名学生值班，规定大学生每周值班不少于8小时，研究生每周值班不少于7小时，每名学生值班不超过

5、3次，每次不少于2小时，每天安排值班不超过3人，且一名为研究生。试安排一张，使总报酬最低。例2设：xij为学生i在周j值班时间，aij代表学生i在周j最多值班时间，ci代表学生i的报酬。例3红星日用化工厂为发运产品，下一年度需6种不同容积的包装，每种包装的需求量及生产一个的可变费用如下表：：由于生产不同容积包装箱需进行专门准备、下料等，生产某一容积包装箱的固定费用为1200元，又若某一容积包装箱数量不够时，可用比它容积大的代替。试问化工厂应订做哪几种代号的包装箱各多少个，使费用最节省。包装箱代号123456容积（m3）

6、0.080.10.120.150.20.25需求量（个)500550700900450400可变费用（元/个）581012.116.318.2设：xj为代号j包装箱的订做数量。补充练习题：1.整数规划maxZ=3x1+2x22x1+3x2≤142x1+x2≤9x1≥0,x2≥0x1,x2整数2.0－1规划minZ=4x1+3x2+2x32x1－5x2+3x3≤44x1+x2+3x3≥3+x2+x3≥1x1,x2,x3=0或1maxZ=3x1－x23x1-2x2≤3－5x1－4x2≤－102x1＋x2≤5x1≥0,x

7、2≥0x1,x2整数补充练习题：3.指派问题