第2章-物流配送方案的选择

物流运筹学教学课件第2章物流配送方案的选择物流配送方式的选择1物资的调运问题的数学模型2物资调运中的表上作业法3产销平衡物资调运问题的图上作业法4车辆调度问题52.1物流配送方式的选择2.12.1物流配送方式的选择在物流管理过程中，组织物流配送与运输工作应该以及时、准确、经济、安全为原则，在选择配送与运输方式（铁路、公路、水路、航空、管道等）时都应该以上述原则为依据。2.1物流配送方式的选择1.经济性指标设F1（*）表示某种物流配送方式的经济性指标，例如

F1（空）表示航空运输的经济性指标；

C（*）表示某种配送与运输方式的费用支出。铁路、公路、水路、航空这四种运输方式的平均费用支出为：2.1物流配送方式的选择2.迅速性指标设F2（*）表示某种物流配送方式的迅速性指标；D（*）表示用某种物流配送方式运输所需要的时间。用铁路、公路、水路、航空这四种运输方式运输平均需要的时间为:2.1物流配送方式的选择3.安全性指标设F3（*）表示某种物流配送方式的安全性指标；E（*）表示用某种物流配送方式的损坏率。用铁路、公路、水路、航空这四种运输方式运输平均损坏率为:2.1物流配送方式的选择4.便利性指标设F4（*）表示某种物流配送方式的便利性指标；L（*）表示用某种物流配送方式的发货地到收货地的距离。用铁路、公路、水路、航空这四种运输方式运输平均距离为:2.1物流配送方式的选择其中b1，

b2，b3，

b4为大于等于0的实数，且

。即为综合考察某种运输方式的经济性、迅速性、安全性和便利性的综合指标数值越少，其对应的运输方式越好。2.2物资的调运问题的数学模型2.22.2物资的调运问题的数学模型有某种物资需要调运有m个地点可以供应该种物资（以后通称产地，用i=1,2，…，m

表示）这m个产地的可供量（以后通称产量）为a1,

a2,

…,

am

（可通写为ai）n个销地的需要量（以后通称销量）分别为b1,

b2,…,bn

（可通写为bi）从第i个产地到第j个销地的单位物资运价为cij2.2物资的调运问题的数学模型产销平衡表12…n产量12…m

a1a2…am销量b1b2…bn

2.2物资的调运问题的数学模型单位运价表12…n12…mc11c21…cm1

c12c22…cm2

…………

c1nc2n…cmn2.2物资的调运问题的数学模型如果用xij代表从第i个产地调运给第j个销地的物资的单位数量，那么在产销平衡的条件下，使总的运费支出最小，可以表为以下数学形式：2.3物资调运中的表上作业法2.32.3物资调运中的表上作业法若有一批物资，要从几个生产地供应若干消费地，各地产量和销量都是已知的，各地运费也已知，如何调运才能使总运费（货总吨公里数）最小？表上作业法可以在不同运输工具和不同单位运价的情况下，在组织调运时，找到使总运费最省或吨公里数最小的方案。2.3.1产销平衡运输问题的表上作业法【例2.1】某公司主要经销的产品是食品。它下面设有三个加工厂。每天的食品生产量分别为A1=7吨，A2=4吨，A3=9吨。该公司把这些食品分别运往四个地区的门市部销售，各地区每天的销售量为：

B1=3吨，

B2=6吨，

B3=5吨,B4=6吨，已知从各个加工厂到各销售门市部每吨食品的运价如表所示，问该公司应如何调运，在满足各门市部销售需要的情况下，使总的运费支出为最少。B1B2B3B4A1311310A21928A3741052.3.1.1编制产销平衡表和运费表产销平衡表B1B2B3B4产量A17A24A39销量36562.3.1.1编制产销平衡表和运费表单位运价表B1B2B3B4A1311310A21928A3741052.3.1.2编制初始方案最小元素法：就近供应，即从单位运价表中最小的运价处开始确定供销关系，依此类推，一直到给出全部方案为止。Vogel法（沃格尔法）：也称元素差额法。从运价表上分别找出每行与每列的最小的两个元素之差，再从差值最大的行或列中找出最小运价确定供需关系和供应数量。当产地货销地中有一方数量上供应完毕或得到满足时，划去运价表中对应的行或列，再重复上述步骤。2.3.1.2编制初始方案第一步：从单位运价表中找出最小运价为1（有两个最小运价时任选其一），即A2生产的食品首先供应B1需要。由于A2每天生产4t，B1每天需要3t，即A2每天生产的除满足B1全部需求外，还余1t。最小元素法2.3.1.2编制初始方案产销平衡表B1B2B3B4产量A17A24A39销量3656最小元素法3在产销平衡表的交叉格中填上数字3，表示A2调运3t食品给B12.3.1.2编制初始方案单位运价表B1B2B3B4A1311310A21928A374105最小元素法单位运价表中将B1这一列运价划去，表示B1

