(4.1.1)--4.1.1运输问题的数学模型.ppt

第第第第4 4 4 4章章章章 运输问题运输问题运输问题运输问题 运输问题是线性规划问题，由于其约束条件的特殊性，产生了运输问题是线性规划问题，由于其约束条件的特殊性，产生了特殊的解法。特殊的解法。4.4.4.4.1 1 运输问题运输问题运输问题运输问题问题的提出问题的提出问题的提出问题的提出 从从m个发点个发点A1,A2,.Am向向n个收点个收点B1,B2.Bn发送某种发送某种货物。货物。Ai发点的发量为发点的发量为ai，Bj收点的收量为收点的收量为bj。由。由Ai 运往运往Bj 单位货物的运费为单位货物的运费为Cij，由由Ai 运往运往Bj 货物的运量为货物的运量为Xij。问如问如何调配，才能使运费最省？何调配，才能使运费最省？当当发点的发量总和为发点的发量总和为 ai，收点的收量总和为收点的收量总和为 bj相等时，称此运输问题为平衡运输问题。否则称相等时，称此运输问题为平衡运输问题。否则称此运输问题为非平衡运输问题。此运输问题为非平衡运输问题。若没有特别说明，若没有特别说明，均假定运输问题为平衡的运输问题。均假定运输问题为平衡的运输问题。运输问题的数学模型运输问题的数学模型：Min S=cijxij i j xij=ai (i=1,2.m)j xij =bj(j=1,2n)i xij 0(i=1,2.m;j=1,2n)运输问题的数学模型运输问题的数学模型：其中其中 ai 0,bj 0,cij 0且共有且共有 m+n 个约束方程。个约束方程。并成立：并成立：ai =bj i j运输问题的图表形式运输问题的图表形式运输问题解的结构运输问题解的结构运输问题解的结构运输问题解的结构 由于由于由于由于 a ai i =b bj j成立成立成立成立 i i j j 其其其其m+nm+n个约束方程并不是独立的。实际上只有个约束方程并不是独立的。实际上只有个约束方程并不是独立的。实际上只有个约束方程并不是独立的。实际上只有m+n-1m+n-1个是独立的。即约束方程系数矩阵的秩为个是独立的。即约束方程系数矩阵的秩为个是独立的。即约束方程系数矩阵的秩为个是独立的。即约束方程系数矩阵的秩为 m+n-1m+n-1。