第二部分线性规划应用 第二章运输问题和指派问题（书第三章，§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 用最小元素法确定如下运输问题的初始方案