第三章 运输问题的特殊解法

表上作业法图上作业法第三章运输问题的特殊解法

(TransportationProblem)第一节运输问题的表上作业法一、运输问题的数学模型及其特点设某种物品有m个产地A1,A2,…,Am，各产地的产量分别是a1,a2,…,am；有n个销地Bl

,B2,…,Bn

,各销地的销量分别为bl

,b2,…,bn。假定从产地Ai(i＝1,2,…,m)向销地Bj

(j＝1,2,…,n)运输单位物品的运价是cij，问怎样调运这些物品能使总运费最小?

这是由多个产地供应多个销地的单品种物资运输问题。为直观清楚起见，可将数据汇总于产销平衡表和单位运价表中：销地产地12…n产量销地产地12…n平1a11c11c12…c1n运衡2a22c21c22…c2n价表..................表mammcm1cm2…cmn销量b1b2…bn（1）产销平衡时矩阵形式（2）产大于销时（3）产小于销时特征

运输问题的基本可行解中应包括

m+n-1个基变量

平衡运输问题必有可行解，也必有最优解二、表上作业法的思路和步骤步骤：1）确定初始调运方案

2）解的最优性判断

3）调整方案

4）重复2）3）步，直到找到最优方案找到初始基可行解最优性判断调整找到新的基可行解重复2、3步直到找到最优解例1某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点出售，各工厂的有关资料如下表，问应怎样调运才使总运费最少?收点发点B1B2B3B4产量B1B2B3B4A17311312A241928A3974105销量365620（一）确定初始调运方案1、最小元素法

思路：就近供应，优先安排运价最小的收发点之间的物资调运量，然后次小，直到给出初始基可行解解题步骤：（1）在运价表中找到最小运价c1k（2）将的Al产品给Bk

①若al>bk，则将al改写为al-bk，划掉bk，同时将运价表中k列的运价划掉

②若al<bk，则将bk改写为bk-al，划掉al，同时将运价表中l行的运价划掉（3）如此重复(1)、(2)，直到分配完毕收点发点B1B2B3B4产量B1B2B3B4A17311312A241928A3974105销量365620对应的目标函数值为：z＝3×4＋12×3十1×3十2×1＋4×6十5×3＝92(元)314633①②③④⑤⑥31343

2、西北角法思路：该法优先满足运输表中西北角上空格的供销需求

收点发点B1B2B3B4产量B1B2B3B4A17311312A241928A3974105销量365620342236对应的目标函数值为：z＝3×3＋11×4十9×2十2×2＋10×3十5×6＝135(元)3、伏格尔法

思想：最小元素法为了节省一处的费用，有时可能造成在其他处要多花几倍的运费。伏格尔法考虑到，一地的产品假如不能按最小运费就近供应，就考虑次小运费，因此就会有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而，对差额最大处，就应当采用最小运费调运解题步骤：（1）计算运输表中每一行和每一列的次小单位运价和最小运价之间的差值（2）从行或列差中选择最大者，选择它所在行或列中的最小元素clk，将Al的产品优先供应Bk，同时将运价表中已满足的行或列划掉。（3）如此重复(1)、(2)，直到分配完毕收点发点B1B2B3B4产量B1B2B3B4行差A17311312A241928A3974105销量3656205130116125243333125对应的目标函数值为：z＝3×2＋3×5十1×1十8×3＋4×6十5×3＝85(元)注：

伏格尔法除确定供求关系的原则与最小元素法不同外，其余步骤与最小元素法相同。

与最优解的接近程度：伏格尔法、最小元素法、西北角法2（二）解的最优性检验求出各非基变量的检验数，判别是否均不小于0：如果是，则得到最优解，停止计算；否则转入下一步注：因为目标函数要求最小化，所以σij<0表示运费减少，σij>0表示运费增加。

