(5.1.1)--第13讲产销平衡运输问题的数学模型.pdf

《(5.1.1)--第13讲产销平衡运输问题的数学模型.pdf》由会员分享，可在线阅读，更多相关《(5.1.1)--第13讲产销平衡运输问题的数学模型.pdf（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运运 筹筹 学学 第第1313讲讲 产销平衡运输问题的数学模型产销平衡运输问题的数学模型 一般的运输问题就是要解决：把某种产品从若干个产地调运到若干个销地，在已知每个产地的供应量供应量、每个销地的需求量需求量、各地之间的运输单价运输单价的前提下，如何确定一个确定一个使得总的运输费用最小总的运输费用最小的方案。2 一、运输问题（一、运输问题（Transportation Problem,TP）3 例题 有三个工厂F1，F2，F3生产同种产品，它们的产量分别为25，15，10单位。该公司把这些产品分别运往四个销售点D1，D2，D3，D4，各销售点销量分别为13，21，9和7。从各工厂到各销售点的单

2、位产品的运价为下表所示。问该公司应如何调运产品问该公司应如何调运产品，在满足各销售点在满足各销售点需求量的前提下需求量的前提下，使总运费为最少使总运费为最少 销地 产地 D1 D2 D3 D4 产量 F1 6 7 5 3 25 F2 8 4 2 7 10 F3 5 9 10 6 15 销量 13 21 9 7 F2 F3 F1 D2 D3 D4 D1 s2=10 s3=15 s1=25 供应量供应量 供应地供应地 运价运价 d1=13 d2=21 d3=9 d4=7 需求量需求量 需求地需求地 6 7 5 3 8 4 2 7 5 9 10 6 图图5-1 运输问题网络图运输问题网络图 S=50

3、 D=50 供应地约束 需求地约束 4,3,2,1;3,2,1,07+9+21+13+15+10+25+.342414332313332212312111343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxtsij3433323124232221141312116+10+9+5+7+2+4+8+3+5+7+6minxxxxxxxxxxxxz 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1343332312423222114131211xxxxxxxxxxxx7921131510254,3,2,1;

4、3,2,1,07+9+21+13+15+10+25+342414332313332212312111343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxij 设某种物品有m个产地Ai(i=1,2,m)，各产地的产量分别是a1,a2,.,am；有n个销地Bj(jl,2,.n)，各销地的销量分别为b1,b2,.bn。假定从产地Ai(i=1,2,m)向销地出Bj(jl,2,.n)运输单位物品的运价是cij，问怎样调运这些物品才能使总运费最小?二、运输问题的描述二、运输问题的描述 产销运价表产销运价表 如果运输问题的总产量等于总销量，即有 minjji

5、ba11则称该运输问题为产销平衡问题产销平衡问题 bn b2 b1 需求量 Bn B2 B1 需方 供方 Am A2 A1 am a2 a1 供应量 nijjm1iibacmn cm2 cm1 c2n c22 c21 c1n c12 c11 如何建立供需搭配，使总的运输费用最小？供需平衡表供需平衡表 销销 产产 B1 B2 Bn 产量产量 c11 c12 c1n A1 x11 x12 x1n a1 c21 c22 c2n A2 x21 x22 x2n a2 cm1 cm2 cmn Am xm1 xm2 xmn am 销量销量 b1 b1 bn 平衡表、运价表和二为一平衡表、运价表和二为一 设从

6、Ai到Bj的物资运量为xij，njmiijijxcz11min三、产销平衡运输问题的数学模型三、产销平衡运输问题的数学模型 n1jjm1iibaAi的产品全部供应出去 m,2,1iaxin1jijn,2,1jbxjm1iijBj的需求全部得到满足 n,2,1j;m,2,1i0 xij1、数学模型、数学模型),.,1,.,1(0),.,2,1(),.,2,1(.11njmiXmiaXnjbXtsijnjiijmijijnimjijijxcz11min 它包含 mn 个变量，(m+n)个约束方程。其系数矩阵的结构比较松散，且特殊。2、数学模型特点、数学模型特点 njnjmimiinjijmiijj

7、axxb111111njmixbxxxbxxxbxxxaxxxaxxxaxxxtsijnmnnnmmmmnmmnn,.121 0 2122221211211121222221111211；mnmnmmnnnnxcxcxcxcxcxcz11222121111111min 它包含 mn 个变量，(m+n)个约束方程。其系数矩阵的结构比较松散，且特殊。2、数学模型特点、数学模型特点 行行nmvvvuuuxxxxxxxxxnmmnmmnn11111111111111111121212122221112113、运输问题约束条件的系数矩阵、运输问题约束条件的系数矩阵 该系数矩阵中对应于变量 的系数向量 ，

8、其分量中除第 i 个和第 m+j 个为1以外，其余的都为零。即 jmiTijeePjmi)0,0,1,0,0,1,0,0(ijPijx minjijijxczmin11 )n,j(bx)m,i(axmijijnjiij1 1 11 )n,j;m,i(xij11 0 uivj无约束（i=1,2,m;j=1,2,n)ui vj 设ui,vj为对偶变量，对偶问题模型为 nijjjm1iiivbuawmaxijjicvum个 n个 约束条件系数矩阵的元素等于0或1；约束条件系数矩阵的每一列有两个非零元素，这对应于每一个变量在前m个约束方程中出现一次，在后n个约束方程中也出现一次；对产销平衡运输问题，除上述两个特点外，还有以下特点：所有结构约束条件都是等式约束；各产地产量之和等于各销地销量之和。秩(A)=m+n-1，运输问题的基可行解中应包含m+n-1个基变量.5、运输问题具有下述特点：、运输问题具有下述特点：