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

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