上海交通大学：《运筹学》教学资源（课程讲义）第二章运输问题和指派问题.pdf_大学文库

=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 得结论

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 开始考虑：

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 " ，即

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 所示的方案的调整过程

上海交通大学：《运筹学》教学资源（课程讲义）第二章 运输问题和指派问题

上海交通大学：《运筹学》教学资源（课程讲义）第二章运输问题和指派问题