05第五章运输问题解析

1、5 - 1 第五章运输问题 在生产实践中，经常会遇到这样一类线性规划问题： 其变量和约束条件的个数都非常庞 大，因此在计算机上应用单纯形法求解时， 可能比较费时或占用大量内存。 但这些线性规划 问题往往具有另一个特点： 系数矩阵A= （aj）中的元素aj大多数为零，而非零的元素aj又 呈现一定的规律。于是可利用这类问题的特殊结构而拟制比单纯形法简单得多的特殊解法， 从而较好地节约计算机的 CPU 时间和内存。本章讨论的运输问题就属于这一类特殊结构的线 性规划问题。先介绍运输问题的数学模型， 然后给出其求解方法一表上作业法，最后介绍 一些典型的运输问题的应用例题。 5.1 运输问题的数学模型 运

2、输问题这个名称的获得是因为这类数学模型首先在物资运输的合理规划中形成并运 用的缘故。但是运输问题及其求解方法所管辖和研究的对象事实上要广泛得多。 例如，对于 生产计划等这类管理问题也是行之有效的。运输问题的典型描述是，在商品的货物运输中， 有 m 个出发地/产地（发点）A1.Am，可供应某种物资，并将物资运送给 n个到达地/ 销地（收点）B1.Bj.Bn，发点A的物资供应量（发量）为q ,收点Bj对物资的需求量（收 m n 量）为bj，且收发平衡：即送a =送bj ,又设物资从A运往Bj的运费是q，求如何运输 y j=i 这些物资，使总运费最小？ 解：可将有关问题制成下表，称为 运输收发平衡单

3、位运价表 ，简称运输表格。 表 5.1 Bj A、 Bj Bn ai A Gi Gj Gn ai 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 A Ci . Gj . Gn ai 1 1 1 1 1 1 1 1 1 1 1 Am Oml Cmj Cmn am bj bj bn 设物资从A运往Bj的运量是x ,则可得表 5.2 5 - 2 A、 Bj Bn ai A X11 X1j Xm a1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 A X1 Xj Xn ai 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 An Xm1 Xmj Xmn am bj

4、b1 bj Q 由此不难建立运输问题的线性规划模型: m n min f _ 7、q xij i j 1 n s.t Xj =ai, i =1,，m j 壬 j （ 5.1） m xij = bj, j =匕,n i 1 Xj KO, i =1,., m; j =1,.,n m n 其中瓦a =瓦勺。上述模型为运输问题的标准模型，它含有 mn个变量。如果将全部 i 1 j吕 n m n m m 发量约束 7 Xj =ai相加，就得到二二Xjj aj ,将全部收量约束 7 Xjj二bj相加，就得 j 1 i ：! j d id i J n m n m n 到E E Xj =瓦bj ,由于收发平衡

5、 E ai =L bj，所以模型中 m+n个等式约束不是相互独 j 壬 y j 1 y j d 立的。但如果在任取 m n -1个，则它们是相互独立的。 所以模型中m n个等式约束中删 除任何一个，运输问题（5.1 ）的可行域不变。运输问题（ 5.1 ）的基本解只有 m n-1个 基本变量。 单纯形法的基本步骤是： 寻找初始基本可行解， 检验是否最优解？若不是最优解， 则进 行转轴运算。对于运输问题来说，这些步骤可以简化。在手算时它们可以在运输表格上直接 进行，所以称运输问题的求解方法为 表上作业法。 在运输收发平衡表的 mn个变量中，如何选取m n-1个变量使其成为基本变量组呢？ 为此，需要

