运筹学 运输问题

《运筹学 运输问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章运输问题TransportationProblem第四章运输问题第1节运输问题及其数学模型第2节表上作业法第3节产销不平衡的运输问题及其求解方法第4节应用问题举例第1节运输问题及其数学模型一、运输问题运输问题属于线性规划问题，因为其约束方程组的系数矩阵A具有特殊的结构，所以专门介绍一种比单纯形法更简便的求解方法，以节约计算时间和费用。第1节运输问题及其数学模型例1：某食品公司经销的主要产品之一是糖果。它下面设有三个加工厂，每天的糖果生产量分别为A1－7t（吨）；A2－4t；A3－9t。该公司把这些糖果分别运往四个地区的门市部销售，各地区每天的销售量为B1－3t（吨）；B2－6

2、t；B3－5t；B4－6t。已知从每个加工厂到各销售门市部每吨糖果的运价，如下表所示。试问该食品公司应如何调运，在满足各门市部销售需要的情况下，使总的运费支出最少。门市部加工厂B1B2B3B4产量A1A2A3749销量3656门市部加工厂B1B2B3B4A1A2A3311310192874105第1节运输问题及其数学模型二、运输问题的数学模型已知有m个生产地点（简称产地）可供应某种物资，其供应量（产量）分别为；有n个销售地点（简称销地），其需要量（销量）分别为，从到运输单位物资的运价（单位运价）为，将这些数据表示在如下页的两个表中。问应如何调运，在满足各销地销量的情况下，使总的运费

3、支出最少？第1节运输问题及其数学模型产销平衡表两个表合二为一销地产地B1B2…Bn产量A1A2…Ama1a2…am销量b1b2…bn销地产地B1B2…BnA1A2…Amc11c12…c1nc21c22…c2n…………cm1cm2…cmn销地产地B1B2…Bn产量A1A2…Amc11c12…c1nc21c22…c2n…………cm1cm2…cmna1a2…am销量b1b2…bn单位运价表第1节运输问题及其数学模型例1：解：设xij为第i加工厂向第j门市部的糖果的供应量，cij表示第i加工厂向第j门市部供应糖果的单位运费第1节运输问题及其数学模型产销平衡运输问题的数学模型：设xij表示从

4、产地Ai运往销地Bj的产品数量第1节运输问题及其数学模型特征（1）决策变量：m×n（2）约束方程：m＋n；都是等式约束（3）目标函数：最小化（4）约束方程组系数矩阵A①A中只有数字0或1②A的每一列只有两个非零元素1（5）各产地产量之和等于各销地销量之和（6）基变量：m＋n－1（7）对于产销平衡的运输问题，必有可行解和最优解第1节运输问题及其数学模型第2节表上作业法一、表上作业法的解题思路表上作业法的实质是单纯形法在求解运输问题时的一种简化方法，属于单纯形法，又称为运输单纯形法。基可行解最优否结束换基是否第2节表上作业法二、表上作业法的特点表上作业法是一种迭代法用表上作业法求解运输

5、问题，直接在表上进行，不必写出数学模型第2节表上作业法三、表上作业法的解题步骤（一）找出初始基可行解：在产销平衡表上找出(m+n-1)个数字格，形成初始产销平衡表方法（二）求非基变量检验数：计算初始产销平衡表中空格的检验数，判别是否达到最优解，如果已达到，停止计算；否则转入3方法（三）确定换入变量和换出变量，找出新的基可行解方法：闭回路调整法（四）重复（二）～（三），直到求出最优解第2节表上作业法（一）确定初始基可行解方法一：最小元素法1、基本思路从运费上考虑，优先安排单位运价最小的产地和销地之间的运输业务，最大限度地满足其产销量，从而实现“就近供应”。第2节表上作业法2、求解步骤

6、第一，从单位运价表中找出最小运价，（有两个或两个以上的最小单位运价，则任选其一），比较产量和销量：产量＞销量，则划去该运价所在列；产量＜销量，则划去该运价所在行。并在初始产销平衡表上填上相应的数字。第二，从单位运价表中未被划去的运价中再找最小运价，重复第一～第二，直到单位运价表中所有运价都被划去，并找出(m+n-1)个数字格。第2节表上作业法例2：用最小元素法找出例1的初始基可行解。产销平衡表和单位运价表合二为一，如下所示：门市部加工厂B1B2B3B4产量A1A2A3311310192874105749销量3656第2节表上作业法例2：解：初始产销平衡表门市部加工厂B1B2B3B4

7、产量A1A2A3433163749销量3656第2节表上作业法3、小结（1）在初始产销平衡表上每填入一个数字，在单位运价表上就划去一行或一列（当表中只剩一个元素时，在初始产销平衡表上填数字时，在单位运价表上同时划去一行和一列）（2）在单位运价表上共划去（m＋n）条直线，（相当于单位运价表上所有cij都被划去两次）（3）在初始产销平衡表上填了（m＋n－1）个数字格，每行数字之和＝该行产量，每列数字之和＝该列销量第2节表上作业法例3：用最小元素法求出下述运输问题的初始基可