运筹学课件第4章_运输问题解读.pptVIP

管理运筹学课件 管理运筹学课件 第4章 运输问题 管理运筹学课件 * 教学目标与要求 【教学目标】 通过本章学习，理解运输问题的特点，会建立运输问题的数学模型；能将产销不平衡的运输问题转化为产销平衡的运输问题，至少掌握一种软件求得运输问题的最优解。 【知识结构】 管理运筹学课件 * 导入案例——配送问题 设xij为从配送中心Ai向城市Bj配送货物数量，z为总运费，则由表可知这个问题的数学模型如下： 管理运筹学课件 * 本章主要内容 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,其数学模型如下。 产地 销地 B1 … Bn 产量 A1 … Am c11 … c1m … … … c1n … cmn a1 … am 销量 b1 … bn 容易看出，产销平衡运输模型具有以下特点： （1）它包含m×n个变量，m+n个约束条件 （2）因为有， 所以系数矩阵中线性独立的列向量的最大个数为（m＋n－1）个，即产销平衡运输问题的解中基变量的个数为(m＋n－1)个。 管理运筹学课件 * 5.1.2 产销不平衡的数学模型 管理运筹学课件 * 5.1.3 非标准形式数学模型的标准化 管理运筹学课件 * 5.1.3 非标准形式数学模型的标准化 销地 产地 B1 B2 B3 最低产量 最高产量 A1 A2 A3 5 3 6 2 4 3 4 4 3 2 0 3 5 不限 3 销量 4 3 4 【例5.1】将极大化运输问题标准化 管理运筹学课件 * 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，为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供销关系，B2需要14，A3产量22，供应14个，B2得到满足，划所该列，A3余8。 余下的最小元素6，为A3与B4供销关系，B4需要14，A3余8，供应8个，A3供应完毕，划所该行，B4还差6。 余下的元素只有11，为A1与B4供销关系，B4还差6，A1余6，供应6个，A3供应完毕，B4得到满足，任选一列或列划去。 有数字格子数(6)=行数(3)+列数(4)-1 得到了初始方案