表格中有调运量的地方为基变量，空格处为非基变量。基变量的检验数σij＝0，需计算非基变量的检验数是否不小于0。1、闭回路法闭回路——以某一空格为起点，用水平线或垂直线向前画，碰到某一个数字格转90度后，继续前进，直到回到起始空格为止B1B2B3B4产量A1437A2314A3639销量365620空格处检验数的计算公式：[偶拐角点对应运价之和]-[奇拐角点对应运价之和]利用最小元素法形成的初始调运方案进行说明：B1B2B3B4产量B1B2B3B4A1437311312A23141928A363974105销量3656202、位势法提出：闭回路法需要多次作闭回路，多次对照运价表，多次计算，繁琐复杂，特别是收发点多时尤为不便，故提出位势法——在运价表上直接操作解题步骤：（1）编制位势表在运输问题的单价表中的基变量处画圈，同时在表中增加一行（列位势）和一列（行位势）（2）填写位势数任选第一个位势数填入表中，其余按ul+vk=clk填写(基变量的σij＝0)（3）计算检验数对运价表没画圈的cij按σij=cij－(ui+vj)

计算检验数B1B2B3B4A1311312u1A21928u2A374105u3v1v2v3v4运价表B1B2B3B4UiA1311312A21928A374105Vj位势表2-13012-711（三）调整方案——闭回路法实质：单纯形法的换基迭代调整步骤（1）作第一个出现负检验数σij的闭回路；（2）求调整量ε。ε=奇拐角点处的最小运量

（3）调整。奇拐角点处的各运量均减去ε；偶奇拐角点处的各运量均加上ε；不在闭回路上的格子运量不变ε的选取原则：1）奇拐角点处的某一个运量减少为02）每一个奇拐角点处的运量不能减少为负数B1B2B3B4产量A1437A2314A3639销量3656-1+1-1-1+1+1B1B2B3B4产量A1527A2314A3549销量3656检验数：-1-1+1+1Vj51047A38191A2123113A1UiB4B3B2B1位势表123113－7-20B1B2B3B4产量A1527A2314A3639销量3656123115－7－40Vj51047A38191A2123113A1UiB4B3B2B1位势表检验数：-2-2+2+2所有σij≥0，得到最优解z＝3×2＋3×5十1×1十8×3＋4×6十5×3＝85(元)10393－5－20Vj51047A38191A2123113A1UiB4B3B2B1B1B2B3B4产量A1257A2134A3639销量3656练习：某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点出售，各工厂的有关资料如下表，问应怎样调运才使总运费最少?收点发点B1B2B3B4产量B1B2B3B4A116412411A21021039A32285116销量814121448821021066①②③61488④⑤⑥利用位势法对上述方案进行检验：

B1B2B3B4UiA1412411A221039A385116Vj210310-510√-2+2-2+2ε=2收点发点B1B2B3B4产量A112416A28210A314822销量814121448利用位势法对上述方案进行检验：

B1B2B3B4UiA1412411A221039A385116Vj22029-38所有σij≥0，得到最优解，最小运费为244元。三、关于表上作业法的几点说明1．关于初始方案中运量填为“0”的规定

在编制初始调运方案时，如果当填上运量xij后，第i行的发量已发完，同时第j列的收量已收足，此时不能把运价表中的第i行和第j列都划去，而只能划去第i行(或第j列)；此后再出现最小运价为(ckj)或(cit)时，尽管Bj已收足(或Ai已发完)，但仍要在格子xkj(或xit)上填上“0”，并把这个填“0”的格子与其他有运量的格子一样看待

当收点个数为n，发点个数为m时，在方案表中，填有运量的格子数必须是m+n-1个例如，假设一个物资调运问题的平衡表和运价表如下收点发点B1B2B3产量B1B2B3A14857A24946A33132收量32611试用最小元素法确定初始调运方案收点发点B1B2B3产量B1B2B3A14857A24946A33132收量3261130224④②收点发点B1B2B3产量B1B2B3A14857A24946A33132收量3261130224④②⑤③①①③⑤24242．关于调整方案中运量填为“0”的规定当奇拐角点中有多个运量都是ε时，那么调整以后就会有多个奇拐点处的运量同时变为零，这时我们规定:把最上一行、最左边那个运量变为零的奇拐角点当作空格，而把其他几个拐角点处的运量填作“0”，并把它们当作有运量的格子一样看待

