第二部分线性规划应用 第二章运输问题和指派问题（书第三章，§5.5) 运输问题和指派问题都是具有特殊结构的线性规划问题，除了可直接用单纯形法求解外，我们可以 根据其特征构造更简易有效的方法进行求解。本章将介绍求解运输问题的表上作业法和求解指派问题的 匈牙利算法。 §2.1运输问题的数学模型 2.1.1运输问题 设某种物质有m个产地A1,…,Am,产量分别为a1,…,am,有n个销地B1,…,Bn,销量分别为b1,…,bn。 己知A到B的运价为c,则应如何安排运输方案，使在满足各销点的销量的前提下，使总运费最小。 设由4，到，B,的运输量为x,则可建立如下运输模型： l 1 SIt. ,≤a,i=l,m =1 (2.1.1) ∑=j=ln xg≥0，i=1,…,m,j=1,…,n 其中a,20,i=1,…,m,b,之0，j=1,…,n, a-立和b-产多分别为21游总产量和8箱量.eL山的可 行解记作x={x}。我们将(2.11)中数据用如下运输表表示： B1 … B … Bn ai A C11 Clj CIn a A Cil Ci Cin ai Am Cml C网 Cmn am ∑a, b b bn ∑b, 表2.1.1运输问题(2.1.1)的运输表 如有如下运输表（右上方为运价）
1 第二部分 线性规划应用 第二章 运输问题和指派问题（书第三章，§5.5） 运输问题和指派问题都是具有特殊结构的线性规划问题，除了可直接用单纯形法求解外，我们可以 根据其特征构造更简易有效的方法进行求解。本章将介绍求解运输问题的表上作业法和求解指派问题的 匈牙利算法。 §2．1 运输问题的数学模型 2．1．1 运输问题 设某种物质有 m 个产地 A1,…,Am，产量分别为 a1,…,am，有 n 个销地 B1,…,Bn，销量分别为 b1,…,bn。 已知 Ai 到 Bj的运价为 cij，则应如何安排运输方案，使在满足各销点的销量的前提下，使总运费最小。 设由 Ai 到,Bj的运输量为 xij，则可建立如下运输模型： 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.1) 其中 0, 1, , , 0, 1, , i j a i mb j n ≥= ≥ = " " ， 1 m i i a a = = ∑ 和 1 n j j b b = = ∑ 分别为(2.1.1)的总产量和总销量。(2.1.1)的可 行解记作 { }ij x = x 。我们将(2.1.1)中数据用如下运输表表示： B1 … Bj … Bn ai A1 c11 c1j c1n a1 ┆ Ai ci1 cij cin ai ┆ Am cm1 cmj cmn am bj b1 bj bn i ∑a j ∑b 表 2.1.1 运输问题(2.1.1)的运输表 如有如下运输表(右上方为运价)
B1 B2 B3 B4 ai 3 11 3 10 A 9 8 A2 7 4 10 5 A3 9 b 6 5 6 20 表2.1.2运输表 当a=b,即产销平衡时，(2.1.1)等价于如下问题： m: S.t. .t=l.m (2.1.2) 2=61=ln xy≥0，i=1,…,m,j=1…,n 这时(2.1.1)即(2.1.2)称为平衡运输问题，其约束矩阵为 Xl…n21…X2m…Xml…Xmm 1.1 1…1 M= 11 即x,的系数矩阵为p,=0…1010,=立P,· 第i个第m+j个 由于x=化，=}是(212)的可行解，因此(2.12的存在可行解。同时，由于212)的可行域有界， 因此(2.1.2)存在最优解。 当a≠b时，称(2.1.1)为不平衡运输问题。其中，若a>b,即产大于销，同样可说明(2.1.1)一定存在 最优解；若a<b,即销大于产，显然(2.1.1)无可行解，这时考虑在保证物质全部运到各销地的前提下的 运费最小的运输问题： 2
2 B1 B2 B3 B4 ai A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 bj 3 6 5 6 20 表 2.1.2 运输表 当 a=b，即产销平衡时，(2.1.1)等价于如下问题： 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.1)即(2.1.2)称为平衡运输问题，其约束矩阵为 11 1 21 2 1 1 1 1 1 1 1 1 1 1 1 1 n n m mn x xx x x x A = " """ " " % " %% % 1 ⎛ ⎞ ⎜ ⎟ ⎝ ⎠ 即 ij x 的系数矩阵为 (0 1 0 1 0)T pij = "" "" ， 1 1 m n ij ij i j A x = = x p = ∑∑ 。 第 i 个 第 m+j 个 由于 { } i j ij a b x a x = = 是(2.1.2)的可行解，因此(2.1.2)的存在可行解。同时，由于(2.1.2)的可行域有界， 因此(2.1.2)存在最优解。 当 a b ≠ 时，称(2.1.1)为不平衡运输问题。其中，若 a>b，即产大于销，同样可说明(2.1.1)一定存在 最优解；若 a<b，即销大于产，显然(2.1.1)无可行解，这时考虑在保证物质全部运到各销地的前提下的 运费最小的运输问题：
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,otherwise
3 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 ，即
=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 得结论
§2.2表上作业法 2.2.1初始方案的求法 下面介绍平衡运输问题(2.12)的初始基本可行解即初始方案的两种确定方法。 1.最小元素法 最小元素法采用运价低的点优先考虑的思想确定方案。下面以具体例子说明最小元素法的步骤。 例2.2.1设有运输表如表2.1.2，用最小元素法确定其初始方案（写在中间）。 解：从表中运价最小c21对应的变量x2!开始考虑： 1=min{a2,b,}=min{4,3}=3=b 在格子(2,1)处填入3，并且x1=x1=0(不用填)，划去第1列，4=a2-3=1。 从表中余下部分运价最小c23对应的变量x23开始考虑： x23 min (a2,b)=min(1,5)=1=a 在格子(2,3)处填入1，并且x21=x24=0(不用填)，划去第2行，=b-1=4。 从表中余下部分运价最小C13对应的变量x13开始考虑： xi3 =min(a,b)min(7,4)=4=b 在格子(1,3)处填入4，并且x3=0(不用填)，划去第3列，4=4-4=3。 从表中余下部分运价最小c2对应的变量x32开始考虑： 2=min{a3,b2}=min9,6}=6=b2 在格子(3,2)处填入6，并且x2=0(不用填)，划去第2列，4=4-6=3。 从表中余下部分运价最小c4对应的变量x34开始考虑： x mina,b)=min(3,6)=3=a 在格子(3,4)处填入3，划去第3行，b=b,-3=3。 从表中余下部分运价最小c14对应的变量x14开始考虑： x=min(a,b)min(3,3)=3 在格子(1,4)处填入3，划去第1行和第4列。至此，得到了如下运输方案。 B2 B3 Ba ai 3 11 3 10 A 4 久 9 8 3 1 年 7 4 10 5 A3 6 3 9 b 6 B 20 表2.2.1由最小元素法确定的例2.2.1的初始方案 我们称填了数字的格子为数学格，未填数学的格子为空格。 例2.2.2用最小元素法确定如下运输问题的初始方案
5 §2．2 表上作业法 2．2．1 初始方案的求法 下面介绍平衡运输问题(2.1.2)的初始基本可行解即初始方案的两种确定方法。 1．最小元素法 最小元素法采用运价低的点优先考虑的思想确定方案。下面以具体例子说明最小元素法的步骤。 例 2.2.1 设有运输表如表 2.1.2，用最小元素法确定其初始方案(写在中间)。 解：从表中运价最小 c21对应的变量 x21 开始考虑： x21 2 1 1 = = == min{ , } min{4,3} 3 ab b 在格子(2,1)处填入 3，并且 11 31 x x = = 0 (不用填)，划去第 1 列， 2 2 a a ′ = − =3 1。 从表中余下部分运价最小 c23 对应的变量 x23 开始考虑： x23 2 3 2 = = == min{ , } min{1,5} 1 ab a ′ ′ 在格子(2,3)处填入 1，并且 21 24 x x = = 0 (不用填)，划去第 2 行， 3 3 b b ′ = − =1 4 。 从表中余下部分运价最小 c13 对应的变量 x13 开始考虑： x13 1 3 3 = = == min{ , } min{7,4} 4 ab b ′ ′ 在格子(1,3)处填入 4，并且 33 x = 0 (不用填)，划去第 3 列， 1 1 a a ′ = − = 4 3 。 从表中余下部分运价最小 c32 对应的变量 x32 开始考虑： x32 3 2 2 = = == min{ , } min{9,6} 6 ab b 在格子(3,2)处填入 6，并且 12 x = 0 (不用填)，划去第 2 列， 3 3 a a ′ = − = 6 3。 从表中余下部分运价最小 c34 对应的变量 x34 开始考虑： x34 3 4 3 = = == min{ , } min{3,6} 3 ab a ′ ′ 在格子(3,4)处填入 3，划去第 3 行， 4 4 b b ′ = −=3 3 。 从表中余下部分运价最小 c14 对应的变量 x14 开始考虑： x ab 14 1 4 = min{ , } min{3,3} 3 ′ ′ = = 在格子(1,4)处填入 3，划去第 1 行和第 4 列。至此，得到了如下运输方案。 B1 B2 B3 B4 ai A1 3 11 3 4 10 3 7 3 A2 1 3 9 2 1 8 4 1 A3 7 4 6 10 5 3 9 3 bj 3 6 5 4 6 3 20 表 2.2.1 由最小元素法确定的例 2.2.1 的初始方案 我们称填了数字的格子为数学格，未填数学的格子为空格。 例 2.2.2 用最小元素法确定如下运输问题的初始方案
B2 B3 B4 4 5 5 6 A 20 0 A2 8 6 5 30 3的 2 3 4 A3 10 10 20 0 403p b 10 10 20 0 020 90 表2.2.2由最小元素法确定的例2.2.2的初始方案 定理2.2.1利用最小元素法确定的x={x}为(2.1.2)的基本可行解，其中数字格对应的变量正好是 基变量。 证明：首先，由最小元素法具体步骤知x={x}为(21.2)的可行解，并且数学格的个数为r。由定理 2.1.2知，现在只需证明数学格对应的变量组不含闭回路。否则，不妨设含有闭回路 Xih 如果格子（么，）填数x时，划去的是行（若是列可类似讨论），则数字x一定比x先填，并且填后划 去了第方列，从而数字x6一定比xh先填，并且填后划去了第马行，从而又知X一定比x先填，并 且填后划去了第。由此知，格子(，)处根本不可能填数，矛盾。 2.伏格尔法 最小元素法的缺点是，为了节省一处的费用，可能会造成其他处多化更多的费用。伏格尔法考虑每 个产点到各销点的最小运价与次小运价之间的差额（行差额）、各产点到每个销点的最小运价与次小运价 之间的差额（列差额），对差额最大的产地或销点中运价最小的点采用优先考虑的思想确定方案。下面以 具体例子说明最小元素法的步骤。 例2.2.3设有运输表2.1.2，用伏格尔法确定其初始方案（写在中间）。 解：先求出各行各列的差额，分别写在最后一行和最后一列。从差额最大的第二列中运价最小C2对应 的变量x2开始考虑： x2=min{a3,b2}=min{9,6}=6=b 在格子(3,2)处填入6，并且x2=x2=0(不用填)，划去第2列，4=a-6=3。 对表中余下部分重新求出各行差额写在最后一列。从差额最大的第4列中运价最小℃4对应的变量 x4开始考虑： x=minfa,b)=min(3,6)=3=a 在格子(3,4)处填入3，并且x31=x3=0(不用填)，划去第3行，b=b-3=3。 对表中余下部分重新求出各列差额写在最后一行。从差额最大的第1列中运价最小c2!对应的变量 x21开始考虑：
6 B1 B2 B3 B4 ai A1 4 5 5 6 20 20 A2 8 67 5 30 30 A3 2 10 3 10 2 20 4 0 40 30 10 0 bj 10 10 20 50 50 20 90 表 2.2.2 由最小元素法确定的例 2.2.2 的初始方案 定理 2.2.1 利用最小元素法确定的 { }ij x = x 为(2.1.2)的基本可行解，其中数字格对应的变量正好是 基变量。 证明：首先，由最小元素法具体步骤知 { }ij x = x 为(2.1.2)的可行解，并且数学格的个数为 r。由定理 2.1.2 知，现在只需证明数学格对应的变量组不含闭回路。否则，不妨设含有闭回路 1 1 i j x 1 2 i j x 2 1 i j x 2 2 i j x 如果格子 1 1 (, ) i j 填数 1 1 i j x 时，划去的是行（若是列可类似讨论），则数字 1 2 i j x 一定比 1 1 i j x 先填，并且填后划 去了第 2j 列，从而数字 2 2 i j x 一定比 1 2 i j x 先填，并且填后划去了第 2 i 行，从而又知 2 1 i j x 一定比 2 2 i j x 先填，并 且填后划去了第 1 j 。由此知，格子 1 1 (, ) i j 处根本不可能填数，矛盾。 2．伏格尔法 最小元素法的缺点是，为了节省一处的费用，可能会造成其他处多化更多的费用。伏格尔法考虑每 个产点到各销点的最小运价与次小运价之间的差额(行差额)、各产点到每个销点的最小运价与次小运价 之间的差额(列差额)，对差额最大的产地或销点中运价最小的点采用优先考虑的思想确定方案。下面以 具体例子说明最小元素法的步骤。 例 2.2.3 设有运输表 2.1.2，用伏格尔法确定其初始方案(写在中间)。 解：先求出各行各列的差额，分别写在最后一行和最后一列。从差额最大的第二列中运价最小 c32 对应 的变量 x32 开始考虑： x32 3 2 2 = = == min{ , } min{9,6} 6 ab b 在格子(3,2)处填入 6，并且 12 22 x x = = 0 (不用填)，划去第 2 列， 3 3 a a ′ = − = 6 3。 对表中余下部分重新求出各行差额写在最后一列。从差额最大的第 4 列中运价最小 c34 对应的变量 x34 开始考虑： x34 3 4 3 = = == min{ , } min{3,6} 3 ab a ′ ′ 在格子(3,4)处填入 3，并且 31 33 x x = = 0 (不用填)，划去第 3 行， 4 3 b b ′ = − = 3 3。 对表中余下部分重新求出各列差额写在最后一行。从差额最大的第 1 列中运价最小 c21 对应的变量 x21 开始考虑：
x3:=min{a2,b}=min{4,3}=3=b 在格子(2,1)处填入3，并且x1=0(不用填)，划去第1列，d=a2-3=1。 对表中余下部分重新求出各行差额写在最后一列。从差额最大的第1行中运价最小℃13对应的变量 x13开始考虑： Xi3=min(a,b3)=min(7,5)=5=b 在格子(1,3)处填入5，并且x23=0(不用填)，划去第3列，a4=a,-5=2。 现在还剩下最后一列的第一、二个格子，从运价最小c24对应的变量x24开始考虑： x=min(az,b)min(1,3)=1=a 在格子(2,4)处填入1，划去第2行，b=b-1=2。 现在还剩下最后一列的第一个格子，考虑变量4： x=min (a,6)min(2,2)=2 在格子(1,4)处填入2，划去第1行和第4列。至此，得到了如下运输方案。 B B2 B3 B4 a 行差额 3 11 3 10 A 祁 才 9 A 3 1 牧 > 4 10 A3 6 3 非 h主 b 69平 20 列差额 表2.2.3由伏格尔法确定的例2.2.1的初始方案 2.2.2检验数的求法 对于己知的基本可行解，为判别其是否为最优解，需求出起检验数以判别是否均为非负。确定检验 数的方法有多种，下面介绍的方法称为位势法。 首先考虑标准形式的线性规划问题LP): min{cx|Ak=b,x≥0} 设B=(Pg,…,Pg)是其可行基，Ca=(Cg,,C)'是基向量对应的目标向量，则检验数 )=C,-cB-p,=C,-wp,其中w=cB称为关于B的对偶基解，即wB=c,也即w是方程 wpg=Cg,i=l…,m (2.2.1)） 的唯一解。根据(22.1)得到w后就可求出检验数r,=C,-wP,· 现在具体到问题(2.1.2)。由于(2.1.2)中有一个等式约束是多余的，故去掉(2.1.2)的第1个方程。设 XX,…,是关于可行基B=(P,P5,P)的基变量，其中卫为P,取掉第1个元素后得到的 向量，w=(,…,4,,,了为(4.12)关于B的对偶基解，则由(22.1)知wp=Ck=1…,r,即
7 x21 2 1 1 = = == min{ , } min{4,3} 3 ab b 在格子(2,1)处填入 3，并且 11 x = 0 (不用填)，划去第 1 列， 2 2 a a ′ = − =3 1。 对表中余下部分重新求出各行差额写在最后一列。从差额最大的第 1 行中运价最小 c13 对应的变量 x13 开始考虑： x13 1 3 3 = = == min{ , } min{7,5} 5 ab b 在格子(1,3)处填入 5，并且 23 x = 0 (不用填)，划去第 3 列， 1 1 a a ′ = − = 5 2 。 现在还剩下最后一列的第一、二个格子，从运价最小 c24 对应的变量 x24开始考虑： x24 2 4 2 = = == min{ , } min{1,3} 1 ab a ′ ′ ′ 在格子(2,4)处填入 1，划去第 2 行， 4 4 b b ′′ ′ = −=1 2 。 现在还剩下最后一列的第一个格子，考虑变量 x14： x ab 14 1 4 = == min{ , } min{2,2} 2 ′ ′′ 在格子(1,4)处填入 2，划去第 1 行和第 4 列。至此，得到了如下运输方案。 B1 B2 B3 B4 ai 行差额 A1 3 11 3 5 10 2 7 2 0 7 A2 1 3 9 2 8 1 4 1 1 7 A3 7 4 6 10 5 3 9 3 1 2 bj 3 6 5 6 3 2 20 列差额 2 5 1 3 2 表 2.2.3 由伏格尔法确定的例 2.2.1 的初始方案 2．2．2 检验数的求法 对于已知的基本可行解，为判别其是否为最优解，需求出起检验数以判别是否均为非负。确定检验 数的方法有多种，下面介绍的方法称为位势法。 首先考虑标准形式的线性规划问题(LP)： min{ | , 0} T cx x bx A = ≥ 设 1 ( ,, ) B Bm B = p p " 是其可行基， 1 (,, ) m T BB B c = c c " 是基向量对应的目标向量，则检验数 T T 1 j jB j j j rc B c − =− =− c p wp ，其中 T T 1 B B− w c = 称为关于 B 的对偶基解，即 T T w c B = B ，也即 w 是方程 , 1, , i i T B B w p = = ci m " (2.2.1) 的唯一解。根据(2.2.1)得到 w 后就可求出检验数 T jj j r c = − w p 。 现在具体到问题(2.1.2)。由于(2.1.2)中有一个等式约束是多余的，故去掉(2.1.2)的第 1 个方程。设 11 2 2 , ,, r r ij i j ij x x x " 是关于可行基 11 2 2 ( , ,, ) r r B ij i j ij = pp p ′′ ′ " 的基变量，其中 ij p′ 为 ij p 取掉第 1 个元素后得到的 向量， 2 1 (, , ,, , )T m n w = u uv v " " 为(4.1.2)关于 B 的对偶基解，则由(2.2.1)知 , 1, , kk kk T ij ij w p′ = = ck r " ，即
Ph=C,k=1,…,r，也即 山=0，，+V方=C,…,4,+V方=Ch 因此w是方程： 4=0,4+y,=C,(,)为数字格 的唯一解。该方程称为位势方程，4称为行位势，V,称为列位势。于是，检验数 P=Cg-4,-y,(i,)空格 例2.2.4确定表2.2.1所示的方案的检验数（写在各空格的左下角）。 2 9 3 10 B B2 B3 Ba ai 3 11 3 10 A1 4 3 7 1 2 1 9 2 8 -1A2 3 1 1 -1 4 10 5 -543 6 3 9 10 12 b 3 6 女 20 表2.2.4表2.2.1所示的方案的检验数 解：先由位势方程确定行位势和列位势： 41=0-→y3=3,y4=10→42=-1,43=-5→y=2,y2=9 再求出空格的检验数（各格子的左下角）： n1=3-0-2=-1,r12=11-0-9=2,r22=9-(-1)-9=1,r24=8-(-1)10=-1,3=7-(5)2=10,r33=10-(-5)3=12 例2.2.5确定表2.2.2所示的方案的检验数。 4 4 6 山 B B2 B3 BA ai 5 5 0 A 20 20 0 0 6 7 5 -142 30 30 2 4 2 3 2 4 -2A3 10 10 20 0 40 b 10 10 20 50 90 表2.2.5表2.2.2所示的方案的检验数 2.2.3方案的调整 P
8 0 , 1, , kk kk T ij ij ck r ⎛ ⎞ ⎜ ⎟ = = ⎝ ⎠ p w " ，也即 1 1 11 1 0, , , r r rr i j ij i j ij u uv c uv c = += += " 因此 w 是方程： 1 u = 0 ， , (, i j ij u v c ij + = ∀ ）为数字格 的唯一解。该方程称为位势方程， i u 称为行位势， j v 称为列位势。于是，检验数 0 , (, ) T T ij ij ij ij ij ij i j r c c c u v ij ⎛ ⎞ = − = − = −− ∀ ′ ⎜ ⎟ ⎝ ⎠ wp p w 空格 例 2.2.4 确定表 2.2.1 所示的方案的检验数(写在各空格的左下角)。 vj uj 2 B1 9 B2 3 B3 10 B4 ai 0 A1 3 1 11 2 3 4 10 3 7 -1 A2 1 3 9 1 2 1 8 -1 4 -5 A3 7 10 4 6 10 12 5 3 9 bj 3 6 5 6 20 表 2.2.4 表 2.2.1 所示的方案的检验数 解：先由位势方程确定行位势和列位势： 1 u = →0 3 4 v v = =→ 3, 10 2 3 u u = − =− → 1, 5 1 2 v v = 2, 9 = 再求出空格的检验数(各格子的左下角)： r11=3-0-2=-1，r12=11-0-9=2，r22=9-(-1)-9=1，r24=8-(-1)-10= -1，r31=7-(5)-2=10，r33=10-(-5)-3=12 例 2.2.5 确定表 2.2.2 所示的方案的检验数。 vj uj 4 B1 5 B2 4 B3 6 B4 ai 0 A1 4 0 5 0 5 1 6 20 20 -1 A2 8 5 6 2 7 4 5 30 30 -2 A3 2 10 3 10 2 20 4 0 40 bj 10 10 20 50 90 表 2.2.5 表 2.2.2 所示的方案的检验数 2．2．3 方案的调整
由单纯形法知，对于(2.1.2)的当前基本可行解x°={x}，若其检验数≥0，(，)空格，则 x°={x}为(2.1.2)的最优解。否则，则用以下的闭回路调整法对原方案进行调整。先给出如下结论。 定理2.2.1设变量组 X3X2’…,X (2.2.2) 是(2.1.2)关于某个基B的基变量组。若x,是关于B的非基变量，则在变量组 术，XX…,Xi (2.2.3) 这存在唯一的闭回路。 证明：首先，由定理2.1.2知(2.2.2)不含闭回路，由(4)=r和定理2.1.1知(2.2.3)含闭回路。其次，假 若(2.2.3)含两条不同的闭回路，则由(2.2.2)不含闭回路知，这两条闭回路均含有x,从而得知P.可用两 种不同方式表示为P,P,…,P,的线性组合，由此知P,P,…,P,线性相关，再根据定理2.11 知X…,含闭回路，矛盾。 令r=min{U|(i,j)空格}，则x,进基。根据定理2.2.1知，当把x,加入原基变量组(2.2.2)后，可 找到唯一的闭回路，不妨设为 Xsm=xstXs2XsXsXsea 当将x由x=0增加到x=0时，为保证等式约束条件成立，由以下推论： x4=X增加8(9，)带正号)→x6减少0(S,4)带负号)→x增加0(S,2)带正号) →x4减少0(S2,)带负号)→…→x4增加0(S,4)带正号)→4减少0(，4)带负号) 因此为保证非负性，应取0=mi{xI亿，)带负号}兰x,于是xm出基，新的基本可行解为： xg+日，6，)：+ x{x-, 0,):- 9, otherwise 例2.2.6用闭回路调整法对表2.2.4所示的方案进行调整。 解：由表22.4知，24=min|(亿，)空格}，则x24进基。易得闭回路x24,x23,x3,x4,分别标上 正负号，得下标： 号 2 9 3 10 B B2 B3 Ba a; 3 11 3 10 0 A 4 3 7 1 2 9 2 8 -1A 3 十 4 10 5 -5 A3 6 9 10 12 b 3 6 5 6 20 表2.2.6对表2.2.4所示的方案的调整过程 9
9 由单纯形法知，对于(2.1.2)的当前基本可行解 0 0 { }ij x = x ，若其检验数 0, ( , ) ij r ij ≥ ∀ 空格，则 0 0 { }ij x = x 为(2.1.2)的最优解。否则，则用以下的闭回路调整法对原方案进行调整。先给出如下结论。 定理 2.2.1 设变量组 11 2 2 , ,, r r ij i j ij x x x " (2.2.2) 是(2.1.2)关于某个基 B 的基变量组。若 st x 是关于 B 的非基变量，则在变量组 st x , 11 2 2 , ,, r r ij i j ij x x x " (2.2.3) 这存在唯一的闭回路。 证明：首先，由定理 2.1.2 知(2.2.2)不含闭回路，由 r(A)=r 和定理 2.1.1 知(2.2.3)含闭回路。其次，假 若(2.2.3)含两条不同的闭回路，则由(2.2.2)不含闭回路知，这两条闭回路均含有 st x ，从而得知 st p 可用两 种不同方式表示为 11 2 2 , ,, r r ij i j ij pp p " 的线性组合，由此知 11 2 2 , ,, r r ij i j ij pp p " 线性相关，再根据定理 2.1.1 知 11 2 2 , ,, r r ij i j ij x x x " 含闭回路，矛盾。 令 min{ | ( , ) st ij r r ij = 空格}，则 st x 进基。根据定理 2.2.1 知，当把 st x 加入原基变量组(2.2.2)后，可 找到唯一的闭回路，不妨设为 11 12 2 2 2 3 1 1 , , , ,, , kk k kk s t st s t s t s t s t s t s t x xx x x x x x + = = " + - + - + - 当将 st x 由 0 st x =0 增加到 st x =θ 时，为保证等式约束条件成立，由以下推论： 1 1 s t st x = x 增加θ ( 1 1 (,) s t 带正号)→ 1 2 s t x 减少θ ( 1 2 (,) s t 带负号)→ 2 2 s t x 增加θ ( 2 2 (,) s t 带正号) → 1 3 s t x 减少θ ( 2 3 (,) s t 带负号)→ → " k k s t x 增加θ ((,) k k s t 带正号)→ k 1 s t x 减少θ ( 1 ( ,) k s t 带负号) 因此为保证非负性，应取θ = 0 min{ | ( , ) ij x i j 带负号} 0 pq x ，于是 pq x 出基，新的基本可行解为： 0 0 0 0 , ( , ): , ( , ): , ij ij ij ij x ij x x ij x otherwise θ θ ⎧ + ∀ + ⎪⎪ ⇐ ⎨ −∀ − ⎪ ⎪⎩ 例2.2.6 用闭回路调整法对表 2.2.4 所示的方案进行调整。 解：由表 2.2.4 知， 24 min{ | ( , ) ij r r ij = 空格}，则 24 x 进基。易得闭回路 24 x , 23 x , 13 x , 14 x ，分别标上 正负号，得下标： vj uj 2 B1 9 B2 3 B3 10 B4 ai 0 A1 3 1 11 2 3 4 + 10 - 3 7 -1 A2 1 3 9 1 2 1 - 8 + -1 4 -5 A3 7 10 4 6 10 12 5 3 9 bj 3 6 5 6 20 表 2.2.6 对表 2.2.4 所示的方案的调整过程
得调整量0=min{x,x4}=min{1,3}=1=x3,因此x3出基变为空格， x94=0=1,x9=x9+0=4+1=5,04=x9-0=3-1=2 得如下新方案： 山 B1 B2 B3 B4 ai 11 10 A 5 > 9 2 A2 3 7 10 U A3 6 b 6 5 6 20 表2.2.7对表2.3.4所示的方案进行调整后的新方案 综合上述过程，我们给出求解平衡运输问题(2.1.2)的表上作业法的具体步骤。 1.初始步：给出运输表2.11，用最小元素法或伏格尔法确定初始方案。 2.确定检验数：用位势法确定行位势4，i=1,…,m和列位势y,广=1，…，n。对所有空格()，令 r=Cg-4-V,。 3.最优性判别。若≥0，(i,)空格，则当前方案为最优方案。 4.调整方案。令r=min{|(亿，j)空格}，xu进基。用闭回路调整法确定出基变量xp并调整当前方案。 转2。 例2.2.7求例2.2.1的最优方案。 用最小元素法得初始方案如表2.2.1，用位势法得检验数如表2.2.4，用闭回路调整法得新方案如表 2.2.7,继续求解得如下表格： 3 9 3 10 山 B B2 B3 Ba ai 3 11 3 10 0 A 2 > 0 2 9 2 -2A2 3 2 7 10 5 A3 6 9 12 b 3 6 6 20 由于所有检验数均非负，得最优方案： x13=5,x14=2,3X21=4,X24=1,X32=6,x34=3,其他x=0 最小费用为85。 S
10 得调整量 0 0 min{ , } 23 14 θ = x x =min{1,3}=1= 0 23 x ，因此 23 x 出基变为空格， 0 00 00 24 13 13 14 13 x xx xx = = = + = += = − = −= θθ θ 1, 4 1 5, 3 1 2 得如下新方案： vj uj B1 B2 B3 B4 ai A1 3 11 3 5 10 2 7 A2 1 3 9 2 8 1 4 A3 7 4 6 10 5 3 9 bj 3 6 5 6 20 表 2.2.7 对表 2.3.4 所示的方案进行调整后的新方案 综合上述过程，我们给出求解平衡运输问题(2.1.2)的表上作业法的具体步骤。 1．初始步：给出运输表 2.1.1，用最小元素法或伏格尔法确定初始方案。 2．确定检验数：用位势法确定行位势 , 1, , i ui m = " 和列位势 , 1, , j vj n = " 。对所有空格(i,j)，令 ij ij i j r c uv = −− 。 3．最优性判别。若 0, ( , ) ij r ij ≥ ∀ 空格，则当前方案为最优方案。 4．调整方案。令 min{ | ( , ) st ij r r ij = 空格}， st x 进基。用闭回路调整法确定出基变量 pq x 并调整当前方案。 转 2。 例 2.2.7 求例 2.2.1 的最优方案。 用最小元素法得初始方案如表 2.2.1，用位势法得检验数如表 2.2.4，用闭回路调整法得新方案如表 2.2.7，继续求解得如下表格： vj uj 3 B1 9 B2 3 B3 10 B4 ai 0 A1 3 0 11 2 3 5 10 2 7 -2 A2 1 3 9 2 2 1 8 1 4 -5 A3 7 9 4 6 10 12 5 3 9 bj 3 6 5 6 20 由于所有检验数均非负，得最优方案： x13=5，x14=2，x21=4，x24=1，x32=6，x34=3，其他 xij=0 最小费用为 85
