第七章整数线性规划 在某些线性规划问题中,变量只有取整数值才有意义。这时约束条件中还需添上变量取 整数值的限制,因而称为整数线性规划问题,其一般形式是: 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 问题的基础上，它可以不必增加多少计算量就能很容 易地求出一个相当好的近似解
设(1)系数矩阵A的秩为m,目标函数系数C(=1,…n)为整数。再设相应的松弛 问题(2)的最优表(3)化为最优典式表示如下 ∫=/0-∑4x ∑月 xi,I 0,j=1, 则知检验数λ≤0,j=1,…n,令松弛问题(2)的最优值 这里[]表示最优值的整数部分,0≤a<1,则问题(1)的最优值z2[门,引进 辅助变量y,考虑如下辅助问题 In +∑月x=a,l=1 x-y=- K J=+ x1≥0,y1≥0,j=1 其中K(以后也总)假定为非负整数。注意,由于(3)是最优表,故有 1≤0,j=m+1…,n。辅助问题(9)与(1)有如下关系 定理2、如果问题(1)存在可行解,则X为(1)的可行解之充要条件是存在一个非 负整数K,使(X,0)为(9)的整数解,并且与x相应的(1)之目标函数值z=[门]+K。 证:必要性。设X为(1)的可行解,则Z=CX2[]。因假定C(=1…m)是 整数,从而CX是整数。故存在一个非负整数K,使Z=CX=[°]+K。又由松弛问题 (2)之最优典式(3)知CX=-∑礼,所以 nix 于是由式(8),有
139 设（1）系数矩阵 A 的秩为 m，目标函数系数 ( 1, , ) C j n j = 为整数。再设相应的松弛 问题（2）的最优表（3）化为最优典式表示如下 0 1 1 , 1, , 0, 1, , n j j j m n i i ij j j m j min f f x x x i m x j n = + = + = − = − = = (3) 则知检验数 0, 1, , j =j n ，令松弛问题（2）的最优值 0 0 f f = − （8） 这里 0 f 表示最优值 0 f 的整数部分， 0 1 ，则问题（1）的最优值 * 0 Z f ，引进 辅助变量 1 y ，考虑如下辅助问题： 1 1 1 1 1 , 1, 2, , 0, 0, 1, , n i ij j i j m n j j j m j min y x x i m x y K x y j n = + = + + = = − = − − = （9） 其中 K （以 后也总 ）假 定为非 负整 数。 注意， 由于 （3） 是最 优表 ，故有 0, 1, , j = + j m n。辅助问题（9）与（1）有如下关系。 定理 2、如果问题（1）存在可行解，则 X 为（1）的可行解之充要条件是存在一个非 负整数 K，使 ( ,0)T X 为（9）的整数解，并且与 X 相应的（1）之目标函数值 0 Z f K = + 。 证：必要性。设 X 为（1）的可行解，则 0 Z CX f = 。因假定 ( 1, , ) C j n j = 是 整数，从而 CX 是整数。故存在一个非负整数 K，使 0 Z CX f K = = + 。又由松弛问题 （2）之最优典式 (3) 知 0 1 n j j j m CX f x = + = − ，所以 0 0 1 n j j j m f x f K = + − = + 于是由式（8），有
a, =f-lf-k =m+1 这说明(X,0)是(9)的整数解 充分性。如果存在一个非负整数K,使(x,0)是辅助问题(9)的整数解,注意到式 (9)与(3)的关系,则显然AX=b,可见ⅹ是问题(1)的可行解,由辅助问题(9)的 最后一个约束及y=0知 ∑x=-a-K (10) j=m+1 再由式(3)及(8),便有 z=CX=/-∑4x=°+(a+)=[门+k (11) 推论、设K'=mmn{k|K为非负整数且使(9)有整数解(x,0)},当K=K 式(9)的整数解为(X,0),则x'是问题(1)的最优解 根据定理2及其推论知,为求解问题(1),可先就K=0时考察辅助问题(9)的最优 解(后面将说明式(9)之最优解极易求得)。若有整数解且y等于0,则它即为式(1)的 最优解,否则,说明原间题(1)没有目标函数值Z=[]+K=[/的可行解:再依次 令K=1,2,…,重复以上考察。下面的定理表明,上述过程不会无限的进行下去。 定理3、若对某个K,辅助问题(9)的最优值miny>0,则问题(1)不存在使自 己目标函数值Z2[]+K的可行解 证:易见与问题(9)相应的初始单纯形表如下表所示: x 0 B m+1 B0|a1 Am 1 B a 00 0 -+1|+a+K K 表1
140 0 0 1 n j j j m x f f K K = + = − − = − − 这说明 ( ,0)T X 是（9）的整数解。 充分性。如果存在一个非负整数 K，使 ( ,0)T X 是辅助问题（9）的整数解，注意到式 （9）与 (3) 的关系，则显然 AX b = ，可见 X 是问题（1）的可行解，由辅助问题（9）的 最后一个约束及 y1 = 0 知 1 n j j j m x K = + = − − （10） 再由式 (3) 及（8），便有 0 0 0 1 ( ) n j j j m Z CX f x f K f K = + = = − = + + = + （11） 推论、设 * { | ( ,0) }T K min K K x = 为非负整数且使（9）有整数解 ，当 * K K ＝ 时， 式（9）的整数解为 ( ,0)T X ，则 x 是问题（1）的最优解。 根据定理 2 及其推论知，为求解问题（1），可先就 K＝0 时考察辅助问题（9）的最优 解（后面将说明式（9）之最优解极易求得）。若有整数解且 1 y 等于 0，则它即为式（1）的 最优解，否则，说明原问题（1）没有目标函数值 0 0 Z f K f = + = 的可行解；再依次 令 K =1,2, ，重复以上考察。下面的定理表明，上述过程不会无限的进行下去。 定理 3、若对某个 K，辅助问题（9）的最优值 min 0 1 y ，则问题（1）不存在使自 己目标函数值 0 Z f K + 的可行解。 证：易见与问题（9）相应的初始单纯形表如下表所示： 1 2 1 1 m m n x x x x x y + 1 1 m x x y 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 0 1 m n m m m n m n + + − − + + 1 m K + + 0 0 0 0 − − m n +1 + + K 表 1
设对上表1实行单纯形迭代求得的最优解为(X,y),由定理假定y>0,说明y是 基变量,注意到初始表中y已是基变量,故寻优迭代中主元可不选在y这一行。今把表中 的K换成R,其余不变。若K≥K,则y行的常数项变大,故主元亦不能选在y这一行, 这样迭代过程便与原来的完全相同,于是有最优解(X,y+R一K),其最优值为 y1+K-K>0。 若问题(1)存在Z2[°]+k的可行解,设Z=[门]+R,则≥K,对该, 由定理2之必要性,辅助问题(9)应有整数解(x,0),其最优值为0这与以上的分析矛 盾,故式(1)不存在22」+K的可行解。 依据定理3,若随着辅助问题(9)中K值的增加,迭代至某步出现miny1>0,即可 停止,原问题(1)无解 由于表1最后两行除了这列以外是一样的,故主元一旦选在y行,迭代一次后可立 得最优解,可见式(9)中的最优解极易求出,然而考察其最优解中是否有整数解却并非易 事。实际上注意辅助问题(9)的最后一个约束,当y1=0实际就是 CX=[°]+K (12) 不难看出,它是将(2)的目标函数之最优割平面CX=f向其可行解域里面平行推进a+K 的结果(程序的几何意义也就在于此),因此只要K取得不是很大,从而保证(12)总是穿 过松弛问题(2)的可行域(此为定理3的几何解释),则一方面说明辅助问题(9)的最优 值miny=0,另一方面又说明式(9)的最优解有无穷多。这样,判断是否有整数解就不 容易了。不过易证下述论断成立。 定理4,假定松弛问题(2)是非退化的,又设在由辅助问题(9)出发寻找问题(1) 的目标函数Z=[f]+K的可行解之过程中,典式(3的基变量仍保持非0的性质,若集 合(a+K)4,|j=m+1,…,m}中无整数,则式(1)不存在含有(nm-1)个0分量的可 行解。 证:与典式(3)比较,式(9)中增加了一个约束,故式(9)的基变量比式(3)的多 个,由于假定式(3)的基变量仍保持非0的性质,故迭代至最后,它们仍是基变量,这说 明式(9)所增加的基变量必须在表1的(m+1)行取得。由于基变量全相同的基可行解必相 等,故一开始就以(m1)行的那个主元实行一次 Gauss消元,所得即为最优解。这样,如 果集合{(+K)/4,j=m+1…,n中无整数,则最优解中自然不会有整数解。故定理结 论成立 诚然,定理4中的假定事先无法验证,但考虑到问题(1)与其松弛问题(2)的最优 解之间虽然可能相差很大,但后者的基变量变为0的情形在实际中比较少见,于是假定也就 常被满足了
141 设对上表 1 实行单纯形迭代求得的最优解为 1 ( , )T X y ，由定理假定 y1 0 ，说明 1 y 是 基变量，注意到初始表中 1 y 已是基变量，故寻优迭代中主元可不选在 1 y 这一行。今把表中 的 K 换成 K ，其余不变。若 K K ，则 1 y 行的常数项变大，故主元亦不能选在 1 y 这一行， 这样迭代过程便与原来的完全相同，于是有最优解 1 ( , )T X y K K + − ，其最优值为 y K K 1 + − 0。 若问题（1）存在 0 Z f K + 的可行解 X ，设 0 Z f K = + ，则 K K ，对该 K ， 由定理 2 之必要性，辅助问题（9）应有整数解 ( ,0) T X ，其最优值为 0。这与以上的分析矛 盾，故式（1）不存在 0 Z f K + 的可行解。 依据定理 3，若随着辅助问题（9）中 K 值的增加，迭代至某步出现 min 0 1 y ，即可 停止，原问题（1）无解。 由于表 1 最后两行除了 1 y 这列以外是一样的，故主元一旦选在 1 y 行，迭代一次后可立 得最优解，可见式（9）中的最优解极易求出，然而考察其最优解中是否有整数解却并非易 事。实际上注意辅助问题（9）的最后一个约束，当 y1 = 0 实际就是 0 CX f K = + [ ] （12） 不难看出，它是将（2）的目标函数之最优割平面 0 CX f = 向其可行解域里面平行推进 + K 的结果（程序的几何意义也就在于此），因此只要 K 取得不是很大，从而保证（12）总是穿 过松弛问题（2）的可行域（此为定理 3 的几何解释），则一方面说明辅助问题（9）的最优 值 min y1 = 0 ，另一方面又说明式（9）的最优解有无穷多。这样，判断是否有整数解就不 容易了。不过易证下述论断成立。 定理 4，假定松弛问题（2）是非退化的，又设在由辅助问题（9）出发寻找问题（1） 的目标函数 0 Z f K = + [ ] 的可行解之过程中，典式 (3) 的基变量仍保持非 0 的性质，若集 合 {( ) | 1, , } + = + K j m n j 中无整数，则式（1）不存在含有（n-m-1）个 0 分量的可 行解。 证：与典式 (3) 比较，式（9）中增加了一个约束，故式（9）的基变量比式 (3) 的多 一个，由于假定式 (3) 的基变量仍保持非 0 的性质，故迭代至最后，它们仍是基变量，这说 明式（9）所增加的基变量必须在表 1 的（m+1）行取得。由于基变量全相同的基可行解必相 等，故一开始就以（m+1）行的那个主元实行一次 Gauss 消元，所得即为最优解。这样，如 果集合 {( ) | 1, , } + = + K j m n j 中无整数，则最优解中自然不会有整数解。故定理结 论成立。 诚然，定理 4 中的假定事先无法验证，但考虑到问题（1）与其松弛问题（2）的最优 解之间虽然可能相差很大，但后者的基变量变为 0 的情形在实际中比较少见，于是假定也就 常被满足了
基于以上理由,我们可以只考察辅助问题(9)的部分最优基可行解: a+k ,0.i=1.…,m 如其中有整数解,就得到问题(1)的一个Z=[∫°]+K的可行解:否则,增加K值,继续 考察(13),以期得到一个可行解。具体的做法是先计算(13)中的第一式,挑出其中取整 数的j,看它们是否满足第二式,并取整数,如发现某x不为整数,即将此j弃之,转而考 察别的。若能得到整数解,则已得式(1)的一个可行解,否则令K增加1,重复以上过程 例3用本方法求解上节例2 将例2的最优表稍加改变:f0→a+K,检验数变号,即得表1的简化形式 x x2 x3 x4 x5 x& xo x012 %%分 x0010 1 00为 为0%号 3% 为0% 由定理4知,最小正检验 幻>a=37,故知当K=0时,问题无可 行解。今取K0=1,最小比值均在最后一行,且知+人=1为整数,故宣以-为主元 实行 Gauss消元,得 x x 3 x0为 3 x。0-%- 71% 93% 8 故得可行解x=(37000010881),它即是最优解,而最优值 CX=D°]+K0=-73
142 基于以上理由，我们可以只考察辅助问题（9）的部分最优基可行解： , 0, { 1, , } 0, 1, , j j j i i ij j K x j m n K x i m + = + − + = + = （13） 如其中有整数解，就得到问题（1）的一个 0 Z f K = + [ ] 的可行解；否则，增加 K 值，继续 考察（13），以期得到一个可行解。具体的做法是先计算（13）中的第一式，挑出其中取整 数的 j ，看它们是否满足第二式，并取整数，如发现某 i x 不为整数，即将此 j 弃之，转而考 察别的。若能得到整数解，则已得式（1）的一个可行解，否则令 K 增加 1，重复以上过程。 例3 用本方法求解上节例 2 将例 2 的最优表稍加改变： 0 f K → + ,检验数变号，即得表 1 的简化形式： 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 0 1 0 0 30 38 5 9 4 7 7 7 7 7 2 7 + K 由定理 4 知，最小正检验数 0 4 4 2 7 7 − = − = = j ，故知当 K=0 时，问题无可 行解。今取 K0 =1 ，最小比值均在最后一行，且知 0 9 1 K + = − 为整数，故宜以−9 为主元， 实行 Gauss 消元，得 x x x x x x x x x 1 2 3 4 5 6 7 8 9 1 8 6 x x x 13 13 2 1 1 1 0 0 0 9 3 9 9 9 1 1 1 2 0 0 0 1 0 3 3 3 3 1 1 2 2 8 0 1 0 0 9 3 9 9 9 − − − − − − − − 37 88 1 9 x 0 0 0 1 7 10 38 5 4 9 3 9 9 9 1 故得可行解 (37 0 0 0 0 1 0 88 1)T x = ，它即是最优解，而最优值 0 0 CX f K = + = − [ ] 73
