运输问题讲义PPT学习教案

1、会计学1 运输问题讲义运输问题讲义 管理 计划 组织 生产1生产2生产3 销售1销售4销售2销售3 原材料1原材料2原材料3原材料4 物流 第1页/共37页 运输问题的数学模型运输问题的数学模型 设有设有m个产地（记作个产地（记作A1，A2，A3,Am），生产），生产 某种物资，其产量分别为某种物资，其产量分别为a1,a2，am；有；有n个销个销 地（记作地（记作B1，B2，Bn），其需要量分别为），其需要量分别为 b1,b2，bn；且产销平衡，即；且产销平衡，即 。从。从 第第i个产地到个产地到j 个销地的单位运价为个销地的单位运价为cij ，在满足各，在满足各 地需要的前提下，求总运输费用

2、最小的调运方案地需要的前提下，求总运输费用最小的调运方案 。 设设xij(i=1,2,，m；j=1,2,n)为第为第i个产地到个产地到 第第j个销地的运量。个销地的运量。 n j j m i i ba 11 第2页/共37页 销地销地 产地产地 B 1 B 2 B n 产量产量 C 11 C 1 2 C 1 n A 1 x 11 x 1 2 x 1 n a 1 C 21 C 2 2 C 2 n A 2 x 21 x 2 2 x 2 n a 2 C m 1 C m 2 C m n A m x m1 x m 2 x m n a m 销量销量 b 1 b 2 b n 第3页/共37页 m i n j

3、 ji ba 11 njmix njbx miax xcz ij j m i ij i n j ij m i n j ijij , 2 , 1;, 2, 1, 0 , 2 , 1, , 2 , 1, min 1 1 11 第4页/共37页 nnmmnn nmmm nmmn mnmmmnmn nmnn nmnn bxxxxxx bxxxxxxx bxxxxxxx axxxxxx axxxxxxx axxxxxxx 1221111 22122211211 11222111211 211111 23122221111000 0000 0000 000 0000 0000 第

4、5页/共37页 111 111 111 111 111 111 212221212111 nmmmnn xxxxxxxxx 行 行 n m 第6页/共37页 （1 1）约束条件系数矩阵中）约束条件系数矩阵中元素等于元素等于0 0或或1 1； （2 2）约束条件系数矩阵的）约束条件系数矩阵的每一列有两个非每一列有两个非0 0元素元素，与每，与每 个变量在前个变量在前 m m 个约束方程和后个约束方程和后 n n 个约束方程中各出现个约束方程中各出现 一次相对应。一次相对应。 （3 3）所有的结构约束方程都是）所有的结构约束方程都是等式等式； （4 4）各产地的产量之和等于各销地的销量之和。）各产

5、地的产量之和等于各销地的销量之和。 第7页/共37页 （1 1）产销平衡时一定有最优解；）产销平衡时一定有最优解； （2 2）如果）如果 ai 和 和 bj 都是整数，则一定都是整数，则一定 有有 整数最优解。整数最优解。 （3 3）基变量有）基变量有 m + n - 1 个。个。 （4 4） m + n - 1 m + n - 1 个基变量不构成闭回个基变量不构成闭回 路路 产销平衡的运输问题，有以下产销平衡的运输问题，有以下3 3条结论：条结论： 第8页/共37页 x31 x41 x43 x34 x14x 13 x31 x23 x22 x33 x12 x11 x22 x12 x21 x11

6、 闭回路类型图 闭回路示意图 1 1、闭回路的连线、闭回路的连线 都是水平或垂直的都是水平或垂直的 。 2 2、表中每一行和、表中每一行和 每一列由折线相连每一列由折线相连 的闭回路的顶点只的闭回路的顶点只 有两个有两个 第9页/共37页 设设 X X= =（x xij ij）为运输问题的一个解，则要 ）为运输问题的一个解，则要 求每步得到的求每步得到的 X X 都必须是基本可行解，这就要都必须是基本可行解，这就要 求：求： （1 1）X X 必须满足模型中的所有约束条件必须满足模型中的所有约束条件 ； （2 2）基变量对应的约束方程组的系数列）基变量对应的约束方程组的系数列 向量线性无关；向

7、量线性无关； （3 3）解中非）解中非0 0变量变量x xij ij的个数不能多于 的个数不能多于 个；个； （4 4）基变量的个数在迭代过程中应该保）基变量的个数在迭代过程中应该保 持为持为个。个。 第10页/共37页 某制药公司在全国设有三个生产基地，其中 某品种药的日产量为：A1厂700箱，A2厂400箱，A3厂 900箱。这些生产基地每天将这些药分别运往四个地 区的经销部门，各经销部门每天的需求量为：B1部 门300箱，B2部门600箱，B3部门500箱，B4部门600箱 。已知从每个生产基地到各销售部门每箱药品的运 价如表所示，问该制药公司应如何调运，使在满足 各销售部门需要的情况下

