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

三、三、0-10-1规划的应用举例规划的应用举例1、m个约束条件只有k个起作用mibainjij,,11m个约束条件可表示为：增加变量定义为：个约束条件起作用假定第个约束条件不起作用假定第iiyi01又设M为任意大的数，则kmyyyMybxatsmiijnjij211..表明：m个约束条件中有m-k个的右端项为bi+Myi，不起约束作用【实例】【实例】3,2,1i0i1iyi个约束条件起作用假定第个约束条件不起作用假定第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或122、约束条件的右端可能是b1或b2…brr211bbbxajnjij或或即：引入变量定义为：否则假定约束右端为01iiby则原约束可表示为121111rriiinjijyyyybxa【例如】某约束为2x1+5x2-x3≤2或3引入辅助变量y1,y2,约束化为2x1+5x2-x3≤2y1+3y2y1+y2=1y1,y2只取0或133、两组条件满足其中一组若x1≤4,则x2≥1；否则（即x1>4时），x2≤3引入变量定义为：2101，组条件起作用第组条件不起作用第iiiyi10,13414212122211211或只取yyyyMyxMyxMyxMyx又M为任意大的数，则问题可表达为44、用以表示含固定费用的函数、用以表示含固定费用的函数用xj代表产品j的生产量，其生产费用函数通常可表示为：Kj为与生产量无关的生产准备费用解决方法：设置一个逻辑变量yj，当xj=0时，yi=0，当xj>0时，yj=11yMyxyyKxcziijinjjjjj或00min1可以看出当xj=0时，yi=0000jjjjjijxxxcKxC为此引进一个特殊的约束条件，则模型设为【应用【应用11】】工厂的各种产品所需要的机时、人工工时、原材料的资源数量及可用资源的总量、产品的售价和各种资源的价格等因素。有关信息在下表中给出。产品A产品B资源总量资源价格（元／单位）机器（时）68120５人工（时）10510020原材料(公斤)1181301产品售价（元）600400设x1,x2分别为产品A、B的生产量。0,13081110051012086181120510586400600max2121212121212121xxxxxxxxxxxxxxxxz一很大数代替代表任意大的数，可用注：其中或为M10yyyyxxMyxMyxxxxxxxyyxxxxxxxxz21212122112121212121212121,0,,,130811100510120868001000181120510586400600max如果生产产品A，工厂要花费1000元的固定成本，如果生产产品B，工厂要花费800元的固定成本。假设其它情况不变，请你为该工厂设计一个使利润最大化的生产方案。再令y1,y2分别表示生产A、B和可能性（即1为生产，0为不生产）例例22东方大学计算机实验室聘用4名大学生（代号为1、2、3、4），两名研究生（代号为5、6）值班答疑，已经每人周一至周五每天最多可安排时间及每人每小时的报酬如下表：学生代号报酬每天最多可安排的值班时间周一周二周三周四周五110606072100606039.94830549.855604510.830480611.306063实验室开放时间为早8：00至晚10：00，值班时须有且仅须有一名学生值班，规定大学生每周值班不少于8小时，研究生每周值班不少于7小时，每名学生值班不超过3次，每次不少于2小时，每天安排值班不超过3人，且一名为研究生。试安排一张，使总报酬最低。例例225,,1;6,,110;0136,,1335,,13145,,11476,5784,,185,,1;6,,12min6551616151516151ji或yx每天至少一个研究生yy次每人不超过iy人每天不超过jyh每天jxh研究生不ixh大学生不ix不超过jiyaxyxczijijjjjijiijiijjijjijijijijijijiji开放少于少于安排设：xij为学生i在周j值班时间，aij代表学生i在周j最多值班时间，ci代表学生i的报酬。否则ij安排学生在周值排...