的需求已满足，不需要继续调运给它。2.3.1.2编制初始方案第二步：从单位运价表未划去的元素中找出最小的运价2，即A2每天剩余的食品应供应B3。

最小元素法2.3.1.2编制初始方案产销平衡表B1B2B3B4产量A17A234A39销量3656最小元素法1B3每天需要5t，A2只能供应1t，因此在产销平衡表交叉处填写12.3.1.2编制初始方案单位运价表B1B2B3B4A1311310A21928A374105最小元素法划去单位运价表中的A2这一行运价，表示A2生产的食品已分配完。2.3.1.2编制初始方案第三步：从单位运价表未划去元素中找出最小元素为3，即A1生产的应优先满足

B3需要。A1每天生产7t，B3尚缺4t。最小元素法2.3.1.2编制初始方案产销平衡表B1B2B3B4产量A17A2314A39销量3656最小元素法42.3.1.2编制初始方案单位运价表B1B2B3B4A1311310A21928A374105最小元素法2.3.1.2编制初始方案第四步：从单位运价表未划去元素中找出最小元素为4，即A3生产的应优先满足

B2需要。

A3每天生产9t，

B2满足所需6t后尚余3吨。最小元素法2.3.1.2编制初始方案产销平衡表B1B2B3B4产量A147A2314A39销量3656最小元素法62.3.1.2编制初始方案单位运价表B1B2B3B4A1311310A21928A374105最小元素法2.3.1.2编制初始方案第五步：从单位运价表未划去元素中找出最小元素为5，即A3生产的应优先满足

B4需要。

A3尚余3吨，全供给B4。最小元素法2.3.1.2编制初始方案产销平衡表B1B2B3B4产量A147A2314A369销量3656最小元素法32.3.1.2编制初始方案单位运价表B1B2B3B4A1311310A21928A374105最小元素法2.3.1.2编制初始方案第六步：从单位运价表未划去元素中找出最小元素为10，即A1生产的应优先满足

B34吨需要外，尚余3吨，全供给B4。最小元素法2.3.1.2编制初始方案产销平衡表B1B2B3B4产量A147A2314A3639销量3656最小元素法32.3.1.2编制初始方案单位运价表B1B2B3B4A1311310A21928A374105最小元素法2.3.1.2编制初始方案产销平衡表B1B2B3B4产量A1437A2314A3639销量3656最小元素法到这一步，单位运价表所有元素都划去了，产销平衡表上就得到了一个调运方案，总费用为8600元2.3.1.2编制初始方案在调运方案表中，称填写数字处为有数字的格，它对应运输问题解中的基变量取值；称不填数字处为空格，它对应解中的非基变量。因运输问题中基变量数一般为（m+n-1）个，故调运方案中有数字的格也为（m+n-1）个。一般调运方案表每填一个数，划去单位运价表中的一行或一列。当选定最小元素后，发现该元素所在行的产地产量等于所在列的销地的销量，这时在产销平衡表上填一个数，运价表上就要同时划去一行和一列。为了使调运方案中的有数字格仍为（m+n-1）个，需要在同时划去的该行或该列的任一空格为止补填一个“0”。这个填写“0”的格被当作有数字的格看待。最小元素法2.3.1.2编制初始方案第一步：从单位运价表中找出每元素之差中标志①的行和列。从表中看到B2列的差值最大，从该列找出最小元素为4，即A3生产的首先满足B2的需要。Vogel法B1B2B3B4两最小元素之差①

②

③

④A1A2A3317119432101085011两最小元素之差①②③④25132.3.1.2编制初始方案产销平衡表B1B2B3B4产量A17A24A369销量3656Vogel法2.3.1.2编制初始方案第二步：从表中未划去的元素中再找出每行与每列的最小两个元素之差，列于栏目中标志②的行和列，因B4列差值最大，又该列的最小元素为5，即A3分配的剩余量满足B4需要。Vogel法B1B2B3B4两最小元素之差①

②

③