6、首先介绍一些相关的基本概念。 1、闭回路的概念5 - 3 设E是运输问题（5.1 ）式的一组变量，如果对 E的变量作适当的排列后能得到下列形 其中i!,i2,.,is互不相同，ji, J2,-, js互不相同，则称E为运输问题（5.1 ）式的一个闭 回路，闭回路中的相应变量为 闭回路的顶点。 例如，设 m=3,n=4, E二X21, X23是一个闭回路，如下表所示。 顶点用线段相连，构成闭回路中边，贝 U E就有了表 5.3 的形状。 闭回路中的边只能是水平的垂直的，闭回路的边所通过的行或列都恰有它的两个顶点。 2、孤立点的概念 设Q是运输问题（5.1 ）式的一组变量，若 冷是Q中的一个变量，

7、且 是第 i 行或第 j 列中属于Q的唯一变量，则称 冷为Q的一个孤立点。例如，在变量组: Q - X11,X14, X15,X16 ,X26 , X23, X31 , X42 , X43 , X45 中，X|1, X31, X42 , X|4 都是孤立点。E = X15, X|6 ,X26 , X23 , X43 , X45是一 -个闭回路，E的顶点都 表 5.4 A、B B2 B3 B4 B5 B6 A * *1 * X14 X15 X16 A X23 X26 A * X31 A * X42 X43 X45 在Q中，称E为Q中的一个闭回路。 定理 5.1 式: X1ji, Xlj2，X为2

8、3，表 5.3 5 - 4 1、在运输问题（5.1 ）式的 m+n个等式约束方程中，只有 m n_1个是相互独立的, 而且其中任意一组 m n 一1个等式约束方程都是相互独立的。 2、在运输问题（5.1）式的mn个变量中，选取 m - n 1个变量构成变量组 Q，则Q 能够成为基本变量组的充分必要条件是：变量组 Q中不存在闭回路。 3、设Q是运输问题（5.1 ）式的一个基本变量组， xst为非基本变量，则xst必对应一 条唯一的闭回路E， E除顶点Xst外，其余顶点都是基本变量。 4、如果在运输问题（5.1 ）式中a （i =1,.,m）和bj （j = 1,.,n）都为整数，则任一基 本解中

9、各变量的取值均为整数。 例 5.1，表 5.5 所给出的变量组 Q =x12, x14, X15，X23 ,X26，X35，X41，X43，X45 就是一个基本变量组。此时， X11是一个非基变量，用记号 表示。在Q u X11中就存 在一条闭回路E X11,X15,X45,X41 o U表示并集。 表 5.5 Bj A、 B2 B3 B4 B5 B6 A X11 乂 X12 X14 X15 A2 X23 X26 A3 X35 A4 X41 X43 X45 讨论：若Q是运输问题（5.1 ）式的一个基本变量组， Xst为非基本变量，则应该如何 在Q U xst中确定闭回路E ? 由闭回路的性质可

10、知，Q U Xst中的孤立点Xj 定不是E的顶点。因此，我们可以通 过反复从变量组中删去孤立点来获得 E。有些变量原来并不是一个孤立点，但是当变量组 中删除一些变量后，就有可能在余下变量所组成的变量组中成为孤立点，它同样应被删去。 最后剩下的未被删去的变量便组成了闭回路 E，而xst 定是E的一个顶点。 例如，在表 5.5 中，对于Q U &来说，X|2,为4, X26, X35是孤立点，但从 Q U Xn中 5 - 5 删去这四个点后得到 Q ,则X23成为Qi的孤立点，从Qi中删去X23得到Q2 ,则X43又成为Q? 的孤立点，再从 Q2中删去X43，得到E =Xii,X4i,X4

11、5,Xi5，它是一个闭回路。 5.2 表上作业法 5.2.1 初始基本可行解的寻求 求运输问题（5.1）式的初始基本可行解有多种方法， 这里介绍西北角法和最小元素法。 1. 西北角法 西北角法按下列规则在 mn个变量中选取 m n-1个基本变量构成变量组 Q :从运输 表格的西北角Xii开始，优先安排编号小的发点和收点之间的运输任务。 例 5.2 给出运输问题，如表 5.6 所示，试用西北角法确定它的一个基本可行解。 表 5.6 AW B1 B2 B3 B4 ai A 15 A 20 A 10 bj 12 15 10 8 表 5.7 单位：吨 A、Bj、 B1 B2 B3 B4 q A 12

