文档详情

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

发布:2016-11-05约2.32千字共23页下载文档
文本预览下载声明
* * 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 其
显示全部
相似文档