清华大学出版社：《运筹学》课程电子教案（PPT课件讲稿）第4章 运输问题

第4章运输问题 日第节运输问题的数学模型 口第2节表上作业法 口第3节产销不平衡的运输问题及其求解方法 口第4节 MATLAB解法 口第5节应用举例 清华大学出版社

清华大学出版社 2 第4章 运输问题 第1节 运输问题的数学模型 第2节 表上作业法 第3节 产销不平衡的运输问题及其求解方法 第4节 MATLAB解法 第5节 应用举例

第1节运输问题的数学模型 已知有m个生产地点A,÷=1,2,,m。可供应某种物资, 其供应量(产量)分别为a,÷=1,2,…,m,有n个销地 B,产=1,2,,n,其需要量分别为b,产12,n,从4 到B运输单位物资的运价(单价)为C,这些数据可汇总 于产销平衡表和单位运价表中,见表3-1,表32。有 时可把这两表合二为 、销地12 产量 产地 销地1 _产地 2 m 销量 BI B2 清华大学出版社

清华大学出版社 3 第1节 运输问题的数学模型 ❖ 已知有m个生产地点Ai ,i=1,2,…，m。可供应某种物资， 其供应量(产量)分别为ai，i=1，2，…，m，有n个销地 Bj，j=1,2,…,n，其需要量分别为bj，j=1,2,…,n，从Ai 到Bj运输单位物资的运价(单价)为cij，这些数据可汇总 于产销平衡表和单位运价表中，见表3-1，表3-2。有 时可把这两表合二为一。 销地 产地 1 2 ┉ n 产量 1 2 ┆ m A 1 A2 ┆ Am 销量 B1 B2 ┈ BNn 销地 产地 1 2 ┉ n 1 2 ┆ m C11 c12 ┈ c1n C21 c22 ┈ c2n ┇ cm1 cm2 ┈ cmn

第1节运输问题的数学模型 令若用x.表示从A到B的运量,那么在产销平衡的条件下 要求得总运费最小的调运方案的数学模型为 min=∑∑x ∑x=bj=12 (3-1) st ∑x=ai=1,2,…,m (3-2) ≥0 清华大学出版社

清华大学出版社 4 第1节 运输问题的数学模型 ❖ 若用xij表示从Ai到Bj的运量，那么在产销平衡的条件下， 要求得总运费最小的调运方案的数学模型为           = = − = = − =     = − = = 0 1,2, , (3 2) 1,2, , (3 1) . . min 1 1 1 1 ij n j ij ij m i ij j m i n j ij ij x x a i m x b j n st z c x  

第1节运输问题的数学模型 这就是运输问题的数学模型。它包含m×n个变量,(m+n) 个约束方程,其系数矩阵的结构比较松散,且特殊 1112…nx21x2 n m14m2 11…1 m7行 h v2 n行 清华大学出版社

清华大学出版社 5 第1节 运输问题的数学模型 ❖ 这就是运输问题的数学模型。它包含m×n个变量，(m+n) 个约束方程，其系数矩阵的结构比较松散，且特殊。 行 行 n m v v v u u u x x x x x x x x x n m n n m m mn                                         1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 11 12 1 21 22 2 1 2                 

第1节运输问题的数学模型 该系数矩阵中对应于变量x的系数向量Pn,其分量中除第个和 第m个为1以外,其余的都为零。即 P=(0,,1,0,…,0,10,….0)1=e;+e 对产销平衡的运输问题,由于有以下关系式存在: ∑b=∑∑=∑∑=∑ 清华大学出版社

清华大学出版社 6 第1节 运输问题的数学模型 该系数矩阵中对应于变量xij的系数向量Pij，其分量中除第i个和 第m+j个为1以外，其余的都为零。即 Pij=(0,… ,1,0,…,0,1,0,…,0)T=ei+em+j 对产销平衡的运输问题，由于有以下关系式存在：       = = = = = = =        =         = n j m i n j m i i m i ij n j bj xij x a 1 1 1 1 1 1

第2节表上作业法 令表上作业法是单纯形法在求解运输问题时的一种简化方法, 其实质是单纯形法。但具体计算和术语有所不同。可归纳为: 令(1)找出初始基可行解。即在(m×n)产销平衡表上用西北角 法或最小元素法, Vogel法给出mn-1个数字,称为数字格。 它们就是初始基变量的取值。。 (2)求各非基变量的检验数,即在表上计算空格的检验数, 判别是否达到最优解。如已是最优解,则停止计算,否则转 到下一步。 令(3)确定换入变量和换出变量,找出新的基可行解。在表上 用闭回路法调整。 令(4)重复(2),(3)直到得到最优解为止。 清华大学出版社