④A1A2A3317119432101085001112两最小元素之差①②③④22511332.3.1.2编制初始方案产销平衡表B1B2B3B4产量A17A24A3639销量3656Vogel法2.3.1.2编制初始方案第三步：继续重复上述步骤，一直到产地的产量分配完、销地的销量得到满足为止。Vogel法一般当产销地的数量不多时，Vogel法给出的初始方案有时就是最优方案，所以Vogel法有时就用作求运输问题最优方案的近似解。2.3.1.3最优性检验与方案的调整闭回路法：调运方案中由一个空格和若干个有数字格的水平和垂直连线包围成的封闭回路。最简单的闭回路是矩形，但随着运输问题规模的增大，闭回路的图形也将变得复杂。构建闭回路的目的是要计算解中各非基变量（对应空格）的检验数，方法是令某非基变量取值为1，通过变化原基变量的值找出一个新的可行解，将其同原来的基可行解目标函数值的变化比较。闭回路法2.3.1.3最优性检验与方案的调整【例2.1】最小元素法得出的调运方案B1B2B3B4产量A1437A2314A3639销量3656闭回路法（A1，B1）是空格，即x11为非基变量。令x11=1，为找到新的可行解，原有基变量中令x13应减1，

x23加1，x21减1新的方案费用增加了1元，称为检验数，填入检验数表中（A1，B1）+1-1+1-1类似地（A3，B1）为空格，通过该空格可找出一条其余顶点均为有数字格的闭回路2.3.1.3最优性检验与方案的调整检验数表B1B2B3B4A112A21-1A31012闭回路法由于任意非基向量均可表示为基向量的唯一线性组合，因此通过任一空格可以找到，并且也只能找到唯一的闭回路，并由此计算得出检验数表中的全部非基变量的检验数。2.3.1.3最优性检验与方案的调整如果检验数表中所有数字大于等于零，表明对调运方案作出任何改变将导致运费不会减少，即给定的方案是最优方案。检验数为负，说明方案需要进一步改进。改进的方法是从检验数为负值的格出发（当有两个以上负检验数时，从绝对值最大的负检验数格出发），作一条除该空格外其余顶点均为有数字格组成的闭回路。闭回路法2.3.1.3最优性检验与方案的调整【例2.1】最小元素法得出的调运方案B1B2B3B4产量A1437A2314A3639销量3656闭回路法+1-1+1-12.3.1.3最优性检验与方案的调整产销平衡表B1B2B3B4产量A1527A2314A3639销量3656闭回路法这次给出的调运方案是否为最优呢？还需要对这个方案的每一空格求出检验数2.3.1.3最优性检验与方案的调整闭回路法有时在闭回路调整中，在需要减少运量的地方有两个以上相等的最小数，这样调整时原先空格处填上了这个最小数，而又两个以上最小数的地方成了空格。为了用表上作业法继续计算，就要把最小数的格之一变为空格，其余均补添0，补添0的格当作有数字格看待，使方案中有数字的格仍为（m+n-1）个2.3.1.3最优性检验与方案的调整位势法【例2.1】用最小元素法得出的调运方案B1B2B3B4产量A1437A2314A3639销量3656第一步：先仿照调运方案表作一个表，将该表有数字格的地方换上单位运价表中对应格的运价B1B2B3B4A1310A212A3452.3.1.3最优性检验与方案的调整位势法B1B2B3B4uiA1310A212A345vj第二步：在得到的表右面和下面增加一行（

ui）和一列（

vj），

ui和vj分别称为第i行和第j列的位势.先任意决定其中的一个的数值，如v1=1，然后推导出其他位势的数值：使表中的各个数刚好等于它所在行和所在列的这些新填写的数字之和。1

v1+u2=1，

u2=00

v3+u2=2，

v3=2289-41

v3+u1=3，u1=1

v4+u1=10，v4=9

v4+u3=5，

u3

=-4

v2+u3=4，

v2=82.3.1.3最优性检验与方案的调整位势法B1B2B3B4uiA13101A2120A345-4vj1829第三步：看各空格的检验数。令λ31代入空格（A3，B1）的检验数。由闭回路计算可知：c31是空格（A3，B1）对应的单位运价表的运价。v1+

