运筹学课件第5章 运输问题运筹学课件第5章 运输问题.pptVIP

管理运筹学课件 第5章 运输问题 重庆三峡学院 关文忠 /guanwenzhong 教学目标与要求 【教学目标】 通过本章学习，理解运输问题的特点，会建立运输问题的数学模型；能将产销不平衡的运输问题转化为产销平衡的运输问题，至少掌握一种软件求得运输问题的最优解。 【知识结构】 导入案例——配送问题 本章主要内容 5.1 运输问题的数学模型 5.1.1 产销平衡的数学模型 5.1.2 产销不平衡的数学模型 5.1.3 非标准形式数学模型的标准化 5.2 表上作业法 5.2.1 确定初始基本可行解 5.2.2 解的最优性检验 5.2.3 改进运输方案的办法 5.2.4 如何找多个最优方案 5.3 计算机求解运输问题（各节实验演示） 5.4 应用举例 本章小结 5.1.1 产销平衡的数学模型 一般情况: m个产地，产量为∑ai n个销地，销量为∑bj 当∑ai=∑bj时，称为产销平衡 Ai到Bj的单位运价cij,其数学模型如下。 5.1.2 产销不平衡的数学模型 5.1.3 非标准形式数学模型的标准化 5.1.3 非标准形式数学模型的标准化 5.1.3 非标准形式数学模型的标准化 5.1.3 非标准形式数学模型的标准化 5.3 表上作业法 表上作业法计算过程如下。 (1) 找出初始基本可行解。即在(m×n)产销平衡表上给出(m+n-1)个数字格，其相应的调运量就是基变量，格子中所填写的值即为基变量的解。 (2) 求各非基变量的检验数，即在表上计算除了(m+n-1)个数字格以外的空格的检验数，判别是否已得到最优解。如已是最优解，则停止计算，否则转到下一步。 (3) 确定入基变量与出基变量，找出新的基本可行解，在表上用闭回路上进行调整。 (4) 重复2、3直到得到最优解为止。 2.3.1 初始方案的确定 确定初始基本可行解的方法有西北角法、最小元素法、Vogel法等。由于Vogel法所给的初始方案最佳，最小元素法次之，西北角法最差，故在这里仅介绍后两种方法。无论采取哪一种方法，数字填充都要遵循以下原则。 初始方案数字填充原则： (1) 当需求量已满足，则划去该销地列，产地行的可供量=原可供量-填充数字； (2) 若产量已供应完毕，则划去该产地行，销地列的需求量=原需求量-填充数字； (3) 若需求量与可供量刚好相等，则任选行（或列）划去，未被划去的ai或bj剩余量为0，此0视为可填充的数字，以保证原则(4)的满足； (4) 方案的有数字的格子数=行数+列数-1。 1. 最小元素法 最小元素法的基本思想是就近供应，即从单位运价表中最小的运价处开始确定供销关系，依次类推，一直到给出全部方案为止。 2. Vogel法 用最小元素确定的初始方案只从局部观点考虑就近供应，可能造成总体的不合理。Vogel法的步骤是从运价表上分别找出每行与每列的最小元素和次小元素，求其差值，再从差值最大的行或列中找出最小运价确定供需关系和供应数量。 5.2.2 解的最优性检验——位势法 5.2.3 方案的改进——闭回路法 5.2.4 如何找多个最优方案 5.4 应用举例 由于运输问题模型简捷，求解方便，可将一些非地理问题转换为地理问题。 案例5-1 生产计划问题 案例5-2 空车调度问题 案例5-3 转运问题 案例5-1 生产计划问题 案例5-2 空车调度问题 案例5-3 转运问题 本章小结 * * 设xij为从配送中心Ai向城市Bj配送货物数量，z为总运费，则由表可知这个问题的数学模型如下： bn … b1 销量 a1 … am c1n … cmn … … … c11 … c1m A1 … Am 产量 Bn … B1 产地 销地 容易看出，产销平衡运输模型具有以下特点： （1）它包含m×n个变量，m+n个约束条件 （2）因为有， 所以系数矩阵中线性独立的列向量的最大个数为（m＋n－1）个，即产销平衡运输问题的解中基变量的个数为(m＋n－1)个。 4 3 4 销量 5 不限 3 2 0 3 4 4 3 2 4 3 5 3 6 A1 A2 A3 最高产量 最低产量 B3 B2 B1 销地 产地 【例5.1】将极大化运输问题标准化 初始解如何给？ 检验数如何求？ 方案如何调整？ 三个关键环节： 例（导入案例） 最小元素2，为A2与B1供销关系，B1需要8，A2产量10，供应8个，B1得到满足，划所该列，A2余2。 余下的最小元素3，为A2与B3供销关系，B3需要10，A2剩2，供应2个，A2供应完毕，划所该行，B3还差10。 余下的最小元素4，为A1与B3供销关系，B3还需10，A1产量16，供应10个，B3得到满足，划所该列，A1余6。 余下的最小元素5，为A3与B2