《运输问题模型.ppt》由会员分享，可在线阅读，更多相关《运输问题模型.ppt（64页珍藏版）》请在三一文库上搜索。
1、,运输问题模型,二0一0,运输问题的一般描述,设某种物资有m个产地A1,A2,Am，和n个销地B1,B2,Bn,其中Ai的产量为ai,Bj的销量为bj，产地Ai运往销地Bj的单位运价Cij,i=1,2,m;j=1,2,n. 求尽可能满足销地需求且总费用最小的运输方案。,运输问题的数学模型可以分以下3种情况讨论： 1. 产销平衡问题 2. 销大于产问题 产大于销问题,解：设产地Ai运往销地Bj的运量为,1.产销平衡问题的数学模型,产销平衡时， 各个产地的物资总和正好满足所有销地的需求，运输问题的数学模型为,2. 销大于产问题的数学模型,销大于产时， 各个销地的需求不一定能够得到满足，运输问题的数
2、学模型为,2. 产大于销问题的数学模型,销大于产时， 各个销地的需求一定能够得到满足，但各个产地的物资不一定全部运走。运输问题的数学模型为,运输问题本质是一个线性规划问题,运输问题变量比较多，系数矩阵为0-1矩阵，其中大部分元素为零。计算运输问题我们有比单纯形法更好的专门求解运输问题的算法。,产销平衡运输问题的求解,定理 产销平衡运输问题一定存在最优解 。,产销平衡运输问题的Lingo模型,MODEL: sets: row/1.m/:a; arrange/1.n/:b; link(row,arrange):c,x; endsets data: a=a(1) a(2) a(m); b=b(1)
3、b(2) b(n);,C=c(1,1) c(1,2) c(1,n), c(2,1) c(2,2) c(2,n), c(m,1) c(m,2) c(m,n); enddata OBJmin=sum(link(i,j):c(i,j)*x(i,j); for(row(i):sum(arrange(j):x(i,j)=a(i);); for(arrange(j):sum(row(i):x(i,j)=b(j);); for(link(i,j):x(i,j)=0;); END,产销不平衡运输问题也有类似的Lingo模型,产销平衡运输问题的初始解,1. 西北角法 在运价表的西北角选择运量和销量中的较小数作为
4、运量（初始基变量），每确定一个初始基变量后，划去需求变成零的剩余列元素或划去运量变成零的剩余行元素。,填上x33=1后,自然少去一列(第3列),这时不要再去掉第3行。,注意到每填一个数据恰好减少一行或一列。,总共填写m+n个数据,填上去的m+n个数据为基变量,产销平衡运输问题的初始解,2. 最小元素法 选择运价表中最小运价，运量和销量中的较小数作为运量（初始基变量），每确定一个初始基变量后，划去需求变成零的剩余列元素或划去运量变成零的剩余行元素。,填上x14=4后,第4列自然被去掉,记住每填一个数据减少一行或一列。,3. 位势法求检验数,对每个基变量xij，计算ui和vj，使 ui+vj=ci
5、j 其中u1=0,再计算非基变量检验数,ij=cij-（ui+vj）,11=-4 x11每增加一个单位，目标函数可以减少4个单位。,目标可以减少，说明当前 解不是最优解,闭回路法调整,选x11进基，找到闭回路 x11 x14 4- x21 x24 2+ 3-,闭回路法调整,为了保证所有xij非负，x11最多增加3。 取x11=3 x11 +3 x14 4-3 x21 x24 2+3 3-3,重新计算检验数,22=-1 x22每增加一个单位，目标函数可以减少1个单位。,目标可以减少，说明当前 解不是最优解,闭回路法调整,选x22进基，找到闭回路 x12 5- x14 1 + x22 + x24
6、5-,X22最多增加5,x12 5-5 x14 1 +5 x22 + 5 x24 5-5,X22进基，x12和x24经过调整同时变成零。但是要注意只有一个变量出基。,例如：令x12出基 得调整后的运输表为：,重新计算检验数,所有非基变量检验数均非负，当前解为最优解,最优解为： X11*=3，x14*=6，x22*=5，x32*=3，x33*=4，其余xij*=0 最优目标值为 Z*=32+67+53+34+42=83,运输问题数学模型的应用实例,设某制造企业根据合同要求，从当年起需连续三年在年末提供3套型号规格相同的大型设备，已知该厂的生产能力及生产成本如下表所示：,生产能力与生产成本表,年度
7、 正常生产可 加班生产可 正常生产 完成设备数 完成设备数 成本(万) 第一年 2 3 500 第二年 4 2 600 第三年 1 3 550 设加班生产情况下每套设备成本比正常生产时高70万元,每套设备不及时交货积压一年的维护费用为40万元。该厂现库存有2套设备，希望第三年末完成合同要求后还能储存1台设备，问如何安排生产，才能使总成本最低。,解：设xj为初始存货用于第j年交货的设备数,yij为第i年正常生产用于第j年交货的设备数， zij为第i年加班生产用于第j年交货的设备数， cj为初始库存设备第j年交货时每台设备维护费， aij为第i年正常生产到第j年交货的每台设备成本费， bij为第i
8、年加班生产到第j年交货的每台设备成本费。 上述生产计划问题的数学模型为：,记A为正常生产时的费用矩阵,B为加班生产时的费用矩阵,C=（0，40 ，80）,生产计划问题的Lingo模型为,MODEL: sets: row/1,2,3/; arrange/1,2,3/:c,x; link(row,arrange):a,b,y,z; Endsets data:c=0,40,80; a=500,540,580,0,600,640,0,0,550; b=570,610,650,0,670,710,0,0,620; enddata,OBJmin=sum(arrange(j):c(j)*x(j)+sum (
9、link(i,j):a(i,j)*y(i,j)+sum(link(i,j):b(i,j)*z(i,j); sum(arrange(j):x(j)=2; sum(arrange(j):y(1,j)=2; sum(arrange(j):z(1,j)=3; y(2,2)+y(2,3)=4; z(2,2)+z(2,3)=2; y(3,3)=1; z(3,3)=3; x(1)+y(1,1)+z(1,1)=3; x(2)+y(1,2)+z(1,2)+y(2,2)+z(2,2)=3; x(3)+y(1,3)+z(1,3)+y(2,3)+z(2,3)+y(3,3)+z(3,3)=4;,for(arrange(j):x(j)=0;); for(link(i,j):y(i,j)=0;); for(link(i,j):z(i,j)=0;); END,运行结果：x1=2,y11=y12=1,y22=2,y33=1,z33=3,其余变量均等于0，最低总成本z=4650万元。,谢 谢 !,Thank you!,沈 灏 杭州电子科技大学理学院信息与计算科学教研室,