u3是该空格所在行和列的位势之和以此类推，我们可知任意一个空格的检验数为：2.3.1.3最优性检验与方案的调整位势法B1B2B3B4uiA1（2）（9）3101A21（8）2（9）0A3（-3）4（-2）5-4vj1829第四步：把表中所有空格处的行位势和列位势加起来，得下表。为区别起见，空格处的位势加上括弧。2.3.1.3最优性检验与方案的调整位势法B1B2B3B4A112A21-1A31012第五步：再用单位运价表上的数字减去该表对应格的数字，得下表，这就是所要求的各空格处的检验数。如果表中的出现有负的检验数时，对方案进行改进和调整的方法同前面闭回路法调整一样。2.3.2产销不平衡的运输问题产销不平衡的条件下寻求最优调运方案。一般主要是通过一定的方法将产销不平衡条件下的物资调运问题转化为产销平衡条件下的物资调运问题来解决。2.3.2产销不平衡的运输问题【例2.2】求表中产销不平衡问题的最优解B1B2B3B4发量(t)A1211347A2103595A378127收量23462.3.2产销不平衡的运输问题总发量比总收量多出4t，不论怎样总库存量都是4t。在收点处增加一列库存，同时运费表中也增加一列运费都是零把产销不平衡条件下的物资调运问题转变为产销平衡条件下的物资调运问题来解决B1B2B3B4库存发量(t)A12113407A21035905A3781207收量23464192.3.3表上作业法的实际应用作物布局问题土方的合理调配问题2.3.3表上作业法的实际应用【例2.3】某农场的一个分场要用1320亩土地种植玉米、地瓜、谷子、大豆四种作物。由土地的肥沃程度和水利条件的差别，这些土地可分成五个等级的土壤：I级土壤30亩，II级土壤150亩，III级土壤160亩，IV级土壤770亩，V级土壤210亩。要播种玉米305亩，地瓜620亩，谷子55亩，大豆340亩，并且有产量表（亩产量）。求在各级土壤的土地上，应如何合理安排各种作物的播种面积，使总产量最大。1.作物布局问题IIIIIIIVV玉米300250230200150地瓜

450400350谷子280240220170140大豆2202801551251102.3.3表上作业法的实际应用用最大元素法，即产量表中最大的产量尽可能优先供给的准则来编制初始播种方案1.作物布局问题IIIIIIIVV播种亩数玉米30275305地瓜

160460620谷子352055大豆150190340土壤亩数2015016077021013202.3.3表上作业法的实际应用用闭回路法求检验数，若全部检验数均不为正数，则方案为最优的。否则应调整。1.作物布局问题IIIIIIIVV玉米-90-20-20地瓜-500

-450-20谷子10-700大豆-20-35-152.3.3表上作业法的实际应用第三行第一列空格的检验数是正数，该播种方案不是最优的，应该调整，调整后得：1.作物布局问题IIIIIIIVV播种亩数玉米305305地瓜

160460620谷子3052055大豆150190340土壤亩数301501607702102.3.3表上作业法的实际应用求出其检验数表1.作物布局问题IIIIIIIVV玉米-10-90-20-20地瓜-150-540-20谷子-700大豆-30-35-15检验数全为负数，所以该播种方案是最优的。经计算得总产量为391950kg2.3.3表上作业法的实际应用例2.4设有挖土区甲、乙、丙三处，填土区I、II、III、IV四处。挖土量等于填土量，平衡表与里程表合并。问：如何使挖土区的土运到填土区总的土方公里（即土方数×运行公里数）最小？2.土方的合理调配问题IIIIIIIV挖土量甲109127500乙131194300丙1415115400填土量35045025015012002.3.3表上作业法的实际应用用最小元素法编制初始调配方案2.土方的合理调配问题IIIIIIIV挖土量甲50450500乙150150300丙300100400填土量35045025015012002.3.3表上作业法的实际应用检验数表，第三行与第四列交叉处空格的检验数为负。2.土方的合理调配问题IIIIIIIV甲50乙00丙2-12.3.3表上作业法的实际应用调整后的调配方案2.土方的合理调配问题IIIIIIIV挖土量甲50450500乙25050300丙300100400填土量35045025015012002.3.3表上作业法的实际应用检验数表，第二行与第二列交叉处空格的检验数为负。2.土方的合理调配问题IIIIIIIV甲46乙0-1丙212.3.3表上作业法的实际应用调整后的调配方案2.土方的合理调配问题IIIIIIIV挖土量甲100400500乙50250300丙250150400填土量35045025015012002.3.3表上作业法的实际应用检验数表，没有负数了，以此表2-44所示调配方案最优。2.土方的合理调配问题IIIIIIIV甲56乙21丙20最小土方公里数为2.4产销平衡物资调运问题的图上作业法2.42.4产销平衡物资调运问题的图上作业法图上作业法：利用生产地和消费地的地理分布，根据就近供应的原则，应用交通路线示意图和货物产销平衡表，找出产销之间吨公里数最小或总运费最低的运输路线（称为最优路线）.交通路线示意图（也称为网络图）需要给出三种基本资料收点和发点收点的收货量及发点的发货量连接这些收点、发点的交通线路以及与之相对应的线路长度或运价