12、3 X X 15 3 0 A X： 12 8 X： 20 8 0 A X： X 2 8 10 8 0 bj 12 15 10 8 0 12 2 0 0 0 取Q=X11。此时B|所需要的货物运量 12 吨全部从A运来，B约束X11 - X21 X31 =12 已经满足，变量X21和X31都应取值为零，因此，在相应的空格 （2,1）和（3,1）内打上记号，表 示这两个变量为非基本变量，其值为零。同时 R由 12 减为 0, a1变为 15-12=3 （吨）。 接着，安排发点 A和收点B2之间的运输任务。取 5 - 6 为2 =mi ngb =mi n3,15 =3 于是此时A的发量已全部运完，

13、ai改为 o,变量x,3和Xg作为非基本变量其值为零。 在相应的空格(1,3)和(1,4)内打上记号，同时鸟改为 15-3=12。于是，0=冷，卷。接下去, 再安排发点A2和收点B2之间的运输任务。如此继续进行运量分配， 整个具体的运算过程列 在表 5.7 中，可知基变量组 Q =Xn,X12,X22,X23,X33,X34。 这样，得到基本可行解: X B = (X11 , X12 , X22 , X23, X33 , X34) = (12,3,12,8,2,8) XN =(X13, X14 ,X21, X24, X31, X32) - (0,0,0,0,0,0) 例 5.3 对运输问题表格

14、所示的表 5.8，试用西北角法求它的一个初始基本可行解。 表 5.8 Aj B1 B2 B3 B4 ai A 20 A 10 A 30 b 15 15 10 20 表 5.9 单位：吨 A、Bj B1 B2 B3 B4 A 15 5 X X 20 5 A X 10 A X 30 bj 15 0 15 10 10 20 在表 5.9 中，取x11=15，在相应的空格(2,1)和(3,1)内打上记号，取X12=5，在空格(1,3) 和(1,4)内打上记号，a1变为 5， b减为 0， b2减为 10。 但是在表 5.9 中，当空格(2,2)填上数字x22 =10 以后，发量约束和收量约束都得到满足

15、， 发量a2和收量b2都应变为零。此时，我们只能对行或列之一的剩余空格打记号 。然后在剩 5 - 7 余的空格中再按西北角法运算下去，否则，对行和列的剩余空格同时打记号 ，那么在运算 结束时就会发现基本变量少于 m n -1个。 般地，在算法的迭代过程中，如果对空格（ s,t）填写数字xst后，发量约束和收量约 束都得到满足，比与bt都变为 0,则规定： 对Bt列的剩余空格打记号 汉，对空格（s,（t+1）填写数字xs（t半）=0。xs（t糊作为基本 变量置入基本变量组 Q中，再对As行剩余空格打记号 。然后继续运算。 按此规定，对表 5.9 继续运算，其过程如表 5.10 所示。本题的基本可

16、行解为: X B = (X11, X12, X22 , X23 , X33 , X34) = (15,5,10,0,10,20) XN =(X13, X14 , X21, X24 , X31 , X32 ) - (0,0,0,0,0,0) 表 5.10 单位：吨 AW B1 B2 B3 B4 q A 15 5 X X 20 5 0 A X 10 0 X 10 0 A X X 10 20 30 20 0 bj 15 15 10 20 0 10 0 0 0 倘若在本例中不选 X23=0 作为基本变量，而让 X23=0 作为非基本变量，打记号 。那么, 应该在其余的非基本变量（表 5.10 中打记号

