隐枚举法(运筹学)(课堂PPT).ppt

(一一)、基本思想：、基本思想：对对maxZ=CXAX=bX为为0,1的的2n个可能解，只检查其中一部分个可能解，只检查其中一部分例：例：maxZ=2x1+4x2+x33x1-8x2+5x3 -1x1,x2,x3为为 0,1 2.4 隐枚举法隐枚举法1X1=1X1=0111 01 01 01X2=0X3=00X2=0X2=1X1=1X3=100012(二二)、简单隐枚举法、简单隐枚举法(max)原则：原则：(1)、用试探法，求出一个可行解，以它的目标、用试探法，求出一个可行解，以它的目标值作为当前最好值值作为当前最好值Z0(2)、增加过滤条件、增加过滤条件Z Z0(3)、将、将xi 按按ci由小由小大排列大排列3例：例：maxZ=3x1-2x2+5x3x1+2x2-x3 2 x1+4x2+x3 4 x1+x2 3 4x2+x3 6 x1,x2,x3为为0或或1解：观察得解解：观察得解(x1,x2,x3)=(1,0,0)Z0=3过滤条件过滤条件：3x1-2x2+5x3 3 将将(x1 x2 x3)(x2 x1 x3)4解解(x2 x1 x3)目标值目标值 Z0 当前最好值当前最好值 (0,0,0)0 5 (0,1,0)3 8 (1,0,0)-2 (1,0,1)3 (1,1,0)1 (1,1,1)6 最优解最优解 x=(1,0,1)T Z=85