8、，总的运输费用最少？ 第11页/共37页 生产基地生产基地 销售部门销售部门 B1B2B3B4 A10.31.10.31.0 A20.10.90.20.8 A30.70.41.00.5 （金额单位：元）（金额单位：元） 第12页/共37页 销地销地 产地产地 B 1 B 2 B 3 B 4 产量产量 0.3 1.1 0.3 1.0 A 1 x 1 1 x 1 2 x 1 3 x 1 4 700 0.1 0.9 0.2 0.8 A 2 x 2 1 x 2 2 x 2 3 x 2 4 400 0.7 0.4 1.0 0.5 A 3 x 3 1 x 3 2 x 3 3 x 3 4 900 销量销量

9、300 600 500 600 第13页/共37页 34333231 24232221 14131211 5.00.14.07.0 8.02.09.01.0 0.13.01.13.0min xxxx xxxx xxxxz 4,3,2, 1;3,2, 1,0 600 500 600 300 900 400 700 342414 332313 322212 312111 34333231 24232221 14131211 jix xxx xxx xxx xxx xxxx xxxx xxxx ij 第14页/共37页 销地销地 产地产地 B 1 B 2 B 3 B 4 产量产量 0.3 1.1 0

10、.3 1.0 A 1 400 300 700 0.1 0.9 0.2 0.8 A 2 300 100 400 0.7 0.4 1.0 0.5 A 3 600 300 900 销量销量 300 600 500 600 第15页/共37页 销地 产地 B1 B2 B3 B4 产量 0.3 1.1 0.3 1.0 A1 0.1 0.9 0.2 0.8 A2 0.7 0.4 1.0 0.5 A3 销量 300400 300600500600 700 900 2000 最小元素最小元素 0.1 产量产量400和销量和销量300 最小者最小者 第16页/共37页 销地 产地 B2 B3 B4 产量 1.1

11、 0.3 1.0 A1 0.9 0.2 0.8 A2 0.4 1.0 0.5 A3 销量 300400 600500600 700 900 100 2000 最小元素最小元素 0.2 第17页/共37页 销地 产地 B2 B3 B4 产量 1.1 0.3 1.0 A1 0.4 1.0 0.5 A3 销量 300 600500600 700 900 100 400 2000 最小元素最小元素 0.3 第18页/共37页 销地 产地 B2 B4 产量 1.1 1.0 A1 0.4 0.5 A3 销量 300 600600 700 900 100 400 600 2000 最小元素最小元素 0.4

12、第19页/共37页 销地 产地 B4 产量 1.0 A1 0.5 A3 销量 300 600 700 900 100 400 600300 2000 最小元素最小元素 0.5 第20页/共37页 销地 产地 B4 产量 1.0 A1 0.5 销量 300 600 700 100 400 600300 300 2000 860 3005 . 06004 . 01002 . 0 3001 . 03000 . 14003 . 0 3 1 4 1 ij ijijx cZ 0.3 0.10.2 0.4 第21页/共37页 销地 产地 B1 B2 B3 B4 产量 0.3 1.1 0.3 1.0 A1 0

13、.1 0.9 0.2 0.8 A2 0.7 0.4 1.0 0.5 A3 销量 300 400 300600500600 700 900 200 400 300 600 200 2000 1080 6005 . 03000 . 12002 . 0 2009 . 04001 . 13003 . 0 3 1 4 1 ij ijijx cZ 西北角西北角 第22页/共37页 ai，bj 第23页/共37页 销地 产地 B1 B2 B3 B4 产量 0.3 1.1 0.3 1.0 A1 0.1 0.9 0.2 0.8 A2 0.7 0.4 1.0 0.5 A3 销量 900600300 700400(

14、-1)300(+1) 300(-1)400100(+1) 300600500600 11 11= = c c11 11- - c c2121+ + c c23 23- - c c13 13 = 0.3 - 0.3 + 0.2 - 0. 1 = = 0.3 - 0.3 + 0.2 - 0. 1 = 31 31= = c c31 31- -c c2121+ +c c2323- -c c13 13 + +c c1414- -c c34 34 = 0.7-0.1+0.2-0.3+1.0-0.5 = = 0.7-0.1+0.2-0.3+1.0-0.5 = 找出每一个空格空格(非基变量)的闭回路( )。

