资源描述
交通运输与物流工程专业运 筹 学 教 程同济大学交通运输工程学院2006第三章 运输问题运输问题及其数学模型运输问题基本理论运输问题表上作业法运输问题模型建立3.1 3.1 运输问题及其数学模型运输问题及其数学模型一、一般运输问题一、一般运输问题 设某种货物有设某种货物有m m个产地个产地A1A1，A2A2，,Am,Am,产量分产量分别为别为a1,a2,am,a1,a2,am,有有n n个销地个销地B1,B2,B1,B2,BnBn, ,销量分销量分别为别为b1,b2,b1,b2,bnbn，而且从而且从AiAi到到BjBj的单位运价为的单位运价为CijCij。若产销平衡（。若产销平衡（ aiai= = bjbj），），问如何制定调运问如何制定调运方案，可以使总运费最小？方案，可以使总运费最小？B B1 1 , B, B2 2 , , , , B Bn n产地产地12.mAAA12.maaa 销量销量 b b1 1 , b , b2 2 , , , , b bn n产量产量销地销地 a ai i= = b bj j产销平衡表产销平衡表/ /单位运价表单位运价表111212122212.nnmmmnccccccccc 设设 X Xijij表示从产地表示从产地AiAi调运至销地调运至销地BjBj的货物量的货物量 i=1,2,m; j=1,2,n i=1,2,m; j=1,2,n，则运输问题的则运输问题的（LPLP）模型如下：模型如下： min z = min z = j=1,2,n j=1,2,n i=1,2,m i=1,2,m X Xijij=0=011mnijijijC X 1mijjiXb1nijjjXa二、运输问题模型二、运输问题模型B B1 1 , B, B2 2 , , , , B Bn nAiAi12.mAAA12.maaa b bj j b b1 1 , b , b2 2 , , , , b bn na ai i Bj Bj111112121121212222221122.nnnnmmmmmnmnc Xc Xc Xc Xc Xc Xc Xc Xc X 运输问题的上述运输问题的上述（LPLP）模型，模型，可以形象地表示如下：可以形象地表示如下：B B1 1 , B, B2 2 , , , , B Bn nAiAi12.mAAA12.maaa b bj j b b1 1 , b , b2 2 , , , , b bn na ai i Bj Bj111212122212.nnmmmnccccccccc 若隐含若隐含m m* *n n个决策变量，个决策变量，可以省略地表示如下如下：可以省略地表示如下如下：运输模型运输模型2321341s2=27s3=19d1=22d2=13d3=12d4=13s1=14供应量供应地运价需求量需求地6753842759106例例1 1：（LP）模型模型0 xxxxxxxxxxxx13xxx12xxx13xxx22xxx19xxxx27xxxx14xxxxs.t.x6x10 x9x5x7x2x4x8x3x5x7x6zmin343332312423222114131211342414332313322212312111343332312423222114131211343332312423222114131211供应地约束需求地约束B1B2B3B46753A1x11x12x13x14148427A2x21x22x23x242759106A3x31x32x33x341922131213运输模型运输模型B1B2B3B46753A1148427A22759106A31922131213运输模型运输模型3.2 3.2 运输问题基本理论运输问题基本理论一、运输问题基本特征一、运输问题基本特征 （一）决策变量的个数：（一）决策变量的个数：m m* *n;n; （二）约束方程的个数：（二）约束方程的个数： m+nm+n； （三）独立方程的个数：（三）独立方程的个数： m+n-1m+n-1：（WHYWHY） （四）系数矩阵的特殊结构（四）系数矩阵的特殊结构（P80P80） 变量变量X Xijij的系数向量的系数向量A Aijij A Aijij=(=(0,0,1,0,0,0,1,0,0,0,1,00,0,1,0) )T T i i分量分量j j分量分量二、运输问题的对偶问题二、运输问题的对偶问题 设设 U Ui i，V Vj j，i=1,2,i=1,2,mjmj=1,2,n=1,2,n，为运输问题为运输问题的对偶变量，则运输问题的对偶问题如下：的对偶变量，则运输问题的对偶问题如下： max w = max w = U Ui i+ +V Vj j=0,得到最优解。Min z=61+3 13+8 2+4 13+2 12+5 19=14211554823.4 3.4 运输问题模型建立运输问题模型建立P118 P118 例例3-83-8P119 P119 例例3-93-9P120 P120 例例3-103-10P125 P125 例例3-15 3-15
展开阅读全文