版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、管理运筹学,运输问题,第三讲,8/4/2020,3,若一家公司拥有多个工厂,这些工厂位于不同的地点,并且生产同一种产品。这些产品要运输到不同的地点,以满足用户的需求。 供应节点:这些工厂,它们是运输的起点; 需求节点:用户所在点,它们是运输的终点或目的地。 同时假定产品不能在供应节点之间运输,也不能在需求节点之间运输。 公司面临的问题:应如何组织运输,才能在满足供应节点的供应量约束和需求节点的需求量约束的前提下,使得运输成本最低。 这类问题就是运输问题。,一、问题的模型描述,8/4/2020,4,二、运输问题数学模型,xij -供应节点i至需求节点j的运输量; ai -供应节点i的可供应量,i
2、=1,2, ,m; bj -需求节点j的需求量,j=1,2,n; cij -供应节点i至需求节点j的单位运输成本。,8/4/2020,5,平衡型运输问题:,二、运输问题数学模型,模型包含 变量:mn个 约束方程:m+n个 秩:r(A)=m+n-1,8/4/2020,6,二、运输问题数学模型,m 行,n 行,稀疏矩阵,x11,x12,x1n,x21,x2n,xm1,xmn,8/4/2020,7,平衡型运输问题:,三、运输问题的基本性质,1. 约束方程数为m+n个,但有一个冗余方程,所以独立方程数为m+n-1个,即秩r(A)=m+n-1。 2. 存在最优解 3. 当供应量和需求量均为整数时,存在整
3、数最优解。 4. 基可行解中基变量个数为m+n-1个 5. 基可行解中基变量的重要特征: 不含闭回路。 6. 任何一个非基变量与基变量含且仅含一个闭回路。,8/4/2020,8,最小元素法 西北角法 Vogel法,四、初始基可行解的确定,8/4/2020,9,最小元素法,4,12,4,11,2,10,3,6,8,5,9,11,8/4/2020,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),8/4/2020,11,西北角法,4,12,4,11,2,10,3,6,8,5,9,1
4、1,8,8,8,6,6,4,4,8,8,14,14,X=(8,8,0,0,0,6,4,0,0,0,8,14),8/4/2020,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,8/4/2020,13,1. 闭回路法(Cycle Method),五、最优性检验,定义:,凡能排列成,或者,形式的变量集合,用一条封闭折线将它们连接起来形成的图形称之为一个闭回路。 构成回路的诸变量称为闭回路的顶点; 连接相邻两个顶点的线段称为闭回路的边
5、。,8/4/2020,14,(1) x12,x13,x33,x32,(2) x23,x13,x14 ,x34 ,x31 , x21,转角点,转角点,8/4/2020,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,8/4/2020,16,2. 对偶变量法(Dual Variable Method)/位势法,8/4/2020,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,
6、5,2,3,-1,7,8,8/4/2020,18,1. 确定进基变量,六、基可行解的改进,选择检验数绝对值最大的非基变量为进基变量(存在多个时任选一个),2. 确定离基变量,选择包含进基变量的闭回路上偶数变量中运量最小的基变量为离基变量。,8/4/2020,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,8/4/2020,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,8/4
7、/2020,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,8/4/2020,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,8/4/2020,23,七、非平衡问题,22,18,3,12,3,4,11,2,5,9,1,7,6,5,8/4/2020,24,七、非平衡问题,3,12,3,4,11,2,5,9,1,7,6,5,0,0,0,请同学们自我完成!,8/4/2020,25,八、运输问题的应用,由于运输问题比一般单纯型计算简单,故有些实际问题可以转化为运输问题。,8/4/2020,26,例1,单位产品的保管费用为每季度0.1,求最优生产方案?,8/4/2020,27,生产,交货,8/4/2020,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,8/4/2020,29,16,14,13,19,15,17,22,13,-,23,20,19,例2,8/4/2020,30,16,14,13,19,15,17,22,13,M,23,20,19,16,14,19,17
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2023年耳机插座资金需求报告
- 科学坐月子-健康科普知识讲座课件
- (新版)浙江建筑架子工(普通脚手架)考前强化练习题库300题(含解析)
- (必会)公用设备工程师(给排水)《专业知识》考前巩固模考题库200题(带详解)
- 安全生产风险分级管控体系制度
- 实习生到底能不能够签劳动合同-具备法律法规规定的主体资格吗
- 公司租车合同范本
- (必会)山西环保工程师《公共基础》考前强化练习题库300题(含详解)
- 10万红砖运输协议
- (必会)土木工程师(水利水电)《公共基础知识》近年考试真题题库(含答案解析)
- 五年级科学上册《物体的传热本领》优质课件(苏教版)
- 高等数学课程思政探索与实践
- 产科三基培训资料
- 浅谈师生数字素养现状与提升研究 论文
- 抽 水 试 验 记 录 表
- 人工种草应急预案
- 经营范围登记规范表述目录(试行)(V1.0.2版)
- 小学的惩戒教育研究
- 大学生毕业就业情况调查方案
- 新教材北师大版第3章12建筑物高度的测量测量和自选建模的汇报交流课件(34张)
- 光伏斜屋顶计算书屋顶光伏电站项目荷载计算书
评论
0/150
提交评论