黑龙江工程学院：《运筹学》第三章 运输问题

第三章运输问题 §1.运输问题的典例和数学模型 §2.表上作业法 §3.产销不平衡的运输问题及其应用

§1．运输问题的典例和数学模型 § 2．表上作业法 § 3．产销不平衡的运输问题及其应用 第三章 运输问题

§1.运输问题的典例和数学模型 例1某食品公司经销主要产品之一是糖果,它下面 设有三个加工厂,每天的糖果生产量分别为:A1-7t A2-4t,43-9。该公司把这些糖果分别运往四个地区 的门市部销售,各地区每天的销售量为:B1-36B,-66 B3-5,B4-6。已知从每个加工厂到各销售门市部每 吨糖果的运价如下表: 单位:元/t 市部 加工厂 A3 7 10

§1．运输问题的典例和数学模型 例1 某食品公司经销主要产品之一是糖果，它下面 设有三个加工厂，每天的糖果生产量分别为： ， ， 。该公司把这些糖果分别运往四个地区 的门市部销售，各地区每天的销售量为： ， ， ， 。已知从每个加工厂到各销售门市部每 吨糖果的运价如下表： A 7t 1 − A 4t 2 − A 9t 3 − B 3t 1 − B 6t 2 − B 5t 3 − B 6t 4 − 单位：元/t

现在把问题概括一下,在线性规划中我们研究这样 类运输问题:有某种物资需要调运,这种物资的计量 单位可以是重量、包装单位或其他。已知有m个地点可以 供应该种物资(以后通称产地,用,…,m表示), 有n个地点需要该种物资(以后通称销地j用…,n 表示),又知这m个产地的可供量(以后通称产量)为 ●。 9 an(可通写为a1),n个销地的需要量(以后 通称销量)分别为b,b…,bn(通写为b),从第个产地 到第个销地的单位物资运价为Cn

现在把问题概括一下，在线性规划中我们研究这样 一类运输问题：有某种物资需要调运，这种物资的计量 单位可以是重量、包装单位或其他。已知有m个地点可以 供应该种物资（以后通称产地，用 表示）， 有n个地点需要该种物资（以后通称销地，用 表示），又知这m个产地的可供量（以后通称产量）为 （可通写为 ），n个销地的需要量（以后 通称销量）分别为 （通写为 ）,从第i个产地 到第j个销地的单位物资运价为 。 i =1,  ,m j =1,  ,n a a am , , , 1 2  i a b b bn , , , 1 2  j b ij c

产销平衡表 销地 产量 产地 销量 b, b bx 单位运价表 销地 产地

产销平衡表 单位运价表

如果用x;代表从第i个产地调运给第j个销地的 物资的单位数量,那么在产销平衡的条件下,使总运 费支出最小,其数学模型如下: mmn2三 ∑∑cx ∑ 12 x.≥0

如果用 xij 代表从第 i 个产地调运给第 j 个销地的 物资的单位数量，那么在产销平衡的条件下，使总运 费支出最小，其数学模型如下： ( ) ( )            = = = = =    = = = = 0 1, , 1, , min 1 1 1 1 i j m i i j i i n j i j m i n j i j i j x x b j n x a i m z c x  

§2.表上作业法 用表上作业法求解运输问题时,首先给出一个初始方案,其 次给出一个判别准则,然后对初始方案进行调整,直到求出最优 解。 由上节例子来具体说明表上作业法的步骤,首先列出产销平 衡表和单位运价表。 产销平衡表 门市部 加工厂 BI B3 B4产量 A 7 Ah A3 9 单位运价表 门市部\B1 B2 B3 Bu A 3 11 3 10 A 1 9 2 A3 7 5

§2．表上作业法 用表上作业法求解运输问题时，首先给出一个初始方案，其 次给出一个判别准则，然后对初始方案进行调整，直到求出最优 解。 由上节例子来具体说明表上作业法的步骤，首先列出产销平 衡表和单位运价表

、初始方案的给定 初始方案的给定方法很多,这里介绍两种: 1.最小元素法 基本思想是就近供应,即从单位运价表中最小的运 价处开始确定供销关系,依次类推,直到求出全部方案 第一步: 产销平衡表 市部 B 加工 B2 B,产量 A 7 A2 单位运价表 门市部 B 加工厂 B2 B 11 A44 9 2 8 4

一、初始方案的给定 初始方案的给定方法很多，这里介绍两种： 1. 最小元素法 基本思想是就近供应，即从单位运价表中最小的运 价处开始确定供销关系，依次类推，直到求出全部方案 第一步：

第二步: 产销平衡表 门市部 B4 加工厂 产量 A 单位运价表 市部 加工厂 B 11 3 4 5 第三步: 产销平衡表 门市部 加工厂 BI B B4|产量 A1 4 3 1 A 3 单位运价表 门市部 B B 加工厂 11 A3 5

第二步： 第三步：

第四步: 加x八门市部 B B B3 B,‖产量 A1 4 A3 单位运价表 门市部 B4 Ay 第五步: 产销平衡表 门市部 B. B B B4 A1 A3 单位运价表 门市部

第四步： 第五步：

第六步 产销平衡表 门市部 By B2 B3 B 产量 加工厂 AAA 单位运价表 门市部 加工厂 这时单位运价表中所有元素已经都划掉了,产销平 衡表中数字就是一个调运方案,这个方案的总费用为 3×1+6×4+4×3+1×2+3×10+3×5=86

第六步： 这时单位运价表中所有元素已经都划掉了，产销平 衡表中数字就是一个调运方案，这个方案的总费用为： 31+64+43+12+310+35 =86