资源描述：
《运筹学 04 运输问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、运输模型TransportModel运输问题的表上作业法TableMethodofTP运输问题的进一步讨论FurtherDiscussionofTP运输问题的思考题及练习题QuestionsandExercisesforTP运输问题TransportationProblem1运输模型一般的运输问题就是要解决把某种产品从若干个产地Ai(i=1,2,…,m)调运到若干个销地Bj(j=1,2,…,n)，在每个产地的供应量ai(i=1,2,…,m)、每个销地的需求量bj(j=1,2,…,n)、Ai运输到Bj的单位运价cij已知的前提下，如何确定一个运输方案，使总运价最低。设xij为从
2、Ai运输到Bj的产品数量，若Σai=Σbj，则称为产销平衡的运输规划问题，数学模型为minf=c11x11+…+c1nx1n+c21x21+…+cmnxmnxi1+xi2+…+xin=ai(i=1,2,…,m)x1j+x2j+…+xmj=bj(j=1,2,…,n)xij≥0(i=1,2,…,m;j=1,2,…,n)有时运输问题的一般模型会有一些变化，如求目标函数的最大值某些运输线路的运输能力有一定限制生产地产量有所限制销售地销量有所限制总产量不等于总销量，即产销不平衡某些地方只是中转站这些问题也可以转化为平衡运输问题对产销平衡运输问题，若用u1,u2,…,um分别表示前m个约
3、束等式相应的对偶变量，用v1,v2,…,vn分别表示后n个约束等式相应的对偶变量，即对偶变量为Y=(u1,u2,…,um,v1,v2,…,vn)T运输问题的对偶问题可以写成maxf=a1u1+…+amum+b1v1+…+bnvnui+vj≤cij(i=1,2,…,m;j=1,2,…,n)ui,vj任意原问题变量xj的检验数σj=cj-zj=cj-CBB-1Pj=cj-YPj变量xij的检验数σij=cij-zij=cij-YPij=cij-(u1,u2,…,um,v1,v2,…,vn)Pij=cij-(ui+vj)2运输问题的表上作业法运输问题的数学模型及其约束方程组的系数矩
4、阵结构具有特殊性，使用表上作业法解决运输问题，比单纯形法更为简便。表上作业法的步骤：第1步：确定初始基可行解第2步：解的最优性检验第3步：解的调整，转第2步例1：某集团公司3个工厂A1、A2、A3生产同一产品的产量、4个销售点B1、B2、B3、B4的销量及单位产品的运价如下表。试确定使总运费最低的运输方案。工厂B1B2B3B4产量A141241116A22103910A38511622销量8141214第1步：确定初始基可行解最小元素法(最低运价法)步骤：运价表中找出一个最低运价(即最小元素)cij在该处确定运量xij=min(ai,bj)计算剩余产量ai’=ai-xij和剩
5、余销量bj’=bj-xij，则出现(1)ai’=0，bj’≠0——划去第i行运价；(2)ai’≠0，bj’=0——划去第j列运价；(3)ai’=0，bj’=0——划去第i行或第j列运价重复上述，直到获得(m+n-1)个运输数量工厂B1B2B3B4产量A141241116A22103910A38511622销量8141214工厂B1B2B3B4产量A110616A28210A314822销量8141214(1)(2)(3)最低运价234运价标号c21c23c13线路x21x23x13数量比较8,102,1216,10运输数量8210新产量a2’=2a2’’=0a1’=6新销量b
6、1’=0b3’=10b3’’=0划去第1列第2行第3列西北角法步骤运价表中找出西北角(左上角)运价cij在该处确定运量xij=min(ai,bj)计算剩余产量ai’=ai-xij和剩余销量bj’=bj-xij，则出现(1)ai’=0，bj’≠0——划去第i行运价；(2)ai’≠0，bj’=0——划去第j列运价；(3)ai’=0，bj’=0——划去第i行或第j列运价重复上述，直到获得(m+n-1)个运输数量伏格尔法步骤运价表中计算每行和每列最小和次小运价之差，从差值最大的行或列中找出最小运价cij在该处确定运量xij=min(ai,bj)计算剩余产量ai’=ai-xij和剩余销
7、量bj’=bj-xij，则出现(1)ai’=0，bj’≠0——划去第i行运价；(2)ai’≠0，bj’=0——划去第j列运价；(3)ai’=0，bj’=0——划去第i行或第j列运价重复上述，直到获得(m+n-1)个运输数量罗素法步骤运价表中找出每行和每列的最大值ui和vj，每个单元格计算λij=cij-ui-vj，找到最小值λij在该处确定运量xij=min(ai,bj)计算剩余产量ai’=ai-xij和剩余销量bj’=bj-xij，则出现(1)ai’=0，bj’≠0——划去第i行运价；(2)ai’≠0
