第四章(肖健华).ppt

1、1,第四章 运输问题,2,运输问题一般是研究把某种商品从若干个产地运往若干个销地而使总运费最小的一类问题。 从本质上讲，运输问题是一类线性规划问题，因此可采用单纯形法进行求解。 结合运输问题的特殊性，提出表上作业法。 表上作业法也可应用于类似问题。,3,4.1 运输问题的典例和数学模型,例1：某食品公司经销的主要产品之一是糖果。它下面设有三个加工厂A1、A2、A3，每天糖果的产量分别为7吨、4吨和9吨，该公司把这些糖果分别运往四个地区的门市部B1、B2、B3、B4进行销售，各地区每天的销量分别为3吨、6吨、5吨和6吨。已知从各个加工厂到各销售门市部每吨糖果的运价表如下所示，问该食品公司应如何调

2、运，在满足各门市部销售需要的情况下，使总的运费支出为最少？,4,5,例1中总产量等于总销量，属于产销平衡问题 此外，现实中还存在产销不平衡的问题，以后再介绍。,6,运输问题的一般描述,7,产销平衡表与单位运价表,运输问题中的数据通常用产销平衡表和单位运价表来表示，实际应用中有时也将这两个表合在一起，如例1,8,思考题,画出例1的产销平衡表和单位运价表,9,运输问题的数学模型,现用xij表示从第i个产地到第j个销地的物资数量，那么在产销平衡的条件下，使总运费支出最小的目标函数可表示为：,10,问题：模型中有多少个基变量？,11,4.2 运输问题的求解方法： 表上作业法,表上作业法步骤 找出初始基

3、可行解，即要在mn阶产销平衡表上给出m+n-1个有数字格（基变量）； 求出各非基变量（空格）的检验数，判断当前的基可行解是否是最优解，如已得到最优解，则停止计算，否则，转到下一步； 确定入基变量，若minij|ij 0=lk，那么选取xlk为入基变量；,12, 确定出基变量，找出入基变量的闭合回路，在闭合回路上最大限度地增加入基变量的值，那么闭合回路上首先减少为“0”的基变量即为出基变量； 在表上用闭合回路法调整运输方案； 重复步骤，直到得到最优解。,13,综合上述步骤，表上作业法在求解运输问题中，主要要解决以下三个问题： 如何给出初始基可行解：最小元素法和伏格尔法 如何对解进行检验，即判断解

4、是否最优：闭合回路法和位势法 如何对方案进行调整：闭合回路法,14,4.2.1 确定初始基可行解,最小元素法： 基本思想是就近供应，即从单位运价表中最小的运价处开始确定供销关系，依此类推，一直到给出完整方案为止。,15,用最小元素法求例1的初始调运方案，并计算对应的运价。,16,例2,某电视机厂有三个分厂，生产同一种彩电，供应该厂在市内的四个门市部销售，已知三个分厂的日生产能力分别是50，60，50台，四个门市部的日销售量分别是40，40，60，20台。各分厂运往各门市部的运费如表，试用最小元素法确定初始方案。,17,同时划去行和列的处理方法：补零,18,最小元素法的缺点,给定初始方案只从局部

5、观点考虑就近供应，可能造成总体的不合理。为了节省一处的费用，有时造成在其它处要多花几倍的运费。,19,伏格尔法,指导思想：考虑到一产地假若不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多，因而对差额最大处，就应当采用最小运费调运。 步骤：从运价表上分别找出每行与每列的最小的两个元素之差，再从差值最大的行或列中找出最小运价确定供需关系和供应数量。当产地和销地中有一方数量上供应完毕或得到满足时，划去运价表中对应的行或列，再重复以上的步骤。,20,用伏格尔法求例1的初始调运方案，并计算对应的运价。,记住：当最大差存在两个相等时，原则为最大差对应

6、最小元素最小 如需要补零，与最小元素法一致,21,一般地，当产销地的数量不多时，伏格尔法给出的初始解有时就对应着最优方案，所以，伏格尔法有时就用作求运输问题最优方案的近似解。 事实上，伏格尔法比最小元素法要复杂，但所得到的初始解的质量也更好一些。,22,例3：试用伏格尔法直接给出下述运输问题的近似最优解（下表含产销平衡表和单位运价表）,23,4.2.2 基可行解的最优性检验及方案的调整,检验的方法 闭合回路法 位势法,24,1. 闭回路法,运输问题的闭回路是指调运方案中由一个空格和若干个有数字格的水平和垂直连线包围的封闭曲线。 对于任一非基变量，存在且仅存在一个闭回路。 构建闭回路的目的是要计

7、算解中各非基变量（对应空格）的检验数。,25,令某非基变量取值为1，通过变化原基变量的值找出一个新的可行解，将其同原来的基可行解目标函数值的变化比较。 如果检验数表中所有数字大于等于零，表明对调运方案作出任何改变将导致运费不会减少，即给定的方案是最优方案。 如果检验数表中，存在为负的检验数，说明方案需要进一步改进。,检验数的计算方法：,26,例1中，利用最小元素法得到的初始调运方案如下左，右为运价表，应用闭合回路法计算检验数表。,27,调运方案调整方法,从检验数为负值的格出发（当有两个以上负检验数时，从绝对值最大的负检验数出发），作一条除空格外其余顶点均为有数字格组成的闭合回路。 在这条闭回路

8、上，对运量作最大可能的调整。特别强调：调整量可能是0. 通过闭回路法获得的解是否为最优解？进一步对新方案的每一空格求出检验数。,28,完成例1,29,例4：判断表1和表2给出的调运方案能否用作表上作业法求解时的初始解？为什么,30,31,例5. 用表上作业法求下表中给出的运输问题的最优解,32,2. 位势法,闭合回路法求检验数存在的不足：需要对每一个空格寻找闭合回路，以及根据闭合回路求出每一个空格的检验数。当一个运输问题的产地和销地较多时，求检验数的工作将十分繁重。 用位势法求检验数的思路与步骤,33,例1中，利用最小元素法得到的初始调运方案如下左，右为运价表，应用位势法计算检验数表。,34,

9、例：某百货公司去外地采购A、B、C、D四种规格的服装，数量分别是A：1500套，B：2000套，C：3000套，D：3500套。有三个城市可供应上述规格服装，供应数量分别城市I：2500套，城市II：2500套，城市III：5000套。由于这些城市的服装质量、运价及销售情况不一，预计销售后的利润（元/套）也不同，详见表，请帮助该公司确定一个预期盈利最大的采购方案。,35,表上作业法的步骤,36,4.3 产销不平衡的运输问题及应用,37,4.3.1 产大于销：数学模型,38,39,例1：,设有A1、A2、A3三个产地生产某种物资，其产量分别是7t、5t、7t。B1、B2、B3、B4四个销地需要该

10、种物资，需求量分别是2t、3t、4t、6t。又知各产销地的单位运价表如右，试决定总运费最小的调运方案。,40,例2：,某地区有两个粮库A1、A2及三个粮店B1、B2、B3，粮库可发运粮食数量及地区间单位运价Cij如表，试求这个问题的最优调运方案。要求：用最小元素法求初始运输方案；位势法求检验数。,41,4.3.2 销大于产的问题,42,例2：,求右表所示的销大于产的运输问题,43,4.3.3 运输问题的应用举例,例1：设有三个化工厂供应四个地区的农用化肥。假定等量的化肥在这些地区的使用效果相同，已知各化肥厂的年产量、各地区的年需求量及各化肥厂到各地区单位化肥的运价如表所示，试决定使总的运费最小的化肥调拨方案。,44,例2 可转化为运输问题的其它线性规划问题,某车间今