整数规划解法

《整数规划解法》由会员分享，可在线阅读，更多相关《整数规划解法（95页珍藏版）》请在金锄头文库上搜索。

1、5.2 整数规划解法一、整数规划的解可行域为其相应线性规划问题的可行域的子集例1、LP:X=(4.8,0) maxZ=9600 IP:X=(4,1) maxZ=9000x1x262O6.5(4.8,0) 分枝定界法 割平面法 隐枚举法二、常用方法三、分枝定界法基本思路maxZ=CXAX=bX0(A)maxZ=CXAX=bX0X为整数 (B)(B)为(A)的松弛问题。(C)(D)(B)xj i+1(B)xj iX*Xj*i+1imaxZ=40x1 + 90x2 9x1+7x2 567x1+20x2 70x1 , x2 0 x1 , x2为整数例1：解：先解(1)的松弛问题X* =4.8091.8

2、17Z* =355.890， 上界Z* 选x1分枝问题(2)(1)x1 4问题(3)(1)x1 5选(2)继续分枝问题(4)(2)x2 2问题(5)(2)x2 3解为x1 =4x2 =2.1Z=349.0解为x1 =5x2 =1.571Z=341.39 图解法分析：、 、 、 、 、 、 、 、 、 、 、 0 1 2 3 4 5 6 7 8 9 108 -7 -6 -5 -4 -3 -2 -1 -B不是问题A解 但 图解法分析：0 1 2 3 4 5 6 7 4321 图解法分析：0 1 2 3 4 5 6 7 4321 图解法分析：43210 1 2 3 4 5 6 7 是问题A解 但 不

3、是问题A解 而 剪枝 图解法分析：0 1 2 3 4 5 6 7 4321(1)4.809 1.817S0 =0355.890(2)4 2.1S0 =0349.0(3)5 1.571S0 =0341.39(4)4 2S0 =0340(5)1.428 3340327.12(6)5.444 1340307.76(7)无解x1 4x1 5x2 2x2 1x2 2x2 3分枝定界法一般步骤：(1)、(A), 先解(A)的松弛问题(B)(2)、 (B)无可行解(A)无可行解。 (B)最优解符合(A)要求，停。 (B)最优解不符合(A)要求，转(3)。(3)、估整数解S0 ，作下界(4)、选(B)解中不符

