运筹学基础及应用第五版胡运权第三章

1、1 1运输问题的典例和数学模型运输问题的典例和数学模型 2表上作业法表上作业法 3产销不平衡的运输问题及其应用产销不平衡的运输问题及其应用第三章第三章 运输问题运输问题1 1运输问题的典例和数学模型运输问题的典例和数学模型 例例1 1 某食品公司经销主要产品之一是糖果，它下面某食品公司经销主要产品之一是糖果，它下面设有三个加工厂，每天的糖果生产量分别为：设有三个加工厂，每天的糖果生产量分别为： ， ， 。该公司把这些糖果分别运往四个地区。该公司把这些糖果分别运往四个地区的门市部销售，各地区每天的销售量：的门市部销售，各地区每天的销售量： ， ， ， 。已知从每个加工厂到各销售门市部每。已知从每

2、个加工厂到各销售门市部每吨糖果的运价如下表：吨糖果的运价如下表：ta71ta42ta93tb31tb62tb53tb64单位：元/t 现在把问题概括一下，在线性规划中我们研究这样现在把问题概括一下，在线性规划中我们研究这样一类运输问题：有某种物资需要调运，这种物资的计量一类运输问题：有某种物资需要调运，这种物资的计量单位可以是重量、包装单位或其他。已知有单位可以是重量、包装单位或其他。已知有m个地点可以个地点可以供应该种物资（以后通称产地，用供应该种物资（以后通称产地，用 表示），有表示），有n个地点需要该种物资（以后通称销地，用个地点需要该种物资（以后通称销地，用表示），又知这表示），又知这

3、m个产地的可供量（以后通称产量）为个产地的可供量（以后通称产量）为 （可通写为（可通写为 ），），n个销地的需要量（以后个销地的需要量（以后通称销量）分别为通称销量）分别为 （通写为（通写为 ）,从第从第i个产地个产地到第到第j个销地的单位物资运价为个销地的单位物资运价为 。 mi, 1nj, 1maaa,21ianbbb,21jbijc产销平衡表产销平衡表单位运价表单位运价表 如果用如果用 xij 代表从第代表从第 i 个产地调运给第个产地调运给第 j 个销地的个销地的物资的单位数量物资的单位数量，那么在产销平衡的条件下，使总运，那么在产销平衡的条件下，使总运费支出最小，其数学模型如下：费支

4、出最小，其数学模型如下：1111min 1, 1,0mnijijijnijijmijjiijzc xxaimxbjnx2 2表上作业法表上作业法 用表上作业法求解运输问题时，用表上作业法求解运输问题时，首先首先给出一个初始方案，给出一个初始方案，其其次次给出一个判别准则，给出一个判别准则，然后然后对初始方案进行调整，直到求出最优对初始方案进行调整，直到求出最优解。解。 由上节例子来具体说明表上作业法的步骤，首先列出产销平由上节例子来具体说明表上作业法的步骤，首先列出产销平衡表和单位运价表。衡表和单位运价表。一、初始方案的给定初始方案的给定方法很多，这里介绍两种：初始方案的给定方法很多，这里介绍

5、两种：1. 最小元素法最小元素法 基本思想是就近供应，即从单位运价表中最小的运基本思想是就近供应，即从单位运价表中最小的运价处开始确定供销关系，依次类推，直到求出全部方案价处开始确定供销关系，依次类推，直到求出全部方案第一步：第一步：第二步：第二步：第三步：第三步：第四步：第四步：第五步：第五步：第六步：第六步： 这时单位运价表中所有元素已经都划掉了，产销平这时单位运价表中所有元素已经都划掉了，产销平衡表中数字就是一个调运方案，这个方案的总费用为：衡表中数字就是一个调运方案，这个方案的总费用为：865310321344613 在选定最小元素后，如果该元素所在行的产量与在选定最小元素后，如果该元