2.4产销平衡物资调运问题的图上作业法图上作业法：利用生产地和消费地的地理分布，根据就近供应的原则，应用交通路线示意图和货物产销平衡表，找出产销之间吨公里数最小或总运费最低的运输路线（称为最优路线）.交通路线示意图（也称为网络图）需要给出三种基本资料收点和发点收点的收货量及发点的发货量连接这些收点、发点的交通线路以及与之相对应的线路长度或运价

2.4.1交通路线不成圈问题的图上作业法交通线路不成圈问题也称为树状交通路线问题，是指所有供应点（发货点）和需求点（收货点）之间的一切道路都不构成任何圈，即运输路线构成的交通图中没有任何回路出现，是树状的.求解原则是：只要货物流向图中无对流出现就是最优流向圈，即最优调运方案.2.4.1交通路线不成圈问题的图上作业法交通图：用图上作业法来解物资调运问题，第一步是画一张图，在图上标出产地和销地，并将产地用“○”表示，在这个圈内填上该产地的产量；将销地用“□”表示，在这个方块内填上该销地的销量。第二步把连接这些点的交通路线画出来，在每段路线旁注明该路线的长度，这样的图称为交通图。2.4.1交通路线不成圈问题的图上作业法交通流向图：设A是发点，发量为10t；B是收点，收量也是10t。把A点的10t物资运到B点，只需从A点画一条带箭头的直线指向B点，且这条直线要画在从A到B前进方向的右侧，在直线旁标明发量。箭头所指的方向是物资运输的方向，称为流向；运输物资的数量称为流量（一般标明在带箭头的直线旁，用括号括上）。2.4.1交通路线不成圈问题的图上作业法流向要画在物资运输方向的右侧。流向不能直接通过路线上的收点，发点及交叉点。2.4.1交通路线不成圈问题的图上作业法在一段路线上若有几个同方向的流向，应该把它们合并成一个流向，并把流量也相加。2.4.1交通路线不成圈问题的图上作业法对流运输：在同一段路线上相对运输的现象。如：某种物资A地生产10t，D地生产5t；B地需要5t，C地需要10t。图2-13所示的流向图表示把A地的10t物资经B地运往C地，把D地的5t物资经C地运往B地。这样在B地与

C地之间的这段线路上就产生了对流运输的现象，这是不合理的。2.4.1交通路线不成圈问题的图上作业法“取一端，它的供需归邻站”这个交通图中没有圈，A端的10t运往其邻站B点，D端的5t运往其邻站C点，再从B点运5t到其邻站C点，如图2-14所示。2.4.1.2交通路线不成圈问题的图上作业法的步骤第一步：编制货物产销平衡表第二步：

在交通示意图上，按就近供应原则，从各端点开始安排初始调运路线，图中货物流动的方向和流动的数量用虚线箭头即虚线旁边的数字表示，然后，简化初始调运路线，得出调整后的供应数量及其交通示意图.第三步：在简化的交通路线示意图上，按就近供应原则，从各端点开始安排第二次调运路线第四步：把最佳调运路线的结果填入货物产销平衡表后得最佳调运方案2.4.1.2交通路线不成圈问题的图上作业法的步骤【例2.5】设有4个产地A1，

A2，A3，A4生产分别同一产品，销往4个消费地B1，

B2，

B3，

B4,其交通路线示意图如图所示.试用图上作业法确定产品调运的最优方案.2.4.1.2交通路线不成圈问题的图上作业法的步骤第一步：编制货物产销平衡表

B1B2B3B4发货量A1

100A2

20A3

60A4

140收货4.1.2交通路线不成圈问题的图上作业法的步骤第二步：在交通路线示意图上，从各端点开始，按就近供应的原则安排初始调运路线，图中货物流动的方向和流动的数量用虚线箭头和虚线旁边的数字表示2.4.1.2交通路线不成圈问题的图上作业法的步骤第三步：将最佳调运路线的结果填入货物产销平衡表得到一个最佳调运方

B1B2B3B4发货量A1100

100A220

20A320

2020

60A4

40

100

140收货4.1.2交通路线不成圈问题的图上作业法的步骤通路线不成圈问题的图上作业法求得的最优调运方案不一定是唯一的.不同的最佳调运方案的总成本一定都是相同的用图上作业法寻找不成圈的最佳路线时不必考虑各地之间运输距离或运输成本.2.4.1.2交通路线不成圈问题的图上作业法的步骤【例2.6】设有4个产地A1，A2，A3，A4生产分别同一产品，销往5个消费地B1，B2，B3，

