设(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），有