运筹学 04 运输问题VIP免费

1.运输模型TransportModel2.运输问题的表上作业法TableMethodofTP3.运输问题的进一步讨论FurtherDiscussionofTP4.运输问题的思考题及练习题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为从Ai运输到Bj的产品数量，若Σai=Σbj，则称为产销平衡的运输规划问题，数学模型为minf=c11x11+…+c1nx1n+c21x21+…+cmnxmnxi1+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个约束等式相应的对偶变量，用v1,v2,…,vn分别表示后n个约束等式相应的对偶变量，即对偶变量为Y=(u1,u2,…,um,v1,v2,…,vn)T运输问题的对偶问题可以写成maxf=a1u1+…+amum+b1v1+…+bnvnui+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运输问题的表上作业法运输问题的数学模型及其约束方程组的系数矩阵结构具有特殊性，使用表上作业法解决运输问题，比单纯形法更为简便。表上作业法的步骤：第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和剩余销量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新销量b1’=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和剩余销量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，bj’=0——划去第j列运价；(3)ai’=0，bj’=0——划去第i行或第j列运价重复上述，直到获得(m+n-1)个运输数量任意方法也能获得初始运输方案，自己思考第2步：解的最优性检验运输问题是...