B4，B5，其交通路线示意图如图所示.试用图上作业法确定产品调运的最优方案.2.4.1.2交通路线不成圈问题的图上作业法的步骤第一步：编制货物产销平衡表

B1B2B3B4B5发货量A1

700A2

400A3

900A4

500收货量30070050060040025002.4.1.2交通路线不成圈问题的图上作业法的步骤第二步：在交通示意图上，按就近供应原则，从各端点开始安排初始调运路线，图中货物流动的方向和流动的数量用虚线箭头及虚线旁边的数字表示2.4.1.2交通路线不成圈问题的图上作业法的步骤第二步：简化初始调运路线，得出调整后的供应数量及其交通示意图2.4.1.2交通路线不成圈问题的图上作业法的步骤第三步：在简化的交通路线示意图上，按就近供应原则，从各端点开始安排第二次调运路线2.4.1.2交通路线不成圈问题的图上作业法的步骤由于图中各地产销已经平衡，而且没有对流，故合并两次调运路线后，即得最佳调运路线2.4.1.2交通路线不成圈问题的图上作业法的步骤第四步：把最佳调运路线的结果填入货物产销平衡表后得最佳调运方案

B1B2B3B4B5发货量A1

300300

100700A2

400

400A3

600300900A4

500

500收货量30070050060040025002.4.1.2交通路线不成圈问题的图上作业法的步骤【例2.7】现有某物资20吨要从发点A1，A2，A3，A4运到收点B1，B2，B3，B4，其交通路线示意图如图所示.问应如何安排调运计划，才能使运输量（吨公里）最小.2.4.1.2交通路线不成圈问题的图上作业法的步骤解：做一个没有对流的流程图。2.4.1.2交通路线不成圈问题的图上作业法的步骤将最佳调运路线的结果填入货物产销平衡表得到一个最佳调运方

B1B2B3B4发货量A155A233A3325A4257收货量8345202.4.2交通路线成圈问题的图上作业法交通路线成圈问题是指交通路线示意图中有些路线构成回路的情况2.4.2交通路线成圈问题的图上作业法一个有圈的交通图作成流向图之后，有些弧上的流向在圈外，这样的流向称为外圈流向；另有些弧上的流向在圈内,称为内圈流向。如果流向图中某一个圈的内圈流向总长（简称内圈长）或者外圈流向总长（简称外圈长）超过整个圈长的一半，就称为迂回运输。2.4.2交通路线成圈问题的图上作业法圈长为4+7+2+3=16外圈长为4+2+3=9这个流向图有迂回运输运输量为54圈长为16内圈长为7这个流向图没有迂回运输运输量为422.4.2交通路线成圈问题的图上作业法在一个流向图的一个圈中，所有顺时针方向的流向，都一定画在圈内；所有逆时针方向的流向，都一定画在圈外。在抹去圈中的弧时，尽量抹去那些最长的弧，因为这样抹去的弧上是没有流量的。Vogel法甩一弧，破一圈；甩了甩，破了破。化为没有圈，然后照样干。2.4.2交通路线成圈问题的图上作业法基本定理：在一个没有对流的流向图中，如果每一个圈上的内圈流向和外圈流向的总长度都不超过圈长的一半，这个流向图就是最优的；如果图中没有圈，只要没有对流，就一定是最优的。反过来，在一个没有对流的流向图中，只要有一个圈上的内圈流向或者外圈流向的总长度超过了圈长的一半，这个流向图就一定不是最优的。2.4.2交通路线成圈问题的图上作业法流向图的调整外调整法：外调整法的步骤为：第一步：取定一个圈。第二步：找出这个圈的内圈流量中的最小值（称为调整量），然后所有的外圈流量都加上这个调整量，而所有的内圈流量都减去这个调整量。没有流量的弧添上外圈流向，流量为调整量。内调整法：调整法的步骤为：第一步：取定一个圈。第二步：找出外圈流量中的最小值（调整量），然后每个外圈流量都减去这个调整量，每个内圈流量都加上这个调整量。无流量的弧添上内圈流向，流量为调整量2.4.2交通路线成圈问题的图上作业法流向图的调整当一个不合格圈的外圈流向的总长度超过圈长的一半时，用内调整法；当内圈流向的总长度超过圈长的一半时，用外调整法2.4.2交通路线成圈问题的图上作业法Vogel法流向画右边，对流不应当。里圈和外圈，不过半圈长。2.4.2交通路线成圈问题的图上作业法基本流向图：若一个有n个点的流向图无对流,且它的投影图具有性质:连通的没有圈有n-1条弧。则这样的流向图称为基本流向图。2.4.2交通路线成圈问题的图上作业法基本流向图为了得到基本流向图，可以再图上加画一些流向，其流量为0，这种流向图叫做虚流向。2.4.2交通路线成圈问题的图上作业法2.4.2交通路线成圈问题的图上作业法改进图上作业法定理1：最优流向图一定可以在基本流向图中找到。定理2：