6、素所在行的产量与所在列的销量相同，这时须同时划掉一行一列，并在所在列的销量相同，这时须同时划掉一行一列，并在该行或列上最小元素对应位置之外添加一个该行或列上最小元素对应位置之外添加一个0。 即下即下述例题表格中红色的零，需要选择且仅选择一个保留。述例题表格中红色的零，需要选择且仅选择一个保留。2. vogel 法法 用最小元素法给定初始方案只从局部观点考虑就近供用最小元素法给定初始方案只从局部观点考虑就近供应，可能造成总体的不合理。应，可能造成总体的不合理。2. vogel 法法vogel 法的步骤：法的步骤：1. 从运价表上分别找出每行与每列的最小的两个元从运价表上分别找出每行与每列的最小的

7、两个元素之差；素之差；2. 从差值最大的行或列中找到最小运价确定供需关从差值最大的行或列中找到最小运价确定供需关系和供应数量；系和供应数量；3. 当产地或销地中有一方数量上供应完毕或得到满当产地或销地中有一方数量上供应完毕或得到满足时，划去运价表中对应的行或列；足时，划去运价表中对应的行或列；4. 重复步骤重复步骤1、2、3，直到划去所有元素为止。，直到划去所有元素为止。二、最优性检验与方案的调整1.闭回路法闭回路法 闭回路是指调运方案中由一个空格，和有数字的格，闭回路是指调运方案中由一个空格，和有数字的格，用水平和竖直连线包围成的封闭回路。用水平和竖直连线包围成的封闭回路。利用前面最小元素法

