资源预览内容
第1页 / 共4页
第2页 / 共4页
第3页 / 共4页
第4页 / 共4页
亲,该文档总共4页全部预览完了,如果喜欢就下载吧!
资源描述
运筹学 北京邮电大学 5.4 01规划规划 Binary Integer Programming Ch5Integer Programming 2013-5-17Page 1 of 4 求解求解01整数规划的隐枚举法整数规划的隐枚举法(Implicit Enumeration Method) 隐枚举法的步骤: 1.找出任意一可行解,目标函数值为Z0; 2. 原问题求最大值时,则增加一个约束 02211 Zxcxcxc nn 当求最小值时,上式改为小于等于约束; 3. 列出所有可能解,对每个可能解先检验式(*),若满足再检 验其它约束,若不满足式(*),则认为不可行,若所有约束都 满足,则认为此解是可行解,求出目标值; 4. 目标函数值最大(最小)的解就是最优解。 (*) 运筹学 北京邮电大学 5.4 01规划规划 Binary Integer Programming Ch5Integer Programming 2013-5-17Page 2 of 4 【例【例5.6 】用隐枚举法求下列01整数规划的最优解 3 , 2 , 110 )3(42 )2(253 ) 1 (32 326max 321 321 321 321 jx xxx xxx xxx xxxZ j 或 【解】容易求得X(1,0,0)是一可行解,Z06。加一个约束 6326 321 xxx (0) 由于3个变量每个变量取0或1,共有8种组合,用列表的方法检验每 种组合解是否可行解,满足约束打上记号“”,不满足约束打上记 号“ ”,计算如表53所示。 运筹学 北京邮电大学 5.4 01规划规划 Binary Integer Programming Ch5Integer Programming 2013-5-17Page 3 of 4 表53 变量组合约束(0)约束(1)约束(2)约束(3)Z ( 0 , 0 , 0) ( 0 , 0 , 1) ( 0 , 1 , 0) ( 0 , 1 , 1) ( 1 , 0 , 0) ( 1 , 0 , 1) ( 1 , 1 , 0) ( 1 , 1 , 1) 由表53知,X(1,0,1)是最优解,最优值Z9。 6 9 运筹学 北京邮电大学 5.4 01规划规划 Binary Integer Programming Ch5Integer Programming 2013-5-17Page 4 of 4 作业:教材P135 T5.6 指派问题 Exit
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号