运输问题模型.pptx

运输问题模型运输问题模型杭州电子科技大学杭州电子科技大学 数学教研室数学教研室杭州电子科技大学杭州电子科技大学 沈沈 灏灏二二0一一0年四月年四月运输问题的一般描述运输问题的一般描述设某种物资有设某种物资有m个产地个产地A1,A2,Am，和和n个销地个销地B1,B2,Bn,其中其中Ai的产量的产量为为ai,Bjai,Bj的销量为的销量为bjbj，产地产地Ai运往销地运往销地Bj的单位运价的单位运价Cij,i=1,2,m;j=1,2,n.求尽可能满足销地需求且总费用最小的求尽可能满足销地需求且总费用最小的运输方案。运输方案。n运输问题的数学模型可以分以下运输问题的数学模型可以分以下3种情种情况讨论：况讨论：n1.产销平衡问题产销平衡问题n2.销大于产问题销大于产问题n产大于销问题产大于销问题解：设产地Ai运往销地Bj的运量为1.1.产销平衡问题的数学模型产销平衡问题的数学模型n产销平衡时，产销平衡时，n各个产地的物资总和正好满足所有各个产地的物资总和正好满足所有销地的需求，运输问题的数学模型销地的需求，运输问题的数学模型为为2.2.销大于产问题的数学模型销大于产问题的数学模型n销大于产时，销大于产时，n各个销地的需求不一定能够得到各个销地的需求不一定能够得到满足，运输问题的数学模型为满足，运输问题的数学模型为2.2.产大于销问题的数学模型产大于销问题的数学模型n销大于产时，销大于产时，n各个销地的需求一定能够得到满足，各个销地的需求一定能够得到满足，但各个产地的物资不一定全部运走。但各个产地的物资不一定全部运走。运输问题的数学模型为运输问题的数学模型为运输问题本质是一个线性规划问题运输问题本质是一个线性规划问题n运输问题变量比较多，系数矩阵为运输问题变量比较多，系数矩阵为0-1矩阵，其中大部分元素为零。计算运矩阵，其中大部分元素为零。计算运输问题我们有比单纯形法更好的专门输问题我们有比单纯形法更好的专门求解运输问题的算法。求解运输问题的算法。产销平衡运输问题的求解产销平衡运输问题的求解n定理 产销平衡运输问题一定产销平衡运输问题一定存在最优解存在最优解。产销平衡运输问题的产销平衡运输问题的Lingo模型模型nMODEL:nsets:nrow/1.m/:a;narrange/1.n/:b;nlink(row,arrange):c,x;nendsetsndata:na=a(1)a(2)a(m);nb=b(1)b(2)b(n);nC=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);nenddatanOBJmin=sum(link(i,j):c(i,j)*x(i,j);nfor(row(i):sum(arrange(j):x(i,j)=a(i););nfor(arrange(j):sum(row(i):x(i,j)=b(j););nfor(link(i,j):x(i,j)=0;);nENDn产销不平衡运输问题也有类似的产销不平衡运输问题也有类似的Lingo模型模型产销平衡运输问题的初始解产销平衡运输问题的初始解n1.西北角法西北角法n在运价表的西北角选择运量和销量中在运价表的西北角选择运量和销量中的较小数作为运量（的较小数作为运量（初始基变量初始基变量），），每确定一个初始基变量后，划去需求每确定一个初始基变量后，划去需求变成零的剩余列元素或划去运量变成变成零的剩余列元素或划去运量变成零的剩余行元素。零的剩余行元素。B1B2B3B4产量A13 2 9 10 7 9,6A2 1 3 4 2 5A3 8 4 2 5 7销量 3,0 8 4 6B1B2B3B4产量A13 26 9 10 7 9,6,0A2 1 3 4 2 5A3 8 4 2 5 7销量 3,0 8,2 4 6B1B2B3B4产量A13 26 9 10 7 9,6,0A2 12 3 4 2 5,3A3 8 4 2 5 7销量 3,0 8,2,0 4 6B1B2B3B4产量A13 26 9 10 7 9,6,0A2 12 3 3 4 2 5,3,0A3 8 4 2 5 7销量 3,0 8,2,0 4,1 6B1B2B3B4产量A13 26 9 10 7 9,6,0A2 12 3 3 4 2 5,3,0A3 8 41 2 5 7,6销量 3,0 8,2,0 4,1,0 6填上填上x33=1后后,自然少去一列自然少去一列(第第3列列),这时不要再去掉第这时不要再去掉第3行。行。n注意到每填一个数据恰好减少一注意到每填一个数据恰好减少一行或一列。行或一列。B1B2B3B4产量A13 26 9 10 7 9,6,0A2 12 3 3 4 2 5,3,0A3 8 41 26 5 7,6销量 3,0 8,2,0 4,1,0 6总共填写总共填写m+n个数据个数据n填上去的填上去的m+n个数据为基变个数据为基变量量产销平衡运输问题的初始解产销平衡运输问题的初始解n2.最小元素法最小元素法n选择运价表中最小运价，运量和销量选择运价表中最小运价，运量和销量中的较小数作为运量（中的较小数作为运量（初始基变量初始基变量），），每确定一个初始基变量后，划去需求每确定一个初始基变量后，划去需求变成零的剩余列元素或划去运量变成变成零的剩余列元素或划去运量变成零的剩余行元素。零的剩余行元素。B1B2B3B4产量A1 2 9 10 7 9A23 1 3 4 2 5，2A3 8 4 2 5 7销量 3,0 8 4 6B1B2B3B4产量A1 2 9 10 7 9A23 1 3 4 2 5，2A3 8 44 2 5 7，3销量 3,0 8 4，0 6B1B2B3B4产量A1 2 9 10 7 9A23 1 3 42 2 5,2,0A3 8 44 2 5 7，3销量 3,0 8 4，0 6,4B1B2B3B4产量A1 2 9 10 7 9A23 1 3 42 2 5,2,0A3 83 44 2 5 7,3,0销量 3,0 8,5 4，0 6,4B1B2B3B4产量A1 2 9 104 7 9,5A23 1 3 42 2 5,2,0A3 83 44 2 5 7,3,0销量 3,0 8,5 4，0 6,4,0填上填上x14=4后后,第第4列自然列自然被去掉被去掉n记住每填一个数据减少一记住每填一个数据减少一行或一列。行或一列。B1B2B3B4产量A1 25 9 104 7 9,5A23 1 3 42 2 5,2,0A3 83 44 2 5 7,3,0销量 3,0 8,5 4，0 6,4,03.3.位势法求检验数位势法求检验数n对每个基变量对每个基变量xij，计算，计算ui和和vj，使，使 ui+vj=cij 其中其中u1=0u1=0B1B2V2=9B3B4V4=7产量A1u1=0 25 9 104 7 9,5A23 1 3 42 2 5,2,0A3 83 44 2 5 7,3,0销量 3,0 8,5 4，0 6,4,0B1B2V2=9B3B4V4=7产量A1u1=0 25 9 104 7 9,5A2u2=-53 1 3 42 2 5,2,0A3u3=-5 83 44 2 5 7,3,0销量 3,0 8,5 4，0 6,4,0B1v1=6B2v2=9B3v3=7B4V4=7产量A1u1=0 25 9 104 7 9,5A2u2=-53 1 3 42 2 5,2,0A3u3=-5 83 44 2 5 7,3,0销量 3,0 8,5 4，0 6,4,0再计算非基变量检验数再计算非基变量检验数nij=cij-（ui+vj）B1v1=6B2v2=9B3v3=7B4V4=7产量A1u1=0-4 25 93 104 7 9,5A2u2=-53 1-1 3 2 42 2 5,2,0A3u3=-57 83 44 23 5 7,3,0销量 3,0 8,5 4，0 6,4,011=-4 x1111=-4 x11每增加一个单每增加一个单位，目标函数可以减少位，目标函数可以减少4 4个单位。个单位。目标可以减少，说明当前目标可以减少，说明当前解不是最优解解不是最优解闭回路法调整闭回路法调整n选选x11进基，找到闭回路进基，找到闭回路n x11 x14 4-n x21 x24 2+n 3-闭回路法调整闭回路法调整n为了保证所有为了保证所有xij非负，非负，x11最多增加最多增加3。n取取x11=3n x11+3 x14 4-3n x21 x24 2+3 n 3-3B1B2B3B4产量A1u1=03 25 93 101 7 9,5A2 1-1 3 2 45 2 5,2,0A37 83 44 23 5 7,3,0销量 3,0 8,5 4，0 6,4,0重新计算检验数重新计算检验数B1v1=2B2v2=9B3B4v4=7产量A1u1=03 25 93 101 7 9,5A2u2=-5 1-1 3 2 45 2 5,2,0A3u3=-57 83 44 23 5 7,3,0销量 3,0 8,5 4，0 6,4,0B1v1=2B2v2=9B3V3=7B4v4=7产量A1u1=03 25 93 101 7 9,5A2u2=-54 1-1 3 2 45 2 5,2,0A3u3=-511 83 44 23 5 7,3,0销量 3,0 8,5 4，0 6,4,022=-1 x2222=-1 x22每增加一个单每增加一个单位，目标函数可以减少位，目标函数可以减少1 1个单位。个单位。目标可以减少，说明当前目标可以减少，说明当前解不是最优解解不是最优解闭回路法调整闭回路法调整n选选x22进基，找到闭回路进基，找到闭回路n x12 5-x14 1+n x22+x24 5-X22最多增加最多增加5n x12 5-5 x14 1+5n x22+5 x24 5-5 X22进基，进基，x12和和x24经过调整同时变成经过调整同时变成零。但是要注意只有一个变量出基。零。但是要注意只有一个变量出基。n例如：例如：令令x12x12出基出基n得调整后的运输表为：得调整后的运输表为：B1B2B3B4产量A1u1=03 2 93 106 7 9,5A24 15 3 2 40 2 5,2,0A311 83 44 23 5 7,3,0销量 3,0 8,5 4，0 6,4,0重新计算检验数重新计算检验数B1v1=2B2B3B4v4=7产量A1u1=03 2 93 106 7 9,5A2u2=-54 15 3 2 40 2 5,2,0A311 83 44 23 5 7,3,0销量 3,0 8,5 4，0 6,4,0B1v1=2B2v2=8B3B4v4=7产量A1u1=03 2 93 106 7 9,5A2u2=-54 15 3 2 40 2 5,2,0A3u3=-411 83 44 23 5 7,3,0销量 3,0 8,5 4，0 6,4,0B1v1=2B2v2=8B3V3=6B4v4=7产量A1u1=03 2 1 94 106 7 9,5A2u2=-54 15 3 3 40 2 5,2,0A3u3=-410 83 44 22 5 7,3,0销量 3,0 8,5 4，0 6,4,0所有非基变量检验数均非所有非基变量检验数均非负，当前解为负，当前解为最优解最优解n最优解为：最优解为：X11*=3X11*=3，x14*=6x14*=6，x22*=5x22*=5，x32*=3x32*=3，x33*=4x33*=4，其余，其余xij*=0 xij*=0n最优目标值为最优目标值为nZ*=3Z*=32+67+53+34+42=832+67+53+34+42=83运输问题数学模型的应用实例运输问题数学模型的应用实例n设某制造企业根据合同要求，从当年起需连续设某制造企业根据合同要求，从当年起需连续三年在年末提供三年在年末提供3套型号规格相同的大型设备，套型号规格相同的大型设备，已知该厂的生产能力及生产成本如下表所示：已知该厂的生产能力及生产成本如下表所示：生产能力与生产成本表生产能力与生产成本表n年度年度 正常生产可正常生产可 加班生产可加班生产可 正常生产正常生产 完成设备数完成设备数 完成设备数完成设备数 成本成本(万万)n第一年第一年 2 3 500n第二年第二年 4 2 600 n第三年第三年 1 3 550 设加班生产情况下每套设备成本比正常生产时高设加班生产情况下每套设备成本比正常生产时高70万元万元,每套设备不及时交货积压一年的维护费每套设备不及时交货积压一年的维护费用为用为40万元。该厂现库存有万元。该厂现库存有2套设备，希望第三套设备，希望第三年末完成合同要求后还能储存年末完成合同要求后还能储存1台设备，问如何台设备，问如何安排生产，才能使总成本最低。安排生产，才能使总成本最低。解解：设设xj为初始存货用于第为初始存货用于第j年交货的设备数年交货的设备数 yij为第为第i年正常生产用于第年正常生产用于第j年交货的设备数，年交货的设备数，zij为第为第i年加班生产用于第年加班生产用于第j年交货的设备数，年交货的设备数，cj为初始库存设备第为初始库存设备第j年交货时每台设备维护费，年交货时每台设备维护费，aij为第为第i年正常生产到第年正常生产到第j年交货的每台设备成本年交货的每台设备成本费，费，bij为第为第i年加班生产到第年加班生产到第j年交货的每台设备成本年交货的每台设备成本费。费。上述生产计划问题的数学模型为：上述生产计划问题的数学模型为：记记A为正常生产时的费用矩阵为正常生产时的费用矩阵B为加班生产时的费用矩阵为加班生产时的费用矩阵C=（0，40，80）生产计划问题的生产计划问题的Lingo模型为模型为nMODEL:nsets:nrow/1,2,3/;narrange/1,2,3/:c,x;nlink(row,arrange):a,b,y,z;nEndsetsndata:c=0,40,80;na=500,540,580,0,600,640,0,0,550;nb=570,610,650,0,670,710,0,0,620;nenddataOBJmin=sum(arrange(j):c(j)*x(j)+sum(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)=0;);for(link(i,j):y(i,j)=0;);for(link(i,j):z(i,j)=0;);nEND运行结果：x1=2,y11=y12=1,y22=2,y33=1,z33=3,其余其余变量均等于变量均等于0，最低总成本，最低总成本z=4650万元。万元。谢谢 谢谢 !Thank you!沈沈 灏灏杭州电子科技大学理学院信息与计算科学教研室杭州电子科技大学理学院信息与计算科学教研室