《北邮运筹学ch5-4_规划》由会员分享，可在线阅读，更多相关《北邮运筹学ch5-4_规划（4页珍藏版）》请在金锄头文库上搜索。
1、运筹学 北京邮电大学 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. 列出所有可能解，对每个可能解先检验式（*），若满足再检 验其它约束，若不满足式（*），则认为不可行，若所有约束都 满足，则认为此
2、解是可行解，求出目标值； 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个变量每个变量取
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
