《《运筹学》教学课件 第4章》由会员分享，可在线阅读，更多相关《《运筹学》教学课件 第4章（90页珍藏版）》请在金锄头文库上搜索。
1、运筹学课件 制作： 北京理工大学 吴祈宗等 2 第四章 运输问题 运输问题与有关概念 运输问题的求解 表上作业法 运输问题应用 建模 本章内容重点 3 问题的提出 一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地 ， 在每个产地的供应量与每个销地的需求量已知 ， 并知道各地之间的运输单价的前提下 ， 如何确定一个使得总的运输费用最小的方案 。 4 例 公司从两个产地 2将物品运往三个销地 产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？ 5 解： 产销平衡问题： 总产量 = 总销量 设 从产地 到下列运输量表： 6 f = 6
2、 200 300 150 150 200 ( i=1,2； j=1,2,3） 7 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 系数矩阵 8 模型系数矩阵特征 m+别表示各产地和销地； m别表示各决策变量； 1，其余为 0，分别表示只有一个产地和一个销地被使用。 9 一般运输问题的线性规划模型及求解思路 一般运输问题的提法： 假设 ,示某物资的 2, ,示某物资的 产量； 示销地 销量； 示把物资从产地 往销地 单位运价 （ 表 4。 如果 + + 称该运输问题为产销平衡问题；否则 ， 称产销不平衡 。 首先讨论产销平衡
3、问题 。 10 表 4输问题数据表 销地 产地 量 Am 量 从产地 往销地 运输量 ， 根据这个运输问题的要求 ， 可以建立运输变量表 （ 表 4。 11 表 4输问题变量表 销地 产地 量 Am 量 12 m n f = （ 4 i=1 j=1 n i = 1,2, ,m （ 4 j=1 m (=,)j = 1,2, ,n （ 4 i=1 0 (i=1,2, ,m;j=1,2, ,n)（ 4 于是得到下列 一般运输问题 的模型： 在模型 （ 4（ 4中 ， 式 （ 4为 m 个产地的产量约束；式 （ 4为 n 个销地的销量约束 。 13 m n f = i=1 j=1 n = i = 1,
4、2, ,m (4 j=1 m = j = 1,2, ,n (4 i=1 ( i=1,2, ,m;j=1,2, ,n) 对于 产销平衡 问题，可得到下列运输问题的模型： 14 在产销平衡问题中 ， 仔细观察式 （ 4、 （ 4分别变为 （ 4、 （ 4， 约束条件成 为等式 。 在实际问题建模时 ， 还会出现如下一 些变化： （ 1） 有时目标函数求最大 ， 如求利润最 大或营业额最大等； （ 2） 当某些运输线路上的能力有限制时 ， 模型中可直接加入 （ 等式或不等式 ） 约束； 15 (3)产销不平衡的情况 。 当销量大于产量时可加入一个虚设的产地去生产不足的物资 ， 这相当于在式（ 4每一
5、式中加上 1 个松弛变量 ， 共 m 个；当产量大于销量时可加入一个虚设的销地去消化多余的物资 ， 这相当于在式 （ 4每一式中加上 1 个松弛变量 ， 共 n 个 。 16 运输问题是一种特殊的线性规划问题 ， 在求解时依然可以采用单纯形法的思路 ， 如图 4 由于运输规划系数矩阵的特殊性 ， 如果直接使用线性规划单纯形法求解计算 ， 则无法利用这些有利条件 。 人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表上作业法 。 在这里需要讨论基本可行解 、 检验数以及基的转换等问题 。 17 基本可行解 是否最优解 结束 换基 是 否 图 4输问题的求解思路 18 运输问题求解的有关
6、概念 考虑产销平衡问题 ， 由于我们关心的量均在表 4 因此考虑把表 4 如下表 4表 4输问题求解作业数据表 (下页） 19 销地 产地 2 量 Am 量 b1 0 运输问题的基变量共有 m + n ， m + n 运输问题的 m + n 变量构成基变量的充分必要条件是不含闭回路。 重要概念 : 闭回路、闭回路的顶点 特点 运输问题基变量的 21 定义 表 4是能够排列成下列形式的 , (4或 , (4其中 ， a,d, ,s 各不相同； b,c, ,t 各不相同 ， 我们称之为变量集合的一个 闭回路 ，并将式 （ 4、 式 （ 4中的变量称为这个 闭回路的顶点 。 为了说明这个特征 ， 我
7、们不加证明的给出一些概念和结论 。 下面的讨论建立在表 4 22 例如 ， 若把闭回路的各变量格看作节点 ， 在表中可以画出如下形式的闭回路： 闭回路示意图 23 根据定义可以看出闭回路的一些明显特点： (1)闭回路均为一封闭折线 ， 它的每一条边 ， 或为水平的 ， 或为垂直的； (2)闭回路的每一条边 （ 水平的或垂直的 ） 均有且仅有两个闭回路的顶点 （ 变量格 ） 。 24 关于闭回路有如下的一些重要结论： (1) 设 , 是一个闭回路 ， 那么该闭回路中变量所对应的系数列向量 , 性相关； (2) 若变量组 , 中包含一个部分组构成闭回路 ， 那么该变量组所对应的系数列向量 , 性相
8、关 。 根据上述结论以及线性规划基变量的特点 ， 可以得到下面重要定理及其推论 。 25 定理 量组 , 所对应的系数列向量 , 性无关的充分必要条件是这个变量组中不包含闭回路 。 推论 产销平衡运输问题的 m + n 变量构成基变量的充分必要条件是它不含闭回路 。 这个推论给出了运输问题基本解的重要性质 ， 也为寻求基本可行解提供了依据 。 26 表上作业法 上一节已经分析了 ， 对于产销平衡问题 ， 我们关心的量均可以表示在表 4 因此可以建立基于表 4表上作业法 。这里求解运输问题的思想和单纯形法完全类似 ， 即首先确定一个初始基本可行解 ， 然后根据最优性判别准则来检查这个基本可行解是不是最优的 。如果是则计算结束；如果不是 ， 则进行换基 ， 直至求出最优解为止 。 27 表上作业法 一 、 初始基本可行解的确定 根据上面的讨论 ， 要求得运输问题的初始基本可行解 ， 必须保证找到 m + n 1 个不构成闭回路的基变量 。一般的方法步骤如下： (1)在运输问题求解作业数据表中任选一个单元格 交叉位置上的格 ),令 28 表上作业法 即从 最大量 (使行或
