运筹学——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) 称为过滤性条件。初看起来，增加约束条件需增加计算量，实际减少了计算量。 no 6 2 6 (1,1,1) 8 no 1 (1,1,0) 7 8 yes 1 1 2 0 8 (1,0,1) 6 3 yes 0 1 1 1 3 (1,0,0) 5 no 5 1 3 (0,1,1) 4 no -2 (0,1,0) 3 5 yes 1 0 1 -1 5 (0,0,1) 2 no 0 (0,0,0) 1 Z值 满足 s.t.4 s.t.3 s.t.2 s.t.1 s.t.0 (X1,X2,X3) 循环 最优解（1，0，1） Z=8 增加约束条件（0）（Z ? 3)后实际做了24次运算，而原问题需要计算23*4=32次运算（3个变量，4个约束条件）。 注意： 改进过滤性条件，在计算过程中随时调整右边常数。 价值系数按递增排列。 以上两种方法可减少计算量。 5 yes 1 0 1 -1 5 (0,0,1) 2 no 0 (0,0,0) 1 Z值 满足 s.t.4 s.t.3 s.t.2 s.t.1 s.t.0 (X2,X1,X3) 循环 改进过滤性条件Z ? 5 (0’) 8 yes 1 1 2 0 8 (0,1,1) 4 no 3 (0,1,0) 3 Z值 满足 s.t.4 s.t.3 s.t.2 s.t.1 s.t.0’ (X2,X1,X3) 循环 改进过滤性条件Z ? 8 (0’’) no 6 (1,1,1) 8 no 1 (1,1,0) 7 no 3 (1,0,1) 6 no -2 (1,0,0) 5 Z值 满足 s.t.4 s.t.3 s.t.2 s.t.1 s.t.0’’ (X2,X1,X3) 循环 最优解(X2,X1,X3) =（0，1，1） Z=8 实际只计算了16次 例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 其