新运输问题讲解

《新运输问题讲解》由会员分享，可在线阅读，更多相关《新运输问题讲解（69页珍藏版）》请在金锄头文库上搜索。

1、第4章 运输问题 运输问题是一类重要而又特 殊的线性规划问题，它具有 特殊的结构，因而可以找到 比单纯形法更具有针对性也 更简便的方法表上作业 法。 第4章 运输问题 v运输问题的数学模型 v运输问题的表上作业法 v产销不平衡的运输问题的求解 v运输问题的应用 例 某工厂经销甲产品它下设三个加工厂。每日的产量 分别是：A1为吨， A2为吨，A3为吨该公司把这 些产品分别运往四个销售点各销售点每日销量为：B1 为吨，B2为吨，B3为吨， B4为吨已知从各个 加工厂到各销售点的单位产品的运价, 问该公司应如何调 运产品,在满足各销点的需要量的前提下,使总运费最少. 销地 单位运价 产地 产量 31

2、13107 19284 741059 销量3656 1 运输问题的数学模型 销地 运价 产地 产 量 销 量 一 产销平衡的运输问题的数学模型 二 产销平衡运输问题的结构特点和性质 1 产销平衡的运输问题（4.1）必有最优解。 2 若记 矩阵表示的平衡运输问题模型为 系数列向量 去掉A的第一行，并取如下m+n-1列，得到m+n-1阶 子式 所以 r(A)=m+n-1. 2 表上作业法 步骤： .找出初始基本可行解（初始调运方案，一 般m+n-1个数字格）（西北角法、最小元素法、 伏格尔法）； .求出各非基变量（空格）的检验数，判别 是否达到最优解。如果是，停止计算，否则转入 下一步（用闭回路法

3、、位势法计算检验数）； .改进当前的基本可行解（确定换入、换 出变量），用闭回路法调整； .重复. ，直到找到最优解为止。 v西北角法 v最小元素法 v伏格尔法 一、初始方案的给定 1. 最小元素法 基本思想是就近供应，即从单位运价表中最小的运 价处开始确定供销关系，依次类推，直到求出全部方案 第一步： 第二步： 第三步： 第四步： 第五步： 第六步： 这时单位运价表中所有元素已经都划掉了，产销平 衡表中数字就是一个调运方案，这个方案的总费用为： 在选定最小元素后，如果该元素所在行的产量与 所在列的销量相同，这时须同时划掉一行一列，并在 该行或列上最小元素对应位置之外添加一个0。 即下 述例题

4、表格中红色的零，需要选择且仅选择一个保留 。 2. Vogel 法 用最小元素法给定初始方案只从局部观点考虑就近供 应，可能造成总体的不合理。 Vogel 法的步骤： 1. 从运价表上分别找出每行与每列的最小的两个元 素之差； 2. 从差值最大的行或列中找到最小运价确定供需关 系和供应数量； 3. 当产地或销售地中有一方数量上供应完毕或得到 满足时，划去运价表中对应的行或列； 4. 重复步骤1、2、3，直到划去所有元素为止。 v闭回路法 v位势法（利用对偶理论中的互补松弛性） 二、最优性检验（计算空格检验数） 1.闭回路法 闭回路是指调运方案中由一个空格，和有数字的格， 用水平和竖直连线包围成

5、的封闭回路。 利用前面最小元素法得到的初始方案为例： 计算x11的检验数 将上述检验数填入检验数表中： 计算 x31 的检验数 计算 x12 的检验数 以此类推，算出所有检验数： 如果检验数表中，所有数字大于等于零，则此时为最 优解，如果有小于零的，在该格所对应的调运方案表中按 闭回路进行调整。 2.位势法 仍以上例中最小元素法确定的初始调运方案为例。 第一步：将调运方案中有数字的格内数字改换 为单位运价表中对应格的运价。即由下述两表 ： 得： 第二步：在表格下方和右方增加一行和一列，并填 上一些数字，使得格中数字正好等于它所在行与所在列数 字之和。 依次计算填入各数： 最终得： 将 vi 与

