整数规划及分支定界法课件

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