交通运输与物流工程专业

交通运输与物流工程专业运筹学教程同济大学交通运输工程学院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产地12...mAAA12...maaa销量b1,b2,…,bn产量销地ai=bj产销平衡表/单位运价表111212122212.....................nnmmmnccccccccc设Xij表示从产地Ai调运至销地Bj的货物量i=1,2,…,m;j=1,2,…,n，则运输问题的（LP）模型如下：minz=j=1,2,…,ni=1,2,…,mXij=011mnijijijCX1mijjiXb1nijjjXa二、运输问题模型B1,B2,…,BnAi12...mAAA12...maaabjb1,b2,…,bnaiBj111112121121212222221122.....................nnnnmmmmmnmncXcXcXcXcXcXcXcXcX运输问题的上述（LP）模型，可以形象地表示如下：B1,B2,…,BnAi12...mAAA12...maaabjb1,b2,…,bnaiBj111212122212.....................nnmmmnccccccccc若隐含m*n个决策变量，可以省略地表示如下如下：运输模型2321341s2=27s3=19d1=22d2=13d3=12d4=13s1=14供应量供应地运价需求量需求地6753842759106例1：（LP）模型0xxxxxxxxxxxx13xxx12xxx13xxx22xxx19xxxx27xxxx14xxxxs.t.x6x10x9x5x7x2x4x8x3x5x7x6zmin343332312423222114131211342414332313322212312111343332312423222114131211343332312423222114131211供应地约束需求地约束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分量二、运输问题的对偶问题设Ui，Vj，i=1,2,…,mj=1,2,…,n，为运输问题的对偶变量，则运输问题的对偶问题如下：maxw=Ui+Vj=Cij(i=1,…,m;j=1,…,n)Ui,Vj自由变量11mniijjijaUbV三、运输问题的基本定理（一）基本概念1。闭回路及其顶点；设E是运输问题的一组决策变量，如果对E中的变量做适当的排列后具有如下特殊的序列结构：Xi1j1Xi1j2Xi2j2,…,Xisjs,Xisj1其中，i1,i2,…,is各不相同，j1,j2,…,js2各不相同，则称E为运输问题的一个闭回路。E中变量成为闭回路的顶点。（二）基本定理定理1：运输问题的(m+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：如果运输问题中均是整数，则其任意基本解中各变量的取值均为整数。3.3运输问题表上作业法初始基本可行解检验数的计算方法迭代规则与转轴运算方法多重最优解与退化问题12346753114842722759106319221312138131314663.3.1初始基本可行解的求法_西北角法1234675311484272122715591063192213121303.3.1初始基本可行解的求法_最小元素法123467531131418427212271559106319221312130012346753113141842721312272591063192213121300012346753113141842721312272591063191902213121330001234675311131408427213122725910631919022131213200012346753111314084272213122705910631919022131213000012346753114148427281362759106361319221312135c12-z12=c12-(c11-c21+c22)=7–(6-8+4)=53.3.2检验数的计算方法_闭回路法12346753114148427281362759106361319221312135c13-z13=c13-(c11-c21+c23)=5–(6-8+2)=5512346753114148427281362759106361319221312135c14-z14=c13-(c11-c21+c21-c23+c33-c14)=3-(6-8+2-10+6)=77512346753114148427281362759106361319221312135c24-z24=c24-(c23-c33+c34)=7-(2-10+6)=9-95712346753114148427281362759106361319221312135c31-z31=c31-(c21-c23+c33)=5-(8-2+10)=-11-1157912346753114148427281362759106361319221312135c32-z32=c32-(c22-c23+c33)=9-(4-2+10)=-3-3579-1112346753114u1842728136u2591063613u3v1v2v3v4=0v4=03.3.2检验数的计算方法_位势法12346753114u1842728136u2591063613u3=6v1v2v3v4=0位势法(2)u3+v4=c34u3=612346753114u1842728136u2591063613u3=6v1v2v3=4v4=0位势法(3)u3+v3=c33v3=412346753114u1842728136u2=-2591063613u3=6v1v2v3=4v4=0位势法(4)u2+v3=c23u2=-212346753114u1842728136u2=-2591063613u3=6v1v2=6v3=4v4=0位势法(5)u2+v2=c22v2=612346753114u1842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0位势法(6)u2+v1=c21v1=1012346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0位势法(7)u1+v1=c11u1=-412346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0位势法(8)c12-z12=c12–(u1+v2)=7-(-4)-6=5512346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0位势法(9)c13-z13=c13–(u1+v3)=5-(-4)-4=55512346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0位势法(10)c14-z14=-c14u1+v4=3-(-4)-0=775512346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0位势法(11)c24-z24=c24–(u2+v4)=7-(-2)-0=9955712346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0位势法(12)c31-z31=c31–(u3+v1)=5–6-10=-11-11557912346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0位势法(13)c32-z32=c32–(u3+v2)=9–6-6=-3-35579-1112346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0x31进基,min{x21,x33}=min{8,6}=6,x33离基-35579-113.3.3迭代规则与转轴运算方法12346753114148427221312275910636131922131213转轴运算,重新计算检验数,确定进基、离基变量x14进基,min{x11,x34}=min{14,13}=13,x34离基1155-4-2812346753111314842722131227591063191922131213转轴运算,重新计算检验数所有cij–zij0,得到最优解。Minz=6×1+3×13+8×2+4×13+2×12+5×19=14211554823.4运输问题模型建立P118例3-8P119例3-9P120例3-10P125例3-15