第七章整数线性规划 在某些线性规划问题中,变量只有取整数值才有意义。这时约束条件中还需添上变量取 整数值的限制,因而称为整数线性规划问题,其一般形式是: min Z=CX AX= 6 X≥0且为整数 这称为纯整数规划。若其中只有部分变量要求取整数,则称之为混合整数规划 整数规划有着广泛的实际背景和明显的经济意义,在许多领域中有着重要应用,但是求 解(1)比求解相应的无整限制的线性规划问题(LP)要困难得多,被认为是NP困难问题。 我们在§1、§2中介绍以往常采用的分枝定界法、割平面法,在§3提出一种新程序。 §1分枝定界法 此法之原理及步骤前面己有介绍,可适用于纯整数规划及混合整数规划,它是以相应的 LP问题为松弛问题,把它的可行解域D分解成若干个子域,对每个子域求解LP问题,具体 作法我们通过例子说明。 例1 +3 X2≥3.13 D:22x1+34x2≥285 x,x2为非负整数 先不考虑x1,x2为整数的条件,求得最优解为 x1=8.12,x2=3.13,最优值minz=z0=17.51。 这不是整数,由于对变量的整数限制,则最优解必在如下两个子域D1或D2中: XI ≥9 x1≤8 D1:x2≥3.13 D2:x2≥3.13 22x+34x2≥285 22x+34x2≥285 分别在D1及D2上求问题的最优解,得 (D1):x1=9,x2=3.13,minz=z1=18.39 (D2):x1=8,x2=3.21,minz=z2=17.62 由于所得的解都不是整数解,于是进一步将D1分成D1和Dh2两个子域,D2分成D2和D2两个 子域,并分别求解。由于z2<z1,故求解宜先在D2的子域上进行。这样做的好处是,若在D2 的某个子域上已求得整数解,并且相应的最优值不大于z1,则对D1的分枝求解自然不必再进 行了。所谓“定界”的意义就在于此 整个求解过程可列表简示如下,其中分枝方框中只表示在前一约束基础上新加的约 束。方框上面括号内的数字表示求解的先后顺序
134 第七章 整数线性规划 在某些线性规划问题中，变量只有取整数值才有意义。这时约束条件中还需添上变量取 整数值的限制，因而称为整数线性规划问题，其一般形式是： 0 min Z CX AX b X = = 且为整数 （1） 这称为纯整数规划。若其中只有部分变量要求取整数，则称之为混合整数规划。 整数规划有着广泛的实际背景和明显的经济意义，在许多领域中有着重要应用，但是求 解（1）比求解相应的无整限制的线性规划问题（LP）要困难得多，被认为是 NP_困难问题。 我们在§1、§2 中介绍以往常采用的分枝定界法、割平面法，在§3 提出一种新程序。 §1 分枝定界法 此法之原理及步骤前面已有介绍，可适用于纯整数规划及混合整数规划，它是以相应的 LP 问题为松弛问题，把它的可行解域 D 分解成若干个子域，对每个子域求解 LP 问题，具体 作法我们通过例子说明。 例 1 min z=x1+3x2 x2≥3.13 D: 22x1+34x2≥285 x1,x2为非负整数 先不考虑 x1,x2 为整数的条件，求得最优解为： x1＝8.12,x2=3.13，最优值 minz=z0=17.51。 这不是整数，由于对变量的整数限制，则最优解必在如下两个子域 D1 或 D2 中： x1≥9 x1 8 D1: x2≥3.13 D2: x2≥3.13 22x1+34x2≥285 22x1+34x2≥285 分别在 D1 及 D2 上求问题的最优解，得 （D1）：x1＝9，x2＝3.13，min z＝z1＝18.39 （D2）：x1＝8，x2＝3.21，min z＝z2＝17.62 由于所得的解都不是整数解，于是进一步将 D1 分成 D11 和 D12 两个子域，D2 分成 D21 和 D22 两个 子域，并分别求解。由于 z2<z1，故求解宜先在 D2 的子域上进行。这样做的好处是，若在 D2 的某个子域上已求得整数解，并且相应的最优值不大于 z1,则对 D1 的分枝求解自然不必再进 行了。所谓“定界”的意义就在于此。 整个求解过程可列表简示如下，其中分枝方框中只表示在前一约束基础上新加的约 束。方框上面括号内的数字表示求解的先后顺序：
Min Z=x,+3x2 x2≥3.13 x1,x2为非负整数 z0=17.51 解:x1=9 解: D =3.21 z1=1839 z2=1762 四￥解: D1:x2≥4|x2=4 D2:x2≤3 无 D21:x2≥ z21=18.77 D2x3解 解: D21:x≥7 D2:x≤6 4.5 z21=19 Z,2=195 如果在分枝求解的过程中,求得的整数解之目标函数值成为所有分枝稍头上诸解的最小 值,过程即可停止,此即最优解。否则,对于比整数解之目标函数小的,还需继续分枝搜索。 可见,最先得到的整数解未必是最优的。如此例中,第六步已得整数解,但它不是最优的, 而于第八步得到的才是最优解,即 X1=7x2=4minz=z21=19 需要指出的是,分枝定界法每步迭代,由于是增加一个上限或者下限约束,故一般都要 用对偶单纯形法或第五章的方法求解LP问题,且不能保证用最少的迭代次数达到最优解 在不顺利的情况下,甚至需要对全部区域进行搜索。但根据经验,它还是比较有效的,目前 应用也最广泛。 §2割平面法 解整数LP问题(1)的割平面法是R·E· Gomory于1959年首先提出来的。从此以后整 数规划逐渐形成一个独立的运筹学分支,割平面法被认为是整数规划的核心部分,其基本思 想是仍以LP问题为松弛问题。若求得的最优解不是整数,就设法把这个最优的极点连同它 的一个域,从可行解集中“切除”,但保留其中的全部整数点,从而不影响(1)的求解 如此进行,直到找到整数解为止,而“切除”将通过一个附加的约束条件(称为割平面)来 实现,故称为割平面法。具体说明如下: 设与(1)相应的LP问题 min CX AX= b (2) X≥0 之最优单纯形表为 135
135 1 2 2 1 2 1 2 3 3.13 22 34 285 , Min Z x x x x x x x = + + 为非负整数 1 2 0 8.12 3.13 17.51 x x Z = = = 解： 1 1 D x: 9 2 1 D x: 8 1 2 2 8 3.21 17.62 x x Z = = = 1 解： 2 1 9 3.13 18.39 x x Z = = = 解： 11 2 D x: 4 1 2 11 9 4 21 x x Z = = = 解： 21 2 D x: 4 1 2 21 6.77 4 18.77 x x Z = = = 解： 22 2 D x: 3 无 解 212 1 D x: 6 1 2 212 6 4.5 19.5 x x Z = = = 解： 211 1 D x: 7 1 2 211 7 4 19 x x Z = = = 解： 12 2 D x: 3 无 解 （ 一 ） （ 八 ） （ 九 ） （ 六 ） （ 七 ） （ 四 ） （ 五 ） （ 二 ） （ 三 ） 如果在分枝求解的过程中，求得的整数解之目标函数值成为所有分枝稍头上诸解的最小 值，过程即可停止，此即最优解。否则，对于比整数解之目标函数小的，还需继续分枝搜索。 可见，最先得到的整数解未必是最优的。如此例中，第六步已得整数解，但它不是最优的， 而于第八步得到的才是最优解，即 x1=7 x2=4 min z=z211=19 需要指出的是，分枝定界法每步迭代，由于是增加一个上限或者下限约束,故一般都要 用对偶单纯形法或第五章的方法求解 LP 问题，且不能保证用最少的迭代次数达到最优解， 在不顺利的情况下，甚至需要对全部区域进行搜索。但根据经验，它还是比较有效的，目前 应用也最广泛。 §2 割平面法 解整数 LP 问题（1）的割平面法是 R·E·Gomory 于 1959 年首先提出来的。从此以后整 数规划逐渐形成一个独立的运筹学分支，割平面法被认为是整数规划的核心部分，其基本思 想是仍以 LP 问题为松弛问题。若求得的最优解不是整数，就设法把这个最优的极点连同它 的一个邻域，从可行解集中“切除”，但保留其中的全部整数点，从而不影响（1）的求解。 如此进行，直到找到整数解为止，而“切除”将通过一个附加的约束条件（称为割平面）来 实现，故称为割平面法。具体说明如下： 设与（1）相应的 LP 问题： 0 min CX AX b X = （2） 之最优单纯形表为 1 2 m x x x m n 1 x x +
B B1 00 I B 00 0凡 元n (3) 若存在a.≠整数,考虑(3)中相应的方程 B,r,=ar j=m+1 它可写成 +∑[+∑bx=a j=m+1 这里符号[表示不超过t的最大整数。h=B-[B],g,=a-[a,],则0≤b<1, 0<g,<1,由(4)有 x+∑[x≤[aJ]+g 若问题(1)有整数解(x,x均为整数),则由上式又可得 x+∑[B1lx≤a =m+ x+∑[x+=,4120为整数,由上式减去(4)得 (5) (5)是在(1)有整数解的假定下导出来的新的约束条件,称为割平面方程。用来导出(5) 的方程(4)称为诱导方程,(5)的作用由下面的定理可以看出。 定理1、问题(1)的可行解与方程组 x+∑x=a,=1,2,…m l-∑bx 的非负整数解一一对应
136 1 m x x 1 0 0 0 0 1 1 1 1 1 m n m m mn + + 1 m 0 0 0 m n +1 0 f （3） 若存在 r 整数，考虑（3）中相应的方程 1 n r rj j r j m x x = + + = （4） 它可写成 1 1 [ ] [ ] n n r rj j rj j r r j m j m x x h x g = + = + + + = + (4) 这里符号 []t 表示不超过 t 的最大整数。 [ ] hrj rj rj = − ， [ ] gr r r = − ，则 0 1 hrj ， 0 1 gr ，由 (4) 有 1 [ ] [ ] n r rj j r r j m x x g = + + + 若问题（1）有整数解（ , r j x x 均为整数），则由上式又可得 1 [ ] [ ] n r rj j r j m x x = + + 或 1 [ ] [ ], 0 n r rj j r r r j m x x u u = + + + = 为整数，由上式减去 (4) 得 1 n r rj j r j m u h x g = + − = − （5） （5）是在（1）有整数解的假定下导出来的新的约束条件，称为割平面方程。用来导出（5） 的方程（4）称为诱导方程，（5）的作用由下面的定理可以看出。 定理 1、问题（1）的可行解与方程组 1 1 , 1,2, , n i ij j i j m n r rj j r j m x x i m u h x g = + = + + = = − = − （6） 的非负整数解一一对应
证:(6)的非负整数解,显然是(1)的可行解。 设x0是(1)的可行解,代入(5)得 l=g+∑bx=a]-a+∑(B-[Bx=a}-∑IBlx-x 可见u为整数,又因b非负,x≥0,故 于是u.≥0,即(1)的可行解与(6)的非负整数解一一对应 根据定理1可得结论:整数线性规划(1)与规划 min Cx AX=6 4-∑b1x=8 x(=1…,n),l1为非负整数 是等价的 minz=-2x1-3x2+x3+2x5+x6 x1+2x2+x3-x4+3x5-5x6+x7=32 例2 x1-3x2+x4-x5+4x6+x8=18 x1+2x2+2x3+x1+x+2x+x=40 x(=1…9)为非负整数 不计整数限制的最优解如下表: x 2 3 4 x x12B为V0为0别m xg 2%为20%1% x00-1-0%号 3--3810-0- 它右端不全是整数。取第二行为诱导方程,得割平面方程为 x3 填入上表,用对偶单纯形法迭代求解。再加割平面,求解得
137 证：（6）的非负整数解，显然是（1）的可行解。 设 0 x 是（1）的可行解，代入（5）得 0 0 1 1 [ ] ( [ ]) n n r r rj j r r rj rj j j m j m u g h x x = + = + = − + = − + − 0 1 [ ] [ ] n r rj j r j m x x = + = − − 可见 r u 为整数，又因 ij h 非负， 0 xj 0 ，故 u g r r − −1 于是 ur 0 ，即（1）的可行解与（6）的非负整数解一一对应。 根据定理 1 可得结论：整数线性规划（1）与规划 1 ( 1, , ), n r rj j r j m j r min CX AX b u h x g x j n u = + = − = − = 为非负整数 是等价的。 例 2． 1 2 3 5 6 1 2 3 4 5 6 7 1 2 4 5 6 8 1 2 3 4 5 6 9 2 3 2 2 3 5 32 2 3 4 18 2 2 2 40 ( 1, ,9) i min Z x x x x x x x x x x x x x x x x x x x x x x x x x x i = − − + + + + + − + − + = − − + − + + = + + + + + + = = 为非负整数 不计整数限制的最优解如下表： 1 2 3 4 5 6 7 8 9 x x x x x x x x x 1 8 6 x x x 12 11 2 3 5 1 2 0 0 7 7 7 7 7 20 5 23 8 6 0 1 0 1 7 7 7 7 7 1 2 2 1 1 0 0 1 0 7 7 7 7 7 − − 5 37 7 6 88 7 8 7 30 38 5 9 4 0 1 0 0 7 7 7 7 7 − − − − − − 2 74 7 − 它右端不全是整数。取第二行为诱导方程，得割平面方程为 2 3 4 5 7 9 6 5 2 1 6 6 ( ) 7 7 7 7 7 7 u x x x x x − + + + + = − 填入上表，用对偶单纯形法迭代求解。再加割平面，求解得 x x x x x x x x x 1 2 3 4 5 6 7 8 9 u u 2 3
12 07030芳 x 12030110 x6 0000 000 1s o 000 1s 35 0000 0 %-7 4-56-5 l3 为030为 4% 0-1-1%0-2%0-%0-%-0n3 XI 1210%4000013 0120 01101 10 000 000 001 000 -%4 0-1 32 -54 0-1-30 0000%-%-73 于是已得(7)的最优解: x=37,x2=x3=…=x5=x7=0,x6=x,=1,x8 最优值miz=-73 通常取g,=mx1≤m,以x,-∑hx=-g,作为割平面方程,亦可采取 J=H+ 使目标函数上升最大的原则选择g 每增加一割平面方程,就增加一松弛变量u,在用对偶单纯形法求解时,u1将离基,但 以后它还可能成为基变量。 §3一种新程序 分枝定界法和割平面法只能用来求解中、小规模的问题,对于大型问题,前者常因分枝 太多而疲于搜索,后者也往往由于割平面选择不当而收敛很慢,甚至找一个较好的可行解都 不容易。因此迫切需要研究出可以求解大型问题的有效算法。 为了克服割平面法收敛慢的弱点,我们设计了一种新程序,这种程序也有明显的几何意 义,它迭代步骤简单,计算最小,并可利用多台机器并行计算,从而很快求得最优解。因此 颇适宜解大型问题,特别是在相应LP问题的基础上,它可以不必增加多少计算量就能很容 易地求出一个相当好的近似解
138 1 8 6 4 3 x x x x u 1 2 0 0 0 0 6 7 3 3 1 5 5 5 5 5 0 1 2 0 3 0 1 1 0 1 0 0 0 0 1 0 0 1 2 1 1 2 5 5 5 5 5 0 0 1 0 0 0 6 6 7 2 1 5 5 5 5 5 0 0 0 0 0 1 4 4 4 2 3 5 5 5 5 5 −−−− − − 1 37 5 88 4 5 6 5 4 5 0 1 0 0 0 0 18 26 3 3 4 5 5 5 5 5 − − − − − − 3 735 − 9 4 6 8 1 x x x x x 4 5 2 0 1 0 1 1 4 0 0 1 0 3 2 0 1 0 0 2 3 2 0 0 0 1 1 4 1 2 1 0 0 0 1 4 0 0 0 0 1 0 1 2 0 3 0 1 1 0 1 0 4 1 2 0 0 0 0 1 4 1 2 1 0 5 − − − − − − 37 88 1 0 1 0 1 3 0 0 0 0 0 19 3 1 4 2 4 − − − − − −73 于是已得（7）的最优解： x x x x x x x x 1 2 3 5 7 6 9 8 = = = = = = = = = 37, 0, 1, 88 最优值 min Z = −73 通常取 { |1 } g max g i m r i = ，以 r n j m ur − hij x j = −g = +1 作为割平面方程，，亦可采取 使目标函数上升最大的原则选择 r g 。 每增加一割平面方程，就增加一松弛变量 i u ,在用对偶单纯形法求解时， i u 将离基，但 以后它还可能成为基变量。 §3 一种新程序 分枝定界法和割平面法只能用来求解中、小规模的问题，对于大型问题，前者常因分枝 太多而疲于搜索，后者也往往由于割平面选择不当而收敛很慢，甚至找一个较好的可行解都 不容易。因此迫切需要研究出可以求解大型问题的有效算法。 为了克服割平面法收敛慢的弱点，我们设计了一种新程序，这种程序也有明显的几何意 义，它迭代步骤简单，计算最小，并可利用多台机器并行计算，从而很快求得最优解。因此 颇适宜解大型问题，特别是在相应 LP 问题的基础上，它可以不必增加多少计算量就能很容 易地求出一个相当好的近似解