若一个运输问题的最优调运方案表中，某个空格(非基变量)xkt对应的检验数σkt=0,那么该运输问题必有另一个最优调运方案。这个新的最优调运方案可以通过在原最优调运方案表上，沿σkt对应的空格作闭回路调整而得到。事实上，调整后总运费的减少数σkt×ε=0(因σkt=0)，可见新旧方案对应的总运费不变，因此调整后的调运方案必然仍为最优方案3．最优方案不唯一的情况单纯形法中，如果一个线性规划问题的最优基对应的单纯形表中某个非基变量对应的检验数等于零，那么该线性规划问题的最优解可能不唯一例如，一个物资调运问题的平衡表及运价表如下收点发点B1B2B3B4B5发量B1B2B3B4B5A123521432A2232713521A351614321收量2254518计算表中检验数发现σ11=0，σ35=0，过相应的空格对上表中的最优调运方案作调整，可得下面两个表收点发点B1B2B3B4B5发量B1B2B3B4B5A123521432A2232713521A351614321收量2254518+2-2-2+2收点发点B1B2B3B4B5发量B1B2B3B4B5A1221521432A234713521A351614321收量2254518收点发点B1B2B3B4B5发量B1B2B3B4B5A123521432A2232713521A351614321收量2254518收点发点B1B2B3B4B5发量B1B2B3B4B5A123521432A2241713521A351614321收量2254518+1-1-1+14．产销不平衡情况的处理方法思路：先将原问题变为平衡问题，再用前面的方法确定调运方案产大于销—增加假想销地，设定销量，运价为0；销大于产—增加虚拟产地，设定假想产量，运价为0例2

用表上作业法求下列运输问题的最优解90801514211812产量365212863241065242301149371销量戊丁丙乙甲产地销地产地销地甲乙丙丁戊己销量130224336产量1218211415甲乙丙丁戊己739411425610681225214251231021211490701523121830044227911010采用伏格尔法得初始调运方案（先将运价表中的0列划去）采用位势法进行最优性检验甲乙丙丁戊己7394110425610068122500037-38-136计算检验数

练习水泥调运的产销不平衡情况及运价表，如下表所示，试求最优调运方案。

收点发点B1B2B3B4发量(吨)B1B2B3B4A1721134A2510359A377812收量(吨)2346

1915在平衡表中增加库存一列；同时在运价表也相应地增加一列，该列的运价都是零，于是就得到一个新的平衡表和运价表。

收点发点B1B2B3B4库存发量(吨)B1B2B3B4库存A17211340A25103590A3778120收量(吨)2346419四、作物布局问题的表上作业法

例3某农场有土地9公顷。这些土地因土壤的肥沃程度和水源条件不同，可以分成三类。现在农场要在这三类土地上计划种植三种作物。各类土地面积、计划种植面积，以及各种作物在各类土地上的亩产量如下表所示。问应如何因地制宜安排作物布局，才能使作物总产量最多?土地类别作物种类B1B2B3播种面积（公顷）B1B2B3A11700500480A24850700600A34400300500土地面积（公顷）3249目标函数求极大解：(1)确定初始种植方案——用最大元素法编制初始方案

土地类别作物种类B1B2B3播种面积（公顷）B1B2B3A11700500480A24850700600A34400300500土地面积（公顷）3249

①③⑤②④1314110(2)

最优方案的判别——用闭回路法计算检验数

如果所有检验数σ≤0，就可判定这个方案是最优方案。否则，就要对方案进行调整

对于这个例子的初始方案，因为σ11=50，所以需要调整。σij

=偶拐角点亩产总和-奇拐点亩产总和

(3)

方案调整——用闭回路法调整种植方案

