22整数规划解法

1§2.2整数规划解法(一)、整数规划的解：可行域为其相应线性规划问题的可行域的子集例1、LP:X=(4.8,0)maxZ=96ILP:X=(4,1)maxZ=90x1x262O6.5(4.8,0)2(1)、四舍五入法可估近似解，例中X=(4,0),Z=8080Z*960Z*-8016(2)、穷举法当100个0－1变量，计算机，几亿年3•分枝定界法•割平面法•隐枚举法(二)、常用方法4(三)、分枝定界法基本思路maxZ=CXAX=bX0(A)maxZ=CXAX=bX0X为整数(B)(B)为(A)的松弛问题。5(C)(D)(B)Xji+1(B)XjiX*Xj*i+1i6maxZ=40X1+90X29X1+7X2567X1+20X270X1,X20X1,X2为整数例：7解：先解(1)的松弛问题X*=4.8091.817Z*=355.890，上界Z*选X1分枝问题(2)(1)X14问题(3)(1)X158选(2)继续分枝问题(4)(2)X22问题(5)(2)X23解为X1=4X2=2.1Z=349.0解为X1=5X2=1.571Z=341.399(1)4.8091.817S0=0355.890(2)42.1S0=0349.0(3)51.571S0=0341.39(4)42S0=0340(5)1.4283340327.12(6)5.4441340307.76(7)无解X14X15X22X21X22X2310分枝定界法一般步骤：(1)、(A),先解(A)的松弛问题(B)(2)、①(B)无可行解→(A)无可行解。②(B)最优解符合(A)要求，停。③(B)最优解不符合(A)要求，转(3)。(3)、估整数解S0，作下界(4)、选(B)解中不符合整数条件的分量Xj(Xj=bj)分枝，作(B)的后续问题(C)、(D)。(C)：(B）加约束Xj[bj](D)：(B)加约束Xj[bj]+111(5)、解(C)、(D)剪枝条件：①(C)，[(D)]无可行解②(C)，[(D)]对应的目标值SS0③(C)，[(D)]对应的目标值ScS0且解为整数解，令ScS0且解为非整数解，令(C)，[(D)]取代(B)返回(4)(6)、全部枝剪完，停12优点：(1)、任何模型均可用；(2)、思路简单、灵活；(3)、速度快；(4)、适合上机。13分枝定界法注意事项：(1)、分枝变量选择原则：①按目标函数系数：选系数绝对值最大者变量先分。对目标值升降影响最大。②选与整数值相差最大的非整数变量先分枝。③按使用者经验，对各整数变量排定重要性的优先顺序。14(2)、分枝节点选择：②广探法：选目标函数当前最大值节点，找到的整数解质量高。慢。①深探法(后进先出法)：最后打开的节点最先选，尽快找到整数解。整数解质量可能不高。150－1问题的分枝定界法（背包问题)例：maxZ=12X1+12X2+9X3+15X4+90X5+26X6+112X7(A)3X1+4X2+3X3+3X4+15X5+13X6+16X735Xj为0或1，(j=1…7)松弛问题(B)为同于(A)约束，目标0Xj1(j=1…7)16解:“单位重量价值大的先放”重量价值价/重13124④24123339343155③515906②6132627161127①17(0)Z=221X7=X5=X4=1X1=1/3(9)217X1=X4=X7=1X5=13/5(10)217X1=X7=X5=1X2=1/4(5)216X3=X7=X5=1X4=1/3(6)219X7=X5=X4=1X6=1/13(1)219X1=X7=X5=1X4=1/3(7)174X6=X7=1X5=6/15(8)217X7=X5=X4=1(2)220X7=X5=X4=1X2=1/4(3)214X2=X7=X5=1(4)220X7=X5=X4=1X3=1/3X1=1X1=0X2=1X2=0X3=1X3=0X4=1X4=0X6=1X6=018隐枚举法(一)、基本思想：对maxZ=CXAX=bX为0的2n个可能解，只检查其中一部分例：maxZ=2x1+4x2+x33x1-8x2+5x3-1x1,x2,x3为0,119X1=1X1=0111010101X2=0X3=00X2=0X2=1X1=1X3=1000120(二)、简单隐枚举法(max)原则：(1)、用试探法，求出一个可行解，以它的目标值作为当前最好值Z0(2)、增加过滤条件ZZ0(3)、将xi按ci由小大排列21例：maxZ=3x1-2x2+5x3x1+2x2-x32①x1+4x2+x34②x1+x23③4x2+x36④x1,x2,x3为0或1解：观察得解(x1,x2,x3)=(1,0,0)Z0=3过滤条件：3x1-2x2+5x33将(x1x2x3)(x2x1x3)22解(x2x1x3)目标值Z0①②③④当前最好值(0,0,0)03(0,0,1)55(0,1,0)3(0,1,1)88(1,0,0)-2(1,0,1)3(1,1,0)1(1,1,1)6最优解x=(1,0,1)TZ=8