天水师范学院：运输问题的线性规划（运输问题）

主讲人:卫斌 制作:魏永牛 天水师乾学院薮理与信科学学院数学系 2004车5月

主讲人：卫 斌 制 作：魏永牛 天水师范学院 数理与信息科学学院 数学系 ２００４年５月

第五章运输问题 导 在处理产、供、销的经济活动中, 会经常遇到物资调拨的运输问题。如粮 棉油、煤炭、钢铁、水泥、化肥、木材 等物资要由若干个产地调运到若干个销 言售地。问题是,怎样制定合理的调用方 案才能使总运输费用最少?本章将专门 讨论这类特殊形式的线性规划问题

在处理产、供、销的经济活动中， 会经常遇到物资调拨的运输问题。如粮 棉油、煤炭、钢铁、水泥、化肥、木材 等物资要由若干个产地调运到若干个销 售地。问题是，怎样制定合理的调用方 案才能使总运输费用最少？本章将专门 讨论这类特殊形式的线性规划问题。 导 言 第五章 运输问题

产销平衡的运输问题 5.1 运例某食品公司经销的主要商品之一是糖果,它下面设有三个加 工厂。某个的产量分别为A—7t,A24,A3-9该公司把这 些糖果分别运往四个地区的门市部销售,各地区每天的销售量为: 输问题的数学模型 B1-3t,B26t,B3-5t,B46t。已知从各个加工厂到各销 售部门每吨的运价见下表: 单位:元 加工厂 门市部B1 B 10 问:该食品公司应如何调运,在满足各部门销售的情况下, 使总的运费支出为最少?

例 某食品公司经销的主要商品之一是糖果，它下面设有三个加 工厂。某个的产量分别为A1—7t， A2—4t， A3—9t该公司把这 些糖果分别运往四个地区的门市部销售，各地区每天的销售量为： B1—3t， B2—6t， B3—5t， B4—6t 。已知从各个加工厂到各销 售部门每吨的运价见下表： 5.1 运 输 问 题 的 数 学 模 型 A3 7 4 10 3 A2 1 9 2 8 A1 3 11 3 10 B1 B2 B3 B4 门市部 加工厂 单位：元/t 问：该食品公司应如何调运，在满足各部门销售的情况下， 使总的运费支出为最少？ 产销平衡的运输问题

产销平衡的运输问题 5.1 运输问题的数学模型一 无论全国或一个地区,在各种生产或生活物 资调运中都可以提出入上述问题类似的例子。 现在把问题概括一下,在线性规划中我们研 究这样一类运输问题:

无论全国或一个地区，在各种生产或生活物 资调运中都可以提出入上述问题类似的例子。 现在把问题概括一下，在线性规划中我们研 究这样一类运输问题： 5.1 运 输 问 题 的 数 学 模 型 产销平衡的运输问题

产销平衡的运输问题 5.1 运输问题的数学模型一 设有某种物资要从m个产地(或称发点) A1(i=1,2,…,m运往n个销地(或称收点)B;(j 2,灬m),A1的产量为a;,B;的销量为b;把A运 到B的单位运价设为c1;,问怎样编制调运方 案才能使总运费最少? 假设从A运到B的物资数量为x1,总运 费为S,总产量=总销量。那么这个运输问题 的数学模型是:

设有某种物资要从m个产地（或称发点） Ai(i=1，2，…，m)运往n个销地（或称收点）Bj (j=1， 2，…n) ，Ai的产量为ai，Bj的销量为bj，把Ai运 到Bj的单位运价设为cij，问怎样编制调运方 案才能使总运费最少？ 假设从Ai运到Bj的物资数量为xij，总运 费为S，总产量=总销量。那么这个运输问题 的数学模型是： 5.1 运 输 问 题 的 数 学 模 型 产销平衡的运输问题

产销平衡的运输问题 5.1 运输问题的数学模型是: 产销平衡表 运输问题的数学模型一 地 销地 2 n a X X X X X X a m 销量bb,b 单位运价表 地销地|1 12 21

产销平衡的运输问题 5.1 运输问题的数学模型 运输问题的数学模型是: 产销平衡表 产地 产量ai 销地 销量bi 1 ２ … n １２m  b1 b2 … bn a1 a2 am x11 x12 … x1n x21 x22 … x2n xm1 xm2 … xmn     产地 销地 1 ２ … n １２m  c11 c12 … c1n c21 c22 … c2n cm1 cm2 … cmn     单位运价表

产销平衡的运输问题 5.1 运输问题的数学模型是: min s= 运输问题的数学模型一 ∑ ∑ s t i=1 ∑ a1≥0,b≥0,x≥0(=1,2,…,m2j=1,2,…,n)

   nj mi ij ij S c x 1 1 min             0, 0, 0( 1,2, , , 1,2, , ) . 1 1 11 a b x i m j n a b x b x a s t i j ij mi nj i j mi ij j nj ij i   产销平衡的运输问题 5.1 运输问题的数学模型 运输问题的数学模型是:

产销平衡的运输问题 51其矩阵形式为mimS=cx aX=b st X≥0.b≥0 运输问题的数学模型一 100 00 011 00 0 00 000 010 0 00 0 00 100 00 C=(c1,c12,…,c1n,C21,C2,c2n,…,cm1,cm2,…Cm Ⅹ=(1,X12,…,X1n,X21,X2,X2n,…,Xm1,Xm2,…,xm)T

       0, 0 . . min X b AX b st S CX C=(c11，c12，…，c1n，c21，c22，c2n，…，cm1，cm2，…cmn ) B=（a1，a2，…，am，b1，b2，…bn )T X =(x11，x12，…，x1n，x21，x22，x2n，…，xm1，xm2，…xmn )T 5.1 运 输 问 题 的 数 学 模 型 其矩阵形式为 产销平衡的运输问题      0 0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0                                           A n行      m行     

产销不平衡运输问题的转化 5.1 运(1)产量大于销量的情形z4>∑ 输 其运输问题的数学模型是 题 的 minS=∑∑cx 数 学 模 型 st ∑x a1≥0.b≥0,x≥0(=1,2…m,j=1,2,…,m)

（1）产量大于销量的情形      m i n j ai bj 1 1    m i n j ij ij S c x 1 1 min                0, 0, 0( 1,2, , , 1,2, , ) . . 1 1 a b x i m j n x b x a st i j ij m i ij j n j ij i   5.1 运 输 问 题 的 数 学 模 型 产销不平衡运输问题的转化 其运输问题的数学模型是

产销不平衡运输问题的转化 5.1 由于总量大于总销量,所以多余物资应储存在产地 运社某产地A的多余存储量为X1m+于是运输问题的约束 条件方程组为: 输问题的数学模型 ∑x=∑x+ in+1 (i=1,2,…,m) 则 ∑x,m=∑a-∑

由于总量大于总销量，所以多余物资应储存在产地。 社某产地Ai的多余存储量为xi,n+1，于是运输问题的约束 条件方程组为： i n i n j n j xij  xij  x   a      , 1 1 1 1 (i  1,2,,m)   m i ij bj x 1 ( j 1,2,, n) 1 1 1 1 , 1           n n j i m i m i xi n ai b b 则 5.1 运 输 问 题 的 数 学 模 型 产销不平衡运输问题的转化