证:(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