17、 者）中选一个变量作为基本变量并取值为 0， 但要保证该变量置入基本变量组 Q后，Q中不包含闭回路。例如可以选X14=0 作为基本变量 置入基本变量组Q中。 在运算中，若以I表示当前还有货物要运送的发点的下标集合， J表示当前需求量尚未 得到满足的收点的下标集合， Q为基本变量组， H为非基本变量组，则西北角法的算法步 骤如下： 取 I 二1,.,m, J =1,., n, Q =. I是否仅含指标 m?若是，则Xm bj, j J Q =QUXmj | j J, H |Xj - Q,i =1,.,m; j =1,.n； Xj =0, Xj E H，算法终止。 若否，则转步骤 5 - 8 J是

18、否仅含指标n?若是，则xn=aj,i| Q =QUXin |i 引, H =Xj |Xi严 Q,i =1,.,m; j =1,.n； Xj =0, Xj H，算法终止。 若否，则确定 s 和 t，取： s = min i | i I, t = min j | j J，转步骤 取；二 minas,h, Xst 二；，Q 二 QUXst Xst = ； = bt ? 若是，则 bt = b - ；, as = as - ；, J = J -t，转步骤 若否，则 as =as - ；，Q =at - ；，I =I -s，转步骤 2. 最小元素法 最小元素法采用如下规则选取 m n -1个基本变量：优

19、先安排单位运价 cj小的发点A 与收点Bj之间的运输任务。 例 5.4 运输问题如表 5.11，用最小元素法求初始基本可行解。 表 5.11 单位：吨 Aj B1 B2 B3 B4 ai A 4 7 3 10 20 A 2 5 2 6 10 A 9 3 8 4 25 bj 12 16 14 13 解: 现在 I 二1,2,3, J= 123,4,取 Cst 二 minq |i I, j J二 C23 = 2，于是，令 xst =x23； - mina2,t3 =min10,14=10 将x23置入变量组Q中，a2变为 0, =14-10=4。对A2行的剩余空格打上记号 。 现在 I I 叫1,

20、3, J =1,2,3,4,取 Cst 二 minq |i I, j J二 G3 = 3，于是，令 5 - 9 xst =为3 = ； =mi ngb/ =mi n20,4 =4 将xn置入变量组Q中，a1变为 16，b3变为 0。对B3列的剩余空格打上记号 。继续运 算，整个过程如表表 5.12 所示。5 - 10 XB =(X11 , X13, X14, X23, X32 , X34) - (12,4,4,10,16,9) XN 二(X12 , X21 , X22 , X24 , X31, X33) (0,0,0,0,0,0) 在运用最小元素法求基本可行解的过程中，为了保证基本变量的个数为

21、 m - n_1，应 遵循下列两点规定： 当运量待分配的运输表格剩下最后一行或最后一列有未填数值或未打记号 的空格 时，只准填写数值（包括 0）,不准打记号 忍 如果空格（s,t ）填写数值Xst后，A行及Bt列的约束方程同时满足， 修改后的as和 bt均变为 0,这时只能对行或列之一的剩余空格打上记号 。在此情况下，不妨规 定对A所在行的剩余空格打记号 。 例 5.5 运输问题如表 5.13 所示，用最小元素法求初始基本可行解。 表 5.13 单位：吨 A B1 B2 B3 B4 q A 6 2 9 7 10 A2 5 3 4 12 25 A 2 8 7 10 15 A、Bj B1 B2 B

22、3 B4 q A 12 4 7 4 3 4 10 20 16 4 0 A X 2 X 5 10 2 X 6 10 0 A 9 16 3 8 9 4 25 9 0 X X bj 12 16 14 13 0 0 4 4 0 0 表 5.12 单位：吨 本题所得的基本可行解为: 5 - 11 bj 15 10 17 8 解：基本变量的个数为 3+4-仁 6 个。5 - 12 现在 I =1,2,3, J = 1,2,3,4,取 cst = minq |i I, j J =c12 = 2，于是，令 xst =x12 - ； - mingb =min10,10 = 10 将為2置入变量组Q中，a1和b2

