运筹学 运输问题VIP免费

第四章运输问题TransportationProblem第四章运输问题第1节运输问题及其数学模型第2节表上作业法第3节产销不平衡的运输问题及其求解方法第4节应用问题举例第1节运输问题及其数学模型一、运输问题运输问题属于线性规划问题，因为其约束方程组的系数矩阵A具有特殊的结构，所以专门介绍一种比单纯形法更简便的求解方法，以节约计算时间和费用。第1节运输问题及其数学模型例1：某食品公司经销的主要产品之一是糖果。它下面设有三个加工厂，每天的糖果生产量分别为A1－7t（吨）；A2－4t；A3－9t。该公司把这些糖果分别运往四个地区的门市部销售，各地区每天的销售量为B1－3t（吨）；B2－6t；B3－5t；B4－6t。已知从每个加工厂到各销售门市部每吨糖果的运价，如下表所示。试问该食品公司应如何调运，在满足各门市部销售需要的情况下，使总的运费支出最少。门市部加工厂B1B2B3B4产量A1A2A3749销量3656门市部加工厂B1B2B3B4A1A2A3311310192874105第1节运输问题及其数学模型二、运输问题的数学模型已知有m个生产地点（简称产地）可供应某种物资，其供应量（产量）分别为；有n个销售地点（简称销地），其需要量（销量）分别为，从到运输单位物资的运价（单位运价）为，将这些数据表示在如下页的两个表中。问应如何调运，在满足各销地销量的情况下，使总的运费支出最少？(1,2,)jBjn(1,2,)iAim(1,2,)iaim(1,2,)jbjnjBijciA第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门市部供应糖果的单位运费34111213143411111213142122232431323334112131122232132333142434min311310574936560(1231234)ijijijijzxxxxxcxxxxxxxxxxxxxxxxxxxxxxxxxxij，=，，；=，，，第1节运输问题及其数学模型产销平衡运输问题的数学模型：设xij表示从产地Ai运往销地Bj的产品数量mniji=1j=1（a=b）1111min12120mnijijijnijijmijjiijzcxxaimxbjnx，=，，，，=，，，第1节运输问题及其数学模型特征（1）决策变量：m×n（2）约束方程：m＋n；都是等式约束（3）目标函数：最小化（4）约束方程组系数矩阵A①A中只有数字0或1②A的每一列只有两个非零元素1（5）各产地产量之和等于各销地销量之和（6）基变量：m＋n－1（7）对于产销平衡的运输问题，必有可行解和最优解mniji=1j=1（a=b）第1节运输问题及其数学模型111213142122232431323334111100000000000011110000000000001111100010001000010001000100001000100010000100010001APPPPPPPPPPPPA第2节表上作业法一、表上作业法的解题思路表上作业法的实质是单纯形法在求解运输问题时的一种简化方法，属于单纯形法，又称为运输单纯形法。基可行解最优否结束换基是否第2节表上作业法二、表上作业法的特点表上作业法是一种迭代法用表上作业法求解运输问题，直接在表上进行，不必写出数学模型第2节表上作业法三、表上作业法的解题步骤（一）找出初始基可行解：在产销平衡表上找出(m+n-1)个数字格，形成初始产销平衡表方法（二）求非基变量检验数：计算初始产销平衡表中空格的检验数，判别是否达到最优解，如果已达到，停止计算；否则转入3方法（三）确定换入变量和换出变量，找出新的基可行解方法：闭回路调整法（四）重复（二）～（三），直到求出最优解最小元素法伏格尔法（Vogel法）闭回路法位势法（对偶变量法）第2节表上作业法（一）确定初始基可行解方法一：最小元素法1、基本思路从运费上考虑，优先安排单位运价最小的产地和销地之间的运输业务，最大限度地满足其产销量，从而实现“...