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

1、表上作业法 图上作业法,第三章 运输问题的特殊解法(Transportation Problem),第一节 运输问题的表上作业法,一、运输问题的数学模型及其特点,设某种物品有m个产地A1 , A2 , , Am ，各产地 的产量分别是a1 , a2 , , am；有n个销地Bl , B2 , , Bn ,各销地的销量分别为bl , b2 , , bn。假定从产地 Ai (i1,2,m) 向销地Bj ( j1,2,n) 运输单位物品 的运价是cij，问怎样调运这些物品能使总运费最小? 这是由多个产地供应多个销地的单品种物资运 输问题。为直观清楚起见，可将数据汇总于产销平 衡表和单位运价表中：,（

2、1）产销平衡时,矩 阵 形 式,（2）产大于销时,（3）产小于销时,特征 运输问题的基本可行解中应包括 m+n-1个基变量 平衡运输问题必有可行解，也必有最优解,二、表上作业法的思路和步骤,步骤：1）确定初始调运方案 2）解的最优性判断 3）调整方案 4）重复2）3）步，直到找到最优方案,找到初始基可行解,最优性判断,调整找到新的基可行解,重复2、3步直到找到最优解,例1 某部门有3个生产同类产品的工厂（产地）， 生产的产品由4个销售点出售，各工厂的有关资料 如下表，问应怎样调运才使总运费最少?,（一）确定初始调运方案,解题步骤： （1）在运价表中找到最小运价c1k （2）将的Al 产品给Bk

3、 若al bk，则将al 改写为al -bk，划掉bk，同时将运价表中k 列的运价划掉 若al bk，则将bk改写为bk-al，划掉al，同时将运价表中l 行的运价划掉 （3）如此重复(1)、(2)，直到分配完毕,对应的目标函数值为： z34123十13十2146十5392(元),3,1,4,6,3,3,3,1,3,4,3,2、西北角法 思路：该法优先满足运输表中西北角上空格的供销需求,3,4,2,2,3,6,对应的目标函数值为： z33114十92十22103十56135(元),解题步骤： （1）计算运输表中每一行和每一列的次小单位运价和最小运价之间的差值 （2）从行或列差中选择最大者，选择

4、它所在行或列中的最小元素clk，将Al的产品优先供应Bk，同时将运价表中已满足的行或列划掉。 （3）如此重复(1)、(2)，直到分配完毕,5,1,3,0,1,1,6,1,2,5,2,4,3,3,3,3,1,2,5,对应的目标函数值为： z3235十11十8346十5385(元),注： 伏格尔法除确定供求关系的原则与最小元素法不同外， 其余步骤与最小元素法相同。 与最优解的接近程度：伏格尔法、最小元素法、西北角法,2,（二）解的最优性检验,求出各非基变量的检验数，判别是否均不小于 0：如果是，则得到最优解，停止计算；否则转入下 一步,注：因为目标函数要求最小化，所以ij 0 表示运费增加。 表格

5、中有调运量的地方为基变量，空格处为非基变 量。基变量的检验数ij0，需计算非基变量的检验数 是否不小于0。,利用最小元素法形成的初始调运方案进行说明：,解题步骤： （1）编制位势表 在运输问题的单价表中的基变量处画圈，同时在表中增加一行（列位势）和一列（行位势） （2）填写位势数 任选第一个位势数填入表中，其余按ul+vk=clk填写(基变量的ij 0 ) （3）计算检验数 对运价表没画圈的cij按ij=cij(ui+vj) 计算检验数,运价表,位势表,2,-1,3,0,12,-7,11,（三）调整方案闭回路法,实质：单纯形法的换基迭代,调整步骤 （1）作第一个出现负检验数ij的闭回路； （2

6、）求调整量。=奇拐角点处的最小运量 （3）调整。 奇拐角点处的各运量均减去；偶奇拐角点处的各运量均加上；不在闭回路上的格子运量不变,-1,+1,-1,-1,+1,+1,检验数：,-1,-1,+1,+1,12,3,11,3,7,-2,0,12,3,11,5,7,4,0,检验数：,-2,-2,+2,+2,所有ij0，得到最优解 z3235十11十8346十5385(元),10,3,9,3,5,2,0,练习：某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点出售，各工厂的有关资料如下表，问应怎样调运才使总运费最少?,8,2,10,2,10,6,6,6,14,8,8,利用位势法对上述方案进

7、行检验：,2,1,0,3,10,-5,10,-2,+2,-2,+2,=2,利用位势法对上述方案进行检验：,2,2,0,2,9,-3,8,所有ij0，得到最优解，最小运费为244元。,三、关于表上作业法的几点说明,1关于初始方案中运量填为“0”的规定,在编制初始调运方案时，如果当填上运量xij后，第i行的发量已发完，同时第j列的收量已收足，此时不能把运价表中的第i行和第j列都划去，而只能划去第i行(或第j列)；此后再出现最小运价为(ckj)或(cit)时，尽管Bj已收足(或Ai已发完)，但仍要在格子xkj(或xit)上填上“0”，并把这个填“0”的格子与其他有运量的格子一样看待 当收点个数为n，

