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 表1140 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