4、合整数条件的分量xj 分枝，作(B)的后续问题 (C)、(D)。(C)： (B）加约束xj xj (D)：(B)加约束xj xj +1(5)、解(C)、(D)剪枝条件： (C)， (D) 无可行解 (C)， (D) 对应的目标值S S0 (C)， (D) 对应的目标值ScS0 且解为整数解，令ScS0 且解为非整数解，令(C)， (D) 取代(B) 返回(4)(6)、全部枝剪完，停优点：(1)、任何模型均可用；(2)、思路简单、灵活；(3)、速度快；(4)、适合上机。四、割平面法割平面法是通过生成一系列的平面割掉非整数部分 来得到最优整数解的方法。割平面法的基本思路是：当得到的解不满足取整约束

5、时，就设法在问题上增 加一个约束条件，把包含这个非整数解的一部分可行 域从原来的可行域中割除，但不割掉任何一个整数可 行解。这个新增加的约束条件就称为割平面。在纯整数线性规划中，若松弛问题的最优解X*不 满足整数条件，则从X*的非整分量中选取一个，用以 构造一个线性约束条件，将其加入原松弛问题，形成 一个新的线性规划，重复直至获得整数最优解。为了最终获得整数最优解，构造的线性约束条件必须 ：1.不满足整数条件的最优解X*不满足新线性约束 条件。2.凡整数可行解满足新线性约束条件。例题：Max z = x1 + x2- x1 + x2 13x1 + x2 4x1，x2 0且取整用割平面法解例题1

6、.求解相应的线性规划L0 Max z = x1 + x2- x1 + x2 13x1 + x2 4x1，x2 0非整数解为建立割平面，首先考虑非整数解中 余数最大的基变量，此例中x1、 x2的 余数均为3/4，不妨选取x2 ：x2 +3/4 x3 +1/4 x4 =7/4x2 +3/4 x3 +1/4 x4 =7/4 现将各系数分成整数和非负真分数两部分，从而可得：(1+0)x2+(0+3/4) x3+(0+1/4) x4 =(1+3/4) 将整数部分的变量移至等式右端有：3/4 x3 +1/4 x4 =3/4+（1- x2 ） 非负整数解(1- x2)为整数，左端非负故有：3/4 x3 +1

7、/4 x4 =3/4+非负整数 从而：3/4 x3 +1/4 x4 3/4 或 x2 1 以x2 1为割平面可使可行域减少一个包括A点在内的三 角形。x2 A 10 1 x101（整数）型规划 整数规划中会遇到变量取值非0即1的情况，称 这种01规划（01Programming），这是称 为01变量，也称逻辑变量。01规划适用于“ 是”或“非”的决策。 应用01变量的决策问题 1厂址选择问题 2关于产品成本问题 3非此即彼的决策条件 0-10-1规划应用规划应用华美公司有华美公司有5 5个项目被列入投资计划，各项目个项目被列入投资计划，各项目 的投资额和期望的投资收益见下表：的投资额和期望的投

8、资收益见下表：项项项项 目目投投资额资额资额资额 ( (万元万元) )投投资资资资收益收益( (万元万元) )1 12102101501502 23003002102103 310010060604 413013080805 5260260180180该公司只有该公司只有600600万元资金可用于投资，由于万元资金可用于投资，由于 技术原因，投资受到以下约束：技术原因，投资受到以下约束： 在项目在项目1 1、2 2和和3 3中必须只有一项被选中；中必须只有一项被选中； 项目项目3 3和和4 4最多能选中一项；最多能选中一项； 项目项目5 5被选中的前提是项目被选中的前提是项目1 1必须被选中。

9、必须被选中。如何在上述条件下，选择一个最好的投如何在上述条件下，选择一个最好的投 资方案，使收益最大。资方案，使收益最大。解：令解：令 1 1 选中该项目选中该项目0 0 未选中该项目未选中该项目x xi i= =Max Z=150 xMax Z=150 x1 1 + +210x210x2 2 + +60x60x3 3 +80x+80x4 4 + +180x180x5 5s.t.s.t.210 x210 x1 1 + +300x300x2 2 +100x+100x3 3 +130x+130x4 4 + +260x260x5 5 600 600x x1 1 + +x x2 2 + + x x3

10、3 =1=1x x3 3 + x+ x4 4 1 1x x5 5 x x1 1 x xi i=1=1或或0 0五、隐枚举法（01规划求解法）(一)、基本思想：对maxZ=CXAX=bX为0或1的2n个可能解，只检查其中一部分例：maxZ = 2x1+4x2 +x33x1 - 8x2+5x3 -1x1 , x2 , x3为 0 ,1 X1 =1X1 =0111 01 01 01X2 =0X3 =00X2 =0X2 =1X1 =1X3 =10001(二)、简单隐枚举法(max)原则：(1)、用试探法，求出一个可行解，以它的目标 值作为当前最好值Z0(2)、增加过滤条件Z Z0(3)、将xi 按ci

11、由小大排列例：maxZ = 3x1 -2x2+5x3 x1 +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 循循环环环环(X(X1 1,X,X2 2,X,X3 3) )s.t.s.t.0 0s.t.s.t.1 1s.t.s.t.2 2s.t.s.t.3 3s.t.s.t.4 4满满满满 足足Z Z值值值值1 1(0,0,0)(0,0,0)0 0nono2 2(0,0,1)(0,0,1)5 5-1-11 10

12、 01 1yesyes5 53 3(0,1,0)(0,1,0)-2-2nono4 4(0,1,1)(0,1,1)3 31 15 5nono5 5(1,0,0)(1,0,0)3 31 11 11 10 0yesyes3 36 6(1,0,1)(1,0,1)8 80 02 21 11 1yesyes8 87 7(1,1,0)(1,1,0)1 1nono8 8(1,1,1)(1,1,1)6 62 26 6nono最优最优解解（1 1，0 0，1 1） Z=8Z=8增加约束条件（增加约束条件（0 0）（）（Z Z 3) 3)后实际做了后实际做了 2424次运算，而原问题需要计算次运算，而原问题需要计算

13、2 23 3*5=40*5=40次次 运算（运算（3 3个变量，个变量，4 4个约束条件，一个目标个约束条件，一个目标 函数）。函数）。注意：注意： 改进过滤性条件，在计算过程中随改进过滤性条件，在计算过程中随 时调整右边常数。时调整右边常数。 价值系数按递增排列。价值系数按递增排列。以上两种方法可减少计算量。以上两种方法可减少计算量。将(x1 x2 x3 ) (x2 x1 x3 ) 循循 环环环环(X(X2 2,X,X1 1,X,X3 3) )s.t.s.t.0 0s.t.s.t.1 1s.t.s.t.2 2s.t.s.t.3 3s.t.s.t.4 4满满满满 足足Z Z值值值值1 1(0,

14、0,0)(0,0,0)0 0nono2 2(0,0,1)(0,0,1)5 5-1-11 10 01 1yeyes s5 5改进过滤性条件改进过滤性条件Z Z 5 5 (0)(0)循循 环环环环(X(X2 2,X,X1 1,X,X3 3) )s.t.s.t. 00s.t.s.t.1 1s.t.s.t.2 2s.t.s.t.3 3s.t.s.t.4 4满满满满 足足Z Z值值值值3 3(0,1,0)(0,1,0)3 3nono4 4(0,1,1)(0,1,1)8 80 02 21 11 1yeyes s8 8改进过滤性条件改进过滤性条件Z Z 8 (0) 8 (0)循循 环环环环(X(X2 2,X,X1 1,X,X3 3) )s.t.s.t. 00s.t.s.t.1 1s.t.s.t.2 2s.t.s.t.3 3s.t.s.t.4 4满满满满 足足Z Z值值值值5 5(1,0,0)(1,