23、都变为 0,对A行的剩余空格都打上记号 。对B2列的 剩余空格不能都打上记号 ，这时不妨令x2 =0,将x32空格打上记号 。 现在 1 1 二2,3, J =1,2,3,4，取 Cst 二 minq |i I, j J二 C31 = 2，于是，令 xst =x31 = ； = mina3,bj 二 min15,15 = 15 将x31置入变量组Q中，a3和b都变为 0。对A行的剩余空格打上记号 。同理，对B1 列的剩余空格不能都打上记号 ，这时不妨令x21=0。 现在 1 =,J =1,2,3,4，取 Cst = minq X I, j 弋3 = 4,于是，分别 x?3 和 x24置入变量组

24、 Q中，且x2j二bj，整个过程如表表 5.14 所示。 表 5.14 单位：吨 ABj B1 B2 B3 B4 ai A X 6 10 2 X 9 X 7 10 0 A 0 5 0 3 17 4 8 12 25 8 0 A 15 2 X 8 X 7 X 10 15 0 bj 15 0 10 0 17 0 8 0 本题所得的基本可行解为: XB =(X12 ,X21,X22, X23, X24, x31) =(10,0,0,17,8,15) 将最小元素法的算法步骤如下： 取 I =1,.,m, J =1,., n, Q = _ I是否仅含一个指标？ 若是，则对r I，取Xj二bj, j J,

25、Q二QUXj | j J，转步骤 若否，则J是否仅含一个指标？ 若是，则对j = J，取Xj =a, i I, Q =QUXj |i E I，转步骤 若否，则转步骤 XD =(x11 , X13, X14 , X21 , XX ) 二(0,0,0,0,0,0) 5 - 13 取非基本变量组 H =x |i =1,.,m; j =1,.n Q ；对x H，令x” = 0，算法 终止。 取： Q =minq|i I, j J; Xst 二 minas,bj, Q = QUXst, a$ = a$ - Xsth = bt -Xst as = 0? 若是，则I =I -s，转步骤 若否，则J =J-t

26、，转步骤 5.3 位势法 最优基本可行解表上求解法的基本思想，和一般的单纯形法一样，也是从一个基本可 行解出发，按一定的规则进行改进，直至求得最优基本可行解。 位势法也属于表上作业法，之所以将其单独列出，是因为它的作用与前述的西北角法 及最小元素法不同。西北角法与最小元素法是设法求得一个初始基本可行解， 而位势法的作 用是在此基础上，求得最优基本可行解。 设运输问题（5.1 ）式的线性规划标准形式为： . T min z 二 c x s.t Ax=b （ 5.3.1 ） x _ 0 由第四章可知，经过适当的运算， ANB,N All m, N ，B是系数矩阵中对应于基变 量的部分，且： A 叫

27、Pj |i =1,.,m; j =1,.,n pij是系数矩阵的列向量。 c = （cB,Ct）， cB是目标函数的系数向量中应于基变量的部 分，对于一维的线性规划，基变量有 m个，而象运输问题这样的二维线性规划，基变量有 m n T 个。 当一个基本可行解给定后，先要判断该解是否为最优解，为此需要计算对应的每个变 量Xj的判别数： Zj _Cij = CBB斗Pj _q = wp _q （ 5.3.2） 5 - 14 其中，W二（Wi, w?,Wm,Vi,V2,.,Vn） = （w, V）称为单纯形乘子。已知，在（5.1 ）式的 m n个约束中有一个是多余的，可以去掉任意一个，例如去掉第一个

28、，这样单纯形乘子的 计算式为： W = 0, （5.3.3 ） W Vj 二 q ,-基变量 Xj 符号-表示任意。即： （W, v） Pj = q , P 基变量 Xj 而判别数的表达式为： Zj Cj =（w,v） Pj q =w +Vj q Vi, j （5.3.4） Wj和Vj分别是现行基变量下的第 i 行和第 m+j 行的位势，因此上述计算判别数的方法 称为位势法。 若运输问题（5.1 ）式求极小值，则当 全体判别数都小于等于零时达到最优解 ，反之， 若运输问题（5.1 ）式求极大值，则当全体判别数都大于等于零时达到最优解。 当运输表未达到最优时，用闭回路法对现行解加以改进，求出新的

