《广工管理运筹学第三章运输问题.ppt》由会员分享，可在线阅读，更多相关《广工管理运筹学第三章运输问题.ppt（41页珍藏版）》请在三一办公上搜索。
1、第三章 运输问题,运输问题的表示网络图、线性规划模型、运输表初始基础可行解西北角法、最小元素法非基变量的检验数闭回路法、对偶变量法确定进基变量，调整运量，确定离基变量,运输问题的提出,运输问题的直接背景是单一品种的物质的运输调度问题，其典型情况是：设某物品有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,问怎样调运这些物品才能使得总运费最小？,运输问题的表示网络图,产地,销地,若 则称该问题为平衡运输问题，否则称为非平衡运输问题。,
2、运输问题的表示表格表示,这个表常称为运输表,运输问题的数学模型,平衡问题的数学模型为,各产地运出的物资数量等于其产量,各销地接受的物资数量等于其销量,其中,运输问题数学模型的特点,运输问题一定存在最优解实际上 是平衡运输问题的一个可行解。此外由于目标函数有下界，因此平衡运输问题存在最优解。,运输问题系数矩阵的特点,m,n,上述矩阵的列向量具有形式,第i个,第(m+j)个,因此运输问题约束条件系数矩阵的元素只能是0或1，对应变量xij列除了第i个与第(m+j)个分量为1外，其它分量均为零,此外产销平衡运输问题的数学模型还具有特点：所有约束条件都是等式前m个约束条件的和等于后n个约束条件的和（可以
3、证明尽管有m+n个约束条件，但独立的约束条件只有m+n-1个）,运输问题的例子(p.85 例1)表格表示,运输问题的例子线性规划模型,供应地约束,需求地约束,运输问题的解,运输问题的解可以表示为X=(xij),它表示一个运输方案，其中xij表示从产地Ai到销地Bj 运送的物质数量在用运输表表示运输问题时，也常将xij取的值填入对应的格子表示一个解。但是对基可行解，通常仅将基变量取的值填入相应的格中，称之为数字格，而对应着非基变量（其值为零）的格子，则不填数字，称之为空格。注：在一个基可行解中，所有mn个变量（格子）中，只有m+n-1个基变量（数字格）,例1 的一个解,这是一个基可行解，注意数字
4、格个数，以及每行数字的和及每列数字格的和。,求解运输问题的表上作业法,求初始基可行解（初始调运方案）,西北角法最小元素法沃格尔法,初始基可行解西北角法,8,8,6,4,8,14,初始基可行解最小元素法,8,2,10,14,8,6,沃格尔（Vogel）法,14,8,8,12,2,4,行罚数,列罚数,检验数的计算,两种方法：闭回路法和对偶变量法闭回路法的原理：非基变量的检验数等于非基变量增加一个单位时，目标函数的改变量闭回路：从一个空格出发，按水平或垂直方向划线前行，遇到一个合适的数字格转90度，继续这样划线，直到回到出发的空格为止，就得到该空格的闭回路。每个空格都存在唯一的闭回路。,之所以考虑闭
5、回路是因为不能单独调整一个格子的运输量，必须在闭回路的各个拐角的格子上运输量都作相应调整,检验数的计算闭回路法（1）,8,2,10,14,8,6,1,检验数的计算闭回路法（2）,8,2,10,14,8,6,1,2,检验数的计算闭回路法（3）,8,2,10,14,8,6,1,2,1,检验数的计算闭回路法（4）,8,2,10,14,8,6,1,2,1,-1,检验数的计算闭回路法（5）,8,2,10,14,8,6,1,2,1,-1,10,检验数的计算闭回路法（6）,8,2,10,14,8,6,1,2,1,-1,10,12,检验数的计算对偶变量法,对偶变量法也称为位势法，它是利用运输问题的对偶问题求检
6、验数。设运输问题的对偶变量矩阵为则对偶问题为,利用单纯形法的矩阵表示可知，变量xij的检验数可以表示为,另一方面，对于(m+n-1)个基变量而言，检验数等于零，故可以得到包含(m+n)个变量的(m+n-1)个方程,由该方程组求出对偶变量后即可计算出所有的检验数。通常指定u1=0.,检验数的计算对偶变量法,8,2,10,14,8,6,u1=0,v3=4,v4=11,u2=-1,u3=-5,v1=3,v2=10,1,2,1,-1,10,12,解的改进,8,2,10,14,8,6,-1,解的改进,8,12,14,8,4,2,解的改进,8,12,14,8,4,2,u1=0,v3=4,v4=11,u2=
7、-2,u3=-5,v1=4,v2=10,最优解（最优调运方案）,8,12,14,8,4,2,最小运费：,表上作业法的几个问题,换入变量的确定：选取最小的检验数对应的空格为换入格退化（两种情况）：确定初始调运方案时与解的改进时无穷多个最优解的判别：最优解中空格的检验数出现了为零的情况。,产销不平衡的运输问题,解决的基本思路：将其转化为产销平衡的运输问题求解,产大于销的运输问题,这时有,，数学模型为,处理的办法为增加一个假想的销地Bn+1，其销量为,各个产地运送物质到假想销地的单位运价为零，即ci(n+1)=0,假想的销地,这时有,，数学模型为,销大于产的运输问题,处理的办法为增加一个假想的产地Am+1，其产量为,假想产地运送物质到各个销地的单位运价为零，即c(m+1),1=0,假想的产地,