15、第24页/共37页 12 = c12-c32+c34-c14 = 1.1-0.4+0.5-1.0 = 0.2 22 = c22-c32+c34-c14+c13-c23 = 0.9-0.4+0.5-1.0+0.3-0.2= 0.1 24 = c24-c14+c13-c23 = 0.8-1.0+0.3-0.2 = 33 = c33-c34+c14-c13 = 1.0-0.5+1.0-0.3 = 1.2 第25页/共37页 注意：注意：在运输问题中通常目标函数是在运输问题中通常目标函数是 求最小值，所以这时要求所有的检验数为正求最小值，所以这时要求所有的检验数为正 值。值。 对于每一个非基变量，在运

16、输表中唯对于每一个非基变量，在运输表中唯 一对应一条这样的闭回路。一对应一条这样的闭回路。 不能出现全部顶点由填有数字的格构不能出现全部顶点由填有数字的格构 成的闭回路。成的闭回路。 第26页/共37页 5 . 0 4 . 0 2 . 0 1 . 0 0 . 1 3 . 0 43 23 32 12 41 31 vu vu vu vu vu vu 销地销地 产地产地 B 1 B 2 B 3 B 4 产量产量 u i 0 . 3 1 . 0 A 1 4 0 0 3 0 0 7 0 0 u 1 0 . 1 0 . 2 A 2 3 0 0 1 0 0 4 0 0 u 2 0 . 4 0 . 5 A 3

17、 6 0 0 3 0 0 9 0 0 u 3 销量销量 3 0 0 6 0 0 5 0 0 6 0 0 2 0 0 0 v j v 1 v 2 v 3 v 4 ij = cij - CB B 1 Aij = cij - ( ui + vj ) ssss jiji jiji jiji cvu cvu cvu 22 22 1111 9 . 0 2 . 0 8 . 0 1 . 0 4 . 0 0 1 . 0 4 3 2 1 3 2 1 v v v v u u u 不妨设不妨设 u 2 = 0 由基变量的检验数等于由基变量的检验数等于0，可得到这一组等式。，可得到这一组等式。 第27页/共37页 销地

18、销地 产地产地 B 1 B 2 B 3 B 4 产量产量 ui 0. 3 1. 1 0. 3 1. 0 A 1 ( 0. 1) ( 0. 2) 400 300 700 u 1 ( 0. 1 ) 0. 1 0. 9 0. 2 0. 8 A 2 300 ( 0. 1) 100 (-0. 1) 400 u 2 ( 0 ) 0. 7 0. 4 1. 0 0. 5 A 3 ( 1. 0) 600 ( 1.2) 300 900 u 3 ( - 0. 4 ) 销量销量 300 600 500 600 2000 v j v 1 ( 0. 1 ) v 2 ( 0. 8 ) v 3 ( 0. 2 ) v 4 (

19、0. 9 ) 11 = c11 - ( u1 + v1 ) =0.3-(0.1+0.1)=0.1 24 = c24 - ( u2 + v4 ) =0.8 - ( 0+0.9 )= - 0.1 第28页/共37页 销地 产地 B1 B2 B3 B4 产量 0.3 1.1 0.3 1.0 A1 0.1 0.9 0.2 0.8 A2 0.7 0.4 1.0 0.5 A3 销量 900600300 700 300(-100) 300400 300600500600 (+100) 400(+100) 100(-100) 2000 找出检验数找出检验数 ij为最小负值的格子的闭回路为最小负值的格子的闭回路

20、在满足所在满足所 有约束条件的情况下，尽可能增大这个格子的有约束条件的情况下，尽可能增大这个格子的xij j值值 调整此闭回路上其他顶点的值调整此闭回路上其他顶点的值检验新解的最优性检验新解的最优性 重复上步骤直至得到最优解为止重复上步骤直至得到最优解为止 第29页/共37页 销地销地 产地产地 B 1 B 2 B 3 B 4 产量产量 0. 3 1. 1 0. 3 1. 0 A 1 (0) (0. 2) 500 200 700 0. 1 0. 9 0. 2 0. 8 A 2 300 (0. 2) (0. 1) 100 400 0. 7 0. 4 1. 0 0. 5 A 3 (0. 9) 600 (1. 2) 300 900 销量销量 300 600 500 600 2000 第30页/共37页 求初始可行解 (保证填有数字的格子数为 m+n-1) 最小元素法、西北角法、Vogel法 计算位势ui,vj。对每个填有数字的格子 (Ai,Bj)按方程ui+vj=cij求出 u1,u2,um;v1,v2,vn 对每