第三章运输问题 §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
第六步: 这时单位运价表中所有元素已经都划掉了,产销平 衡表中数字就是一个调运方案,这个方案的总费用为: 31+64+43+12+310+35 =86