《整数规划及分支定界法概要ppt课件.ppt》由会员分享,可在线阅读,更多相关《整数规划及分支定界法概要ppt课件.ppt(40页珍藏版)》请在三一办公上搜索。
1、第三章 整数规划,3-1 整数规划问题 整数规划是一类要求变量取整数值的数学规划,可分成线性和非线性两类。 根据变量的取值性质,又可以分为全整数规划,混合整数规划,0-1整数规划等。,整数规划是数学规划中一个较弱的分支,目前只能解中等规模的线性整数规划问题,而非线性整数规划问题,还没有好的办法。,例3-1:一登山队员做登山准备,他需要携带的物品有:食品,氧气,冰镐,绳索,帐篷,照相机和通讯设备,每种物品的重要性系数和重量如下:假定登山队员可携带最大重量为25公斤。,解:如果令xi=1表示登山队员携带物品i,xi=0表示登山队员不携带物品i,则问题表示成0-1规划:Max Z= 20 x1+15
2、x2 +18x3 +14x4 +8x5 +4x6 +10 x7s.t. 5x1 + 5x2 +2x3 +6x4 +12x5 +2x6 +4x7 25xi=1或xi=0 i=1,2,.7,例3-2 背包问题( Knapsack Problem)一个旅行者,为了准备旅行的必须用品,要在背包内装一些最有用的东西,但有个数限制,最多只能装b公斤的物品,而每件物品只能整个携带,这样旅行者给每件物品规定了一个“价值”以表示其有用的程度,如果共有n件物品,第j件物品aj公斤,其价值为cj.问题变成:在携带的物品总重量不超过b公斤条件下,携带哪些物品,可使总价值最大?,解:如果令xj=1表示携带物品j,xj=
3、0表示不携带物品j,则问题表示成0-1规划: Max Z = cjxj s.t. ajxj b xj=0 或1,数学模型整数规划(IP)的一般数学模型:Max (min) Z = cjxjs.t. aijxj bi(i=1,2,m) xj 0且部分或全部是整数,解法概述当人们开始接触整数规划问题时,常会有如下两种初始想法:因为可行方案数目有限,因此经过一一比较后,总能求出最好方案,例如,背包问题充其量有2n-1种方式;连线问题充其量有n!种方式;实际上这种方法是不可行。,设想计算机每秒能比较1000000个方式,那么要比较完20!(大于2*1018)种方式,大约需要800年。比较完260种方式
4、,大约需要360世纪。,先放弃变量的整数性要求,解一个线性规划问题,然后用“四舍五入”法取整数解,这种方法,只有在变量的取值很大时,才有成功的可能性,而当变量的取值较小时,特别是0-1规划时,往往不能成功。,例3-3 求下列问题:Max Z=3x1+13x2s.t.2x1+9x2 40 11x1-8x2 82 x1,x2 0,且取整数值,O 1 2 3 4 5 6 7 8 9 10,5 4 3 2 1,x1,x2,I(2,4),B(9.2,2.4),A,D,可行域OABD内整数点,放弃整数要求后,最优解B(9.2,2.4) Z0=58.8,而原整数规划最优解I(2,4) Z0=58,实际上B附
5、近四个整点(9,2)(10,2)(9,3)(10,3)都不是原规划最优解。,O 1 2 3 4 5 6 7 8 9 10,5 4 3 2 1,x1,x2,I(2,4),B(9.2,2.4),A,D,假如能求出可行域的“整点凸包”(包含所有整点的最小多边形OEFGHIJ),则可在此凸包上求线性规划的解,即为原问题的解。但求“整点凸包”十分困难。,E,F,G,H,I,J,O 1 2 3 4 5 6 7 8 9 10,5 4 3 2 1,x1,x2,I(2,4),B(9.2,2.4),A,D,假如把可行域分解成五个互不相交的子问题P1 P2 P3 P4 P5之和, P3 P5的定义域都是空集,而放弃
6、整数要求后P1最优解I(2,4),Z1=58 P2最优解(6,3),Z2=57 P4最优解(98/11,2),Z4=52(8/11),P1,P2,P4,X1 2,X1 6,X2 3,X2 2,X1 3,X1 7,X2 4,X2 3,P1,P5,P4,P2,P3,P,假如放弃整数要求后,用单纯形法求得最优解,恰好满足整数性要求,则此解也是原整数规划的最优解。 以上描述了目前解整数规划问题的两种基本途径。,分枝定界解法(Branch and Bound Method)原问题的松驰问题:任何整数规划(IP),凡放弃某些约束条件(如整数要求)后,所得到的问题(P) 都称为(IP)的松驰问题。,最通常的
7、松驰问题是放弃变量的整数性要求后,(P)为线性规划问题。,分枝定界法步骤一般求解对应的松驰问题,可能会出现下面几种情况:若所得的最优解的各分量恰好是整数,则这个解也是原整数规划的最优解,计算结束。若松驰问题无可行解,则原整数规划问题也无可行解,计算结束。,若松驰问题有最优解,但其各分量不全是整数,则这个解不是原整数规划的最优解,转下一步。从不满足整数条件的基变量中任选 一个xl进行分枝,它必须满足xl xl 或xl xl +1中的一个,把这两个约束条件加进原问题中,形成两个互不相容的子问题(两分法)。,定界:把满足整数条件各分枝的最优目标函数值作为上(max)(下(min))界,用它来判断分枝
8、是保留还是剪枝。剪枝:把那些子问题的最优值与界值比较,凡不优或不能更优的分枝全剪掉,直到每个分枝都查清为止。,例5-6 用分枝定界法求解: Max Z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 且为整数用单纯形法可解得相应的松驰问题的最优解(6/5,21/10),Z=111/10为各分枝的上界。,0 1 2 3 4,4 3 2 1,x1,x2,分枝:X1 1,x1 2,P1,P2,两个子问题:(P1)Max Z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 , x1 1 ,整数用单纯形法可解得相应的(P1)的最优解
9、(1,9/4) Z=10(3/4),(P2)Max Z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 , x1 2 ,整数用单纯形法可解得相应的(P2)的最优解(2,1/2) Z=9(1/2),0 1 2 3 4,4 3 2 1,x1,x2,再对(P1)分枝:X1 1(P3) x2 2 (P4) x2 3,P1,P2,P3,P4,(P1)两个子问题:(P3)Max Z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 ,x1 1, x2 2整数用单纯形法可解得相应的(P3)的最优解(1,2) Z=10,(P1)两个子问题:
10、(P4)Max Z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 ,x1 1, x2 3整数用单纯形法可解得相应的(P4)的最优解(0,3) Z=9,X1 2,X2 2,X1 1,X2 3,P1:(1,9/4)Z=10(3/4),P4: (0,3) Z=9,P2:(2,1/2) Z=9(1/2),P3: (1,2) Z=10,P:(6/5,21/10) Z=111/10,原问题的最优解(1,2) Z=10,例5-7 用分枝定界法求解: Min Z= x1+4x2 s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0 且取整数用单纯形法可解得相应的
11、松驰问题的最优解(10/3,4/3),Z=26/3为各分枝的下界。,0 1 2 3 4 5 6,8 7 6 5 4 3 2 1,x1,x2,p,0 1 2 3 4 5 6,8 7 6 5 4 3 2 1,x1,x2,p,选 x1进行分枝: (P1) x1 3(P2) x1 4 为空集,P1,(P1) Min Z= x1+4x2 s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0 ,x1 3 整数用单纯形法可解得(P1)的最优解(3,3/2)Z=9,(P2) Min Z= x1+4x2 s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0 x1 4 整数无可行解。,0 1
12、2 3 4 5 6,8 7 6 5 4 3 2 1,x1,x2,p,对(P1) x1 3 选 x2进行分枝: (P3) x2 1无可行解 (P4) x2 2,P4,(P3)Min Z= x1+4x2s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0, x1 3 ,x2 1整数无可行解。,(P4)Min Z= x1+4x2s.t. 2x1+ x2 8 x1+2x2 6x1,x2 0, x1 3 ,x2 2整数用单纯形法可解得(P4)的最优解(2,2)Z=10,X1 4,X2 1,X1 3,X2 2,P1:(3,3/2)Z=9,P4:(2,2) Z=10,P2:无可行解,P3:无可行解,P:(10/3,4/3) Z=26/3,原问题的最优解(2,2) Z=10,