清华大学出版社 7 第2节 表上作业法 ❖ 表上作业法是单纯形法在求解运输问题时的一种简化方法， 其实质是单纯形法。但具体计算和术语有所不同。可归纳为： ❖ (1) 找出初始基可行解。即在(m×n)产销平衡表上用西北角 法或最小元素法，Vogel法给出m+n-1个数字，称为数字格。 它们就是初始基变量的取值。 。 ❖ (2) 求各非基变量的检验数，即在表上计算空格的检验数， 判别是否达到最优解。如已是最优解，则停止计算，否则转 到下一步。 ❖ (3) 确定换入变量和换出变量，找出新的基可行解。在表上 用闭回路法调整。 ❖ (4) 重复(2)，(3)直到得到最优解为止

第2节表上作业法 例1某公司经销甲产品。它下设三个加工厂。每日 的产量分别是:A1为7吨,A2为4吨,A3为9吨。该公 司把这些产品分别运往四个销售点。各销售点每日销 量为:B1为3吨,B2为6吨,B3为5吨,B4为6吨。已知 从各工厂到各销售点的单位产品的运价为表43所示。 问该公司应如何调运产品,在满足各销点的需要量的 前提下,使总运费为最少 清华大学出版社

清华大学出版社 8 第2节 表上作业法 ❖ 例1 某公司经销甲产品。它下设三个加工厂。每日 的产量分别是：A1为7吨，A2为4吨，A3为9吨。该公 司把这些产品分别运往四个销售点。各销售点每日销 量为：B1为3吨，B2为6吨，B3为5吨，B4为6吨。已知 从各工厂到各销售点的单位产品的运价为表4-3所示。 问该公司应如何调运产品，在满足各销点的需要量的 前提下，使总运费为最少

第2节表上作业法 解:先作出这问题的产销平衡表和单位运价表,见表 4-3,表4-4 表43单位运价表 表44产销平衡表 销地|B1|B2|B3|B 销地BB2B3|B 加工厂 加工厂 A1 A2 AAA 749 7|4105 销量 清华大学出版社

清华大学出版社 9 第2节 表上作业法 ❖ 解：先作出这问题的产销平衡表和单位运价表，见表 4-3，表4-4 销 地 加工厂 B1 B2 B3 B4 A1 A2 A3 3 1 7 11 9 4 3 2 10 10 8 5 销 地 加工厂 B1 B2 B3 B4 产 量 A1 A2 A3 7 4 9 销量 3 6 5 6 表4-3 单位运价表 表4-4 产销平衡表

2.1确定初始基可行解 与一般线性规划问题不同,产销平衡的运输问题总是存在 可行解。因有 ∑41=∑b=d 必存在x1≥0,÷1,…,m,产1,…,n,这就是可行解。又因 0≤ Sx. smin((a,b),故运输问题必存在最优解。 清华大学出版社

清华大学出版社 10 2.1 确定初始基可行解 与一般线性规划问题不同，产销平衡的运输问题总是存在 可行解。因有   = = = = m i n j ai bj d 1 1 必存在xij≥0，i=1，…，m，j=1，…，n，这就是可行解。又因 0≤xij≤min(aj，bj )，故运输问题必存在最优解

2.1确定初始基可行解 确定初始基可行解的方法很多,有西北角法,最小元素法 和伏格尔(voge法。一般希望的方法是既简便,又尽可能 接近最优解。下面介绍两种方法: 1.最小元素法 基本思想是就近供应,即从单位运价表中最小的运价开始确定 供销关系,然后次小。一直到给出初始基可行解为止。以例1 进行讨论。 第一步:从表3-3中找出最小运价为1,这表示先将A2的产品供 应给B1。因a2>b1,A2除满足B的全部需要外,还可多余1吨产 品。在表34的(A2,B1)的交叉格处填上3。得表3-5。并将表3 3的B1列运价划去。得表36 清华大学出版社

清华大学出版社 11 2.1 确定初始基可行解 确定初始基可行解的方法很多，有西北角法，最小元素法 和伏格尔(Vogel)法。一般希望的方法是既简便，又尽可能 接近最优解。下面介绍两种方法： 1. 最小元素法 基本思想是就近供应，即从单位运价表中最小的运价开始确定 供销关系，然后次小。一直到给出初始基可行解为止。以例1 进行讨论。 第一步：从表3-3中找出最小运价为1，这表示先将A2的产品供 应给B1。因a2＞b1，A2除满足B1的全部需要外，还可多余1吨产 品。在表3-4的(A2，B1 )的交叉格处填上3。得表3-5。并将表3- 3的B1列运价划去。得表3-6