交通运输与物流工程专业.ppt

《交通运输与物流工程专业.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、交通运输与物流工程专业运筹学教程同济大学交通运输工程学院2006第三章运输问题运输问题及其数学模型运输问题基本理论运输问题表上作业法运输问题模型建立3.1运输问题及其数学模型一、一般运输问题设某种货物有m个产地A1，A2，…,Am,产量分别为a1,a2,…,am,有n个销地B1,B2,…,Bn,销量分别为b1,b2,…,bn，而且从Ai到Bj的单位运价为Cij。若产销平衡（ai=bj），问如何制定调运方案，可以使总运费最小？B1,B2,…,Bn产地销量b1,b2,…,bn产量销地ai=bj产销平衡表/单位运价表设Xij表示从产地Ai调运

2、至销地Bj的货物量i=1,2,…,m;j=1,2,…,n，则运输问题的（LP）模型如下：minz=j=1,2,…,ni=1,2,…,mXij>=0二、运输问题模型B1,B2,…,BnAibjb1,b2,…,bnaiBj运输问题的上述（LP）模型，可以形象地表示如下：B1,B2,…,BnAibjb1,b2,…,bnaiBj若隐含m*n个决策变量，可以省略地表示如下如下：运输模型2321341s2=27s3=19d1=22d2=13d3=12d4=13s1=14供应量供应地运价需求量需求地6753842759106例1：（LP）模型供应地约束需求地

3、约束B1B2B3B46753A1x11x12x13x14148427A2x21x22x23x242759106A3x31x32x33x341922131213运输模型B1B2B3B46753A1148427A22759106A31922131213运输模型3.2运输问题基本理论一、运输问题基本特征（一）决策变量的个数：m*n;（二）约束方程的个数：m+n；（三）独立方程的个数：m+n-1：（WHY）（四）系数矩阵的特殊结构（P80）——变量Xij的系数向量AijAij=(0,0,…,1,…,0,0,0,…,1,…,0)Ti分量j分量二、运输问题

4、的对偶问题设Ui，Vj，i=1,2,…,mj=1,2,…,n，为运输问题的对偶变量，则运输问题的对偶问题如下：maxw=Ui+Vj<=Cij(i=1,…,m;j=1,…,n)Ui,Vj自由变量三、运输问题的基本定理（一）基本概念1。闭回路及其顶点；设E是运输问题的一组决策变量，如果对E中的变量做适当的排列后具有如下特殊的序列结构：Xi1j1Xi1j2Xi2j2,…,Xisjs,Xisj1其中，i1,i2,…,is各不相同，j1,j2,…,js2各不相同，则称E为运输问题的一个闭回路。E中变量成为闭回路的顶点。（二）基本定理定理1：运输问题的(m

5、+n)个约束方程中只有(m+n-1)个独立方程，而且任意一组(m+n-1)个方程都是相互独立的。2。孤立点及其性质；设E为运输问题的一组变量，Xij是其中一个变量，如果它是i行或j列属于E的唯一变量，则称Xij为E的一个孤立点。若Xij为E的一个孤立点，则Xij不可能是E中闭回路的一个顶点。定理2：运输问题中变量组E（包含m+n-1个变量)能够构成基本变量组XB的充要条件：变量组E中不存在闭回路。定理3：设E为运输问题的一基本变量组XB，若变量XijE，则变量组“{Xij}E”（包含m+n个变量）一定存在唯一一条闭回路。定理4：如果运输问题

6、中均是整数，则其任意基本解中各变量的取值均为整数。3.3运输问题表上作业法初始基本可行解检验数的计算方法迭代规则与转轴运算方法多重最优解与退化问题8131314663.3.1初始基本可行解的求法_西北角法3.3.1初始基本可行解的求法_最小元素法5c12-z12=c12-(c11-c21+c22)=7–(6-8+4)=53.3.2检验数的计算方法_闭回路法5c13-z13=c13-(c11-c21+c23)=5–(6-8+2)=555c14-z14=c13-(c11-c21+c21-c23+c33-c14)=3-(6-8+2-10+6)=775

7、5c24-z24=c24-(c23-c33+c34)=7-(2-10+6)=9-9575c31-z31=c31-(c21-c23+c33)=5-(8-2+10)=-11-115795c32-z32=c32-(c22-c23+c33)=9-(4-2+10)=-3-3579-11v4=03.3.2检验数的计算方法_位势法位势法(2)u3+v4=c34u3=6位势法(3)u3+v3=c33v3=4位势法(4)u2+v3=c23u2=-2位势法(5)u2+v2=c22v2=6位势法(6)u2+v1=c21v1=10位势法(7)u1+v1=c11u1=-

8、4位势法(8)c12-z12=c12–(u1+v2)=7-(-4)-6=55位势法(9)c13-z13=c13–(u1+v3)=5-(-4)-4=55