过第一个出现的正检验数对应的空格，作一闭回路；在闭回路奇拐角点的数字中找一个最小的数作为调整量；然后，在这条闭回路上，凡奇拐角点的数减去调整数，凡偶拐角点的数加上调整数，便得新的种植方案。初始方案经过调整后，得新方案如下表所示土地类别作物种类B1B2B3播种面积（公顷）A1101A2314A344土地面积（公顷）3249-1-1+1+1土地类别作物种类B1B2B3播种面积（公顷）A1101A2224A344土地面积（公顷）3249经检验，新的种植方案为最优方案，故最大总产量为（公斤）2064632444836土地亩数507005508509501000蔬菜70950900700800850玉米868001050650600500小麦计划播种面积戊丁丙乙甲

土地块别作物种类练习：用表上作业法求下列作物种植问题的最优方案注：也可用伏格尔法或西北角法确定初始种植方案用位势法计算检验数第二节运输问题的图上作业法

一、物资调运流向图

适用范围：单位运价与运输距离成正比（总运费最小等价于周转量最小）

交通图：收发点的大致相对位置

流向图：在交通图上，发点用圈“○”表示，发货量记在圈“○”内；收点用方框“□”表示，收货量记在方框“□”内；相邻两收发点间的交通线称为一条“边”，交通线的长度称为该两点的间距或边长，其数值记在交通线的旁边物资调运的方向称为流向，用“→”表示，并把“→”画在交通线前进方向的右侧；把通过的物资数量(称为流量)记“→”的右侧，并加上括号二、最优调运方案的判定标准如果一个物资调运流向图中，既没有对流运输，又没有迂回运输，那么该流向图就是最优流向图，对应的调运方案就是最优方案1．对流运输

在物资调运流向图中，如果在一条边上同时标有两个相反的流向，就称在这条边上存在对流运输。如果一个物资调运流向图中的任何一条边上都没有对流，就称该流向图无对流。(5)(5)(10)(10)(5)(10)(5)510105304050A2B2B1A1510105304050A1B2B1A22．迂回运输

在交通图成圈的情况下，物资调运流向图中，有些流向画在圈内，称为内圈流向；有些流向画在圈外，称为外圈流向。内圈流向对应的各边边长之和称为内圈长，记为L内；外圈流向对应的各边边长之和称为外圈长，记为L外；

该圈全部边长之和称为全圈长或总圈长，记为L总。在流向图的某一个圈上：

称在该圈上有迂回运输。如果或如果一个物资调运流向图中的任何一个圈上都没有迂回，就称该流向图无迂回。10503030B1B2A1A22344(20)(10)(30)10503030B1B2A1A22344(30)(20)(10)L总=4+4+3+2=13L内=4+3=7三、图上作业法的一般步骤与方法

借助交通示意图编制既无对流又无迂回的物资调运流向图，求得最优物资调运方案的一种方法步骤:

(1)编制无对流流向图；

(2)检查有无迂回：若无迂回，已得到最优流向图；若有迂回，转为下一步；

(3)利用交通图进行调整，重复第(2)步，直至没有迂回为止；

(4)根据最优流向图制定最优调运方案。1．交通图不成圈的情况

例1有某种物资17万吨，由Al、A2、A3、A4出发，发量分别为5万吨、2万吨、3万吨、7万吨；收点是Bl、B2、B3、B4，收量分别为8万吨、1万吨、3万吨、5万吨。收发平衡。交通图如下图所示。问应如何调运，可使周转量最小？15385237A1A2A3A4B1B2B4B315385237A1A2A3A4B1B2B4B3(7)(5)(1)(2)(1)(2)(5)

(1)作无对流流向图

方法：由各端点开始，由外向里，逐步进行各收发点之间的供求平衡，标明物资的流向和流量。(2)依最优流向图编制最优调运方案175318收量（万吨）752A43111A322A255A1发量（万吨）B4B3B2B1收点发点2．交通图中有圈的情况

例2有某种物资21万吨，由发点A1、A2、A3、A4发出，发量分别为5万吨、8万吨、2万吨、6万吨；收点为B1、B2、B3收量分别为8万吨、7万吨、6万吨，收发量平衡。交通图如下图所示。问应如何调运，可使吨公里最小?687582612211