SI. y=a=l…m ,≤j=l…n xy≥0，i=1,…,m,j=1,…,n 我们首先考虑平衡运输问题的求解方法。由于这时(2.1.2)一定存在最优解，故其最优解可在基本可 行解中找到，因此先讨论(2.1.2)的基本可行解的特征。 2.1.2基本可行解的特征 记=m+n-1。根据A的结构，容易得知(4)=r,并且(2.1.2)的任一等式方程都是其余r个方程的线性 组合。因此，(2.1.2)的基变量个数为r。那么，怎样的r个变量可作为基变量呢？为此先引进如下概念。 定义2.11凡能排成如下形式的变量组： X术形术站X…,X4,X4 (2.1.3) 称为(2.1.2)或表2.1.1的闭回路，其中S,S2,…,S4∈{1，…，m}且互不相同，4,2，…，4∈{1，…，n}且互不 相同。(2.1.3)中的变量称为闭回路的顶点。 在运输表2.1.1上，用直线段把闭回路的相邻顶点连接，最后一个顶点与第一个连接，则得到一个 直观的封闭回路，其中每条线段或水平或垂直，闭回路的每个顶点是回路的转角点，表中每行每列若有 闭回路的顶点则必恰有两个。 例如，m=3,n=4,则变量组2,3,3，x24,X4,x2是闭回路，在运输表上为： B B2 B3 B4 ai A C11 C12 C13 C14 ay C21 C22 C23 C24 az A C31 C32 C33 C34 a3 b b2 b3 b4 定理2.1.1 变量组 Xh…X (2.1.4) 不含闭回路的充要条件是，(2.1.4)所对应的系数列向量 PiP2…P (2.1.5) 线性无关。 证明：必要性。假设(2.1.5)饯性相关，则存在不全为零的数4,42，…，&，使 %Pu+Ph+…+ap=0 令下={区}：不= a,i=j=ji,则=0，即 0,otherwise3 1 1 1 1 min . . , 1, , , 1, , 0, 1, , , 1, , m n ij ij i j n ij i j m ij j i ij z cx st x a i m x bj n x i mj n = = = = = = = ≤ = ≥= = ∑∑ ∑ ∑ " " " " 我们首先考虑平衡运输问题的求解方法。由于这时(2.1.2)一定存在最优解，故其最优解可在基本可 行解中找到，因此先讨论(2.1.2)的基本可行解的特征。 2．1．2 基本可行解的特征 记 r=m+n-1。根据 A 的结构，容易得知 r(A)=r，并且(2.1.2)的任一等式方程都是其余 r 个方程的线性 组合。因此，(2.1.2)的基变量个数为 r。那么，怎样的 r 个变量可作为基变量呢？为此先引进如下概念。 定义 2.1.1 凡能排成如下形式的变量组： 11 12 2 2 2 3 1 , , , ,, , kk k s t st s t s t s t s t x xxx xx " (2.1.3) 称为(2.1.2)或表 2.1.1 的闭回路，其中 1 2 , , , {1, , } k ss s m " " ∈ 且互不相同， 1 2 , , , {1, , } k tt t n " " ∈ 且互不 相同。(2.1.3)中的变量称为闭回路的顶点。 在运输表 2.1.1 上，用直线段把闭回路的相邻顶点连接，最后一个顶点与第一个连接，则得到一个 直观的封闭回路，其中每条线段或水平或垂直，闭回路的每个顶点是回路的转角点，表中每行每列若有 闭回路的顶点则必恰有两个。 例如，m=3，n=4，则变量组 12 13 23 24 34 32 x ,,,,, xxxxx 是闭回路，在运输表上为： B1 B2 B3 B4 ai A1 c11 c12 c13 c14 a1 A2 c21 c22 c23 c24 a2 A3 c31 c32 c33 c34 a3 bj b1 b2 b3 b4 定理 2.1.1 变量组 11 2 2 , ,, s s ij i j ij x x x " (2.1.4) 不含闭回路的充要条件是，(2.1.4)所对应的系数列向量 11 2 2 , ,, s s pp p ij i j ij " (2.1.5) 线性无关。 证明：必要性。假设(2.1.5)线性相关，则存在不全为零的数 1 2 ,,, α α α " s ，使 11 2 2 1 2 0 s s α pp p ij i j s ij +α α ++ = " 令 { }ij x = x : , , 0, kk k ij iij j x otherwise ⎧α = = = ⎨ ⎩ ，则 Ax = 0 ，即