29、基本可行解。可选 择对应最大判别数的变量作为进基变量，若有： maxZj _Cj =Zpq 七 0 则取Xpq作为进基变量。由定理 5.1，任一个非基变量和基变量均构成唯一的闭回路。 在Xpq和基变量均构成的唯一的闭回路上，改变各变量的取值，不属于闭回路的变量保持不 变。设改变量为二，即令Xpq - V,回路中其他变量作相应改变。为保持可行性，原则是回 路中同一行或同一列的两个变量， 一个增加二，另一个就要减少 二。以此确定一个最大改变 量，与之相对应的基变量取值变为 0,成为新的非基变量，Xpq与原有的其他基变量一起构 成一组新基。然后再按（5.3.3 ）式在表上计算 W和V ,按（5.3.

30、4 ）式计算新的判别数 Zj Cj， 若新基已经达到最优，则停止；否则，再取闭回路将其改进，直至求得最优解。 例 5.6 运输问题如表 5.3.1 所示，其中 A是产地，ai是产量，Bj是销地，bj是销量，每个 方格右上角数字是费用系数 q，试确定一个运输方案，使得总运费最小。5 - 15 5.3.2 所示。 表 5.3.2 单位：吨 A、B、 B1 B2 B3 B4 ai A 5 5 5 8 X 3 X 4 10 5 0 A X： 6 0 7 11 4 1 8 12 1 0 A 7 6 8 9 5 9 0 X X X bj 5 5 11 10 0 0 0 0 本题所得的基本可行解为: XB

31、=(X11, X12, X22 , X23 , X24 , X34 ) = (5,5,0,1 1,1,9) XN 二(X13,X14,X21,X31,X32, X33) = (0,0,0,0,0,0) 按（5.3.3 ）式在表上计算 w和Vj ,分别置于左端和上端，再按（5.3.4 ）式计算判别数Zj - Cj , 置于每个方格左下角的方格内，如表 5.3.3 所示。 在表 5.3.3 中，最大判别数 Zu -014 =5，没有达到最优，需用闭回路法对现行解加以改 进，求出新的基本可行解。取闭回路 x14,x24,x22,x12，记改变量为二，为保持可行性，令 X14 - T 0， X24 =

32、 1 -二 一 0， X22 = 0 V - 0, X12 = 5 -二 _ 0 ,从而得 T - 1。同时 X14 成 为基变量，而X24成为非基变量。新的基本可行解置于表 5.3.4 中，基变量取值为： (X11 , X12 , X14, X22, X23, X34) = (5,4,1,1,11,9) 目标函数值为 f =157。A、Bj B1 B2 B3 B4 q A 5 8 3 4 10 A 6 7 4 8 12 A 7 6 8 5 9 bj 5 5 11 10 表 5.3.1 单位：吨 解：基本变量的个数为 3+4-1=6 个。先用西北角法求得初始基本可行解， 计算结果如表 5 -

33、16 到在新基下的位势。进而按（5.3.4 ）式计算新的判别数 z -C，这些计算都在表 5.3.4 上 完成。 表 5.3.4 单位：吨 Vj 5 8 5 4 w A j B2 B3 B4 ai 0 A 5 5 4 8 3 1 4 10 2 | -1 A2 6 1 7 11 4 8 12 -2 -5 1 A3 7 6 8 9 5 9 -1 3 -2 bj 5 5 11 10 在表 5.3.4 中，最大判别数Z32 -2 =3，仍然没有达到最优， 再用闭回路法求改进的基 本可行解。取闭回路 x32,x12,x14,x34，计算调整量 v。令2 -二- 0，x12 = 4 - ： - 0， X14 =1- 0, X34 =9-二-