3.2整数规划的求解方法

解法概述当人们开始接触整数规划问题时，常会有如下两种初始想法：因为可行方案数目有限，因此经过一一比较后，总能求出最好方案，例如，背包问题充其量有2n-1种方式；连线问题充其量有n!种方式；实际上这种方法是不可行。设想计算机每秒能比较1000000个方式，那么要比较完20!（大于2*1018）种方式，大约需要800年。比较完260种方式，大约需要360世纪。先放弃变量的整数性要求，解一个线性规划问题，然后用“四舍五入”法取整数解，这种方法，只有在变量的取值很大时，才有成功的可能性，而当变量的取值较小时，特别是0-1规划时，往往不能成功。例求下列问题：MaxZ=3x1+13x2s.t.2x1+9x24011x1-8x282x1,x20,且取整数值整数规划的图解法O1234567891054321x1x2I(2,4)B(9.2,2.4)AD可行域OABD内整数点，放弃整数要求后，最优解B(9.2,2.4)Z0=58.8，而原整数规划最优解I(2,4)Z0=58，实际上B附近四个整点(9,2)(10,2)(9,3)(10,3)都不是原规划最优解。O1234567891054321x1x2I(2,4)B(9.2,2.4)AD假如能求出可行域的“整点凸包”（包含所有整点的最小多边形OEFGHIJ），则可在此凸包上求线性规划的解，即为原问题的解。但当决策变量多时求“整点凸包”十分困难。EFGHIJO1234567891054321x1x2I(2,4)B(9.2,2.4)AD假如把可行域分解成五个互不相交的子问题P1P2P3P4P5之和,P3P5的定义域都是空集,而放弃整数要求后P1最优解I(2,4),Z1=58P2最优解(6,3),Z2=57P4最优解(98/11,2),Z4=52(8/11)P1P2P4X12X16X23X22X13X17X24X23P1P5P4P2P3P2分枝定界解法（BranchandBoundMethod)原问题的松驰问题：任何整数规划（IP），凡放弃某些约束条件（如整数要求）后，所得到的问题（P）都称为（IP）的松驰问题。最通常的松驰问题是放弃变量的整数性要求后，（P）为线性规划问题。分枝定界法步骤一般求解对应的松驰问题，可能会出现下面几种情况：若所得的最优解的各分量恰好是整数，则这个解也是原整数规划的最优解，计算结束。分枝定界法步骤一般求解对应的松驰问题，可能会出现下面几种情况：若所得的最优解的各分量恰好是整数，则这个解也是原整数规划的最优解，计算结束。若松驰问题无可行解，则原整数规划问题也无可行解，计算结束。若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数规划的最优解，转下一步。若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数规划的最优解，转下一步。从不满足整数条件的基变量中任选一个xl进行分枝，它必须满足xl[xl]或xl[xl]+1中的一个，把这两个约束条件加进松弛问题P中，形成两个互不相容的子问题P1和P2，即改进的松弛问题。定界：把满足整数条件各分枝的最优目标函数值作为上（下）界，用它来判断分枝是保留还是剪枝。（对目标求max的ILP问题,松弛问题的最优值是ILP的最优值的一个上界，松弛问题的任一整数可行解对应的目标函数值都是ILP的一个下界）定界：把满足整数条件各分枝的最优目标函数值作为上（下）界，用它来判断分枝是保留还是剪枝。剪枝：把那些子问题的最优值与界值比较，凡不优或不能更优的分枝全剪掉，直到每个分枝都查清为止。例用分枝定界法求解：MaxZ=4x1+3x2s.t.3x1+4x2124x1+2x29x1,x20整数用单纯形法可解得相应的松驰问题的最优解（6/5，21/10）Z=111/10为各分枝的上界。012344321x1x2分枝：X11,x12P1P2两个子问题：（P1）MaxZ=4x1+3x2s.t.3x1+4x2124x1+2x29x1,x20，x11用单纯形法可解得相应的（P1）的最优解（1，9/4）Z=10(3/4)（P2）MaxZ=4x1+3x2s.t.3x1+4x2124x1+2x29x1,x20，x12用单纯形法可解得相应的（P2）的最优解（2，1/2）Z=9(1/2)012344321x1x2再对（P1）分枝：X11（P11）x22（P12）x23P1P2P11P12（P1）两个子问题：（P11）MaxZ=4x1+3x2s.t.3x1+4x2124x1+2x29x1,x20,x11,x22用单纯形法可解得相应的（P11）的最优解（1，2）Z=10（P1）两个子问题：（P12）MaxZ=4x1+3x2s.t.3x1+4x2124x1+2x29x1,x20,x11,x23用单纯形法可解得相应的（P12）的最优解（0，3）Z=9X12X22X11X23P1:(1,9/4)Z=10(3/4)P12:(0,3)Z=9P2:(2,1/2)Z=9(1/2)P11:(1,2)Z=10P:(6/5,21/10)Z=111/10原问题的最优解（1，2）Z=10例用分枝定界法求解：MinZ=x1+4x2s.t.2x1+x28x1+2x26x1,x20整数用单纯形法可解得相应的松驰问题的最优解（10/3，4/3）Z=26/3为各分枝的下界。012345687654321x1x2p012345687654321x1x2p选x1进行分枝：(P1)x13(P2)x14为空集P1（P1）MinZ=x1+4x2s.t.2x1+x28x1+2x26x1,x20x13用单纯形法可解得（P1）的最优解（3，3/2）Z=9（P2）MinZ=x1+4x2s.t.2x1+x28x1+2x26x1,x20x14无可行解，剪去。012345687654321x1x2p对(P1)x13选x2进行分枝：(P11)x21无可行解(P12)x22P12（P11）MinZ=x1+4x2s.t.2x1+x28x1+2x26x1,x20，x13，x21无可行解，剪去。（P12）MinZ=x1+4x2s.t.2x1+x28x1+2x26x1,x20，x13，x22用单纯形法可解得（P12）的最优解（2，2）Z=10X14X21X13X22P1:(3,3/2)Z=9P12:(2,2)Z=10P2:无可行解P11:无可行解P:(10/3,4/3)Z=26/3原问题的最优解（2，2）Z=10注：求解混合整数规划问题，只对整数变量分支，对非整数变量不分支。