线性规划算法在车辆调度中的应用
徐香
摘 要
线性规划的理论和方法都比较成熟,具有广泛的应用价值.在企业管理的各个领域都发挥着重要作用.本文对线性规划问题在车辆调度问题中的应用进行了研究,认为采用线性规划调派车辆可以压缩企业的运输成本.提高企业竞争力.首先我们介绍线性规划理论及其在一般运输问题中的应用,然后将其推广到车辆调度问题,.车辆调度问题是指在车辆数量一定的情况下,如何根据用户的需要(静态的或动态的)合理地调度有限的车辆资源,从而最大程度满足用户需要(约束条件),并使运输成本降到最低(目标函数),它是运输问题的特殊情形,也是0-1规划的特殊情形.运输问题既然是一种线性规划问题当然可以用单纯形法求解,但解这个模型较简便的方法是匈牙利法,最后我们介绍了把匈牙利法推广到求解一般运输问题的方法,并建立了确定运输问题初始方案的广义匈牙利法.
【关键词】线性规划 车辆调度 匈牙利法 最小元素法 运输问题
绪论
车辆调度问题是指在车辆数量一定的情况下,如何根据用户的需求(静态的或动态的)合理地调度有限的车辆资源,从而在最大程度满足拥护需要的前提下(约束条件)使运输成本降到最低(目标函数).该问题自提出以来,为了缓解城市交通压力,提高运输效率,国内外专家,学者做了大量的研究,并针对不同的实际情况,提出了很多关于车辆调度问题的模型和算法.
但是,纵观国内外学者关于运输调度问题的研究,大多属于车辆行程安排(一点到一点或者一点到多点)的优化问题,或是适应一些特殊的情况.此外,由于缺少现代电子通讯技术和全球定位技术的支持,调度中心既不能实时地掌握车辆信息和任务的变化,也不能在车辆之间的进行实时通信,所采用的调度方法也大都是静态,封闭式的.因此,上述研究具有较大的局限性,难以满足日益复杂的现代车辆调度任务的需要.
针对上述问题,本文利用先进的全球定位技术,无线通讯技术,运用动态规划理论,提出并建立了一个动态的,开放的现代智能车辆管理调度系统.该系统可以实时监控车辆和对车辆进行实时通讯,对任意时刻的任务请求和突发性事件都可以做出合理的调度.
对于运输问题,寻找较优的初始方案非常重要,在这个模型中,我们利用指派问题的匈牙利法思想,并对它进行了推广,对运输问题建立了确定初始方案的一种新的计算方法——广义匈牙利法.这种方法将原问题经过某种等价交换,然后根据变换后的运输问题给出一种比最小元素法更具有全局概念的就近供应算法,通过数值计算表明,广义匈牙利法对很多问题获得的初始方案往往就是原问题的最优方案.
1 线性规划理论
1.1 一般描述
线性规划是科学与工程领域广泛应用的数学模型,它研究一个线性函数在一组由线性等式或不等式组成的约束条件下的极值.在工农业生产,交通运输,财贸工作等各项经济活动中,必须提高经济效果,做到耗费较少的人力,物力,财力,创造出较多的经济价值.这就是运筹学研究的内容.
运筹学是一门应用科学,线性规划作为运筹学的一个基本分支,是实现管理现代化的有力工具,线性规划问题(Linear Programming)就是在一组线性的等式或不等式的约束之下,求一个线性函数的最大和最小值问题.一般数学描述如下:
min(+++…) (1)
s.t
(2)
其中:
+++…称为目标函数 (Objective Function)
(j=1,…n)称为价值函数.(Cost Coefficient)
C= (,…)称为价值向量,(j=1, …n)称为求解变量.由系数组成的矩阵,称
A=
为约束矩阵.(Constraint Matrix).列向量b=称为右端向量,条件0(1jn)称为非负约束.若某个向量x=满足约束条件,则称为可行解和可行点 (Feasible Point).记为D.
对于一个线性规划问题,必有以下三种情况:
当D=,其中表示空集时,则该问题无解或不可行.
(2)当D,但是目标函数在D上无解时,则称该问题无解.
(3)当D,且目标函数有有限的最优解,则该问题有最优解.
求解线性规划问题时需要判别该问题属于哪一种情况,当问题有最优解时,还要在可行区域中找出使目标函数达到最小(或最大)的点,也就是最优解(Optional Solution),以及目标函数的最优解[2].
1.2 运输问题
运输问题是一类特殊的线性规划问题,从历史角度来说并非有了单纯型法才去研究运输问题,相反的,运输问题可以说是线性规划算法的起源.因此,运输问题可以说是线性规划算法的起源,现实生活中的很多问题都可以转化为运输问题来求解.
- 数学建模调度方案 > 线性规划算法在车辆调度中的应用
-
线性规划算法在车辆调度中的应用
下载该文档 文档格式:DOC 更新时间:2010-01-01 下载次数:0 点击次数:4文档基本属性 文档语言: Simplified Chinese 文档格式: doc 文档作者: 微软用户 关键词: 主题: 备注: 点击这里显示更多文档属性 经理: 单位: 微软中国 分类: 创建时间: 上次保存者: 修订次数: 编辑时间: 文档创建者: 修订: 加密标识: 幻灯片: 段落数: 字节数: 备注: 演示格式: 上次保存时间:
- 下载地址 (推荐使用迅雷下载地址,速度快,支持断点续传)
- DOC格式下载
- 更多文档...
-
上一篇:水利工程学术型专业学位硕士研究生培养方案(2010版)
下一篇:全国第二届部分高校研究生数模竞赛
点击查看更多关于数学建模调度方案的相关文档
- 您可能感兴趣的
- 数学建模优化调度标准 数学建模公交车调度 数学建模优化调度问题 警力调度数学建模 数学建模调度问题 数学建模合理调度 数学建模中的调度问题 建模合理的调度方案 调度方案的数学模型
- 大家在找
-
- · 新路径英语备课教案
- · 死神pk火影剑心
- · 素描静物写生图片
- · 金属切削原理与刀具教案
- · 急诊ppt
- · 给排水设计手册下载
- · 死神vs火影卡卡西秘籍
- · 智信学校提库
- · 全国一级b考试时间
- · 单级圆柱齿轮减速器课程设计
- · 高职语文ppt
- · 非手术美容
- · 2011深圳公务员职位表
- · 教育学论文范文
- · 触电急救应急预案
- · 重庆找工作包吃住
- · 芜湖教育学院
- · 会计学社会调查报告
- · 经济法基础2012第三章
- · 圆周计算公式
- · 上海住房保障网
- · 电工基础课件下载
- · 济宁碳素工业总公司
- · 制药用水ppt
- · 电焊工技术
- · 惠普笔记本win7分区
- · 安徽双轮池酒多少钱
- · 人民警察警员职务套改
- · 路桥测量员职责
- · 我国发明生铁冶炼
- 赞助商链接