8、得到的初始方案为例：利用前面最小元素法得到的初始方案为例：计算计算x11的检验数的检验数1) 1(1) 1(2) 1(3) 1(3将上述检验数填入检验数表中：将上述检验数填入检验数表中：计算计算 x31 的检验数的检验数10) 1(5) 1(10) 1(3) 1(2) 1(1) 1(7计算计算 x12 的检验数的检验数以此类推，算出所有检验数：以此类推，算出所有检验数： 如果检验数表中，所有数字大于等于零，则此时为最如果检验数表中，所有数字大于等于零，则此时为最优解，如果有小于零的，在该格所对应的调运方案表中按优解，如果有小于零的，在该格所对应的调运方案表中按闭回路进行调整。闭回路进行调整。闭

9、回路调整：闭回路调整：由此得新的调运方案：由此得新的调运方案： 计算得该方案运费为计算得该方案运费为85元。元。 需要对该方案每一空格需要对该方案每一空格重新求出检验数，判断是否最优，如果不是最优，需继续重新求出检验数，判断是否最优，如果不是最优，需继续调整，计算后可知该方案为最优。调整，计算后可知该方案为最优。注：若减少运量的地方有两个以上相等的最小数时，注：若减少运量的地方有两个以上相等的最小数时，会出现多个变会出现多个变0成空格，此时应补成空格，此时应补0到到(m+n-1)个基变量个基变量调整得新的调运方案：调整得新的调运方案：2.位势法位势法仍以上例中最小元素法确定的初始调运方案为例。

10、仍以上例中最小元素法确定的初始调运方案为例。第一步第一步：将调运方案中有数字的格内数字改：将调运方案中有数字的格内数字改换为单位运价表中对应格的运价。即由下述两换为单位运价表中对应格的运价。即由下述两表：表：得：得： 第二步第二步：在表格下方和右方增加一行和一列，并填：在表格下方和右方增加一行和一列，并填上一些数字，使得格中数字正好等于它所在行与所在列数上一些数字，使得格中数字正好等于它所在行与所在列数字之和。字之和。依次计算填入各数：依次计算填入各数：最终得：最终得：将将 vi 与与 uj 相加求出空格处数字：相加求出空格处数字：用单位运价表中数字减掉上表中对应数字，得：用单位运价表中数字减

11、掉上表中对应数字，得：该表即检验数表，与闭回路法求出的检验数表相同。该表即检验数表，与闭回路法求出的检验数表相同。 当所得检验数不全非负的时候，仍然需要对方案进行当所得检验数不全非负的时候，仍然需要对方案进行调整，调整方法与前面提到的相同。调整，调整方法与前面提到的相同。3. 3. 产销不平衡的运输产销不平衡的运输 问题及其应用问题及其应用 例例2 设有设有a1、a2、a3三个产地生产某种物资，其产三个产地生产某种物资，其产量分别为量分别为7t、5t、7t ，b1、b2、b3、b4 四个销地需要该种四个销地需要该种物资，销量分别为物资，销量分别为2t、3t、4t、6t ，又知各产销地之间的，又

12、知各产销地之间的单位运价如下表，试决定总运费最少的调运方案。单位运价如下表，试决定总运费最少的调运方案。 解解：产地总产量为：产地总产量为19t ，销地总销量为，销地总销量为15t ，所以这，所以这是一个产大于销的运输问题。此时我们假想一个销地，是一个产大于销的运输问题。此时我们假想一个销地，这个销地的销量等于前面的总产量与总销量的差这个销地的销量等于前面的总产量与总销量的差4t ，我，我们也可视其为库存量，这样使得产销达到平衡。这时对们也可视其为库存量，这样使得产销达到平衡。这时对它的运费为它的运费为0，现在我们建立与之对应的产销平衡表和单，现在我们建立与之对应的产销平衡表和单位运价表。位运

13、价表。单单 位位 运运 价价 表表产产 销销 平平 衡衡 表表利用表上作业法求解得：利用表上作业法求解得： 例例3 设有三个化肥厂供应四个地区的农用化肥，假设有三个化肥厂供应四个地区的农用化肥，假定等量的化肥在这些地区使用效果相同，已知各化肥厂定等量的化肥在这些地区使用效果相同，已知各化肥厂年产量，各地区年需要量及从各化肥厂到各地区单位化年产量，各地区年需要量及从各化肥厂到各地区单位化肥的运价表如下，试决定使总的运费最节省的化肥调拨肥的运价表如下，试决定使总的运费最节省的化肥调拨方案。方案。 解解：这是一个产销不平衡的运输问题，总产量为：这是一个产销不平衡的运输问题，总产量为160万万t，四个

14、地区，四个地区最低需求最低需求为为110万万t ，最高需求为无限。，最高需求为无限。当其它地区都是满足最低需求时，第当其它地区都是满足最低需求时，第地区每年最多能地区每年最多能分配到分配到60万万t ，这样，这样最高需求最高需求就是就是210万万t，大于产量。，大于产量。产产 销销 平平 衡衡 表表 为建立产销平衡表，在表中增加一假想化肥厂为建立产销平衡表，在表中增加一假想化肥厂d ，其年产量为其年产量为50万万t 。并把各地区的最低需求和额外需求。并把各地区的最低需求和额外需求区分开来，建立产销平衡表。区分开来，建立产销平衡表。 当一个产地的产量不能运往某一个销地的时候，认为当一个产地的产量

15、不能运往某一个销地的时候，认为运价为运价为m(表示任意大正数表示任意大正数)。额外需求部分的销量，由于。额外需求部分的销量，由于是否满足都可以，所以假想厂运往这些销地的运价定为是否满足都可以，所以假想厂运往这些销地的运价定为0。单单 位位 运运 价价 表表利用表上作业法求解得：利用表上作业法求解得： 例例4 4 某食品公司经销主要产品之一是糖果，它下面某食品公司经销主要产品之一是糖果，它下面设有三个加工厂，每天的糖果生产量分别为：设有三个加工厂，每天的糖果生产量分别为： ， ， 。该公司把这些糖果分别运往四个地区。该公司把这些糖果分别运往四个地区的门市部销售，各地区每天销售量为：的门市部销售，

16、各地区每天销售量为： ， ， ， 。ta71ta42ta93tb31tb62tb53tb64 如果假定如果假定： （1）每个工厂生产的糖果不一定直接发运到销售点，）每个工厂生产的糖果不一定直接发运到销售点，可以将其中几个产地的糖果集中起来一起运。可以将其中几个产地的糖果集中起来一起运。 （2）运往各销地的糖果可以先运给其中几个销地，）运往各销地的糖果可以先运给其中几个销地，再转运给其他销地。再转运给其他销地。 （3）除产地、销地外，中间还可以有几个转运站，）除产地、销地外，中间还可以有几个转运站，在产地之间、销地之间或产地与销地之间转运。在产地之间、销地之间或产地与销地之间转运。 已知各产地、

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