资源描述：
《运输问题模型.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
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;endsetsdata
3、: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模型产销平衡运输问
4、题的初始解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×42
5、57销量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.最小元素法选择运价表中最小运价，运量和销量中的较小数作为运量（初始基变量），每确定一
6、个初始基变量后，划去需求变成零的剩余列元素或划去运量变成零的剩余行元素。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×4
7、225,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产量