如果一个基本流向图中所有“要检查的圈”都合格，该流向图就是最优的。2.4.2.2交通路线成圈问题的图上作业法的步骤第一步：作出调运平衡表；第二步：画出实际交通路线示意图；第三步：在交通路线示意图上，任意安排一个没有对流的初始可行调运方案，其方法是:逐次在一个圈上任意去掉一边，直到不存在圈为止，然后根据不成圈问题的图上作业法找出其最佳调运方案.第四步：检验已有调运方案.检验的方法是：检验已有调运方案是否满足基本定理，若满足基本定理，则已有调运方案就是最佳调运方案；否则转入第五步，对已有调运方案进行调整.2.4.2.2交通路线成圈问题的图上作业法的步骤第五步：调整已有调运方案.调整的方法是：找出不符合要求的内圈或外圈流向弧中流量最小的弧，将其去掉；然后依次调整各点之间的流量，使各点的供需量重新达到平衡，于是得到一个新的可行调运方案，并转向第四步；第六步：当已有调运方案已经满足要求时，即该调运方案的任何一个回路上，内圈和外圈流向的总弧长均小于或等于该回路总长的一半时，这个调运方案就是之间调运方案.然后，将其结果填入调运平衡表，得到调运方案表.2.4.2.2交通路线成圈问题的图上作业法的步骤【例2.8】设某集团公司有A1、A2、A3、A4四个配送中心，要为该公司所属的四个超市B1、B2、B3、B4补充库存，各配送中心和超市的位置如图所示，图中各边旁边括弧内的数字表示相应点之间的里程，各配送中心供应量和各超市的需求量也在图中标出.试确定之间最佳调运方案.2.4.2.2交通路线成圈问题的图上作业法的步骤解：第一步：作出调运平衡表

B1B2B3B4发货量A1150A2180A390A4140收货量1202001001405602.4.2.2交通路线成圈问题的图上作业法的步骤第二步：在交通路线示意图上任意安排一个没有对流的初始可行调运方案2.4.2.2交通路线成圈问题的图上作业法的步骤第三步：检验初始调运方案；圈全长=490，其一半为245；内圈长=260>245.内圈长不符合要求，需要对内圈进行调整.2.4.2.2交通路线成圈问题的图上作业法的步骤第四步：调整初始调运方案：在内圈上流量最小的路线弧是：A3——B3，将其去掉，并将A3的供应量90全部供给B2，进而依次调整各点之间的流量，得到一个新的调运方案.2.4.2.2交通路线成圈问题的图上作业法的步骤第五步：检验一次调整后的调运方案：内圈长=240<245,外圈长=230<245.由于基本定理满足，所以一次调整后的方案就是最佳调运方案.2.4.2.2交通路线成圈问题的图上作业法的步骤第六步：把最佳调运方案的结果填入调运平衡表中，得到最佳调运方案表

B1B2B3B4发货量A150100150A270110180A39090A410040140收货量1202001001405602.4.2.2交通路线成圈问题的图上作业法的步骤【例2.9】设有化肥产地A1、A2、A3、A4及销地B1、B2、B3、B4、B5，表1中数据表示的是一年的产量和销量，表2中数据表示各产地和销地间的距离。怎样调运这些化肥，才能使运输的吨公里数最少？

产地

产量销地销量A16B13A25B25A38B35A42B43B55A1A2A3A4B1B2B3B4B5A1120239A2120266A3349252A4349317B1266180165B2239180118B3252165B4317118393B53932.4.2.2交通路线成圈问题的图上作业法的步骤解：第一步；作物资调运问题的交通图2.4.2.2交通路线成圈问题的图上作业法的步骤第二步；作第一个流向图，图有圈，先“甩弧破圈”。先取上面的小圈：B2A1A2B1B2，抹去较长的弧B1A2

，破掉了这个圈。再取下面的大圈：

