第三章 运输问题

Harbin Institute of Technology,PAGE -,48,-,运筹学第三章,运输问题,运筹学,第三章 运输问题,哈尔滨工业大学 工业工程系,周宇鹏,办公电话：,86417778-604,手机：,13936135705,Email,：,zyp313,某种产品从若干个产地,(,产量,已知,),运往若干个销地,(,销量,已知,),，已知各地间运输单价，求总运费最小的运输方案。,运输问题是我国科学家,(,王元,越民义,等,),在,1959,年前率先研究讨论的，并获得了：,表上作业法,和图上作业法等重要成果。,运输问题在工商管理中有着广泛的应用，它是一类特殊的线性规划问题。,s,2,=27,s,3,=19,d,1,=22,d,2,=13,d,3,=12,d,4,=13,s,1,=14,供应量,供应地,运价,需求量,需求地,6,7,5,3,8,4,2,7,5,9,10,6,B,C,2,A,3,4,1,运输问题网络图,主要内容,一、运输问题的数学模型,二、运输问题的表上作业法,第一节 运输问题的数学模型,第三章 运输问题,一、运输问题的数学模型,1.1,运输问题线性规划模型,(1),有,m,个产地生产某物资，有,n,个地区需要该物资,令,a,1,a,2,a,m,表示各产地产量，,b,1,b,2,b,n,表示各销地的销量。,设,x,ij,表示产地,i,运往销地,j,的物资量，,c,ij,表示对应的单位运费。,一、运输问题的数学模型,1.1,运输问题线性规划模型,(2),供应地约束,需求地约束,一、运输问题的数学模型,1.2,运输问题模型的特征,(1),每一列只有两个,1,包含,m,n,个变量，,(m+n),个约束方程。其系数矩阵的结构比较,松散,。,一、运输问题的数学模型,1.2,运输问题模型的特征,(2),系数矩阵中对应于变量,x,ij,的系数向量,P,ij,，其分量中除第,i,个和第,m+j,个为,1,，其余都为零。,即,P,ij,=(0, ,1,0,0,1,0,0),T,=e,i,+e,m+j,运输问题的独立的等式约束数,=,系数矩阵的秩,=,基变量个数,=,m+n-1,，,非基变量个数,=,m*n,-,m-n+1,。,第二节 运输问题的表上作业法,第三章 运输问题,二、运输问题的表上作业法,2.1,表上作业法的计算步骤,运输问题的表示,网络图、线性规划模型、,运输表,初始基础可行解,西北角法、最小元素法、伏格尔法,(Vogel),非基变量的检验数,闭回路法、位势法、,对偶变量法,确定进基变量，调整运量，确定离基变量,二、运输问题的表上作业法,2.2,运输问题的表格表示,供应约束,需求约束,单位运价,运量,二、运输问题的表上作业法,2.3,确定初始可行基,西北角法,8,13,13,14,6,6,Z,=,146,+,88,+,134,+,62,+,610,+,136,=,350,数字格,空格,二、运输问题的表上作业法,2.3,初始可行基,最小元素法,(1),优先安排单位运价最小的产地与销地之间的运输业务,就近供应。,二、运输问题的表上作业法,2.3,初始可行基,最小元素法,(2),二、运输问题的表上作业法,2.3,初始可行基,最小元素法,(3),二、运输问题的表上作业法,2.3,初始可行基,最小元素法,(4),二、运输问题的表上作业法,2.3,初始可行基,最小元素法,(5),二、运输问题的表上作业法,2.3,初始可行基,最小元素法,(6),Z,=,16,+,28,+,195,+,134,+,122,+,133,=,232,二、运输问题的表上作业法,2.3,最小元素法实例二,二、运输问题的表上作业法,2.3,确定初始可行基,伏格尔法,0,1,1,0,1,2,2,5,1,3,2,-,1,3,0,1,-,0,1,-,伏格尔法经常用作求运输问题近似最优解。,算出每行,/,列运费最小两个元素之差，从差值最大的行,/,列找出最小运价。,2,-,1,2,2,-,1,-,第三章 运输问题,作 业 一,用伏格尔法确定下面运输问题的初始可行基：,二、运输问题的表上作业法,2.4,最优解的判定,求表中各空格（对应于非基变量）的检验数以判定当前解是否最优。,最优解的所有检验数要,:_,全部非负,检验运输方案是否是最优的方法有两种：,闭回路法,位势法,二、运输问题的表上作业法,2.4,闭回路法,(1),闭回路：,运输表中由一个空格（非基变量）和若干数字格（基变量）的水平或垂直连线构成的封闭回路。,任意非基向量可表示为基向量的,唯一,线性组合，因此运输表中通过任意空格能够找到，并且只能找到,唯一的,闭回路。,数字格检验数均为,0,，,二、运输问题的表上作业法,2.4,闭回路法,(2),5,=7-6+8-4=5,的含义就是当,x,12,增加一个单位后总费用,Z,的改变量,Z,。,二、运输问题的表上作业法,2.4,闭回路法,(3),5,5,=5-6+8-2=5,二、运输问题的表上作业法,2.4,闭回路法,(4),5,7,5,=3-6+8-2+10-6,=7,二、运输问题的表上作业法,2.4,闭回路法,(5),5,9,5,7,=7-2+10-6=9,二、运输问题的表上作业法,2.4,闭回路法,(6),5,-11,5,7,9,=5-8+2-10,=,-11,二、运输问题的表上作业法,2.4,闭回路法,(7),5,-3,5,7,9,-11,=,9-4+2-10,=,-3,当产地、销地数量很多时，寻找闭回路很困难，计算量很大。,二、运输问题的表上作业法,2.4,位势法,(1),v,4,=0,令所有数字格的,c,ij,=,u,i,+v,j,二、运输问题的表上作业法,2.4,位势法,(2),u,3,+v,4,=c,34,u,3,=6,1,2,3,4,6,7,5,3,1,14,u,1,8,4,2,7,2,8,13,6,u,2,5,9,10,6,3,6,13,u,3,=6,v,1,v,2,v,3,v,4,=0,二、运输问题的表上作业法,2.4,位势法,(3),u,3,+v,3,=c,33,v,3,=4,二、运输问题的表上作业法,2.4,位势法,(4),u,2,+v,3,=c,23,u,2,=-2,二、运输问题的表上作业法,2.4,位势法,(5),u,2,+v,2,=c,22,v,2,=6,二、运输问题的表上作业法,2.4,位势法,(6),u,2,+v,1,=c,21,v,1,=10,二、运输问题的表上作业法,2.4,位势法,(7),u,1,+v,1,=c,11,u,1,= -4,二、运输问题的表上作业法,2.4,位势法,(8),5,= 7 - (6-4) = 5,二、运输问题的表上作业法,2.4,位势法,(9),5,5,= 5 -,（,4-4,）,= 5,二、运输问题的表上作业法,2.4,位势法,(10),7,5,5,=3 -,（,0-4,）,= 7,二、运输问题的表上作业法,2.4,位势法,(11),9,5,5,7,=7 -,（,0-2,）,= 9,二、运输问题的表上作业法,2.4,位势法,(12),-11,5,5,7,9,= 5 -,（,10+6,）,= -11,二、运输问题的表上作业法,2.4,位势法,(13),-3,5,5,7,9,-11,= 9 -,（,6+6,）,= -3,二、运输问题的表上作业法,2.5,确定进基、,离基,变量,x,31,进基, minx,21,x,33,=min8,6=6,x,33,离基,-3,5,5,7,9,-11,二、运输问题的表上作业法,2.5,调整运量、二次迭代,x,14,进基, minx,11,x,34,=min14,13=13,x,34,离基,11,5,5,-4,-2,8,u,1,=7,u,2,=9,u,3,=6,v,3,=-7,v,2,=-5,v,1,=-1,v,4,=0,二、运输问题的表上作业法,2.5,调整运量、三次迭代,11,5,5,4,8,2,Z,=,16,+,28,+,195,+,134,+,122,+,133,=,232,u,1,=0,u,2,=2,u,3,=-1,v,3,=0,v,2,=2,v,1,=6,v,4,=3,第三章 运输问题,作 业 二,分别用闭回路法和位势法检验下面运输问题解的最优性，并求出最优解：,第三章 运输问题,本章小结,运输问题的数学模型及,特征,运输问题的,表上作业法,运输表,确定初始可行基,西北角法、,最小元素法、伏格尔法,(Vogel),非基变量的检验数,闭回路法、位势法,确定进基、离基变量，调整运量，迭代运算,