=01=lm (2.1.6) 含01-ln (2.1.7 故有如下推导： a,4,“,a,不全为零→3取6≠021→取0≠021”→3取≠0216→灭0≠0 21》→瓦6≠0211→… 由于x={民}的分量个数有限，故存在k,使1k1=1或S=S,由此得闭回路： XXnmXnmXaX4X (2.1.8) 或 X州，XlX4n2,,X-4X (2.1.9) 由x={}的构造知，(2.1.8)和(2.1.9)都是(2.1.4)的一部分，因此(2.1.4)含闭回路，矛盾。 充分性。假设(2.1.4)含闭回路，不妨设为(2.1.8)，则(2.1.8)是(2.1.4)的一部分，因此 Pst Psat Ps43…,P-4P (2.1.10) 是(2.15)的一部分。由a,的结构知，P一P4+P4-…+P4一P4=0,即(2.1.10)线性相关，因 此(2.1.5)也线性相关，矛盾。 定理2.1.2r个变量 X,X2h’…,X (2.1.11) 构成某个基的基变量的充要条件是，变量组(2.1.11)不含闭回路。 证明：(2111)构成某个基的基变量的充要条件是P,P,…,P线性无关，根据定理2.11得结 论。 为揭示(2.1.2)的基本可行解的另一特征，再引进如下概念。 定义2.1.2若一个矩阵的所有元素都是整数，并且它的各阶子式只取0、1、-1这三个值，则称此 矩阵为全单模的。 定理2.1.3对于标准形式的线性规划问题(LP),若等式约束中A=b中的A是全单模的，b是整数 向量，则LP)的每一个基解都是整数解（即所有分量都取整数）。 证明：设是(LP)对应于基B的基解，基变量为xg,…,xg。,则由基解定义，B(xg,…,xg)'=b, 即 g=8引=lm BI' 其中B表示B的行列式，B表示B的第i列换成b后的行列式。由A是全单模和B可逆知B吲为1或-1， 由A和b的元素都是整数知B为整数，所以x8,i=1,…,m都是整数。再由x=0,j∈ID,知x°是整数 解。 我们可用归纳法证明，(212)的系数矩阵是全单模的，由此得到如下定理。 推论2.1.4若平衡运输问题(4.1.2)中的所有4和b,都是整数，则它的基本可行解是整数解。 证明：由于(4.12)的系数矩阵是全单模的，因此去掉一个多余约束后的系数矩阵还是全单模的，于 是由定理2.1.3得结论。4 1 0, 1, , n ij j x i m = ∑ = = " (2.1.6) 1 0, 1, , m ij i x j n = ∑ = = " (2.1.7) 故有如下推导： 1 2 ,,, α α α " s 不全为零 11 12 2 2 2 3 (2.1.6) (2.1.7) (2.1.6) 0000 st st s t s t → ∃ ≠ ⎯⎯⎯ xxx x →∃ ≠ ⎯⎯⎯→∃ ≠ ⎯⎯⎯→∃ ≠ ⎯(2.1.7) ⎯⎯→ 3 3 (2.1.6) 0 s t ∃ ≠ ⎯⎯⎯ x →" 由于 { }ij x = x 的分量个数有限，故存在 j<k，使 k j 1 t t + = 或 k j s s = ，由此得闭回路： 1 11 12 , , , ,, , j j j j j j j j kk k j s t st s t s t st st x x x x xx + ++ ++ " (2.1.8) 或 1 11 12 1 , , ,, , j j j j j j k k jk s t s t s t s t st x x x xx + ++ ++ − " (2.1.9) 由 { }ij x = x 的构造知，(2.1.8)和(2.1.9)都是(2.1.4)的一部分，因此(2.1.4)含闭回路，矛盾。 充分性。假设(2.1.4)含闭回路，不妨设为(2.1.8)，则(2.1.8)是(2.1.4)的一部分，因此 12 22 23 1 1 , , ,, , kk k s t s t s t s t st " − ppp p p (2.1.10) 是(2.1.5)的一部分。由 ij a 的结构知， 12 22 23 1 1 0 kk k st s t s t s t st − ppp p p − + −+ − = " ，即(2.1.10)线性相关，因 此(2.1.5)也线性相关，矛盾。 定理 2.1.2 r 个变量 11 2 2 , ,, r r ij i j ij x x x " (2.1.11) 构成某个基的基变量的充要条件是，变量组(2.1.11)不含闭回路。 证明：(2.1.11)构成某个基的基变量的充要条件是 11 2 2 , ,, s s pp p ij i j ij " 线性无关，根据定理 2.1.1 得结 论。 为揭示(2.1.2)的基本可行解的另一特征，再引进如下概念。 定义 2.1.2 若一个矩阵的所有元素都是整数，并且它的各阶子式只取 0、1、-1 这三个值，则称此 矩阵为全单模的。 定理 2.1.3 对于标准形式的线性规划问题(LP)，若等式约束中 Ax=b 中的 A 是全单模的，b 是整数 向量，则(LP)的每一个基解都是整数解(即所有分量都取整数)。 证明：设 x 0是(LP)对应于基 B 的基解，基变量为 1 , , B Bm x " x ，则由基解定义， 1 (,, ) m T Bx x B B " = b ， 即 0 | | , 1, , | | i i B B x i m B = = " 其中|B|表示 B 的行列式，|Bi|表示 B 的第 i 列换成 b 后的行列式。由 A 是全单模和 B 可逆知|B|为 1 或-1， 由 A 和 b 的元素都是整数知|Bi|为整数，所以 0 , 1, , Bi x i m = " 都是整数。再由 0 0, j D x = j I ∈ ，知 x 0 是整数 解。 我们可用归纳法证明，(2.1.2)的系数矩阵是全单模的，由此得到如下定理。 推论 2.1.4 若平衡运输问题(4.1.2)中的所有 i a 和 j b 都是整数，则它的基本可行解是整数解。 证明：由于(4.1.2)的系数矩阵是全单模的，因此去掉一个多余约束后的系数矩阵还是全单模的，于 是由定理 2.1.3 得结论