线性规划算法在车辆调度中的应用.doc

线性规划算法在车辆调度中的应用 徐香 摘 要 线性规划的理论和方法都比较成熟,具有广泛的应用价值.在企业管理的各个领域都发挥着重要作用.本文对线性规划问题在车辆调度问题中的应用进行了研究,认为采用线性规划调派车辆可以压缩企业的运输成本.提高企业竞争力.首先我们介绍线性规划理论及其在一般运输问题中的应用,然后将其推广到车辆调度问题,.车辆调度问题是指在车辆数量一定的情况下,如何根据用户的需要(静态的或动态的)合理地调度有限的车辆资源,从而最大程度满足用户需要(约束条件)，并使运输成本降到最低(目标函数),它是运输问题的特殊情形,也是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 运输问题 运输问题是一类特殊的线性规划问题,从历史角度来说并非有了单纯型法才去研究运输问题,相反的,运输问题可以说是线性规划算法的起源.因此,运输问题可以说是线性规划算法的起源