第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）问题放在表格上来进行。其大致步骤为： 首先列出被调物资的单位运价表和平衡表，然后判定初始调运方案，即求出初始基
可行解。其次判别所得解是不是最优解(即运费最少的调运方案)。如果所得解不优, 则进行调整,得出新的基可行解(新的调运方案),再进行判定新基可行解,直至得到 最优解为止。 1.初始调运方案的编制(初始基可行解的方法) 初始方案编制的好坏将直接影响着求优解进度的快慢,一般来说,初始方案编制的 较好,该方案的运费离最小运费的差距就较小,相对来说调整的次数也少。如果初始方 案编的不好,调整的次数也就越多。目前采用的初始编制方案很多,但其中较好的方法 就是最小元素法,故在这里我们以例来介绍该方法。 最小元素法的基本思想是按运价最小的尽可能地优先供应优先满足,为了便于理解 以实际问题来介绍其具体做法。 例3.4己知某物资的平衡表和运价表如表3-3和表3-4所示,求该(7,P)问题 的最优调运方案。 平衡表 表3-3 运价表 表3-4 点BBBB发量(吨) 发收点BBBB A l 1056 A2 76 A x33x34 A 收量(吨)15203035 100 为了叙述方便起见,我们在表3-5中把x排列在第行第j列交又的方格内,用(i 代表这一个方格,一个方格对应一个变量。将(,P)的一个基可行解中基变量所取的 值填入对应的方格里,非基变量对应的方格让空着(因为非基变量所取的值为0),由(T, P的性质1知,m行n列的方格内恰有(m+n-1)个格子要填上数字,其余m-(m+n-1) 方格要空着,现我们采用最小元法编制例3.4的初始调运方案见表3-5(每一个方格可右 上角数字为单位运价) 初始调运方案表 表3-5 发占收 B B B B 发量(吨) 25 2 收量(吨) 20 30 35 100
可行解。其次判别所得解是不是最优解（即运费最少的调运方案）。如果所得解不优， 则进行调整，得出新的基可行解（新的调运方案），再进行判定新基可行解，直至得到 最优解为止。 1．初始调运方案的编制（初始基可行解的方法） 初始方案编制的好坏将直接影响着求优解进度的快慢，一般来说，初始方案编制的 较好，该方案的运费离最小运费的差距就较小，相对来说调整的次数也少。如果初始方 案编的不好，调整的次数也就越多。目前采用的初始编制方案很多，但其中较好的方法 就是最小元素法，故在这里我们以例来介绍该方法。 最小元素法的基本思想是按运价最小的尽可能地优先供应优先满足，为了便于理解 以实际问题来介绍其具体做法。 例 3.4 已知某物资的平衡表和运价表如表 3-3 和表 3-4 所示，求该（T，P）问题 的最优调运方案。 为了叙述方便起见，我们在表3-5中把 ij x 排列在第i 行第 j 列交叉的方格内，用(i j , ) 代表这一个方格，一个方格对应一个变量。将（T，P）的一个基可行解中基变量所取的 值填入对应的方格里，非基变量对应的方格让空着（因为非基变量所取的值为 O），由（T， P）的性质 1 知，m 行n 列的方格内恰有(m n + -1) 个格子要填上数字，其余 方格要空着，现我们采用最小元法编制例 3.4 的初始调运方案见表 3-5(每一个方格可右 上角数字为单位运价) 。 mn − + ( ) m n -1 平 衡 表 表 3-3 B1 B2 B3 B4 发量（吨） A1 x11 x12 x13 x14 25 A2 x21 x22 x23 x24 25 A3 x31 x32 x33 x34 50 收量（吨） 15 20 30 35 100 运 价 表 表 3-4 B1 B2 B3 B4 A1 10 5 6 7 A2 8 2 7 6 A3 9 3 4 8 初始调运方案表 表 3-5 B1 B2 B3 B4 发量（吨） 10 5 6 7 A1 25 8 2 7 6 A2 25 9 3 4 8 A3 50 收量（吨） 15 20 30 35 100 15 20 30 25 5 5 发 点 收点 发 点 发 点 收点 收点
1.1表3-5中的数字的填法为 在表中找到最小的运价(本例为(2,2)格)在本方格中填上尽可能的数字,(本例为 m2520)=20),将该数圈入圆圈内填到格上,(本例在(,2)格上填②,如果填数 格所对应的行发行量运完,则用虚线划掉该行,若对应的列收量得到满足.则划掉该例 (本例划掉第2例)。 1.2在划去一行或一列后,在余下的方格中重复上述步骤,直到所有的行列被划 去为止,得出表3-5。 此时只能划去行(或列,而在所在列(或行)中其余空格中挑运价最小的方格填入O, 然后再划去这一列(或行) 例:表3-6中编制的初始调运方案 表3-6 发 收 点 B B B B发量(吨) 9 6 20 收量(吨) 5 8 4 20 在(2.4)格上填 在表3-8中,填了数字的格恰好为m+n1个(包括填(O的格子)。空格为 m-(m+n-1)个 2.最优解的判定方法 给定一个初始解之后,就需要判定这个解是不是最优的,即运费是不是最小的。现 我们仍以例3.4为例进行说明。由线性规划知,最优解的判定准则是:如果所有检验数 都非负,则该解对应的调运方案就是最优调运方案。反之,如果检验数中有负数,则这 个解对应的方案就不优,需调整。所以,要判定方案的优劣,必须求出检验数.而利用 表上作业法求检验数的方法,一般采用闭回路法或位势法。 2.1闭回路法 闭回路法是首先在初始调运方案表上找出适当的闭回路,然后把闭回路上每个转角 上的数字通过代数运算得出检验数,最后才利用检验数来判定方案的优、劣,所以,我 们首先了解闭回路的作法,其次了解检验数的求法,最后给出判定及调整法。 (1)闭回路的作法
1.1 表 3-5 中的数字的填法为: 在表中找到最小的运价(本例为(2，2)格)在本方格中填上尽可能的数字，(本例为 )，将该数圈入圆圈内填到格上，(本例在(2，2)格上填 ，如果填数 格所对应的行发行量运完，则用虚线划掉该行，若对应的列收量得到满足.则划掉该例 (本例划掉第 2 例)。 min(25,20) 20 = 20 1.2 在划去一行或一列后，在余下的方格中重复上述步骤，直到所有的行列被划 去为止，得出表 3-5 。 [注]:当某方格填入数字后，如果所对应的行发量无余量且列收量同时得到满足， 此时只能划去行(或列)，而在所在列(或行)中其余空格中挑运价最小的方格填入 ， 然后再划去这一列(或行) 0 例：表 3-6 中编制的初始调运方案 表 3-6 B1 B2 B3 B4 发量（吨） 5 3 10 7 A1 9 1 6 9 6 A2 4 20 10 5 7 A3 7 收量（吨） 3 5 8 4 20 3 1 0 7 发 点 收点 5 4 在(2.4)格上填 。 在表 3-8 中，填了数字的格恰好为 m n + -1 个(包括填 的格子)。空格为 mn − + ( ) m n -1 个。 0 2.最优解的判定方法 给定一个初始解之后，就需要判定这个解是不是最优的，即运费是不是最小的。现 我们仍以例 3.4 为例进行说明。由线性规划知，最优解的判定准则是:如果所有检验数 都非负，则该解对应的调运方案就是最优调运方案。反之，如果检验数中有负数，则这 个解对应的方案就不优，需调整。所以，要判定方案的优劣，必须求出检验数.而利用 表上作业法求检验数的方法，一般采用闭回路法或位势法。 2.1 闭回路法 闭回路法是首先在初始调运方案表上找出适当的闭回路，然后把闭回路上每个转角 上的数字通过代数运算得出检验数，最后才利用检验数来判定方案的优﹑劣，所以，我 们首先了解闭回路的作法，其次了解检验数的求法，最后给出判定及调整法。 （1）闭回路的作法
从某一空格出发,沿水平或垂直方向前进,当碰到另一个适当的有数字格后,转90 度弯继续前进,依次进行下去,一直回到原出发空格为止,我们称按以上方法做出的路 径为原出发空格的闭回路 例表3-5中的各空格的闭回路分别是: a(1,1)格的闭回路为:x Qd2,1)格的闭回路为:x< b(,2格的闭回路为:@2,3)格的闭回路为:9 c(1,3)格的闭回路为:x Qf(3,2)格的闭回路为Qo (2)检验数求法 检验数的求法是:从空格开始出发,沿闭回路前进,凡奇数次转角格相应的运价前 加负号,空格和偶数次转角空格相应的运价前加正号,然后求其代数和,将所得的和作 为空格(,八的检验数,记为石 例表5中(1.1)格的检验数,41=10-9+8-7=2,相应地A2=5-2+6-7=2,A13=3, 2.2位势法 (1)作位势表 位势表 表3-7 第一步:做出调运方案表中有数字格发点点 BBBB li 所对应的运价表 AL 第二步:在做出表的下方和右方加行 A 2 和一列,并且在所加行、列构成的每一空 A3 格上填上一个数,在各行上填的数称为行 位势,记为u。在各列上填的数称为列位
从某一空格出发，沿水平或垂直方向前进，当碰到另一个适当的有数字格后，转 90 度弯继续前进，依次进行下去，一直回到原出发空格为止，我们称按以上方法做出的路 径为原出发空格的闭回路。 例表 3-5 中的各空格的闭回路分别是： a (1，1)格的闭回路为：x d (2，1)格的闭回路为： 15 30 5 5 25 20 5 x 15 30 5 b (1，2)格的闭回路为： e(2，3)格的闭回路为：x 5 30 5 x 20 5 25 c(1，3)格的闭回路为： x f (3，2)格的闭回路为： 30 5 5 25 20 5 x 30 5 (2)检验数求法 检验数的求法是：从空格开始出发，沿闭回路前进，凡奇数次转角格相应的运价前 加负号，空格和偶数次转角空格相应的运价前加正号，然后求其代数和，将所得的和作 为空格(i j , ) 的检验数，记为λij 。 例表 5 中（1.1）格的检验数，11 λ =10 -9 +8- 7 = 2，相应地 12 λ = 5- 2 + = 6 - 7 2，13 λ = 3 ， 21 λ =1， 23 λ = 5， 32 λ = −1， 2.2 位势法 位势表 表 3-7 B1 B2 B3 B4 ui A1 7 3 A2 2 6 2 A3 9 4 8 4 vj 5 0 0 4 发 点 收点 (1)作位势表 第一步：做出调运方案表中有数字格 所对应的运价表 第二步：在做出表的下方和右方加行 和一列，并且在所加行﹑列构成的每一空 格上填上一个数，在各行上填的数称为行 位势，记为ui 。在各列上填的数称为列位
势,记为v,新填数要求满足:1+v=C"(数字格(i,八对应的运价)。 填满数字的位势表表3-8例表3-5对应的位势表如表3-7所 示,表的填法是:首先在表3-9的的第 发 收点BBBB AAA (8)(3)(3) 个列位势v1=4,满足a1+V1=C=7的 (7)2(2) 63行令41=3,则在第4列(B4列)下方填 9(4)48 要求,其次填a2=2, 依次 下去,得到表3-7,并称表3-7为位势表 (2)求检验数 第一步,在位势表的空格中填入(u+ν,), 检验数表表3-9 如表3-8(填满数字的位势表) 发收点BBBB 第二步,计算=C"-(4+") 其中,C"为调运方案中空格对应的运价, 或利用运价表,表3-4中数减去表3-8中相对 AAA 应的数(u+v,)。得表3-9(检验数表)。 表3-11中的检验数和我们利用闭回路法求出来的完全一样,这样我们就可根据情 况来选择其中一种方法来求检验数。另一方面表39中检验数2=-1<0,所以初始方 案不是最优方案,还需要进行调整。 2.3调运方案的调整方法 现我们仍以上例说明其调整方法 第一步,据需调整的调运方案表,画出<0所对应空格的闭回路,该例2=-1<0 画出(3,2)格的闭回路Q0 第二步,从空格(3,2)出发 调整后的调运方案 表3-10 沿闭回路前进,在回路所有奇数次 发 收点BBBB发量(吨) 转角格中选出最小的运量(调整量) A1 本例(3,4)格对应的运量是5 第三步,将闭回路上凡奇数转 A 角格对应的运量减去调整量(本例 A3 为5),其余转角格对应的运量加调收量(吨)15203035 00 整量,将得到的新的调运方案,本 例如表3-10所示。 在重复三,利用位势法求得调整后的调运方案的检验数如表3-13所示
势，记为vj ，新填数要求满足： i j u v Cij + = ′ (数字格(i j , ) 1 u 3 对应的运价)。 = i u + ( )j v i u + λ 例表 3-5 对应的位势表如表 3-7 所 示，表的填法是：首先在表 3-9 的的第一 行令 ，则在第 4 列（ B4 列）下方填 一个列位势 1 v = 4，满足u v 的 要求，其次填 1 1 14 + = C′ = 7 2 u = 2， ，……依次 下去，得到表 3-7，并称表 3-7 为位势表。 2 v = 0 (2)求检验数 第一步，在位势表的空格中填入( v )， 如表 3-8(填满数字的位势表) j 第二步，计算λij C u ij i = ′′ − + 其中， 为调运方案中空格对应的运价， 或利用运价表，表 3-4 中数减去表 3-8 中相对 应的数( ) 。得表 3-9(检验数表)。 Cij′′ vj 表 3-11 中的检验数和我们利用闭回路法求出来的完全一样，这样我们就可根据情 况来选择其中一种方法来求检验数。另一方面表 3-9 中检验数 32 λ = − <1 0，所以初始方 案不是最优方案，还需要进行调整。 2.3 调运方案的调整方法 现我们仍以上例说明其调整方法。 第一步，据需调整的调运方案表，画出 0 ij < 所对应空格的闭回路，该例 32 λ = −1< 0， 画出(3，2)格的闭回路 第二步，从空格（3，2）出发 沿闭回路前进，在回路所有奇数次 转角格中选出最小的运量（调整量） 本例（3，4）格对应的运量是 5。 第三步，将闭回路上凡奇数转 角格对应的运量减去调整量（本例 为 5），其余转角格对应的运量加调 整量，将得到的新的调运方案，本 例如表 3-10 所示。 填满数字的位势表 表 3-8 B1 B2 B3 B4 ui A1 (8) (3) (3) 7 3 A2 (7) 2 (2) 6 2 A3 9 (4) 4 8 4 vj 5 0 0 4 检验数表 表 3-9 B1 B2 B3 B4 A1 2 2 3 A2 1 5 A3 -1 调整后的调运方案 表 3-10 B1 B2 B3 B4 发量（吨） A1 25 A2 25 A3 50 收量（吨） 15 20 30 35 100 25 15 10 15 5 30 发 点 收点 20 5 x 30 5 发 点 收点 发 点 收点 在重复三，利用位势法求得调整后的调运方案的检验数如表 3-13 所示
从检验数表3-13看出,所有的检验数都 检验数表表3-11 非负,所以,我们调整后的调运方案是一个优 方案它所对应的最优解为 发收点BBBB x1=x12=x13=x21=x23=x3 AL x1=25 x,=10 A2 x31=15x2 5 A3 最小运费为: minf=2×15+7×25+6×10+9×15+3×5+4×30=535 3.4平衡的运输问题及其解法 上面讨论的运输问题都是产销平衡问题,但是实际问题中,产销往往是不平衡的, 时为了仍能应用表上作业法进行计算,就需要将产销不平衡问题化为产销平衡问题。 和前面一样,用a表示产地A(=12,…m)的产量,b表示销地B(=12…;m)的销 量,x表示由A调运给B的物资数量。于是当产大于销时,即当 时,运输问题的数字模型可写为: mIn s= ∑2 Ci ri t|>xn≤a x=b (=1,2,…,n) x≥0(=1,2,…,mj=1,2,…,mn) 其中cn表示从A到B的单价物资的运价。 由于总的产量大于销量,就要考虑将多余的物资就地存储起来。设xn1是产地A的 存储量,于是有 Xu txi x (i=1,2, 或者移项得 x (i=1,2,…,m) 所以有
从检验数表 3-13 看出，所有的检验数都 非负，所以，我们调整后的调运方案是一个优 方案它所对应的最优解为： 11 12 13 21 23 34 x x = = x = x = x = x = 0 14 22 24 x x = = 25 =15 x =10 = ) ) 检验数表 表 3-11 B1 B2 B3 B4 A1 1 2 2 A2 0 4 A3 1 发 点 收点 31 32 33 x x = = 15 = 5 x 30 最小运费为： min f = 2×15 + ×7 25+ 6×10 + 9×15+ 3×5+ ×4 30 = 535 3.4 平衡的运输问题及其解法 上面讨论的运输问题都是产销平衡问题，但是实际问题中，产销往往是不平衡的， 这时为了仍能应用表上作业法进行计算，就需要将产销不平衡问题化为产销平衡问题。 和前面一样，用ai 表示产地 A i i ( 1 = ,2,…,m 的产量，bj 表示销地 ( 1, 2, , Bj j n = … 的销 量， ij x 表示由 Ai 调运给 Bj 的物资数量。于是当产大于销时，即当 1 1 m n i j i j a b = = ∑ >∑ 时，运输问题的数字模型可写为： 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 s c x s t x a i m x b j n x i m j = = = = = ⋅ ≤ = = = ≥ = = ∑∑ ∑ ∑ " " " " n (Ⅰ) 其中cij 表示从 Ai 到 Bj 的单价物资的运价。 由于总的产量大于销量，就要考虑将多余的物资就地存储起来。设 i n, 1 x + 是产地 的 存储量，于是有 Ai 1 , 1 1 1 ( 1, 2, , n n ij i n ij i j j x x x a i ) + + = = ∑ ∑ + = = = " m ) 或者移项得 , 1 1 ( 1, 2, , n i n i ij j x a x i + = = −∑ = " m 所以有