




已阅读5页,还剩26页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
管理运筹学 3 18 2020 1 运输问题 第三讲 3 18 2020 2 2020 3 18 3 若一家公司拥有多个工厂 这些工厂位于不同的地点 并且生产同一种产品 这些产品要运输到不同的地点 以满足用户的需求 供应节点 这些工厂 它们是运输的起点 需求节点 用户所在点 它们是运输的终点或目的地 同时假定产品不能在供应节点之间运输 也不能在需求节点之间运输 公司面临的问题 应如何组织运输 才能在满足供应节点的供应量约束和需求节点的需求量约束的前提下 使得运输成本最低 这类问题就是运输问题 一 问题的模型描述 2020 3 18 4 二 运输问题数学模型 xij 供应节点i至需求节点j的运输量 ai 供应节点i的可供应量 i 1 2 m bj 需求节点j的需求量 j 1 2 n cij 供应节点i至需求节点j的单位运输成本 2020 3 18 5 平衡型运输问题 二 运输问题数学模型 模型包含变量 m n个约束方程 m n个秩 r A m n 1 2020 3 18 6 二 运输问题数学模型 m行 n行 稀疏矩阵 x11 x12 x1n x21 x2n xm1 xmn 2020 3 18 7 平衡型运输问题 三 运输问题的基本性质 1 约束方程数为m n个 但有一个冗余方程 所以独立方程数为m n 1个 即秩r A m n 1 2 存在最优解3 当供应量和需求量均为整数时 存在整数最优解 4 基可行解中基变量个数为m n 1个5 基可行解中基变量的重要特征 不含闭回路 6 任何一个非基变量与基变量含且仅含一个闭回路 2020 3 18 8 最小元素法西北角法Vogel法 四 初始基可行解的确定 2020 3 18 9 最小元素法 4 12 4 11 2 10 3 6 8 5 9 11 2020 3 18 10 4 12 4 11 2 10 3 6 8 5 9 11 8 2 2 10 10 14 8 8 6 6 X 0 0 10 6 8 0 2 0 0 14 0 8 2020 3 18 11 西北角法 4 12 4 11 2 10 3 6 8 5 9 11 8 8 8 6 6 4 4 8 8 14 14 X 8 8 0 0 0 6 4 0 0 0 8 14 2020 3 18 12 Vogel法 沃格尔法 4 12 4 11 2 10 3 6 8 5 9 11 0 1 1 2 5 1 3 14 0 1 2 2 1 3 8 0 1 2 1 2 8 7 6 1 2 12 0 0 2 2 4 2020 3 18 13 1 闭回路法 CycleMethod 五 最优性检验 定义 凡能排列成 或者 形式的变量集合 用一条封闭折线将它们连接起来形成的图形称之为一个闭回路 构成回路的诸变量称为闭回路的顶点 连接相邻两个顶点的线段称为闭回路的边 2020 3 18 14 1 x12 x13 x33 x32 2 x23 x13 x14 x34 x31 x21 转角点 转角点 2020 3 18 15 4 12 4 11 2 10 3 6 8 5 9 11 8 2 10 14 8 6 以最小元素法求得的初始方案为例 1 1 2 1 10 12 2020 3 18 16 2 对偶变量法 DualVariableMethod 位势法 形式的变量集合 用一条封闭折线将它们连接起来形成的图形称之为一个闭回路 构成回路的诸变量称为闭回路的顶点 连接相邻两个顶点的线段称为闭回路的边 2020 3 18 17 8 7 4 2 1 3 5 7 2 4 9 6 由基变量决定位势 计算非基变量的检验数 u1 0 v3 3 u2 2 v4 1 v2 5 u3 1 v1 3 5 2 3 1 7 8 2020 3 18 18 1 确定进基变量 六 基可行解的改进 选择检验数绝对值最大的非基变量为进基变量 存在多个时任选一个 2 确定离基变量 选择包含进基变量的闭回路上偶数变量中运量最小的基变量为离基变量 2020 3 18 19 4 12 4 11 2 10 3 6 8 5 9 11 8 2 10 14 8 6 以最小元素法求得的初始方案为例 1 1 2 1 10 12 2 12 4 2020 3 18 20 4 12 4 11 2 10 3 6 8 5 9 11 8 14 8 以最小元素法求得的初始方案为例 1 2 2 9 12 0 2 12 4 2020 3 18 21 8 7 4 2 1 3 5 7 2 4 9 6 P101 u1 0 v3 3 u2 2 v4 1 v2 5 u3 1 v1 3 5 2 3 1 7 8 2020 3 18 22 8 7 4 2 1 3 5 7 2 4 9 6 P101 u1 0 v3 3 u2 2 v4 1 v2 4 u3 0 v1 2 6 7 3 1 3 6 2020 3 18 23 七 非平衡问题 22 18 3 12 3 4 11 2 5 9 1 7 6 5 2020 3 18 24 七 非平衡问题 3 12 3 4 11 2 5 9 1 7 6 5 0 0 0 请同学们自我完成 2020 3 18 25 八 运输问题的应用 由于运输问题比一般单纯型计算简单 故有些实际问题可以转化为运输问题 2020 3 18 26 例1 单位产品的保管费用为每季度0 1 求最优生产方案 2020 3 18 27 生产 交货 2020 3 18 28 12 0 12 1 12 2 12 3 0 M 11 0 11 1 11 2 0 M M 11 5 11 6 0 M 12 5 M M 0
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 大模型助力工科类专业跨学科融合教学模式研究
- xx园区污水处理及管网配套工程施工方案
- 会记基础试题及答案
- 税法基础试题及答案四
- 高强度铝合金制品生产制造项目经济效益和社会效益分析报告
- 焦化厂循环水系统改造工程实施方案
- 矿山合作协议及承包权转让与执行监督协议
- 食用菌种植加工项目可行性研究报告
- 社会保险停缴期间劳动者权益保障及再就业合同
- 社区绿化带租赁与景观维护管理合同
- 临床预防与健康教育
- 蔬菜园艺培训
- 2025年水力发电运行值班员(技师)考试题(附答案)
- 博士后申请书范文
- DBJ41T 190-2018 保温装饰板外墙外保温应用技术规程
- 在编警察签署合同范例
- 高中数学学法指导讲座
- 《中国歼击机大全》课件
- (三级)智能云服务交付工程师理论考试题库大全-上(单选题)
- GB 19053-2024殡仪场所致病菌安全限值
- 酒店前台新员工培训
评论
0/150
提交评论