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