6、 uj 相加求出空格处数字： 用单位运价表中数字减掉上表中对应数字，得： 该表即检验数表，与闭回路法求出的检验数表相同。 当所得检验数不全非负的时候，仍然需要对方案进行 调整，调整方法与前面提到的相同。 三 闭回路法调整（基转换） 算出所有检验数： 检验数表中，所有数字大于等于零，则此时为最优解，如 果有小于零的，在该格所对应的调运方案表中按闭回路进 行调整。 闭回路调整： 由此得新的调运方案： 计算得该方案运费为85元。 需要对该方案每一空格 重新求出检验数，判断是否最优，如果不是最优，需继续 调整，计算后可知该方案为最优。 几个需要说明的问题 v退化情形 v最优方案不唯一的情形 例3 设有

7、三个化肥厂供应四个地区的农用化肥，假 定等量的化肥在这些地区使用效果相同，已知各化肥厂 年产量，各地区年需要量及从各化肥厂到各地区单位化 肥的运价表如下，试决定使总的运费最节省的化肥调拨 方案。 解：这是一个产销不平衡的运输问题，总产量为 160万t，四个地区最低需求为110万t ，最高需求为无限 。 当其它地区都是满足最低需求时，第地区每年最多能 分配到60万t ，这样最高需求就是210万t，大于产量。 产 销 平 衡 表 为建立产销平衡表，在表中增加一假想化肥厂D ， 其年产量为50万t 。并把各地区的最低需求和额外需求区 分开来，建立产销平衡表。 当一个产地的产量不能运往某一个销地的时候

8、，认为 运价为M(表示任意大正数)。额外需求部分的销量，由于 是否满足都可以，所以假想厂运往这些销地的运价定为0 。 单 位 运 价 表 利用表上作业法求解得： 例4 某食品公司经销主要产品之一是糖果，它下面 设有三个加工厂，每天的糖果生产量分别为： ， ， 。该公司把这些糖果分别运往四个地区 的门市部销售，各地区每天的销售量为： ， ， ， 。 如果假定： （1）每个工厂生产的糖果不一定直接发运到销售点 ，可以将其中几个产地的糖果集中起来一起运。 （2）运往各销地的糖果可以先运给其中几个销地， 再转运给其他销地。 （3）除产地、销地外，中间还可以有几个转运站， 在产地之间、销地之间或产地与销

9、地之间转运。 已知各产地、销地、中间转运站之间的单位运价， 求如何在各地之间进行调运，使总的运费最小。 产地、销地、中间转运站间运价表： 首先通过该表建立单位运价表，由于各个地点间糖 果可以相互运送，因此都可以作为产地，也都可以作为 销地来考虑，将产地和销地都扩大为11个，不能够直接 运送到的地点间运价设为M ，运送到本地的运价设为0 。 单 位 运 价 表 下面考虑如何建立产销平衡表： 1. 中间转运站产、销量的确定 由于中间转运站所有的糖果都不保留，所以我们认为 产量等于销量，同时因为在运费最小时不可能出现一批糖 果在两地见来回倒运的现象，并且已知 总产量=总销量=20t ， 所以每个转运

10、站的转运数不能超过20t ，因此可以规定产 量和销量都是20t 。而实际转运量是20t减掉运给自身的运 量。 2. 原来产地和销地的产、销量调整 由于原来的产地和销地也都起到转运站的作用，所 以同样需要在原来的产量和销量上加20t 。 建立产销平衡表： 最后利用表上作业法求解。 第3节 产销不平衡的运输问题及其求解方法 v前面所讲表上作业法，都是以产销平衡为前 提条件的；但是实际问题中产销往往是不平 衡的。就需要把产销不平衡的问题化成产销 平衡的问题。 例2 设有A1、A2、A3三个产地生产某种物资，其产 量分别为7t、5t、7t ，B1、B2、B3、B4 四个销地需要该种 物资，销量分别为2

11、t、3t、4t、6t ，又知各产销地之间的 单位运价如下表，试决定总运费最少的调运方案。 解：产地总产量为19t ，销地总销量为15t ，所以这 是一个产大于销的运输问题。此时我们假想一个销地， 这个销地的销量等于前面的总产量与总销量的差4t ，我 们也可视其为库存量，这样使得产销达到平衡。这时对 它的运费为0，现在我们建立与之对应的产销平衡表和单 位运价表。 单 位 运 价 表 产 销 平 衡 表 利用表上作业法求解得： v目标函数： v满足： 由于总的产量大于销量，就要考虑多余的物资在哪一 个产地就地储存的问题。设xi, n+1是产地Ai的储存量， 于是有： 令： 当 i=1,，m，j=1

