(精选)运输问题的表上作业法课件.pptVIP

Chapter 06 中文资料——运输问题的表上作业法 内容 运输问题及其数学模型 表上作业法 基本步骤 初始解的确定方法 解的最优性检验 解的改进 运输问题及其数学模型 运输问题 单一品种 m个产地S1,S2,…,Sm，产量分别为s1,s2,…,sm； n个销地D1,D2,…,Dn，销量分别为d1,d2,…,dn ； 从产地Si(i=1,2,…,m)向销地Dj(j=1,2,…,n)运输单位物品的运价是cij; 问题：如何调运物品才能使总运费最小？ 表上作业法 基本步骤 1按某种规则找出一个初始解； 最小元素法 西北角法 沃格尔（Vogel）法 拉塞尔（Russell）法 2对解作最优性判别； 若不是最优，则在运输表上进行改进，得到新解，重复第2步； 若为最优解，则中止。 初始解的产生办法 最小元素法：优先满足单位运价最小的供销业务； 西北角法：优先满足运输表西北角（左上角）空格的供销需求； 沃格尔（Vogel）法：优先满足罚数最大的行（列）中单位运价最小的供销业务。 罚数：行（列）中单位运价最小和次小两个数的差值的绝对值 该方法常可以得到近似最优解 拉塞尔（Russell）法：优先满足行列最大差额和的单元的供销业务。 解的最优性检验 ——闭回路法（cycle method） 对所有未填数字的空格（非基变量），先要找出它在运输表上的闭回路。 计算闭回路的检验数。 若检验数为负，说明解非最优 若检验数全为非负，说明解最优 运价为15，故增加15 减少17 增加13 减少13 目标函数总变化：15-17+13-13=-2，即增加(2,5)一单位运量可使总运费降低2单位。 解的改进 换入量的确定：检验数为负数且绝对值最大的那个空格为换入量； 换出量的确定： 以闭合回路顺时针方向，空格为第1个奇数顶点，编号为1，依次对所有顶点编号。 可分为奇数顶点和偶数顶点 偶数顶点中的运输量最小顶点，作为空格所要增加的运量 奇数顶点和偶数顶点的计算 几点说明 换入变量以负的检验数中最小的那个； 最优解出现时，若有某非基变量对应的检验数为零，则无穷多最优解； 退化的处理 运输问题的退化 运输表 　 销地 D1 D2 D3 产量 产地 　 S1 　 8 　 5 　 7 4 　 　 　 　 　 　 S2 　 9 　 4 　 6 4 　 　 　 　 　 　 S3 　 1 　 3 　 2 3 　 　 　 　 　 　 销量 3 2 6 　 3 2 2 4 43+3-1=5，问题出现退化！ 退化的处理（第1步） 运输表 　 销地 D1 D2 D3 产量 产地 　 S1 　 8 　 5 　 7 4 　 　 　 　 　 　 S2 　 9 　 4 　 6 4 　 　 　 　 　 　 S3 　 1 　 3 　 2 3 　 　 　 　 　 　 销量 3 2 6 　 3 0 2 2 4 +8 -1 =2 +2 -7 2 0 4 退化的处理（第2步） 运输表 　 销地 D1 D2 D3 产量 产地 　 S1 　 8 　 5 　 7 4 　 　 　 　 　 　 S2 　 9 　 4 　 6 4 　 　 　 　 　 　 S3 　 1 　 3 　 2 3 　 　 　 　 　 　 销量 3 2 6 　 3 0 2 2 4 2 0 4 5 2