《运筹学基础整数规划》由会员分享，可在线阅读，更多相关《运筹学基础整数规划（12页珍藏版）》请在金锄头文库上搜索。
1、三、三、三、三、0-10-1规划的应用举例规划的应用举例规划的应用举例规划的应用举例 1、m个约束条件只有个约束条件只有k个起作用个起作用m个约束条件可表示为：增加变量定义为：又设M为任意大的数，则 表明：m个约束条件中有m-k个的右端项为bi+Myi，不起约束作用整数规划1 1【实例】【实例】【实例】【实例】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只取只取
2、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整数规划2 22 2、约束条件的右端可能是、约束条件的右端可能是b1或或b2br即：引入变量定义为：则原约束可表示为【例如】某约束为 2x1+5x2-x32或3引入辅助变量y1,y2, 约束化为2x1+5x2-x32y1+3y2y1+y2=1y1，y2只取0或1整数规划3 33 3、两组条件满足其中一组、两组
3、条件满足其中一组若x14,则 x21；否则（即x14时）， x23引入变量定义为：又M为任意大的数，则问题可表达为整数规划4 44 4、用以表示含固定费用的函数、用以表示含固定费用的函数、用以表示含固定费用的函数、用以表示含固定费用的函数用xj代表产品j的生产量，其生产费用函数通常可表示为：Kj为与生产量无关的生产准备费用，生产才发生，不生产不发生。解决方法：设置一个逻辑变量yj，当 xj=0时，yi=0，当xj0时，yj=1 可以看出当xj=0时，yi=0；而如果yi=1，则必有xj0为此引进一个特殊的约束条件，则模型设为整数规划5 5【应用【应用【应用【应用1 1】 工厂的各种产品所需要的
4、机时、人工工时、原材料的资源数量及可用资源的总量、产品的售价和各种资源的价格等因素。有关信息在下表中给出。 产品A 产品B 资源总量资源价格（元单位）机器（时） 6 8 120人工（时） 10 5 10020 原材料(公斤) 11 8 130 1产品售价（元） 600 400 设 x1,x2分别为产品A、B的生产量。整数规划6 6 如果生产产品A，工厂要花费1000元的固定成本，如果生产产品B，工厂要花费800元的固定成本。 假设其它情况不变，请你为该工厂设计一个使利润最大化的生产方案。再令y1,y2分别表示生产A、B和可能性（即1为生产，0为不生产）整数规划7 7例例例例2 2 红星日用化工
5、厂为发运产品，下一年度需6种不同容积的包装，每种包装的需求量及生产一个的可变费用如下表： 由于生产不同容积包装箱需进行专门准备、下料等，生产某一容积包装箱的固定费用为1200元，又若某一容积包装箱数量不够时，可用比它容积大的代替。试问化工厂应订做哪几种代号的包装箱各多少个，使费用最节省。包装箱代号包装箱代号1 12 23 34 45 56 6容积（容积（m3m3）0.080.080.10.10.120.120.150.150.20.20.250.25需求量（个需求量（个) )500500550550700700900900450450400400可变费用（元可变费用（元/ /个）个）5 58
6、8101012.112.116.316.318.218.2整数规划8 8 设： xj为代号j包装箱的订做数量。包装箱代号包装箱代号1 12 23 34 45 56 6容积（容积（m3m3）0.080.080.10.10.120.120.150.150.20.20.250.25需求量（个需求量（个) )500500550550700700900900450450400400可变费用（元可变费用（元/ /个）个）5 58 8101012.112.116.316.318.218.2整数规划9 9例例3 3 东方大学计算机实验室聘用4名大学生（代号为1、2、3、4），两名研究生（代号为5、6）值班答疑
7、，已经每人周一至周五每天最多可安排时间及每人每小时的报酬如下表：学生代号学生代号报酬报酬每天最多可安排的值班时间每天最多可安排的值班时间周一周一周二周二周三周三周四周四周五周五1 110106 60 06 60 07 72 210100 06 60 06 60 03 39.99.94 48 83 30 05 54 49.89.85 55 56 60 04 45 510.810.83 30 04 48 80 06 611.311.30 06 60 06 63 3 实验室开放时间为早8：00至晚10：00，值班时须有且仅须有一名学生值班，规定大学生每周值班不少于8小时，研究生每周值班不少于7小时，
8、每名学生值班不超过3次，每次不少于2小时，每天安排值班不超过3人，且一名为研究生。试安排一张，使总报酬最低。整数规划1010【解】设： xij为学生i在周j值班时间，aij代表学生i在周j 最多值班时间，ci代表学生i的报酬。整数规划11110-1规划应用举例：maxZ= 12 x1 + 8 x2 5x1+2 x2 150 2 x1+3 x2 100 4x1+2 x2 80或6x1+8x2 120 x1, x2 0maxZ= 12 x1 + 8 x2 5x1+2 x2 150 2 x1+3 x2 100 4x1+2 x2 80+My1 6x1+8x2 120+My2 y1+y2 1 x1, x2 0整数规划1212