B1B2A4A3B1，抹去较长的弧A3A4，破掉这个圈。剩下的图就变成没有圈的图了。用口诀“取一端，它的供需归邻站”的方法作第一个流向图。再把弧B1A2和弧A3A4添上去，就得到图2-38所示有圈交通图的第一个流向图2.4.2.2交通路线成圈问题的图上作业法的步骤第三步；检验初始调运方案；用基本定理检查是不是最优总长：内圈：总长：内圈：外圈：2.4.2.2交通路线成圈问题的图上作业法的步骤第三步；检验初始调运方案；用基本定理检查是不是最优总长：内圈：外圈：2.4.2.2交通路线成圈问题的图上作业法的步骤第四步；经检验图所有三个圈均合格，不需要对内圈进行调整.。因此，是最优流2.4.2.2交通路线成圈问题的图上作业法的步骤第五步；把最佳调运方案的结果填入调运平衡表中，得到最佳调运方案表

B1B2B3B4B5发量A1156A255A3358A422收量355352.4.2.2交通路线成圈问题的图上作业法的步骤【例2.10】某物资从发点A1、A2、A3、A4运往收点B1、B2、B3、B4、B5、B6，它的交通图如图所示，求最优调运方案。2.4.2.2交通路线成圈问题的图上作业法的步骤第1步：做一个没有对流的流程图。用“丢边破圈”的方法，把有圈的交通图化为无圈的交通图。比如，先丢掉边B5A4，破圈B5A4B4B3A2B1

A1B6B5；再丢掉边B4B2，破圈B4

B2A2B3B4。无圈且没有对流，其投影图是连通，恰好有10个点9条弧，再加上一条弧就能作成一个圈了，这样的圈正是“要检查的圈”，补回丢掉的B5A4和B4B2两边，得原交通图的流程图2.4.2.2交通路线成圈问题的图上作业法的步骤第2步：检验初始调运方案总圈长：＝63＋50＋21＋58＋37＋21＋39＋46＝3351/2圈长＝167.5内圈＝50＋21＋37＋39＋46＝193＞167.52.4.2.2交通路线成圈问题的图上作业法的步骤第3步：第一次调整。取内圈流向的最小运调量为调整量

按调整规则进行调整，所有内圈流向上的调运量都减去

，并丢掉B6B5边上调运量为零的流向；所有外圈流向上的调运量都加上

；原来没有流向的边A4A5加上外圈流向2.4.2.2交通路线成圈问题的图上作业法的步骤第4步：再检验调整后的调运方案总圈长：＝70＋45＋58＋21＝1941/2圈长＝97内圈＝45＋58＝103＞972.4.2.2交通路线成圈问题的图上作业法的步骤第5步：第二次调整。取内圈流向的最小运调量为调整量

2.4.2.2交通路线成圈问题的图上作业法的步骤第6步：再检验调整后的调运方案总圈长：＝3351/2圈长＝167.5内圈＝50＋21＋37＋39＝147＜167.5外圈＝63＋58＋21＝142＜167.5总圈长：＝1941/2圈长＝97内圈＝58＜97外圈＝70＋21＝91＜972.4.2.2交通路线成圈问题的图上作业法的步骤第7步：由此可得，这是一个最优流程图，它对应的最优调运计划如表

B1B2B3B4B5B6发量A19918A24812A310919A4131519收量1310211059S＝5×63＋14×50＋13×21＋9×70＋8×58＋9×30＋4×37＋9×21＋9×39＝36402.4.2.2交通路线成圈问题的图上作业法的步骤【例2.11】如图2-45所示的交通图，求其最优流向图2.4.2.2交通路线成圈问题的图上作业法的步骤第一步：用“甩弧破圈”的方法，作第一个流向图，如图2-46所示，其投影图如图2-47所示2.4.2.2交通路线成圈问题的图上作业法的步骤第二步：检验初始调运方案；投影图（图2-47）是连通，恰好有9个点8条弧，再加上一条弧就能作成一个圈了，这样的圈正是“要检查的圈”。图2-47中有四条没有流向的弧：AD，BC，GH，HE。把AD加入图：总圈长：＝10内圈＝3＜5外圈＝5＜52.4.2.2交通路线成圈问题的图上作业法的步骤第二步：检验初始调运方案；投影图（图2-47）是连通，恰好有9个点8条弧，再加上一条弧就能作成一个圈了，这样的圈正是“要检查的圈”。图2-47中有四条没有流向的弧：AD，BC，GH，HE。把BC加入图：总圈长：＝10内圈＝2＜5外圈＝5＜52.4.2.2交通路线成圈问题的图上作业法的步骤第二步：检验初始调运方案；投影图（图2-47）是连通，恰好有9个点8条弧，再加上一条弧就能作成一个圈了