管理运筹学--第三章运输问题(可编辑)

管理运筹学--第三章运输问题(可编辑) 管理运筹学--第三章运输问题 第三章 运输问题 本章主要内容 第一节 运输 问题的数学模型及其特征 2. 一般运输问题的数学模型 运输问题的约束方程 组系数矩阵及特征 3. 运输问题的特征 闭回路 第二节 运输问题表上作业法 第一步:编制初始调运方案 最小元素法 Vogel 法 第二步:计算各非基变量的 闭回路法 2. 位势法 位势及检验数的求法 第四步:调整调运方案 检验数 1. 表上作业法计算中应注意的问题 第三节 产销不平衡的运输问题及应用 1. 确 定入基变量:选取最小负检验数对应的非基变量入基 2. 确定出基变量和调整量 将进基变量对应的闭回路中的顶点分为奇顶点和偶顶点， 令θ= min{ 闭回路上 则θ即为调整量，选取一个运量等于θ的偶顶点所有偶顶点对应的运量xij } 为出基变量。 3.调整:闭回路上奇顶点上的运量增加θ，偶顶点上的运量减少 θ。闭回路以外顶点的运量不变。 上例中:若选x14进基，则?=min{6,3,6}=3, 出基变量为x23,调整后得: 6 4 8 3 需求量 3 14 7 5 2 4 8 A3 -5 5 5 2 4 3 1 A2 -6 0 9 7 10 9 2 A1 库存量 B4 B3 B2 B1 6 2 3 1 6 3 总运费: z= 2×3 + 9×3 + 7×3 + 3×5 + 2×4 + 5×3 = 92 110 x32进基，则?=min{3,3}=3, 出基变量选x34,调整后得: 6 4 8 3 需求量 7 5 2 4 8 A3 5 2 4 3 1 A2 9 7 10 9 2 A1 库存量 B4 B3 B2 B1 3 5 4 3 3 3 0 -6 -2 2 9 4 7 5 6 6 1 8 -3 检验数全部非负，已经是最优调运方案; 总费用 z*= 2×3 + 9×0 + 7×6 + 3×5 + 4×3 + 2×4 = 83 6 4 8 3 需求量 7 5 2 4 8 A3 5 2 4 3 1 A2 9 7 10 9 2 A1 库存量 B4 B3 B2 B1 0 5 4 3 3 6 0 -6 -5 2 9 7 7 3 5 3 1 11 3 1.解的情况 唯一:非基变量检验数全部大于0; 无穷多解:至少存在一 个非基变量检验数等于0。 2.退化情况: 在确定初始基可行解的时候，当填(i,j) 格子时，若ai=bj, 则xij=ai=bj, 但此时只能划去一行或一列，在后面的填充 过程中相应格子要填0。 3.调整时，若闭回路上出现两个或两个以上偶顶点取 值同时达到最小，只能选一个变量出基。 例3-4 用表上作业法求解下列运输问 题. 6 5 6 3 需求量 9 5 10 4 7 A3 4 8 2 9 1 A2 7 10 3 11 3 A1 供应量 B4 B3 B2 B1 6 5 6 3 需求量 9 5 10 4 7 A3 4 8 2 9 1 A2 7 10 3 11 3 A1 供 应量 B4 B3 B2 B1 4 3 1 3 6 3 6 5 6 3 需求量 9 5 10 4 7 A3 4 8 2 9 1 A2 7 10 3 11 3 A1 供应量 B4 B3 B2 B1 4 3 1 3 6 3 0 3 10 -1 2 -5 9 1 2 1 -1 10 12 调整量为 min{3,1}=1，出基变量为x23. 6 5 6 3 需求量 9 5 10 4 7 A3 4 8 2 9 1 A2 7 10 3 11 3 A1 供应量 B4 B3 B2 B1 2 3 -5 9 0 2 2 1 9 12 由于x11的检验数为0，5 3 1 3 6 2 最优解: 0 3 10 - 所以最优解不唯一。 6 5 6 3 需求量 9 5 10 4 7 A3 4 8 2 9 1 A2 7 10 B4 B3 B2 B1 5 1 3 3 6 2 0 3 10 -2 3 -5 9 2 2 3 11 3 A1 供应量 1 9 12 0 最优解: 表上作业法是以产销平衡为前提的: 实际中，往往遇到产销 不平衡的运输问题 1.产大于销(供过于求) 2.销大于产(供不应求) 一、 产销不平衡运输问题向产销平衡运输问题的转化 产大于销的运输问题: 数学模 型 设xi n+1 是产地Ai 的储存量，化成标准形 其中 引入一个虚拟的销地(需 求量等于 )，并令各个产地到虚拟销地的单位运费为0。 产小于销 的运输问题: 引入一个虚拟的产地(产量等于 )， 并令该虚拟产 地到各销地的单位运费为0。 总供应量为42千吨，而总需求量为37千吨 例3-5: A1、A2、A3三个蔬菜生产地生产的蔬菜主要供应B1、B2、B3、B4四个城市。已 知三个产地今年的蔬菜产量预计分别为17千吨、15千吨和10千吨;四个城市 今年的蔬菜需求量分别为20千吨、5千吨、8千吨和4千吨;从每个蔬菜产地平 均运输1千吨蔬菜到各个城市的单位费用(万元)见下表，你能否替他们编制一个 总运费最省的蔬菜调运方案, 4 8 5 20 需求量 10 8 9 2 5 A3 15 3 10 5 7 A2 17 12 4 8 1 A1 供应量 B4 B3 B2 B1 单位运费 5 4 8 5 20 需求量 10 0 8 9 2 5 A3 15 0 3 10 5 7 A2 17 0 12 4 8 1 A1 供应量 B5 B4 B3 B2 B1 单位运费 注 意:求出最优方案后， A1、A2、A3三个蔬菜产地运往虚拟城市的运量，刚好分别是各产地的剩余蔬菜量。 6 2 9 4 B4 4 4 3 2 需求量 7 0 1 8 7 A3 5 0 5 3 10 A2 7 0 3 11 2 A1 供应量 B5 B3 B2 B1 需求地 生产地 0 0 -2 2 0 4 3 0 8 2 5 7 2 3 3 4 3 2 2 2 3 8 7 最优解中x15=2, x25=2，表示两个产地没有运出去的蔬菜量。 例3―6 假如将例3―5中产地A1蔬菜产量不是17千吨，而是10千吨，就成了一个供不应求的运输问题，引入一个供应量为2千吨的虚拟产地A4;令虚拟产地到城市B1、B2、B3、B4的单位运费为0 4 8 5 20 需求量 2 0 0 0 0 A4 10 8 9 2 5 A3 15 3 10 5 7 A2 10 12 4 8 1 A1 供 二、转运问题 前面研究的运输问题:每个供应点应量 B4 B3 B2 B1 单位运费 和每个需求点之间都可以直接运送物资;供应点只输出不输入，而需求点只输入不输出，这是比较简单的物资调运问题。但是在实际生活中，关于物资调运的情况通常要复杂得多: (1)不仅有供应点和需求点，还可能存在中转站点; (2)有的供应点不能向某需求点直接供应物资; (3)有些供应点不仅能输出，还能输入物资;同样某些需求点不仅能输入物资，还能输出物资。即有些供应点或需求点具有了中转站的作用。 这就使得在物资调运过程中出现了物资中转的情形，因此我们把这类问题叫作转运问题。 转运问题可以看作是运输问题的推广，所以也可以用表上作业法求解。不过首先要将转运问题转化为产销平衡的运输问题，下面我们就举例来介绍如何转化。 例3―7 现有某种物资要从两个产地A1、A2运到三个需求地B1、B2、B3去，产地A1、A2的供应量分别为10和2，需求地B1、B2、B3的需求量分别为3、1和8。其中，产地A2和需求地B2具有中转功能;另外，还有一个纯粹的中转站C。各产地、需求地以及中转站之间的单位运价见下表。试求一个使总运费最省的物资调运方案。 0 7 2 3 1 C 1 3 0 2 M B2 4 2 M 3 0 A2 2 1 3 6 2 A1 C B3 B2 B1 A2 单位运费 解:这个转运问题的总产量为10+2=12，总需求量为3+1+8=12，是一个产销平衡的转运问题。显然，中转站或者具有中转作用的点的最大中转量Q=12。 首先分析一下中 转站C，C既有从A1、A2、B2的物资输入，又有向A2、B1、B2和B3的物资输出，具有需求点和供应点的双重地位。为了转化成运输问题，不妨将C一分为二，其中一个为供应点，只有物资输出，另一个为需求点，只有物资输入。 由于最大中转量Q=12，所以我们规定供应点C的供应量为12，需求点C的需求量也为12。 其次，我们分析一下产地A1、A2，其中A1只有输出，没有输入，可以看作是一个纯粹的供应点，所以不需要作任何调整。而A2则除了有输出，还有输入，是一个兼具中转功能的供应点。跟前面的处理方式类似，因为A2的实际供应量是2，而A2可能的最大中转量为Q=12，所以规定: 供 = Q + A2的实际供应量 = 12+2 = 14 需求点A2的需求量 = Q 应点A2的供应量 = 12 * * 管理运筹学教学课件 第一节 运输问题的数学模型及其特征 第二节 第三节 产销不平衡的运输问题及应用 第四节 运输问运输问题的表上作业法 题的软件求解方法及应用 案例分析 实例 一般运输问题的数学模型 运输问题的特征 例3-1 某公司下属两个工厂生产的产品都需要先存放一段时间再销售，产品可以任意存放在三个仓库，各工厂需要运输到仓库的产品数量、从各个工厂运输一件产品的运费以及每个仓库的最大库存量见下表 单位运费 仓库1 仓库2 仓库3 产品量(件) 工厂1 4 8 6 150 工厂2 3 5 2 200 库存量(件) 160 80 110 问两个工厂的产品分别应该运往哪些仓库，运多少，才能使总运费最省? 1.实例 由于需要运出的产品总量是150+200=350，恰等于仓库的总库存量160+80+110=350，供需平衡，我们把这样的运输问题称为产销平衡的运输问题。在产销平衡的运输问题中，目标函数是总运费最少，约束条件有两类:一类是从每个工厂运出去的产品恰好等于总产量;另一类是每个仓库收到的产品数量刚好等于其最大库存量。由此可以建立该问题的线性 规划 污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文 模型: 进一步讨论，如果工厂1的产品量不是150件，而是200件，问题就成为一个供过于求的产销不平衡运输问题，这就意味着工厂的部分产品无法运出，这时问题的数学模型可以表示为: 供不应求的运输问题与供过于求的运输问题类似 有m个供应点向 n个需求点供应某种物资，这m个供应点A1、A2、…...Am的供应量分别为a1、 a2、…...am;n个需求点B1、B2、…...Bn的需求量分别为b1、b2、…...bn; 已知从任一供应点Ai向任一需求点Bj运输一个单位物资的费用为cij。问采取 什么样的物资调运方案才能使总运费最省, bn … b2 b1 需求量 am cmn … cm2 cm1 Am … … … … … … a2 c2n … c22 c21 A2 a1 c1n … c12 c11 A1 供应量 Bn … B2 B1 矩阵A是一个m+n行mn列的矩阵，它的秩为m+n-1。 运 输问题应该有m+n-1个基变量。 系数矩阵非常稀疏。 xij的系数列向量为: m 行 n行 特征1:运输问题一定有可行解; 特征2:运输问题一定有最优解; 特 :运输问题每一组基对应 m+n-1个基变量; 特征4:运输问题的 m+n-1个征3 基变量构成的变量组不含闭回路; 特征5:任意一个非基变量和 m+n-1个基变 特征6:如果运量组成的变量组中必定存在一条并且只存在唯一一条闭回路; 输问题中的供应量和需求量都是整数，则任一基解中各变量的取值也都是整数。 定义3-1:凡是能够排列成下列序列的一组变量的集合就称为运输问题的一个闭 回路。 并称集合中每一个变量为此闭回路的一个顶点;称连接相邻两个变量(顶 点)以及连接最后一个顶点和第一个顶点的线段为此闭回路的边。 或 A4 A3 A2 A1 B5 B4 B3 B2 B1 X45 X41 X31 X33 X13 X15 A4 A3 A2 A1 B5 B4 B3 B2 B1 X34 X32 X14 X12 A4 A3 A2 A1 B5 B4 B3 B2 B1 X35 X41 X31 X43 X13 X15 A4 A3 A2 A1 B5 B4 B3 B2 B1