运输问题模型

运输问题模型杭州电子科技大学数学教研室杭州电子科技大学沈灏二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.销大于产问题产大于销问题ijx解：设产地Ai运往销地Bj的运量为1.产销平衡问题的数学模型产销平衡时，各个产地的物资总和正好满足所有销地的需求，运输问题的数学模型为jjiibanjmixnjbxmiaxtsxczijnijijnjiijninjijij,,1;,,1,0,,1,,,1,..min11112.销大于产问题的数学模型销大于产时，各个销地的需求不一定能够得到满足，运输问题的数学模型为jjiibanjmixnjbxmiaxtsxczijnijijnjiijninjijij,,1;,,1,0,,1,,,1,..min11112.产大于销问题的数学模型销大于产时，各个销地的需求一定能够得到满足，但各个产地的物资不一定全部运走。运输问题的数学模型为jjiibanjmixnjbxmiaxtsxczijnijijnjiijninjijij,,1;,,1,0,,1,,,1,..min1111运输问题本质是一个线性规划问题运输问题变量比较多，系数矩阵为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)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[OBJ]min=@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.西北角法在运价表的西北角选择运量和销量中的较小数作为运量（初始基变量），每确定一个初始基变量后，划去需求变成零的剩余列元素或划去运量变成零的剩余行元素。B1B2B3B4产量A13291079,6A2×13425A3×84257销量3,0846B1B2B3B4产量A13269×10×79,6,0A2×13425A3×84257销量3,08,246B1B2B3B4产量A13269×10×79,6,0A2×123425,3A3×8×4257销量3,08,2,046B1B2B3B4产量A13269×10×79,6,0A2×12334×25,3,0A3×8×4257销量3,08,2,04,16B1B2B3B4产量A13269×10×79,6,0A2×12334×25,3,0A3×8×41257,6销量3,08,2,04,1,06填上x33=1后,自然少去一列(第3列),这时不要再去掉第3行。注意到每填一个数据恰好减少一行或一列。B1B2B3B4产量A13269×10×79,6,0A2×12334×25,3,0A3×8×412657,6销量3,08,2,04,1,06总共填写m+n个数据填上去的m+n个数据为基变量产销平衡运输问题的初始解2.最小元素法选择运价表中最小运价，运量和销量中的较小数作为运量（初始基变量），每确定一个初始基变量后，划去需求变成零的剩余列元素或划去运量变成零的剩余行元素。B1B2B3B4产量A1×291079A2313425，2A3×84257销量3,0846B1B2B3B4产量A1×29×1079A2313×425，2A3×844257，3销量3,084，06B1B2B3B4产量A1×29×1079A231×3×4225,2,0A3×844257，3销量3,084，06,4B1B2B3B4产量A1×29×1079A231×3×4225,2,0A3×83442×57,3,0销量3,08,54，06,4B1B2B3B4产量A1×29×10479,5A231×3×4225,2,0A3×83442×57,3,0销量3,08,54，06,4,0填上x14=4后,第4列自然被去掉记住每填一个数据减少一行或一列。B1B2B3B4产量A1×259×10479,5A231×3×4225,2,0A3×83442×57,3,0销量3,08,54，06,4,03.位势法求检验数对每个基变量xij，计算ui和vj，使ui+vj=cij其中u1=0B1B2V2=9B3B4V4=7产量A1u1=0×259×10479,5A231×3×4225,2,0A3×83442×57,3,0销量3,08,54，06,4,0B1B2V2=9B3B4V4=7产量A1u1=0×259×10479,5A2u2=-531×3×4225,2,0A3u3=-5×83442×57,3,0销量3,08,54，06,4,0B1v1=6B2v2=9B3v3=7B4V4=7产量A1u1=0×259×10479,5A2u2=-531×3×4225,2,0A3u3=-5×83442×57,3,0销量3,08,54，06,4,0再计算非基变量检验数σij=cij-（ui+vj）B1v1=6B2v2=9B3v3=7B4V4=7产量A1u1=0-4259310479,5A2u2=-531-1324225,2,0A3u3=-5783442357,3,0销量3,08,54，06,4,0σ11=-4x11每增加一个单位，目标函数可以减少4个单位。目标可以减少，说明当前解不是最优解闭回路法调整选x11进基，找到闭回路x11x144-x21x242+3-闭回路法调整为了保证所有xij非负，x11最多增加3。取x11=3x11+3x144-3x21x242+33-3B1B2B3B4产量A1u1=03259310179,5A21-1324525,2,0A3783442357,3,0销量3,08,54，06,4,0重新计算检验数B1v1=2B2v2=9B3B4v4=7产量A1u1=03259310179,5A2u2=-51-1324525,2,0A3u3=-5783442357,3,0销量3,08,54，06,4,0B1v1=2B2v2=9B3V3=7B4v4=7产量A1u1=03259310179,5A2u2=-541-1324525,2,0A3u3=-51183442357,3,0销量3,08,54，06,4,0σ22=-1x22每增加一个单位，目标函数可以减少1个单位。目标可以减少，说明当前解不是最优解闭回路法调整选x22进基，找到闭回路x125-x141+x22+x245-X22最多增加5x125-5x141+5x22+5x245-5X22进基，x12和x24经过调整同时变成零。但是要注意只有一个变量出基。例如：令x12出基得调整后的运输表为：B1B2B3B4产量A1u1=0329310679,5A2415324025,2,0A31183442357,3,0销量3,08,54，06,4,0重新计算检验数B1v1=2B2B3B4v4=7产量A1u1=0329310679,5A2u2=-5415324025,2,0A31183442357,3,0销量3,08,54，06,4,0B1v1=2B2v2=8B3B4v4=7产量A1u1=0329310679,5A2u2=-5415324025,2,0A3u3=-41183442357,3,0销量3,08,54，06,4,0B1v1=2B2v2=8B3V3=6B4v4=7产量A1u1=03219410679,5A2u2=-5415334025,2,0A3u3=-41083442257,3,0销量3,08,54，06,4,0所有非基变量检验数均非负，当前解为最优解最优解为：X11*=3，x14*=6，x22*=5，x32*=3，x33*=4，其余xij*=0最优目标值为Z*=3×2+6×7+5×3+3×4+4×2=83运输问题数学模型的应用实例设某制造企业根据合同要求，从当年起需连续三年在年末提供3套型号规格相同的大型设备，已知该厂的生产能力及生产成本如下表所示：生产能力与生产成本表年度正常生产可加班生产可正常生产完成设备数完成设备数成本(万)第一年23500第二年42600第三年13550设加班生产情况下每套设备成本比正常生产时高70万元,每套设备不及时交货积压一年的维护费用为40万元。该厂现库存有2套设备，希望第三年末完成合同要求后还能储存1台设备，问如何安排生产，才能使总成本最低。解：设xj为初始存货用于第j年交货的设备数yij为第i年正常生产用于第j年交货的设备数，zij为第i年加班生产用于第j年交货的设备数，cj为初始库存设备第j年交货时每台设备维护费，aij为第i年正常生产到第j年交货的每台设备成本费，bij为第i年加班生产到第j年交货的每台设备成本费。上述生产计划问题的数学模型为：3,2,1,,0,0,04333124322..min3333232313133222212122111113333232223221312111312113213131313131jizyxzyzyzyxzyzyxzyxzyzzyyzzzyyyxxxtszbyaxczijijjijijijijijijjjj记A为正常生产时的费用矩阵550006406000580540500)(ijaAB为加班生产时的费用矩阵620007106700650610570)(ijbBC=（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[OBJ]min=@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)=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;)