运筹学讲义 又b是整数向量,∴x=Bb≈B b=±Bb为整数向量 B 故x为(LP)的整数解■ Cor对整数规划 (IP): s.L. Ax=b x≥0整数=12…,n 其松弛线性规划问题为 max (LP):{st.Ax=b,其中A是全单模阵,b是整数向量 x≥0 若利用单纯形法求解(LP)得最优解x,则x必定也是(P)的最优解. 证明:由Th知,x为整数解.由命题(3)知,x是(P)的最优解■ 例2求证:运输问题 min ∑∑cn (TP).sL. r=a, i=1,2,,m xi=bj,j= xn≥0,i=1,2 必有整数解,其中a,b∈Z 证明:(TP)的约束条件方程组的系数矩阵为运 筹 学 讲 义 4 又 b 是整数向量，  b B b B B xB B b   − = = =  | | 1 为整数向量. 故 x 为 (LP) 的整数解.▌ Cor 对整数规划       = = = x j n st Ax b z c x IP j T 0, , 1,2, , . . max ( ) : 整数  ， 其松弛线性规划问题为       = = 0 . . max ( ) : x st Ax b z c x LP T ，其中 A 是全单模阵， b 是整数向量. 若利用单纯形法求解 (LP) 得最优解  x ，则  x 必定也是 (IP) 的最优解. 证明：由 Th1 知，  x 为整数解. 由命题（3）知，  x 是 (IP) 的最优解.▌ 例 2 求证：运输问题             = = = = = = =    = = = = x i m j n x b j n st x a i m z c x TP ij m i ij j i n j ij m i n j ij ij 0, 1,2, , ; 1,2, , , 1,2, , . . , 1,2, , min ( ) : 1 1 1 1     必有整数解，其中 + ai ,bj Z . 证明： (TP) 的约束条件方程组的系数矩阵为