




已阅读5页,还剩40页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第七章运输问题之表上作业法 一 运输问题模型及其求解思路二 确定初始基本可行解三 最优性检验四 方案调整五 几种特殊情况 一 运输问题模型及其求解思路 1 问题的提出 某公司从两个产地A1 A2将物品运往三个销地B1 B2 B3 各产地的产量 各销地的销量和各产地运往各销地每件物品的运费如下表所示 问 应如何调运可使总运输费用最小 一 运输问题模型及其求解思路 一 运输问题模型及其求解思路 2 产销平衡运输问题模型的特点从模型的建立可知 列数为2 产地数 3 销地数 6 行数为2 产地数 3 销地数 5 再观察模型的系数矩阵 一 运输问题模型及其求解思路 前2行之和 后3行之和 一 运输问题模型及其求解思路 对于产销平衡的运输问题 若产地为m个 销地为n个 则变量个数为m n个 线性无关的约束条件个数为m n 1 故基本解中的基变量个数为m n 1 一 运输问题模型及其求解思路 3 运输问题求解思路 表上作业法由于运输规划系数矩阵的特殊性 如果直接使用线性规划单纯形法求解计算 则无法利用这些有利条件 人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表上作业法 一 运输问题模型及其求解思路 我们关心的量均在运价表和运量表中 故将两表和为作业表 一 运输问题模型及其求解思路 表上作业法的总体思路和单纯形法类似 每个步骤都充分利用运输表的特点 一 运输问题模型及其求解思路 例 某食品公司下属的A1 A2 A3 3个厂生产方便食品 要运输到B1 B2 B3 B4 4个销售点 数据如下表 求最优运输方案 二 确定初始基本可行解 1 西北 左上 角法每次找最西北角的元素 让其运输量尽可能的满足一个约束条件 二 确定初始基本可行解 3 4 2 2 3 6 二 确定初始基本可行解 这样得到的初始基本可行解为 x11 3 x12 4 x22 2 x23 2 x33 3 x34 6 其余均为0 对应的总运费为 3 3 4 11 2 9 2 2 3 10 6 5 135 二 确定初始基本可行解 2 最小元素法每次找到剩下的最小运价 让其对应的运输量尽可能的满足一个约束条件 二 确定初始基本可行解 3 4 3 1 6 3 二 确定初始基本可行解 用最小元素法求出的初始基本可行解为 x21 3 x22 1 x13 4 x32 6 x34 3 x14 3 其余均为0 对应的总运费为 3 1 1 2 4 3 6 4 3 5 3 10 86 二 确定初始基本可行解 为保证基变量的个数有m n 1个 注意 1 每次填完数 只能划去一行或一列 只有最后一个格子例外 2 用最小元素法时 可能会出现基变量个数还差两个以上但只剩下一行或一列的情况 此时不能将剩下行或列按空格划掉 应在剩下的空格中标上0 退化的基本可行解 二 确定初始基本可行解 3 5 3 0 6 3 二 确定初始基本可行解 3 4 0 1 6 3 三 最优性检验 检验数的意义 非基变量增加一个单位 使目标函数值增加的数量 运输问题中目标函数值要求最小化 因此 当所有的检验数都大于或等于零时该调运方案就是最优方案 否则不是 下面介绍两种计算检验数的方法 三 最优性检验 1 闭回路法闭回路 在已给出基本解的运输表上 从一个非基变量出发 沿水平或竖直方向前进 只有碰到基变量 才能向右或向左转90o 当然也可以不改变方向 继续前进 这样继续下去 总能回到出发的那个非基变量 由此路线形成的封闭曲线 叫闭回路 三 最优性检验 每一个非基变量都有唯一的闭回路 三 最优性检验 观察x24的闭回路 若让第一个顶点非基变量x24的取值变为1 为了保持产销平衡 其闭回路上的顶点运量都要调整 基数顶点 1 偶数顶点 1 上述调整使总的运输费用发生的变化为8 10 3 2 1 这就说明原方案还不是最优方案 需要进行调整 三 最优性检验 若让x11 1 则总运费变化 3 3 2 1 1 三 最优性检验 如果规定作为起始顶点的非基变量xij为第1个顶点 其闭回路上的其他顶点依次为第2个顶点 第3个顶点 那么就有该非基变量的检验数 ij 闭回路上的奇数顶点运价之和 闭回路上的偶数顶点运价之和 最优标准 所有检验数 0 三 最优性检验 检验数计算如下表 1 2 1 1 10 12 三 最优性检验 2 位势法闭回路法的缺点 当变量个数较多时 寻找闭回路以及计算两方面都容易出错 位势法 设产地Ai对应的位势量为ui 销地Bj对应的位势量为vj 检验数 ij cij ui vj 三 最优性检验 三 最优性检验 根据基变量xij的检验数 ij 0 对应基变量的运价cij可以分解为ui和vj 即cij ui vj 因为位势量ui vj的总数为m n个 而限定方程只有m n 1个 基变量个数 所以位势量 ui vj 有无穷多组解 其中总有一个自由变量 故可以任意取一个位势量赋以定值 从而确定其它位势量的值 一般取u1 0 三 最优性检验 10 3 9 2 vj 20 6 5 6 3 销量bj 5 9 53 10 46 7 A3 1 4 8 21 9 13 A2 0 7 103 34 11 3 A1 ui 产量ai B4 B3 B2 B1 1 2 1 1 10 12 检验数计算总结 1 闭回路法计算式 ij 闭回路上的奇数顶点运价之和 闭回路上的偶数顶点运价之和 2 位势法计算式 ij cij ui vj 四 方案调整 最小检验数原则 确定进基变量 最小偶点原则 确定出基变量和调整量 1 1 1 1 四 方案调整 得到新的基变量 x13 5 x14 2 x21 3 x24 1 x32 6 x34 3 重新计算检验数 0 2 2 1 9 12 四 方案调整 经过一次基变换 所有 ij 0 已得到最优解 x13 5 x14 2 x21 3 x24 1 x32 6 x34 3 其它为0 最优值 f 3 5 10 2 1 3 8 1 4 6 5 3 85 四 方案调整 闭回路调整法步骤 1 入基变量的确定 选负检验数中最小者 rk 那么xrk作为进基变量 使总运费尽快减少 2 出基变量的确定 在进基变量xrk的闭回路上 选取偶数顶点上调运量最小的值 将其对应的运量作为出基变量 刚好有一个基变量出基 其它基变量都为正 四 方案调整 即求 Min xij 闭回路上的偶数顶点的xij xpq 那么确定xpq为出基变量 为调整量 3 换基调整 对闭回路的奇数顶点运量调整为 xij 对各偶数顶点运量调整为 xij 特别xpq 0 xpq变为非基变量 重复以上步骤 直到所有检验数均非负 即得到最优解 练习题已知如下运价表 用表上作业法求解 初始解对应目标值为3 3 4 1 4 2 4 4 8 3 61 3 4 2 1 0 3 0 3 4 1 3 3 4 3 2 3 0 1 2 4 0 3 0 2 4 0 3 4 1 3 3 2 3 2 3 2 1 2 已达到最优 最优目标值为4 4 4 2 4 4 5 3 55 五 运输问题的几种特殊情况 1 多个最优方案的情况 若最优表中有非基变量的检验数为0 则为多个最优方案的情况 这种情况下 可将检验数为0的非基变量作为进基变量 即可得到另一个最优方案 五 运输问题的几种特殊情况 如上例中的最优方案就不唯一 0 2 2 1 9 12 检验数为0者进基 最小偶点为出基变量和调整量 2 2 2 2 五 运输问题的几种特殊情况 得到另一个最优方案 x11 2 x13 5 x21 1 x24 3 x32 6 x34 3 其余xij 0 最优值仍然为f 85 五 运输问题的几种特殊情况 2 无解情况 当某个产地Ai不能向
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 幼儿卫生保健说课课件
- 持续扰动作用下的飞行机械臂自主控制方法研究
- 初一学习之航
- 2025年江苏商贸职业学院单招综合素质考试题库及答案
- 血透管的安全留置与维护措施
- 呼吸机患者的安全护理规范
- 术后恢复期的安全监护要点
- 急性肾衰竭患者综合护理方案
- 术前评估对护理质量的影响查房
- 汉阳区八下数学试卷
- GB/T 24128-2018塑料塑料防霉剂的防霉效果评估
- GB/T 15305.1-2005涂附磨具砂页
- GB 7793-1987中小学校教室采光和照明卫生标准
- 质量样板引路方案计划
- 测量误差及数据处理课件
- 测量工具使用规范培训教材课件
- 中压交联电缆电缆正、负和零序计算
- 优衣库商业模式分析
- 调度系统介绍课件
- 华联学院日语能力考试N5试题二及参考答案
- 地铁车站主体结构缺陷处理施工技术交底二级
评论
0/150
提交评论