8、发点个数为m时，在方案表中，填有运量的格子数必须是m+n-1个,例如，假设一个物资调运问题的平衡表和运价表如下,试用最小元素法确定初始调运方案,3,0,2,2,4,3,0,2,2,4,2,4,2,4,2关于调整方案中运量填为“0”的规定,当奇拐角点中有多个运量都是时，那么调 整以后就会有多个奇拐点处的运量同时变为零， 这时我们规定:把最上一行、最左边那个运量变为 零的奇拐角点当作空格，而把其他几个拐角点处 的运量填作“0”，并把它们当作有运量的格子一样 看待,若一个运输问题的最优调运方案表中，某个空格(非基变量)xkt对应的检验数kt=0,那么该运输问题必有另一个最优调运方案。这个新的最优调运

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

10、销量，运价为0； 销大于产增加虚拟产地，设定假想产量，运价为0,2,1,4,2,5,1,2,3,10,21,21,14,90,7,0,15,2,3,12,18,3,0,0,4,4,2,2,7,9,1,10,10,采用伏格尔法得初始调运方案（先将运价表中的0列划去）,采用位势法进行最优性检验,0,0,3,7,-3,8,-1,3,6,计算检验数,练习 水泥调运的产销不平衡情况及运价表，如下表 所示，试求最优调运方案。,在平衡表中增加库存一列；同时在运价表也相应地增加一列，该列的运价都是零，于是就得到一个新的平衡表和运价表。,四、作物布局问题的表上作业法,例3 某农场有土地9公顷。这些土地因土壤的肥

11、沃程度和水源条件不同，可以分成三类。现在农场要在这三类土地上计划种植三种作物。各类土地面积、计划种植面积，以及各种作物在各类土地上的亩产量如下表所示。问应如何因地制宜安排作物布局，才能使作物总产量最多?,目标函数求极大,解： (1) 确定初始种植方案用最大元素法编制初始方案,1,3,1,4,1,1,0,(2) 最优方案的判别用闭回路法计算检验数,如果所有检验数0，就可判定这个方案是最优方案。否则，就要对方案进行调整,对于这个例子的初始方案，因为11=50，所以需要调整。,ij =偶拐角点亩产总和-奇拐点亩产总和,(3) 方案调整用闭回路法调整种植方案,过第一个出现的正检验数对应的空格，作一闭回

12、路；在闭回路奇拐角点的数字中找一个最小的数作为调整量；然后，在这条闭回路上，凡奇拐角点的数减去调整数，凡偶拐角点的数加上调整数，便得新的种植方案。初始方案经过调整后，得新方案如下表所示,注：也可用伏格尔法或西北角法确定初始种植方案 用位势法计算检验数,第二节 运输问题的图上作业法,一、物资调运流向图,适用范围：单位运价与运输距离成正比 （总运费最小等价于周转量最小）,交通图：收发点的大致相对位置 流向图：在交通图上， 发点用圈“”表示，发货量记在圈“”内； 收点用方框“”表示，收货量记在方框“”内； 相邻两收发点间的交通线称为一条“边”，交通线的长度称为该两点的间距或边长，其数值记在交通线的旁

13、边 物资调运的方向称为流向，用“”表示，并把“”画在交通线前进方向的右侧； 把通过的物资数量(称为流量)记“”的右侧，并加上括号,二、最优调运方案的判定标准,如果一个物资调运流向图中，既没有对流运输，又没有迂回运输，那么该流向图就是最优流向图，对应的调运方案就是最优方案,1对流运输,在物资调运流向图中，如果在一条边上同时标有两个相反的流向，就称在这条边上存在对流运输。如果一个物资调运流向图中的任何一条边上都没有对流，就称该流向图无对流。,(5),(5),(10),(10),(5),(10),(5),2迂回运输,在交通图成圈的情况下，物资调运流向图中，有些流向画在圈内，称为内圈流向；有些流向画在

14、圈外，称为外圈流向。,内圈流向对应的各边边长之和称为内圈长，记为 L内；,外圈流向对应的各边边长之和称为外圈长，记为L外；,该圈全部边长之和称为全圈长或总圈长，记为L总。,(20),(10),(30),(30),(20),(10),三、图上作业法的一般步骤与方法,借助交通示意图编制既无对流又无迂回的物资调运流向图，求得最优物资调运方案的一种方法,步骤: (1) 编制无对流流向图； (2) 检查有无迂回：若无迂回，已得到最优流向图； 若有迂回，转为下一步； (3) 利用交通图进行 调整，重复第(2)步，直至没有 迂回为止； (4) 根据最优流向图制定最优调运方案。,1交通图不成圈的情况,例1 有

15、某种物资17万吨，由Al、A2、A3、A4出发，发量分别为5万吨、2万吨、3万吨、7万吨；收点是Bl、B2、B3、B4，收量分别为8万吨、1万吨、3万吨、5万吨。收发平衡。交通图如下图所示。问应如何调运，可使周转量最小？,(7),(5),(1),(2),(1),(2),(5),(1) 作无对流流向图 方法： 由各端点开始，由外向里，逐步进行各收发点之间的供求平衡，标明物资的流向和流量。,(2) 依最优流向图编制最优调运方案,2交通图中有圈的情况,例2 有某种物资21万吨，由发点A1、A2、A3、A4发出，发量分别为5万吨、8万吨、2万吨、6万吨；收点为B1、B2、B3收量分别为8万吨、7万吨、6万吨，收发量平衡。交通图如下图所示。问应如何调运，可使吨公里最小?,(1) 作无对流的流向图,具体作法是：“用丢边破圈”的方法，丢一条边，破 一个圈，直至把有圈的交通图变成不成圈的交通图；然后在不成圈的新交通图上作无对流的流向图。(选择最长的边丢掉),4,3,