资源描述：
《运筹学课件第三章运输问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第三章运输问题一、学习目的与要求1、掌握表上作业法及其在产销平衡运输问题求解中的应用2、掌握产销不平衡运输问题求解方法二、课时6学时第一节运输问题及其数学模型一、运输问题的数学模型单一品种运输问题的典型情况：设某种物品有m个产地A1,A2,…,Am，各产地的产量分别是a1,a2,…,am；有N个销地B1,B2,…,Bn，各销地地销量分别为b1,b2,…,bn。假定从产地Ai(i=1,2,…,m)向销地Bj(j=1,2,…,n)运输单位物品的运价是cij，问怎样调运这些物品才能使总运费最小？为直观清楚起见，列出运输表：销地产地B1B2…Bn产量A1c1
2、1c12c1na1x11x12x1nA2c21c22c2na2x21x22x2n…c11c12c1n…x11x12x1nAmcm1cm2cmnamxm1Xm2xmn销量b1b2…bn表中xij为由产地Ai到销地Bj的物品数量，cij表示产地Ai到销地Bj的单位运价。如果运输问题的总产量等于其总销量，即有则称该运输问题为产销平衡运输问题；反之，称为产销不平衡运输问题。产销平衡运输问题的数学模型如下：这就是运输问题的数学模型，它包含m×n个变量，(n十m)个约束方程．其系数矩阵的结构比较松散，且特殊。二、运输问题数学模型的特点1、运输问题有有限最优解，即
3、必有最优基本可行解2、运输问题约束条件的系数矩阵A的秩为(m+n-1)该系数矩陈中对应于变量xij的系数向量pij，其分量中除第i个和第m十j个为1以外，其余的都为零．即Aij＝(0…1…1…0)’=ei+em+j对产销平衡的运输问题具有以下特点：(1)约束条件系数矩阵的元素等于0或1(2)约束条件系数矩阵的每一列有两个非零元素，对应于每一个变量在前m个约束方程中出现一次，在后n个约束方程中也出现一次。此外，对于产销平衡问题，还有以下特点(3)所有结构约束条件都是等式约束(4)各产地产量之和等于各销地销量之和第二节用表上作业法求解运输问题解题步骤第1
4、步：确定初始基本可行解。第2步：最优性判别，若最优准则σij≥0，则当前解最优，计算停止，否则转第3步。第3步：取一个检验数最小的非基变量做进基变量。第4步：调整当前基本可行解，转第2步一、确定初始基本可行解（初始调运方案）以实例介绍：例某部门有3个生产同类产品的工厂(产地),生产的产品由4个销售点(销地)出售，各工厂的生产量、各销点的销售量（假定产位均为t）以及各工厂到各销售点的单位运价（元/t）于下表中，要求研究产品如何调运才能使总运费最小？销地产地B1B2B3B4产量A141241116A22103910A38511622销量8141214A最
5、小元素法销地产地B1B2B3B4产量A141241116106A2210391082A38511622148销量8141214总运费（目标函数）：这个解满足约束条件，其非零变量的个数为6（等于m+n-1=3+4-1=6）。B西北角法销地产地B1B2B3B4产量A14124111688A2210391064A38511622814销量8141214总运费（目标函数）：这个解满足约束条件，其非零变量的个数为6（等于m+n-1=3+4-1=6）。C沃格尔（Vogel）法销地产地B1B2B3B4产量行罚数12345A14124111600071124A221
6、039101116682A3851162212148销量814121448列罚数125132213321241252总运费（目标函数）：二、解的最优性检验1、闭回路法销地产地B1B2B3B4产量A141241116106A2210391082A38511622148销量8141214检验数表销地产地B1B2B3B4产量A112A21-1A31012销量由于，故知解不是最优解。2、对偶变量法（也称位势法）对产销平衡问题，若用分别表示前m个约束条件与后n个约束条件的对偶变量，即有对偶变量这时对偶问题的对偶规划写成由上一章知道，线性规划问题变量xj的检验数
7、可表示为由此可写出运输问题某变量xij的检验数如下：现设我们已得到解到了运输问题的一个基可行解，其基变量是由于基变量的检验数等于零，故对这组基变量可写出方程组这个方程组有m+n-1个方程。解以上方程组，可得解（上方程组解不唯一），此方程组解称为位势。由上章知当每个达到最优解。例用位势法对上例最小元素法有的解作最优性检验。销地产地B1B2B3B4产量uiA141241116u1106A22103910u282A38511622u3148销量814121448vjv1v2v3v4解：先建立方程组令得方程组的解：计算检验数销地产地B1B2B3B4产量uiA
8、1412411161A221039100A38511622-4销量814121448vj29310由于σ24
