第3章运输问题的求解方法 物资最佳调运问题是属于线性规划的一种特殊类型—运输问题。它的解法很多 在这一章里将介绍两种求解方法表上作业法和图上作业法 3.1平衡运输问题及数模 3.1.1问题的提出 社会生产活动川流不息、工农之间、地区之间、各生产企业之间、各企业车间之间, 必然产生不间断的,错综复杂的经济联系。这种联系是由交通运输业的货物运输来实现 的 无论地区范围内的运输或者工地范围内的运输,在组织运输时,必须选择合理的物 资调运方案。选择合理的物资调运方案是运输工作组织中十分重要的问题,特别是当物 资的需要特点(收点)及供应地点(发点)较多,而需要的供应数量又各不相同时,如 何根据具体条件,各个收发点的分布,交通运输线路的位置及其他条件等,科学地确定 最为合理,经济的调运方案,对于充分发挥运输工具的潜力,降低运输成本,保证建设 任务的完成有着极为重要的作用。 3.1.2平衡运输问题的数模 设4(=12…m)为出发点,B,(=12…m)为收点,a和b分别表示A和B的 发量和收量,G和x分别表示A到B的单位运费和运量 则有线性规划模型。 minf(x) x=a (i=1,2,…,m) b (=1,2…,n) x20(=12…,m;j=1,2,…,n) 在这里假定∑a=∑b,且a,b≥0,c20。满足以上条件的运输问题被称为平衡运 输模型,为了叙述骨便起见,采用(,P)表示。 3.1.3(T,P的特性 1.(T,P)的系数矩阵A的秩为m+n+1
第 3 章 运输问题的求解方法 物资最佳调运问题是属于线性规划的一种特殊类型——运输问题。它的解法很多， 在这一章里将介绍两种求解方法----------- 表上作业法和图上作业法。 3.1 平衡运输问题及数模 3.1.1 问题的提出 社会生产活动川流不息、工农之间、地区之间、各生产企业之间、各企业车间之间， 必然产生不间断的，错综复杂的经济联系。这种联系是由交通运输业的货物运输来实现 的。 无论地区范围内的运输或者工地范围内的运输，在组织运输时，必须选择合理的物 资调运方案。选择合理的物资调运方案是运输工作组织中十分重要的问题，特别是当物 资的需要特点（收点）及供应地点（发点）较多，而需要的供应数量又各不相同时，如 何根据具体条件，各个收发点的分布，交通运输线路的位置及其他条件等，科学地确定 最为合理，经济的调运方案，对于充分发挥运输工具的潜力，降低运输成本，保证建设 任务的完成有着极为重要的作用。 3.1.2 平衡运输问题的数模 设 A i i ( 1 = , 2,…,m) 为出发点， (1,2, , ) Bj j = … n 为收点，ai 和bj 分别表示 Ai 和 Bj 的 发量和收量，Cij 和 ij x 分别表示 Ai 到 Bj 的单位运费和运量。 则有线性规划模型。 1 1 1 1 min ( ) ( 1,2, , ) ( 1,2, , ) 0 ( 1,2, , ; 1,2, , ) m n ij ij i j n ij i j m ij j i ij f x c x s t x a i m x b j n x i m j = = = = = ⋅ = = = = ≥ = = ∑∑ ∑ ∑ " " " " n j b 在这里假定 i j 1 1 ，且 ，c 。满足以上条件的运输问题被称为平衡运 输模型，为了叙述方便起见，采用（T，P）表示。 m n i a = = ∑ =∑ , 0 i j a b ≥ 0 ij ≥ 3.1.3 （T，P）的特性 1．（T，P）的系数矩阵 A 的秩为m n + +1
因为,A的前m行相加的结果等于后n行相加的结果,所以,它的m+n行的行向 量是线性相关的,秩不可能超过m+n+1。另一方面,我们还可以在A中找到一个m+n-1 阶的非奇异方阵,从而可知A的秩只能为m+n+1。并由此可推知,(T,P)的每个基本 可行解的基变量的个数为m+n+1个。 2.任一个(T,P问题至少有一个最优解存在 (1)(T,P)至少有如下的一个可行解: b (i=1,2,…,m;j=1,2,…,n) 其中,Q=∑a=∑b。 (2)它的目标函数显然有下界零(非负)。故由(1),(2)知(T,P)必有最优解 存在。 3.2图上作业法 图上作业法是解决(’,P问题的一个方法,它是在一张运输交通上通过一定步骤 的规划和计算来完成物资调运计划的编制工作,以便使物资运行的总吨—公里数 最小可使物资运费降低,并缩短了运输时间,所以,在一定条件下称这样的方案为最优 方案 制定一个物资调运方案时,首先要编制物资平衡表(如表3-1)。在编制物资平衡表 时需要做3件事。 1.出需要调出物资的地点(即发点)及发量 2.出需要调进物资的地点(即收点)及收量 3.求:总发量=总收量。 第二步,根据物资平衡表和收点,发点间的相互位置绘制交通图。所谓交通图就是 表明收点和发点间的相互位置以及联结这些点之间的交通线路的简要地图。在交通图 上,用圆圈“O”表示发点,将该发点的发量填入圆圈“O”内。用方框“口”表示收点, 将该收点的收量填入方框“口”内。两点间的距离,记在交通线路的旁边。 交通图绘制好后,即可在其上面进行物资调运,找出初始调运方案(初始基可行解) 即第三步,作物资调运流向图 B□ ○→口B ⑨4我们用箭头“-”表示物资调运的方向即称 B 流向,并规定:流向“→”必须画在沿着线路前 A○(a) 进的右侧。把运送物资的数量记在流向 图3-1 的旁边并加括号(),以区别于两点之间的距
因为， A 的前 行相加的结果等于后 行相加的结果，所以，它的 行的行向 量是线性相关的，秩不可能超过 m n m + n m n + +1。另一方面，我们还可以在 A 中找到一个 m+n-1 阶的非奇异方阵，从而可知 A 的秩只能为m n + +1。并由此可推知，（T，P）的每个基本 可行解的基变量的个数为m n + +1个。 2.任一个（T，P）问题至少有一个最优解存在。 （1） （T，P）至少有如下的一个可行解： ( 1, 2, , ; 1, 2, , ) i j ij a b x i m j Q = = " " = n 其中， b 。 1 1 m n i j i j Q a = = = = ∑ ∑ （2）它的目标函数显然有下界零(非负)。故由（1），（2）知（T，P）必有最优解 存在。 3.2 图上作业法 图上作业法是解决（T，P）问题的一个方法，它是在一张运输交通上通过一定步骤 的规划和计算来完成物资调运计划的编制工作，以便使物资运行的总吨-----------公里数 最小可使物资运费降低，并缩短了运输时间，所以，在一定条件下称这样的方案为最优 方案。 制定一个物资调运方案时，首先要编制物资平衡表（如表 3-1）。在编制物资平衡表 时需要做 3 件事。 1.出需要调出物资的地点（即发点）及发量。 2.出需要调进物资的地点（即收点）及收量。 3.求：总发量=总收量。 第二步，根据物资平衡表和收点，发点间的相互位置绘制交通图。所谓交通图就是 表明收点和发点间的相互位置以及联结这些点之间的交通线路的简要地图。在交通图 上，用圆圈“〇”表示发点，将该发点的发量填入圆圈“〇”内。用方框“□”表示收点， 将该收点的收量填入方框“□”内。两点间的距离，记在交通线路的旁边。 交通图绘制好后，即可在其上面进行物资调运，找出初始调运方案(初始基可行解)。 即第三步，作物资调运流向图。 我们用箭头“→”表示物资调运的方向即称 流向，并规定：流向“→”必须画在沿着线路前 进的右侧。把运送物资的数量记在流向 “→” 的旁边并加括号（ ），以区别于两点之间的距 B (c) A A B (b) B A (a) 图 3-1
离数。另一方面,为了保持图面的整洁,流向量最好不要通过收,发点以及交叉路口 如图3-1中,(a),(b)是正确的 图3-2中,AE是正确的。由此可知,当一个交通图成圈时,若运输方向沿逆时针方 向,则需将流向“→”画在圈外,称外圈流向;若运输方向是沿顺时针方向,则将流向 “→”画在圈内,称为内圈流向。若在图中每个发点吨数全部运完,每个收点所需吨数 均已满足,则称此图为流向图。 B C 在物资运输中,把某种物资从各发点调到各收点的 调运方案是很多的,但我们的目的是找出吨一公里数是 最小的调运方案。这就要注意在调运中不要发生对物流 A 9D运输和迂回运输,因此,我们在制定流向图时,就要避 免它的出现。 F (1)对流:所谓对流就是在一段线路上有同一种物 图3-2 资往返运输(同 (10) A2 段线路上,两各方向都有流向),如图3-3。 203(2010 将某种物资10吨从A4运往B2,同时又有同样 的物资10 (10) 图3-3 BI A1 吨同时从 (1030 (0→运往B,于是在A4之间就出现了对流现象 如果把流向图改成图3-4,即将A1的10吨运往B, 图3-4 而将A的10吨运往B2,就避免了A142的对流, 从而可以节约运输量2×10×30=600(吨公里)。 (2)迂回:当交通图成圈时,如果流向图中内圈流向的总长(简称内圈长)或外圈 流向的总长(简称外圈长)超过整个圈长的一半就称为迂回运输。例如某物资流向图如 图3-5所示。 显然,它是一个迂回运输流向图,它 的内圈长6大于整个圈长的一半5。如果 把它改成图3-6,就避免了迂回现象,可 5B 节约运输量5×6-5×4=10(吨公里) 理论上可以证明,一个物资调运方案 图3-5 图3 中,如果没有对流和迂回运输,则该方案 就是最优调运方案。即运输量最小的方案。 从以上讨论可以看到,图上作业法的实质就是在一张交通图上寻找没有对流和迂回 的最优流向图。 为了贯彻以上原则,则须采用逐步逼近法,即我们可以先设法作一个流向图,然后
离数。另一方面，为了保持图面的整洁，流向量最好不要通过收，发点以及交叉路口， 如图 3-1 中，(a)，(b)是正确的。 图 3-2 中，AE 是正确的。由此可知，当一个交通图成圈时，若运输方向沿逆时针方 向，则需将流向“→”画在圈外，称外圈流向；若运输方向是沿顺时针方向，则将流向 “→”画在圈内，称为内圈流向。若在图中每个发点吨数全部运完，每个收点所需吨数 均已满足，则称此图为流向图。 在物资运输中，把某种物资从各发点调到各收点的 调运方案是很多的，但我们的目的是找出吨—公里数是 最小的调运方案。这就要注意在调运中不要发生对物流 运输和迂回运输，因此，我们在制定流向图时，就要避 免它的出现。 （1）对流：所谓对流就是在一段线路上有同一种物 资往返运输（同一 段线路上，两各方向都有流向），如图 3-3。 图 3-2 D F C A B 将某种物资 10 吨从 A1运往 B2 ，同时又有同样 的物资 10 吨同时从 A2 运往 B1 ，于是在 之间就出现了对流现象. 如果把流向图改成图 3-4，即将 的 10 吨运往 A A1 2 A1 B1， 而将 A2 的 10 吨运往 B2 ，就避免了 的对流， 从而可以节约运输量 2×10×30=600(吨公里)。 A A1 20 30 20 B （10） A2 1 10 10 A1 B2 图 3-3 （10） 10 10 A1 A2 10 20 20 （10） 30 10 B1 10 10 B2 （10） 图 3-4 2 （2）迂回：当交通图成圈时，如果流向图中内圈流向的总长（简称内圈长）或外圈 流向的总长（简称外圈长）超过整个圈长的一半就称为迂回运输。例如某物资流向图如 图 3-5 所示。 （5） 6 6 4 A 5 5 B 显然，它是一个迂回运输流向图，它 的内圈长 6 大于整个圈长的一半 5。如果 把它改成图 3-6，就避免了迂回现象，可 节约运输量 5×6-5×4=10（吨公里） 理论上可以证明，一个物资调运方案 中，如果没有对流和迂回运输，则该方案 就是最优调运方案。即运输量最小的方案。 图 3-5 4 （5） A 5 5 B 图 3-6 从以上讨论可以看到，图上作业法的实质就是在一张交通图上寻找没有对流和迂回 的最优流向图。 为了贯彻以上原则，则须采用逐步逼近法，即我们可以先设法作一个流向图，然后
来检査它是不是最优的,如果是的话,问题就解决了;如果不是,就把这个流向图稍微 变化一下,这样的变化称为调整。调整后的新流向图所花费的吨公里比原流向图的要少 些。然后再检査新流向图是不是最优的,如果仍旧不是,就再进行调整,一直到找到 最优流向图为止。 物资运输的交通图总共分为两类:一类是不成圈的交通图,另一类是成圈交通图, 以下分别举例说明他们的最优流向图的求法。 例3.1求表3-1中,水泥的最优调运方案,其交通图如图3-7。 此例道路不成圈,只要按口诀 调运水泥的物资平衡表 表3-1 “抓各端,各端供需归邻站”办事,发。收点BBBB发量(吨) 就能找到最优方案。为此,可先在 图3-7各个支线上进行平衡,然后 再在各支线间进行平衡 首先看A→A→B1支线,A与 A4A A2共70吨水泥需要调出。显然在调 A 出时必须先经B,而B又需调入80收量(吨)80103050170 吨,所以最好将A1 此70吨全部给(50 B。根据前述, 058B B4 在图上可在沿 80 120 着线路前进的 A371 方向的右侧箭 头来表示流向 并将按此流向 图3-7 调运的数量写在箭头的旁边,并把同方向的两个流向合并成一个 再看B2→A3→B支线,A需调出30吨,B2需调入10吨,本着先平衡支线的原则, 从A调给B210吨余下20吨须调给其他的地方。由于自A3调出时必经过B1,而B还需 10吨,因此从A调给A10吨,余下10吨调给另外地方。 A 1 最后看B4 A2 A4→B3→B1 B (20)4 B4支线。为了避免 (50) 对流,A调出 的10吨只能给 B3,而B3还需 20吨,则由A4 图3-8
来检查它是不是最优的，如果是的话，问题就解决了;如果不是，就把这个流向图稍微 变化一下，这样的变化称为调整。调整后的新流向图所花费的吨公里比原流向图的要少 一些。然后再检查新流向图是不是最优的，如果仍旧不是，就再进行调整，一直到找到 最优流向图为止。 物资运输的交通图总共分为两类：一类是不成圈的交通图，另一类是成圈交通图， 以下分别举例说明他们的最优流向图的求法。 例 3.1 求表 3-1 中，水泥的最优调运方案，其交通图如图 3-7。 此例道路不成圈，只要按口诀 “抓各端，各端供需归邻站”办事， 就能找到最优方案。为此，可先在 图 3-7 各个支线上进行平衡，然后 再在各支线间进行平衡。 首先看 A1→A2 →B1支线， 与 共 70 吨水泥需要调出。显然在调 出时必须先经 A1 A2 B1，而 B1又需调入 80 吨，所以最好将 此 70 吨全部给 B1。根据前述， 在图上可在沿 着线路前进的 方向的右侧箭 头来表示流向， 并将按此流向 调运的数量写在箭头的旁边，并把同方向的两个流向合并成一个。 调运水泥的物资平衡表 表 3-1 B1 B2 B3 B4 发量（吨） A1 50 A2 20 A3 30 A4 70 收量（吨） 80 10 30 50 170 发 点 收 点 A1 50 66 A2 20 45 120 A4 150 B4 50 70 B3 30 B1 80 58 71 再看 B →A →B 支线， 需调出 30 吨，B 需调入 10 吨，本着先平衡支线的原则， 从 调给 10 吨余下 20 吨须调给其他的地方。由于自 调出时必经过 ，而 还需 10 吨，因此从 调给 A110 吨，余下 10 吨调给另外地方。 2 3 A3 B2 A3 1 A3 2 A3 B1 B1 85 A3 B2 10 30 图 3-7 最后看 B4 → A4 →B3 →B1 支线。为了避免 对流， A3 调出 的 10 吨只能给 B3 ，而 B3 还需 20 吨，则由 A4 A1 50 A2 (50) 20 B1 A4 B4 80 B3 (20) (70) 30 50 70 (50) (10) A3 (20) 30 (10) B2 10 图 3-8
供应,A余下的50吨全部给B4。这样最后得到的流向图(如图3-8)。 图3-8所示的流向图既无对流,又无迂回,所以它是最优流向图,对应的方案是最 好方案。相应于该流向图的调运方案显然不是唯一的,现在给出两个调运方案,如表3-2 所示。 表3-2 方收 B B B B 发量 方案1方案2方案1方案2方案1方案2方案1方案2(吨) A 50 5 A A3 20 10 10 10 30 A 4 20 20 收量(吨) 80 10 30 50 170 对于第一个方案运行的总吨公里是 f(x)=50×(66+52)+20×52+10×71+10×85+10×(71+45)+20×120+50×150 =19560(吨公里 对于第二个方案运行的总吨公里是 f(x)=45×(66+52)+15×52+20×71+10×85+5×(66+52+45)+5×(52+45)+20×120+50×150 =19560吨公里 33表上作业法 3.1.1问题的提出 在前节中所介绍的图上作业法,可以很简便地求得吨公里数最小的调运方案。可是 吨公里数有时还不能充分地反映运输耗费的大小程度。例如,从10个不同的产地各运 10吨物资到10公里外的10个销地所耗费的运输力量与从一个产地运10吨物资到100 公里以外的一个销地所耗费的运输力量相比较,虽然它们的吨-公里数都是相等的,两 者都是100吨-公里。可是在不考虑道路好坏的情况下,只是装卸工作量,前者就要比 后者大10倍。因此,从图上作业法所得的吨-公里数最小的调运方案,有时要想利用图 上作业法解决是有一定限制的。故在这节中要介绍的表上作业法就是为了解决寻求费用 最省的这个问题。 3.3.2表上作业法 表上作业法就是要把解决的(T,P)问题放在表格上来进行。其大致步骤为: 首先列出被调物资的单位运价表和平衡表,然后判定初始调运方案,即求出初始基
供应， A4 余下的 50 吨全部给 B4 。这样最后得到的流向图（如图 3-8）。 (x) ×52 45 1956 = × 0 图 3-8 所示的流向图既无对流，又无迂回，所以它是最优流向图，对应的方案是最 好方案。相应于该流向图的调运方案显然不是唯一的，现在给出两个调运方案，如表 3-2 所示。 表 3-2 B1 B2 B3 B4 方案 1 方案 2 方案 1 方案 2 方案 1 方案 2 方案 1 方案 2 发量 （吨） A1 50 45 5 50 A2 20 15 5 20 A3 10 20 10 10 10 30 A4 20 20 50 50 70 收量（吨） 80 10 30 50 170 点 发 案 方 收 点 对于第一个方案运行的总吨公里是 50 (66 52) 20 10 71 10 85 10 (71 45) 20 120 50 150 19560( f = × + + + × + × + × + + × + × = 吨公里) 对于第二个方案运行的总吨公里是 ( ) (66 52) 15 52 2 71 10 85 5 (66 52 45) 5 (52 45) 20 120 50 150 0( ) f x + + × + × + × + × + + + × + + × + × = 吨公里 3.3 表上作业法 3.1.1 问题的提出 在前节中所介绍的图上作业法，可以很简便地求得吨公里数最小的调运方案。可是 吨公里数有时还不能充分地反映运输耗费的大小程度。例如，从 10 个不同的产地各运 10 吨物资到 10 公里外的 10 个销地所耗费的运输力量与从一个产地运 10 吨物资到 100 公里以外的一个销地所耗费的运输力量相比较，虽然它们的吨-公里数都是相等的，两 者都是 100 吨-公里。可是在不考虑道路好坏的情况下，只是装卸工作量，前者就要比 后者大 10 倍。因此，从图上作业法所得的吨-公里数最小的调运方案，有时要想利用图 上作业法解决是有一定限制的。故在这节中要介绍的表上作业法就是为了解决寻求费用 最省的这个问题。 3.3.2 表上作业法 表上作业法就是要把解决的（T，P）问题放在表格上来进行。其大致步骤为： 首先列出被调物资的单位运价表和平衡表，然后判定初始调运方案，即求出初始基