运筹学——0-1整数规划课件.ppt

0-1 规划及其解法 0-1 规划在线性整数规划中具有重要地位。 定理：任何整数规划都可以化成0-1规划。 一般地说，可把整数x变成(k+1)个0-1变量公式为：x=y0+2y1+22y2+….2kyk 若x上界为U，则对0xU,要求k满足2k+1 ? U+1. 由于这个原因，数学界曾纷纷寻找“背包问题”解的方法，但进展缓慢。; 对于0－1 规划问题，由于每个变量只取0，1两个值，一般会用穷举法来解，即将所有的0，1 组合找出，使目标函数达到极值要求就可求得最优解。但此法太繁琐，工作量相当大。而隐枚举法就是在此基础上，通过加入一定的条件，就能较快的求得最优解。; 隐枚举法(Implicit Enumeration) 这种方法可以从所有变量等于零出发（初始点），然后依次指定一些变量取值为1，直到获得一个可行解，于是把第一个可行解记作迄今为止最好的可行解，再重复，依次检查变量为0，1的各种组合，对迄今为止最好的可行解加以改进，直到获得最优解。;例1 求下列问题： Max Z=3x1- 2x2 + 5x3 s.t. x1+2x2 - x3 ? 2 (1) x1+4x2 + x3 ? 4 (2) x1 + x2 ? 3 (3) 4x2 + x3 ? 6 (4) xj ? 0或1 (5);解： 容易看出(1,0,0)满足约束条件，对应Z=3，对Max Z来说，希望Z ? 3,所以增加约束条件： Z=3x1- 2x2 + 5x3 ? 3 (0) 称为过滤性条件。初看起来，增加约束条件需增加计算量，实际减少了计算量。;循环;增加约束条件（0）（Z ? 3)后实际做了24次运算，而原问题需要计算23*4=32次运算（3个变量，4个约束条件）。;注意： 改进过滤性条件，在计算过程中随时调整右边常数。 价值系数按递增排列。 以上两种方法可减少计算量。;循环;;例2 求下列问题： Max Z=3x1+ 4x2 + 5x3 + 6x4 s.t. 2x1+ 3x2 + 4x3 + 5x4 ? 15 xj ? 0且为整数 解：先变换xj为0-1变量 x=y0+2y1+22y2+….2kyk;解：先变换xj为0-1变量 x=y0+2y1+22y2+….2kyk x1 ? 7 x1=y01+2y11+22y21 x2 ? 5 x2=y02+2y12+22y22 x3 ? 3 x3=y03+2y13 x4 ? 3 x4=y04+2y14 代入原问题，得到：;Max Z= 3 y01+6y11+12y21 + 4y02+8y12+16y22 + 5 y03+10y13 + 6 y04+12y14 s.t. 2y01+4y11+8y21 +3y02+6y12 +12y22 + 4 y03+8y13 + 5 y04 +10y14 ? 15 yij=0或=1;用隐枚举法可得到： y11=y21 =y02 =1 其他全为零 最优解（6，1，0，0） Z=22 ; 例3、求解下列0－1 规划问题; 可以从( 1.1.1.1 )开始试算， x′(3)＝( 1.1.0.1 )最优解。 ∴ x(3)＝( 1.0.1.0 )是原问题的最优解，Z* =－2;例4、求解下列0－1 规划问题;y1 . y2. y3 . y4. y5;练习：用隐枚举法求解0—1规划问题;0-1规划应用 华美公司有5个项目被列入投资计划，各项目的投资额和期望的投资收益见下表：;该公司只有600万元资金可用于投资，由于技术原因，投资受到以下约束： 在项目1、2和3中必须有一项被选中； 项目3和4只能选中一项； 项目5被选中的前提是项目1必须被选中。 如何在上述条件下，选择一个最好的投资方案，使收益最大。;解：令 1 选中该项目 0 未选中该项目 ;欢迎你继续学习整数规划的其它内容！