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

第三章第三章第三章第三章 整数规划整数规划整数规划整数规划 3-1 3-1 整数规划问题整数规划问题 整整数数规规划划是是一一类类要要求求变变量量取取整整数数值值的的数数学学规规划划，可可分分成成线线性性和和非非线线性性两类。两类。根根据据变变量量的的取取值值性性质质，又又可可以以分分为为全全整整数数规规划划，混混合合整整数数规规划划，0-10-1整数规划等。整数规划等。整数规划是数学规划中整数规划是数学规划中一个较弱的分支，目前只能一个较弱的分支，目前只能解中等规模的线性整数规划解中等规模的线性整数规划问题，而非线性整数规划问问题，而非线性整数规划问题，还没有好的办法。题，还没有好的办法。例例3-13-1：一一登登山山队队员员做做登登山山准准备备，他他需需要要携携带带的的物物品品有有：食食品品，氧氧气气，冰冰镐镐，绳绳索索，帐帐篷篷，照照相相机机和和通通讯讯设设备备，每每种种物物品品的的重重要要性性系系数数和和重重量量如如下下：假假定定登登山山队队员员可携带最大重量为可携带最大重量为2525公斤。公斤。序号序号序号序号1 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 67 7 7 7物品物品物品物品 食品食品食品食品 氧气氧气氧气氧气 冰镐冰镐冰镐冰镐 绳索绳索绳索绳索 帐篷帐篷帐篷帐篷 相机相机相机相机 设备设备设备设备重量重量重量重量5 5 5 55 5 5 52 2 2 26 6 6 6121212122 2 2 24 4 4 4重要重要重要重要系数系数系数系数202020201515151518181818141414148 8 8 84 4 4 410101010解：解：如果令如果令x xi i=1=1表示登山队员携表示登山队员携带物品带物品i i，x xi i=0=0表示登山队员不携表示登山队员不携带物品带物品i i，则问题表示成，则问题表示成0-10-1规划规划:Max Z=20 xMax Z=20 x1 1+15x+15x2 2+18x+18x3 3+14x+14x4 4 +8x+8x5 5+4x+4x6 6+10 x+10 x7 7s.t.5xs.t.5x1 1+5x+5x2 2+2x+2x3 3+6x+6x4 4+12x+12x5 5+2x+2x6 6+4x7 25x xi i=1=1或或x xi i=0 i=1,2,=0 i=1,2,.7.7例例3-23-2 背包问题背包问题(Knapsack Problem)(Knapsack Problem)一个旅行者一个旅行者,为了准备旅行的必须用品为了准备旅行的必须用品,要要在背包内装一些最有用的东西在背包内装一些最有用的东西,但有个数但有个数限制限制,最多只能装最多只能装b b公斤的物品公斤的物品,而每件物而每件物品只能整个携带品只能整个携带,这样旅行者给每件物品这样旅行者给每件物品规定了一个规定了一个“价值价值”以表示其有用的程度以表示其有用的程度,如果共有如果共有n n件物品件物品,第第j j件物品件物品a aj j公斤公斤,其价其价值为值为c cj j.问题变成问题变成:在携带的物品总重量不在携带的物品总重量不超过超过b b公斤条件下公斤条件下,携带哪些物品携带哪些物品,可使总可使总价值最大价值最大?解：解：如果令如果令x xj j=1=1表示携带物品表示携带物品j j，x xj j=0=0表示不携带物品表示不携带物品j j，则问题表，则问题表示成示成0-10-1规划规划:Max Z=c Max Z=cj jx xj j s.t.a s.t.aj jx xj j b b x xj j=0 =0 或或1 1数学模型数学模型整数规划整数规划(IP)(IP)的一般数学模型的一般数学模型:Max(min)Z=cMax(min)Z=cj jx xj js.t.as.t.aijijx xj j b bi i(i=1,2,(i=1,2,m)m)x xj j 0 0且部分或全部是整数且部分或全部是整数解法概述解法概述当人们开始接触整数规划问题时，当人们开始接触整数规划问题时，常会有如下两种初始想法：常会有如下两种初始想法：因为可行方案数目有限，因此经过因为可行方案数目有限，因此经过一一比较后，总能求出最好方案，一一比较后，总能求出最好方案，例如，背包问题充其量有例如，背包问题充其量有2 2n-1n-1种方式；种方式；连线问题充其量有连线问题充其量有n!n!种方式；实际种方式；实际上这种方法是不可行。上这种方法是不可行。设想计算机每秒能比较设想计算机每秒能比较10000001000000个方式，那么要比较个方式，那么要比较完完20!20!（大于（大于2*102*101818）种方式，）种方式，大约需要大约需要800800年。比较完年。比较完2 26060种种方式，大约需要方式，大约需要360360世纪。世纪。先放弃变量的整数性要求，解一先放弃变量的整数性要求，解一个线性规划问题，然后用个线性规划问题，然后用“四舍五四舍五入入”法取整数解，这种方法，只有法取整数解，这种方法，只有在变量的取值很大时，才有成功的在变量的取值很大时，才有成功的可能性，而当变量的取值较小时，可能性，而当变量的取值较小时，特别是特别是0-10-1规划时，往往不能成功。规划时，往往不能成功。例例3-33-3 求下列问题：求下列问题：Max Z=3xMax Z=3x1 1+13x+13x2 2s.t.2xs.t.2x1 1+9x+9x2 2 40 40 11x 11x1 1-8x-8x2 2 82 82 x x1 1,x,x2 2 0,0,且取整数值且取整数值O 1 2 3 4 5 6 7 8 9 105 4 3 2 1x x1 1x x2 2I(2,4)B(9.2,2.4)AD可行域可行域OABDOABD内整数点，放弃整数要求后，最优内整数点，放弃整数要求后，最优解解B(9.2,2.4)ZB(9.2,2.4)Z0 0=58.8=58.8，而原整数规划最优，而原整数规划最优解解I(2,4)I(2,4)Z Z0 0=58=58，实际上，实际上B B附近四个整点附近四个整点(9,2)(10,2)(9,3)(10,3)(9,2)(10,2)(9,3)(10,3)都不是原规划最优解。都不是原规划最优解。O 1 2 3 4 5 6 7 8 9 105 4 3 2 1x x1 1x x2 2I(2,4)B(9.2,2.4)ADv假如能求出可行域的假如能求出可行域的“整点凸包整点凸包”（包包含所有整点的最小多边形含所有整点的最小多边形OEFGHIJOEFGHIJ），则），则可在此凸包上求线性规划的解，即为原问可在此凸包上求线性规划的解，即为原问题的解。但求题的解。但求“整点凸包整点凸包”十分困难。十分困难。E EF FGGH HI IJ JO 1 2 3 4 5 6 7 8 9 105 4 3 2 1x x1 1x x2 2I(2,4)B(9.2,2.4)ADv假如把可行域分解成五个互不相交的子问题假如把可行域分解成五个互不相交的子问题P P1 1 P P2 2 P P3 3 P P4 4 P P5 5之和之和,P P3 3 P P5 5的定义域都是空集的定义域都是空集,而放弃而放弃整数要求后整数要求后P P1 1最优解最优解I(2,4),ZI(2,4),Z1 1=58=58 P P2 2最优解最优解(6,3),Z(6,3),Z2 2=57=57 P P4 4最优解最优解(98/11,2),Z(98/11,2),Z4 4=52(8/11)=52(8/11)P P1 1P P2 2P P4 4X1 2X1 6X2 3X2 2X1 3X1 7X2 4X2 3P1P5P4P2P3Pv假如放弃整数要求后，用单纯形法假如放弃整数要求后，用单纯形法求得最优解，恰好满足整数性要求，求得最优解，恰好满足整数性要求，则此解也是原整数规划的最优解。则此解也是原整数规划的最优解。以上描述了目前解整数规划问题以上描述了目前解整数规划问题的两种基本途径。的两种基本途径。分枝定界解法分枝定界解法（Branch and Bound Method)Branch and Bound Method)原问题的松驰问题：任何整数规划原问题的松驰问题：任何整数规划（IPIP），凡放弃某些约束条件（如整数），凡放弃某些约束条件（如整数要求）后，所得到的问题（要求）后，所得到的问题（P P）都称为都称为（IPIP）的松驰问题。）的松驰问题。最通常的松驰问题是放弃变最通常的松驰问题是放弃变量的整数性要求后，（量的整数性要求后，（P P）为线性）为线性规划问题。规划问题。分枝定界法步骤分枝定界法步骤一般求解对应的松驰问题，可能一般求解对应的松驰问题，可能会出现下面几种情况：会出现下面几种情况：若所得的最优解的各分量恰好是若所得的最优解的各分量恰好是整数，则这个解也是原整数规划整数，则这个解也是原整数规划的最优解，计算结束。的最优解，计算结束。若松驰问题无可行解，则原整数若松驰问题无可行解，则原整数规划问题也无可行解，计算结束。规划问题也无可行解，计算结束。若松若松驰问题有最有最优解，但其各分量不全解，但其各分量不全是整数，是整数，则这个解不是原整数个解不是原整数规划的最划的最优解，解，转下一步。下一步。从不从不满足整数条件的基足整数条件的基变量中任量中任选 一一个个x xl l进行分枝，它必行分枝，它必须满足足x xl l xxll或或x xl l xxll+1+1中的一个，把中的一个，把这两个两个约束条束条件加件加进原原问题中，形成两个互不相容的中，形成两个互不相容的子子问题（两分法）。（两分法）。定界：把定界：把满足整数条件各分枝的最足整数条件各分枝的最优目目标函数函数值作作为上（上（max）（下）（下(min)）界，）界，用它来判断分枝是保留用它来判断分枝是保留还是剪枝。是剪枝。剪枝：把那些子剪枝：把那些子问题的最的最优值与界与界值比比较，凡不，凡不优或不能更或不能更优的分枝全剪掉，的分枝全剪掉，直到每个分枝都直到每个分枝都查清清为止。止。例例5-65-6 用分枝定界法求解：用分枝定界法求解：Max Z=4x Max Z=4x1 1+3x+3x2 2 s.t.s.t.3x3x1 1+4x+4x2 2 12 12 4x 4x1 1+2x+2x2 2 9 9 x x1 1,x,x2 2 0 0 且为整数且为整数用单纯形法可解得相应的松驰问题的最用单纯形法可解得相应的松驰问题的最优解（优解（6/56/5，21/1021/10），），Z=111/10Z=111/10为各分为各分枝的上界。枝的上界。0 1 2 3 44 3 2 1x1x2分枝：分枝：分枝：分枝：X X1 1 1,x 1,x1 1 2 2P P1 1P P2 2两个子问题：两个子问题：（P P1 1）Max Z=4xMax Z=4x1 1+3x+3x2 2 s.t.s.t.3x3x1 1+4x+4x2 2 12 12 4x 4x1 1+2x+2x2 2 9 9 x x1 1,x,x2 2 0 0，x x1 1 1 1 ，整数，整数用单纯形法可解得相应的（用单纯形法可解得相应的（P P1 1）的最优）的最优解（解（1 1，9/49/4）Z=10(3/4)Z=10(3/4)（P P2 2）Max Z=4xMax Z=4x1 1+3x+3x2 2 s.t.s.t.3x3x1 1+4x+4x2 2 12 12 4x 4x1 1+2x+2x2 2 9 9 x x1 1,x,x2 2 0 0，x x1 1 2 2 ，整数，整数用单纯形法可解得相应的（用单纯形法可解得相应的（P P2 2）的）的最优解（最优解（2 2，1/21/2）Z=9(1/2)Z=9(1/2)0 1 2 3 44 3 2 1x1x2再对（再对（再对（再对（P P1 1）分枝：）分枝：）分枝：）分枝：X X1 1 1 1（P P3 3）x x2 2 2 2（P P4 4）x x2 2 3 3P P1 1P P2 2P P3 3P P4 4（P P1 1）两个子问题：）两个子问题：（P P3 3）Max Z=4xMax Z=4x1 1+3x+3x2 2 s.t.s.t.3x3x1 1+4x+4x2 2 12 12 4x 4x1 1+2x+2x2 2 9 9 x x1 1,x,x2 2 0,x 0,x1 1 1,1,x x x x2 2 2 2 2 2 2 2整数整数用单纯形法可解得相应的（用单纯形法可解得相应的（P P3 3）的）的最优解（最优解（1 1，2 2）Z=10Z=10（P P1 1）两个子问题：）两个子问题：（P P4 4）Max Z=4xMax Z=4x1 1+3x+3x2 2 s.t.s.t.3x3x1 1+4x+4x2 2 12 12 4x 4x1 1+2x+2x2 2 9 9 x x1 1,x,x2 2 0,x 0,x1 1 1,1,x x x x2 2 2 2 3 3 3 3整数整数用单纯形法可解得相应的（用单纯形法可解得相应的（P P4 4）的最优）的最优解（解（0 0，3 3）Z=9Z=9X1 2X2 2X1 1X2 3P1:(1,9/4)Z=10(3/4)P4:(0,3)Z=9P2:(2,1/2)Z=9(1/2)P3:(1,2)Z=10P:(6/5,21/10)Z=111/10原问题的最优解原问题的最优解（1，2）Z=10例例5-75-7 用分枝定界法求解：用分枝定界法求解：Min Z=x Min Z=x1 1+4x+4x2 2 s.t.s.t.2x2x1 1+x+x2 2 8 8 x x1 1+2x+2x2 2 6 6 x x1 1,x,x2 2 0 0 且取整数且取整数用单纯形法可解得相应的松驰问题的最用单纯形法可解得相应的松驰问题的最优解（优解（10/310/3，4/34/3），），Z=26/3Z=26/3为各分枝的为各分枝的下界。下界。0 1 2 3 4 5 6 8 7 6 5 4 3 2 1x1x2p 0 1 2 3 4 5 6 8 7 6 5 4 3 2 1x1x2p选选选选 x x1 1进行分枝：进行分枝：进行分枝：进行分枝：(P(P1 1)x)x1 1 3 3(P(P2 2)x x1 1 4 4 为空集为空集为空集为空集P1（P P1 1）Min Z=x Min Z=x1 1+4x+4x2 2 s.t.s.t.2x2x1 1+x+x2 2 8 8 x x1 1+2x+2x2 2 6 6 x x1 1,x,x2 2 0 0，x x1 1 3 3 整数整数用单纯形法可解得（用单纯形法可解得（P P1 1）的最优解）的最优解（3 3，3/23/2）Z=9Z=9（P P2 2）Min Z=x Min Z=x1 1+4x+4x2 2 s.t.s.t.2x2x1 1+x+x2 2 8 8 x x1 1+2x+2x2 2 6 6 x x1 1,x,x2 2 0 x 0 x1 1 4 4 整数整数无可行解。无可行解。0 1 2 3 4 5 6 8 7 6 5 4 3 2 1x1x2p对对对对(P(P1 1)x)x1 1 3 3 选选选选 x x2 2进行分枝：进行分枝：进行分枝：进行分枝：(P(P3 3)x)x2 2 1 1无可行解无可行解无可行解无可行解 (P(P4 4)x x2 2 2 2P4（P P3 3）Min Z=xMin Z=x1 1+4x+4x2 2s.t.s.t.2x2x1 1+x+x2 2 8 8 x x1 1+2x+2x2 2 6 6 x x1 1,x,x2 2 0 0，x x1 1 3 3，x x2 2 1 1整数整数无可行解。无可行解。（P P4 4）Min Z=xMin Z=x1 1+4x+4x2 2s.t.s.t.2x2x1 1+x+x2 2 8 8 x x1 1+2x+2x2 2 6 6x x1 1,x,x2 2 0 0，x x1 1 3 3，x x2 2 2 2整数整数用单纯形法可解得（用单纯形法可解得（P P4 4）的最优解）的最优解（2 2，2 2）Z=10Z=10X1 4X2 1X1 3X2 2P1:(3,3/2)Z=9P4:(2,2)Z=10P2:无可行解无可行解P3:无可行解无可行解P:(10/3,4/3)Z=26/3原问题的最优解原问题的最优解（2，2）Z=10