教案8_运输问题.ppt

1、第三章 运输问题,产销平衡运输问题的数学模型 产销平衡运输问题的表上作业法,运输问题的数学模型,表上作业法,运输问题的扩展,1 运输问题的数学模型,Bn,B2,B1,需方 供方,Am,A2,A1,供需平衡,1 运输问题的数学模型,Bn,B2,B1,需方 供方,Am,A2,A1,如何建立供需搭配，使总的运输费用最小？,供 需 平 衡 表,平衡表、运价表和二为一：,数学模型,设从Ai到Bj的物资运量为xij ，,产销平衡运输问题的数学模型。,Ai的产品全部供应出去,Bj的需求全部得到满足,m,n,约束条件或解可用产销平衡表表示:,uivj无约束 （i=1,2, ,m;j=1,2, ,n),ui,v

2、j,设ui,vj为对偶变量，对偶问题模型为,m个,n个,2 表上作业法,计算步骤：,(1) 找出初始调运方案。即在(mn)产销平衡表上给出m+n-1个数字格。(最小元素法或差值法）,(2) 求检验数。（闭回路法或位势法） 判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。,(3) 对方案进行改善，找出新的调运方案。（表上闭回路法调整）,确定m+n-1个基变量,(4) 重复（2）、（3），直到求得最优调运方案。,空格,例 运输问题供需平衡表和运价表如下，求最优调运方案。,最小元素法,3,1,4,6,3,3,.,分别计算各行、各列次小、最小运价的差额，优先在最大差额处进行供需搭配。,步

3、骤：,10 计算未划去行、列的差额；,20 找出最大差额对应的最小元素cij进行供需分配；,30 在未被划去的行、列重新计算差额。,6,6,3,6,3,3,6,3,5,1,2,2.1 最优解的判别 （检验数的求法）,闭回路：从空格出发顺时针(或逆时针)画水(或垂直)直线，遇到填有运量的方格可转90，然后继续前进，直到到达出发的空格所形成的闭合回路。,调运方案的任意空格存在唯一闭回路。,差额法方案,2.1 最优解的判别 （检验数的求法）,闭回路：从空格出发顺时针(或逆时针)画水平(或垂直)直线，遇到填有运量的方格可转90，然后继续前进，直到到达出发的空格所形成的闭合回路。,调运方案的任意空格存在

4、唯一闭回路。,最小元素法,+,-,+,-,x11为换入变量，x11增加1，运费的变化为3-1+2-3=1。这个变化就是x11的检验数，故 11=1,基变量的检验数为零(基变量xij)， ij=cij-(ui+vj),ui,vj自由变量,. 位势法 标准型运输问题的对偶问题是：,检验数,得m+n-1个方程，令某个ui ( 或vj)=0，可解出m+n个ui 和vj；由此得非基变量的检验数。,对偶变量值等于原问题的检验数,松弛变量,位势法,令v1=0, 由c21=3= u2 +v1，得 u2=3,0,1,1,2,0,1,1,2,8,-3,7,位势表,2,9,8,9,-3,-2,检验数,0,1,1,2,8,-3,7,检验数表,1,2,1,-1,10,12,24=-10，当前方案 不是最优方案。,从(p,q)空格开始画闭回路，其它转角点都是填有运量的方格，并从(p,q)空格开始给闭回路上的点按+1，-1，+1，-1编号，-1格的最小运量为调整量。,换出变量