运输问题的表上作业法ppt课件.ppt

Chapter 06 中文资料——运输问题的表上作业法内容n运输问题及其数学模型n表上作业法n根本步骤n初始解确实定方法n解的最优性检验n解的改良运输问题及其数学模型运输问题n单一种类nm个产地S1,S2,…,Sm，产量分别为s1,s2,…,sm；nn个销地D1,D2,…,Dn，销量分别为d1,d2,…,dn ；n从产地Si(i=1,2,…,m)向销地Dj(j=1,2,…,n)运输单位物品的运价是cij;n问题：如何调运物品才干使总运费最小？数学模型产销平衡与产销不平衡n产销平衡：n产销不平衡：留意：对于产销平衡问题，约束条件有一个是多余的表上作业法根本步骤n1按某种规那么找出一个初始解；n最小元素法n西北角法n沃格尔〔Vogel〕法n拉塞尔〔Russell〕法n2对解作最优性判别；n假设不是最优，那么在运输表上进展改良，得到新解，反复第2步；n假设为最优解，那么中止初始解的产生方法n最小元素法：优先满足单位运价最小的供销业务；n西北角法：优先满足运输表西北角〔左上角〕空格的供销需求；n沃格尔〔Vogel〕法：优先满足罚数最大的行〔列〕中单位运价最小的供销业务n罚数：行〔列〕中单位运价最小和次小两个数的差值的绝对值n该方法常可以得到近似最优解n拉塞尔〔Russell〕法：优先满足行列最大差额和的单元的供销业务。

解的最优性检验 ——闭回路法〔cycle method〕n对一切未填数字的空格〔非基变量〕，先要找出它在运输表上的闭回路n计算闭回路的检验数n假设检验数为负，阐明解非最优n假设检验数全为非负，阐明解最优运价为15，故添加15减少17添加13减少13目的函数总变化：15-17+13-13=-2，即添加(2,5)一单位运量可使总运费降低2单位解的改良n换入量确实定：检验数为负数且绝对值最大的那个空格为换入量；n换出量确实定：n以闭合回路顺时针方向，空格为第1个奇数顶点，编号为1，依次对一切顶点编号n可分为奇数顶点和偶数顶点n偶数顶点中的运输量最小顶点，作为空格所要添加的运量n奇数顶点和偶数顶点的计算几点阐明n换入变量以负的检验数中最小的那个；n最优解出现时，假设有某非基变量对应的检验数为零，那么无穷多最优解；n退化的处置运输问题的退化运输表　销地D1D2D3产量产地　S1　8　5　74　　　　　　S2　9　4　64　　　　　　S3　1　3　23　　　　　　销量326　32244<3+3-1=5，问题出现退化！退化的处置〔第1步〕运输表　销地D1D2D3产量产地　S1　8　5　74　　　　　　S2　9　4　64　　　　　　S3　1　3　23　　　　　　销量326　30224+8-1=2+2-7204退化的处置〔第2步〕运输表　销地D1D2D3产量产地　S1　8　5　74　　　　　　S2　9　4　64　　　　　　S3　1　3　23　　　　　　销量326　3022420452。