12、,，n时 当 i=1,，m，j=n+1时 将其分别代入，得到 满足： 由于这个模型中 所以这是一个产销平衡的运输问题。 若当产大于销时， 只要增加一个假想的销地j=n+1(实际上是储存)，该销 地总需要量为 而在单位运价表中从各产地到假想销地的单位运价为， 就转化成一个产销平衡的运输问题 当销大于产时， 可以在产销平衡表中增加一个假想的产地 i=m+1，该地产量为 在单位运价表上令从该假想产地到各销地的运价， 同样可以转化为一个产销平衡的运输问题.。 例2 设有A1、A2、A3三个产地生产某种物资，其产 量分别为7t、5t、7t ，B1、B2、B3、B4 四个销地需要该种 物资，销量分别为2t

13、、3t、4t、6t ，又知各产销地之间的 单位运价如下表，试决定总运费最少的调运方案。 解：产地总产量为19t ，销地总销量为15t ，所以这 是一个产大于销的运输问题。此时我们假想一个销地， 这个销地的销量等于前面的总产量与总销量的差4t ，我 们也可视其为库存量，这样使得产销达到平衡。这时对 它的运费为0，现在我们建立与之对应的产销平衡表和单 位运价表。 单 位 运 价 表 产 销 平 衡 表 利用表上作业法求解得： 例3 设有三个化肥厂供应四个地区的农用化肥，假 定等量的化肥在这些地区使用效果相同，已知各化肥厂 年产量，各地区年需要量及从各化肥厂到各地区单位化 肥的运价表如下，试决定使总

14、的运费最节省的化肥调拨 方案。 解：这是一个产销不平衡的运输问题，总产量为 160万t，四个地区最低需求为110万t ，最高需求为无限 。 当其它地区都是满足最低需求时，第地区每年最多能 分配到60万t ，这样最高需求就是210万t，大于产量。 产 销 平 衡 表 为建立产销平衡表，在表中增加一假想化肥厂D ， 其年产量为50万t 。并把各地区的最低需求和额外需求区 分开来，建立产销平衡表。 当一个产地的产量不能运往某一个销地的时候，认为 运价为M(表示任意大正数)。额外需求部分的销量，由于 是否满足都可以，所以假想厂运往这些销地的运价定为0 。 单 位 运 价 表 利用表上作业法求解得： 例

15、3 某食品公司经销主要产品之一是糖果，它下面 设有三个加工厂，每天的糖果生产量分别为： ， ， 。该公司把这些糖果分别运往四个地区 的门市部销售，各地区每天的销售量为： ， ， ， 。 如果假定： （1）每个工厂生产的糖果不一定直接发运到销售点 ，可以将其中几个产地的糖果集中起来一起运。 （2）运往各销地的糖果可以先运给其中几个销地， 再转运给其他销地。 （3）除产地、销地外，中间还可以有几个转运站， 在产地之间、销地之间或产地与销地之间转运。 已知各产地、销地、中间转运站之间的单位运价， 求如何在各地之间进行调运，使总的运费最小。 产地、销地、中间转运站间运价表： 首先通过该表建立单位运价表

16、，由于各个地点间糖 果可以相互运送，因此都可以作为产地，也都可以作为 销地来考虑，将产地和销地都扩大为11个，不能够直接 运送到的地点间运价设为M ，运送到本地的运价设为0 。 单 位 运 价 表 下面考虑如何建立产销平衡表： 1. 中间转运站产、销量的确定 由于中间转运站所有的糖果都不保留，所以我们认为 产量等于销量，同时因为在运费最小时不可能出现一批糖 果在两地见来回倒运的现象，并且已知 总产量=总销量=20t ， 所以每个转运站的转运数不能超过20t ，因此可以规定产 量和销量都是20t 。而实际转运量是20t减掉运给自身的运 量。 2. 原来产地和销地的产、销量调整 由于原来的产地和销地也都起到转运站的作用，所 以同样需要在原来的产量和销量上加20t 。 建立产销平衡表： 最后利用表上作业法求解。 4 应用举例 例 某工厂按合同规定须于当年每个季度分