《运输问题的特殊解法.ppt》由会员分享，可在线阅读，更多相关《运输问题的特殊解法.ppt（54页珍藏版）》请在金锄头文库上搜索。
1、表上作业法表上作业法图上作业法图上作业法第三章第三章运输问题的特殊解法运输问题的特殊解法(TransportationProblem)第一节第一节 运输问题的表上作业法运输问题的表上作业法一、运输问题的数学模型及其特点一、运输问题的数学模型及其特点 设设某某种种物物品品有有m个个产产地地A1 , A2 , , Am ，各各产产地地的的产产量量分分别别是是a1 , a2 , , am；有有n个个销销地地Bl , B2 , , Bn , ,各各销销地地的的销销量量分分别别为为bl , b2 , , bn。假假定定从从产产地地Ai (i1,2,m) 向向销销地地Bj ( j1,2,n) 运运输输单单
2、位位物物品品的运价是的运价是cij，问怎样调运这些物品能使总运费最小问怎样调运这些物品能使总运费最小? ? 这是由多个产地供应多个销地的单品种物资运这是由多个产地供应多个销地的单品种物资运输问题。为直观清楚起见，可将数据汇总于产销平输问题。为直观清楚起见，可将数据汇总于产销平衡表和单位运价表中：衡表和单位运价表中：销地销地产地产地12n产量产量销地销地产地产地12n平平1a11c11c12c1n运运衡衡2a22c21c22c2n价价表表.表表mammcm1cm2cmn销量销量b1b2bn（1）产销平衡时）产销平衡时矩矩阵阵形形式式（2）产大于销时）产大于销时（3）产小于销时）产小于销时特征特征
3、u 运输问题的基本可行解中应包括运输问题的基本可行解中应包括 m+n-1个基变量个基变量u 平衡运输问题必有可行解，也必有最优解平衡运输问题必有可行解，也必有最优解二、表上作业法的思路和步骤二、表上作业法的思路和步骤步骤：步骤：1 1）确定初始调运方案）确定初始调运方案 2 2）解的最优性判断）解的最优性判断 3 3）调整方案）调整方案 4 4）重复）重复2 2）3 3）步，直到找到最优方案）步，直到找到最优方案找到初始基可行解最优性判断调整找到新的基可行解重复2、3步直到找到最优解例例1 1 某部门有某部门有3 3个生产同类产品的工厂（产地），个生产同类产品的工厂（产地），生产的产品由生产的
4、产品由4 4个销售点出售，各工厂的有关资料个销售点出售，各工厂的有关资料如下表，问应怎样调运才使总运费最少如下表，问应怎样调运才使总运费最少? ?收点收点发点发点B1B2B3B4产量产量B1B2B3B4A17311312A241928A3974105销量销量365620（一）确定初始调运方案（一）确定初始调运方案1、最小元素法、最小元素法 思路：就近供应，优先安排运价最小的收发点之间的物资调运量，然后次小，直到给出初始基可行解解题步骤：解题步骤：（1 1）在运价表中找到最小运价）在运价表中找到最小运价c1k（2 2）将将的的Al 产品给产品给Bk 若若al bk，则将则将al 改写为改写为al
5、 -bk，划掉划掉bk，同时同时将运价表中将运价表中k 列的运价划掉列的运价划掉 若若al bk，则将则将bk改写为改写为bk-al，划掉划掉al，同时同时将运价表中将运价表中l 行的运价划掉行的运价划掉（3 3）如此重复）如此重复(1)(1)、(2)(2)，直到分配完毕，直到分配完毕收点收点发点发点B1B2B3B4产量产量B1B2B3B4A17311312A241928A3974105销量销量365620对应的目标函数值为：对应的目标函数值为：z34123十十13十十2146十十5392(元元)31463331343 2、西北角法、西北角法 思路：该法优先满足运输表中西北角上空格的供销需求
6、收点收点发点发点B1B2B3B4产量产量B1B2B3B4A17311312A241928A3974105销量销量365620342236对应的目标函数值为：对应的目标函数值为：z33114十十92十十22103十十56135(元元)3、伏格尔法、伏格尔法 思想：最小元素法为了节省一处的费用，有时可能造成在其他处要多花几倍的运费。伏格尔法考虑到，一地的产品假如不能按最小运费就近供应，就考虑次小运费，因此就会有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而，对差额最大处，就应当采用最小运费调运解题步骤：解题步骤：（1）计计算算运运输输表表中中每每一一行行和和每每一一列列的的次次小
7、小单单位位运运价价和和最最小小运价之间的差值运价之间的差值（2）从从行行或或列列差差中中选选择择最最大大者者，选选择择它它所所在在行行或或列列中中的的最最小小元元素素clk，将将Al的的产产品品优优先先供供应应Bk，同同时时将将运运价价表表中中已已满满足的行或列划掉。足的行或列划掉。（3）如此重复如此重复(1)(1)、(2)(2)，直到分配完毕，直到分配完毕收点收点发点发点B1B2B3B4产量产量B1B2B3B4行差行差A17311312A241928A3974105销量销量3656205130116125243333125对应的目标函数值为：对应的目标函数值为：z3235十十11十十8346
8、十十5385(元元)注：注：u 伏格尔法除确定供求关系的原则与最小元素法不同外，伏格尔法除确定供求关系的原则与最小元素法不同外， 其余步骤与最小元素法相同。其余步骤与最小元素法相同。u 与最优解的接近程度：伏格尔法、最小元素法、西北角法与最优解的接近程度：伏格尔法、最小元素法、西北角法2（二）解的最优性检验（二）解的最优性检验 求出各非基变量的检验数，判别是否均不小于求出各非基变量的检验数，判别是否均不小于0 0：如果是，则得到最优解，停止计算；否则转入下：如果是，则得到最优解，停止计算；否则转入下一步一步 注：注：因为目标函数要求最小化，所以因为目标函数要求最小化，所以ij 0 表示运费增加
9、。表示运费增加。 表格中有调运量的地方为基变量，空格处为非基变表格中有调运量的地方为基变量，空格处为非基变量。基变量的检验数量。基变量的检验数ij0，需计算非基变量的检验数需计算非基变量的检验数是否是否不小于不小于0 0。 1 1、闭回路法、闭回路法 闭闭回回路路 以某一空格为起点，用水平线或垂直线向前画，碰到某一个数字格转90度后，继续前进，直到回到起始空格为止B1B2B3B4产量产量A1437A2314A3639销量销量365620空格处检验数的计算公式：空格处检验数的计算公式： 偶拐角点对应运价之和偶拐角点对应运价之和-奇拐角点对应运价之和奇拐角点对应运价之和 利用最小元素法形成的初始调
10、运方案进行说明：利用最小元素法形成的初始调运方案进行说明：B1B2B3B4产量产量B1B2B3B4A1437311312A23141928A363974105销量销量3656202 2、位势法、位势法 提出：闭回路法需要多次作闭回路，多次对照运价表，多次计算，繁琐复杂，特别是收发点多时尤为不便，故提出位势法在运价表上直接操作 解题步骤：解题步骤：（1）编制位势表编制位势表在在运运输输问问题题的的单单价价表表中中的的基基变变量量处处画画圈圈，同同时时在在表中增加一行（列位势）和一列（行位势）表中增加一行（列位势）和一列（行位势）（2）填写位势数填写位势数任任选选第第一一个个位位势势数数填填入入表
11、表中中，其其余余按按ul+vk=clk填填写写(基变量的基变量的ij 0)（3）计算检验数计算检验数对运价表没画圈的对运价表没画圈的cij按按ij=cij(ui+vj)计算检验数计算检验数B1B2B3B4A1311312u1A21928u2A374105u3v1v2v3v4运价表运价表B1B2B3B4UiA1311312A21928A374105Vj位势表位势表2-13012-711（三）调整方案（三）调整方案闭回路法闭回路法实质：单纯形法的换基迭代调整步骤调整步骤（1 1）作第一个出现负检验数）作第一个出现负检验数ij的闭回路；的闭回路；（2 2）求）求调整量调整量。= =奇拐角点处的最小运
12、量奇拐角点处的最小运量 （3 3）调整。）调整。 奇拐角点处的各运量均减去奇拐角点处的各运量均减去；偶奇拐角点偶奇拐角点处的各运量均加上处的各运量均加上；不在闭回路上的格子运量不变不在闭回路上的格子运量不变的选取原则：的选取原则：1 1）奇拐角点处的某一个运量减少为）奇拐角点处的某一个运量减少为0 02 2）每一个奇拐角点处的运量不能减少为负数）每一个奇拐角点处的运量不能减少为负数B1B2B3B4产量产量A1437A2314A3639销量销量3656-1+1-1-1+1+1B1B2B3B4产量产量A1527A2314A3549销量销量3656检验数：检验数：-1-1+1+1Vj51047A38
13、191A2123113A1UiB4B3B2B1位势表位势表1231137-20B1B2B3B4产量产量A1527A2314A3639销量销量3656123115740Vj51047A38191A2123113A1UiB4B3B2B1位势表位势表检验数：检验数：-2-2+2+2所有所有ij0，得到最优解得到最优解z3235十11十8346十5385(元)10393520Vj51047A38191A2123113A1UiB4B3B2B1B1B2B3B4产量产量A1257A2134A3639销量销量3656练练习习：某某部部门门有有3个个生生产产同同类类产产品品的的工工厂厂（产产地地），生生产产的的
14、产产品品由由4个个销销售售点点出出售售，各各工工厂厂的的有有关关资资料料如如下下表表，问应怎样调运才使总运费最少问应怎样调运才使总运费最少?收点收点发点发点B1B2B3B4产量产量B1B2B3B4A116412411A21021039A32285116销量销量81412144882102106661488利用位势法对上述方案进行检验：利用位势法对上述方案进行检验： B1B2B3B4UiA1412411A221039A385116Vj2 21 10 03 31010-5-51010-2-2+2+2-2-2+2+2=2收点收点发点发点B1B2B3B4产量产量A112416A28210A314822
15、销量销量814121448利用位势法对上述方案进行检验：利用位势法对上述方案进行检验： B1B2B3B4UiA1412411A221039A385116Vj2 22 20 02 29 9-3-38 8所有所有ij0 0，得到最优解，最小运费为得到最优解，最小运费为244244元。元。三、关于表上作业法的几点说明三、关于表上作业法的几点说明1关于初始方案中运量填为关于初始方案中运量填为“0”的规定的规定 在编制初始调运方案时，如果当填上运量xij后，第i行的发量已发完，同时第j列的收量已收足，此时不能把运价表中的第i行和第j列都划去，而只能划去第i行(或第j列)；此后再出现最小运价为(ckj)或
16、(cit)时，尽管Bj已收足(或Ai已发完)，但仍要在格子xkj(或xit)上填上“0”，并把这个填“0”的格子与其他有运量的格子一样看待 当收点个数为n，发点个数为m时，在方案表中，填有运量的格子数必须是m+n-1个 例如，假设一个物资调运问题的平衡表和运价例如，假设一个物资调运问题的平衡表和运价表如下表如下收点收点发点发点B1B2B3产量产量B1B2B3A14857A24946A33132收量收量32611试用最小元素法确定初始调运方案试用最小元素法确定初始调运方案收点收点发点发点B1B2B3产量产量B1B2B3A14857A24946A33132收量收量3261130224收点收点发点发
17、点B1B2B3产量产量B1B2B3A14857A24946A33132收量收量326113022424242 2关于调整方案中运量填为关于调整方案中运量填为“0 0”的规定的规定 当奇拐角点中有多个运量都是时，那么调整以后就会有多个奇拐点处的运量同时变为零，这时我们规定:把最上一行、最左边那个运量变为零的奇拐角点当作空格，而把其他几个拐角点处的运量填作“0”，并把它们当作有运量的格子一样看待 若一个运输问题的最优调运方案表中，某个空格(非基变量)xkt对应的检验数kt=0,那么该运输问题必有另一个最优调运方案。这个新的最优调运方案可以通过在原最优调运方案表上，沿kt对应的空格作闭回路调整而得到
18、。事实上，调整后总运费的减少数kt=0(因kt=0)，可见新旧方案对应的总运费不变，因此调整后的调运方案必然仍为最优方案3 3最优方案不唯一的情况最优方案不唯一的情况 单纯形法中，如果一个线性规划问题的最优基对应的单纯形表中某个非基变量对应的检验数等于零，那么该线性规划问题的最优解可能不唯一例如，一个物资调运问题的平衡表及运价表如下例如，一个物资调运问题的平衡表及运价表如下收点收点发点发点B1B2B3B4B5发量发量B1B2B3B4B5A123521432A2232713521A351614321收量收量2254518计算表中检验数发现计算表中检验数发现11=0，35=0，过相应的空格过相应的
19、空格对上表中的最优调运方案作调整，可得下面两个表对上表中的最优调运方案作调整，可得下面两个表收点收点发点发点B1B2B3B4B5发量发量B1B2B3B4B5A123521432A2232713521A351614321收量收量2254518+2-2-2+2收点收点发点发点B1B2B3B4B5发量发量B1B2B3B4B5A1221521432A234713521A351614321收量收量2254518收点收点发点发点B1B2B3B4B5发量发量B1B2B3B4B5A123521432A2232713521A351614321收量收量2254518收点收点发点发点B1B2B3B4B5发量发量B1
20、B2B3B4B5A123521432A2241713521A351614321收量收量2254518+1-1-1+14 4产销不平衡情况的处理方法产销不平衡情况的处理方法思路：先将原问题变为平衡问题，再用前面的方法确定调运方案产大于销增加假想销地，设定销量，运价为0；销大于产增加虚拟产地，设定假想产量，运价为0例例2 用表上作业法求下列运输问题的最优解用表上作业法求下列运输问题的最优解90801514211812产量产量365212863241065242301149371销量销量戊戊丁丁丙丙乙乙甲甲产地产地销地销地产地产地销地销地甲甲乙乙丙丙丁丁戊戊己己销量销量130224336产量产量12
21、18211415甲甲乙乙丙丙丁丁戊戊己己739411425610681225214251231021211490701523121830044227911010采用伏格尔法得初始调运方案（先将运价表中的采用伏格尔法得初始调运方案（先将运价表中的0列划去）列划去）采用位势法进行最优性检验采用位势法进行最优性检验甲甲乙乙丙丙丁丁戊戊己己7394110425610068122500037-38-136计算检验数计算检验数 练习练习 水泥调运的产销不平衡情况及运价表，如下表水泥调运的产销不平衡情况及运价表，如下表所示，试求最优调运方案。所示，试求最优调运方案。 收点收点发点发点B B1 1B B2 2
22、B B3 3B B4 4发量发量( (吨吨) )B B1 1B B2 2B B3 3B B4 4A A1 17 72 211113 34 4A A2 25 510103 35 59 9A A3 37 77 78 81 12 2收量收量( (吨吨) )2 23 34 46 6 19191515 在平衡表中增加库存一列；同时在运价表也相应地增加一列，在平衡表中增加库存一列；同时在运价表也相应地增加一列，该列的运价都是零，于是就得到一个新的平衡表和运价表。该列的运价都是零，于是就得到一个新的平衡表和运价表。 收点收点发点发点B1B2B3B4库存库存发发量量(吨吨)B1B2B3B4库存库存A17211
23、340A25103590A3778120收量(吨)2346419四、作物布局问题的表上作业法四、作物布局问题的表上作业法 例例3 某某农农场场有有土土地地9公公顷顷。这这些些土土地地因因土土壤壤的的肥肥沃沃程程度度和和水水源源条条件件不不同同，可可以以分分成成三三类类。现现在在农农场场要要在在这这三三类类土土地地上上计计划划种种植植三三种种作作物物。各各类类土土地地面面积积、计计划划种种植植面面积积，以以及及各各种种作作物物在在各各类类土土地地上上的的亩亩产产量量如如下下表表所所示示。问问应应如如何何因因地地制制宜安排作物布局，才能使作物总产量最多宜安排作物布局，才能使作物总产量最多? 土地类
24、别土地类别作物种类作物种类B1B2B3播种面积播种面积（公顷）（公顷）B1B2B3A11700500480A24850700600A34400300500土地面积土地面积（公顷）（公顷）3249目标函数求极大目标函数求极大解：解： (1) 确定初始种植方案确定初始种植方案用最大元素法编制初始方案用最大元素法编制初始方案 土地类别土地类别作物种类作物种类B1B2B3播种面积播种面积（公顷）（公顷）B1B2B3A11700500480A24850700600A34400300500土地面积土地面积（公顷）（公顷）32491314110(2) 最优方案的判别最优方案的判别用闭回路法计算检验数用闭回路
25、法计算检验数 如果所有检验数0，就可判定这个方案是最优方案。否则，就要对方案进行调整 对于这个例子的初始方案，因为对于这个例子的初始方案，因为11=50，所以需要调整。所以需要调整。 ij = =偶拐角点亩产总和偶拐角点亩产总和- -奇拐点亩产总和奇拐点亩产总和 (3) 方案调整方案调整用闭回路法调整种植方案用闭回路法调整种植方案 过第一个出现的正检验数对应的空格，作一闭回路；在闭回路奇拐角点的数字中找一个最小的数作为调整量；然后，在这条闭回路上，凡奇拐角点的数减去调整数，凡偶拐角点的数加上调整数，便得新的种植方案。初始方案经过调整后，得新方案如下表所示土地类别土地类别作物种类作物种类B1B2
26、B3播种面积播种面积（公顷）（公顷）A1101A2314A344土地面积土地面积（公顷）（公顷）3249-1-1+1+1土地类别土地类别作物种类作物种类B1B2B3播种面积播种面积（公顷）（公顷）A1101A2224A344土地面积土地面积（公顷）（公顷）3249经检验，新的种植方案为最优方案，故最大总产量为经检验，新的种植方案为最优方案，故最大总产量为 （公斤）（公斤）2064632444836土地亩数土地亩数507005508509501000蔬菜蔬菜70950900700800850玉米玉米868001050650600500小麦小麦计划播种面积计划播种面积戊戊丁丁丙丙乙乙甲甲土地块别土
27、地块别作物种类作物种类练习：用表上作业法求下列作物种植问题的最优方案练习：用表上作业法求下列作物种植问题的最优方案注：也可用伏格尔法或西北角法确定初始种植方案注：也可用伏格尔法或西北角法确定初始种植方案用位势法计算检验数用位势法计算检验数第二节第二节 运输问题的图上作业法运输问题的图上作业法 一、物资调运流向图一、物资调运流向图适用范围：单位运价与运输距离成正比适用范围：单位运价与运输距离成正比（总运费最小等价于周转量最小）（总运费最小等价于周转量最小）交通图：收发点的大致相对位置交通图：收发点的大致相对位置流向图：在交通图上，流向图：在交通图上，发点用圈发点用圈“”表示，发货量记在圈表示，发
28、货量记在圈“”内；内；收点用方框收点用方框“”表示，收货量记在方框表示，收货量记在方框“”内；内；相相邻邻两两收收发发点点间间的的交交通通线线称称为为一一条条“边边”，交交通通线线的的长长度称为该两点的间距或边长，其数值记在交通线的旁边度称为该两点的间距或边长，其数值记在交通线的旁边物物资资调调运运的的方方向向称称为为流流向向，用用“”表表示示，并并把把“”画在交通线前进方向的右侧；画在交通线前进方向的右侧；把把通通过过的的物物资资数数量量(称称为为流流量量)记记“”的的右右侧侧，并并加加上上括号括号二、最优调运方案的判定标准二、最优调运方案的判定标准 如果一个物资调运流向图中，既没有对流运输
29、，又没有迂回运输，那么该流向图就是最优流向图，对应的调运方案就是最优方案1对流运输对流运输 在在物物资资调调运运流流向向图图中中，如如果果在在一一条条边边上上同同时时标标有有两两个个相相反反的的流流向向，就就称称在在这这条条边边上上存存在在对对流流运运输输。如如果果一一个个物物资资调调运运流流向向图图中中的的任任何何一一条条边边上上都都没没有有对对流流，就就称称该该流流向向图无对流。图无对流。(5)(5)(10)(10)(5)(10)(5)510105304050A2B2B1A1510105304050A1B2B1A22迂回运输迂回运输 在在交交通通图图成成圈圈的的情情况况下下，物物资资调调运
30、运流流向向图图中中，有有些些流流向向画画在在圈圈内内，称称为为内内圈圈流流向向；有有些些流流向向画画在在圈圈外外，称称为外圈流向。为外圈流向。 内圈流向对应的各边边长之和称为内圈长，记为内圈流向对应的各边边长之和称为内圈长，记为 L内内；外圈流向对应的各边边长之和称为外圈长，记为外圈流向对应的各边边长之和称为外圈长，记为L外外； 该圈全部边长之和称为全圈长或总圈长，记为该圈全部边长之和称为全圈长或总圈长，记为L总总。在流向图的某一个圈上：在流向图的某一个圈上： 称在该圈上有迂回运输。称在该圈上有迂回运输。 如果如果 或或 如如果果一一个个物物资资调调运运流流向向图图中中的的任任何何一一个个圈圈
31、上上都都没没有有迂迂回，就称该流向图无迂回。回，就称该流向图无迂回。10503030B1B2A1A22344(20)(10)(30)10503030B1B2A1A22344(30)(20)(10)L总总=4+4+3+2=13L内内=4+3=7三、图上作业法的一般步骤与方法三、图上作业法的一般步骤与方法借助交通示意图编制既无对流又无迂回的物资调运流向图，求得最优物资调运方案的一种方法步骤步骤: (1) 编制无对流流向图；编制无对流流向图； (2) 检查有无迂回：若无迂回，已得到最优流向图；检查有无迂回：若无迂回，已得到最优流向图； 若有迂回，转为下一步；若有迂回，转为下一步； (3) 利用交通图
32、进行利用交通图进行 调整，重复第调整，重复第(2)步，直至没有步，直至没有 迂回为止；迂回为止； (4) 根据最优流向图制定最优调运方案。根据最优流向图制定最优调运方案。1交通图不成圈的情况交通图不成圈的情况 例例1 有有某某种种物物资资17万万吨吨，由由Al、A2、A3、A4出出发发，发发量量分分别别为为5万万吨吨、2万万吨吨、3万万吨吨、7万万吨吨；收收点点是是Bl、B2、B3、B4，收收量量分分别别为为8万万吨吨、1万万吨吨、3万万吨吨、5万万吨吨。收收发发平平衡衡。交交通通图图如如下下图图所所示示。问问应应如如何何调调运运，可可使使周周转转量量最最小？小？ 15385237A1A2A3
33、A4B1B2B4B315385237A1A2A3A4B1B2B4B3(7)(5)(1)(2)(1)(2)(5) (1) 作作无对流流向图无对流流向图 方方法法： 由由各各端端点点开开始始，由由外外向向里里，逐逐步步进进行行各各收收发点之间的供求平衡，标明物资的流向和流量。发点之间的供求平衡，标明物资的流向和流量。(2) 依最优流向图编制最优调运方案依最优流向图编制最优调运方案175318收量收量（万吨）（万吨）752A43111A322A255A1发量发量（万吨）（万吨）B4B3B2B1收点收点发点发点2交通图中有圈的情况交通图中有圈的情况 例例2 有有某某种种物物资资21万万吨吨，由由发发点
34、点A1、A2、A3、A4发发出出，发发量量分分别别为为5万万吨吨、8万万吨吨、2万万吨吨、6万万吨吨；收收点点为为B1、B2、B3收收量量分分别别为为8万万吨吨、7万万吨吨、6万万吨吨，收收发发量量平平衡衡。交交通通图图如下图所示。问应如何调运，可使吨公里最小如下图所示。问应如何调运，可使吨公里最小? 6875 58 82 26 612211343A1A2A3A4B1B2B3(1) (1) 作无对流的流向图作无对流的流向图 具体作法是：具体作法是：“用丢边破圈用丢边破圈”的方法，丢一条边，破的方法，丢一条边，破一一个个圈圈，直直至至把把有有圈圈的的交交通通图图变变成成不不成成圈圈的的交交通通图
35、图；然然后后在在不不成成圈圈的的新新交交通通图图上上作作无无对对流流的的流流向向图图。(选选择择最最长长的的边丢掉边丢掉) 43(5)(1)(7)(6)(2)(8)6875 58 82 26 6122113A1A2A3A4B1B2B3 在作完无对流流向图之后，再把丢掉的边补回去，使在作完无对流流向图之后，再把丢掉的边补回去，使交通图恢复原样。交通图恢复原样。 本例中，补回丢掉的边本例中，补回丢掉的边A3B1，和，和B2B3，就得到有圈就得到有圈的流向图。的流向图。 对对B1B2A4A3圈进行检查，算得：圈进行检查，算得： L总= 1+3+1+49 L内= 1+3+15 该圈有迂回，要对流向图该
36、圈有迂回，要对流向图(上图上图)进行调整进行调整 。 (2) 检查有无迂回检查有无迂回 具体作法是：对流向图中只有一边没有流向的各圈进行检查具体作法是：对流向图中只有一边没有流向的各圈进行检查 (3) 调整调整对有迂回的圈进行调整对有迂回的圈进行调整 1)1)求调整求调整( (数值的确定：在有迂回的圈上，如果是数值的确定：在有迂回的圈上，如果是具体作法是：具体作法是： ，那么，那么等于外圈上的最小流量；如果等于外圈上的最小流量；如果 , ,内圈上的最小流量内圈上的最小流量) )。 那么那么等于等于2 2）调整流量。）调整流量。 即若即若，内圈各流量增加内圈各流量增加，同时对该圈上仅有的一条没有
37、流同时对该圈上仅有的一条没有流向的边添上内圈流向向的边添上内圈流向( (流量为流量为)；如若如若，则把，则把，则把外圈各流量减去，则把外圈各流量减去外圈各流量增加外圈各流量增加，没有流向的边上没有流向的边上内圈各流量减去内圈各流量减去，添上外圈流向添上外圈流向( (流量为流量为)。 43(5)(1)(7)(6)(1)(7)6875 58 82 26 6122113A1A2A3A4B1B2B3本例本例 再检查有无迂回：再检查有无迂回：对对B1B2A4A3圈进行检查，算得：圈进行检查，算得： L总= 1+3+1+49 L内= 1+34 L外4 对对A2B3B2A4A3B1圈圈进行检查，算得：进行检查，算得： L总=2+2+4+1+3+315 L外6 L内= 2+1+36 注注: (1) 调整后需重新检查每个只有一条边无流量的圈调整后需重新检查每个只有一条边无流量的圈 (2) 若同时有几条边流量变为若同时有几条边流量变为0，只能将其中一条边为无，只能将其中一条边为无流向的边（一般取边长最大者），其余边看作流量为流向的边（一般取边长最大者），其余边看作流量为0 (4) 编制调运方案编制调运方案21678收量（万吨）收量（万吨）66A4211A3817A255A1发量发量（万吨）（万吨）B3B2B1收点收点发点发点
