线性规划在车辆调度中的运用

线性规划在车辆调度问题中的应用查迅潘文广林小安钱旭王颖第1页引言正文讨论结论参考文献报告议程线性规划的基本定义线性规划的发展历史线性规划的理论模型线性规划的求解方法引言线性规划的基本定义线性规划是合理利用、调配资源的一种应用数学方法，它的基本思路就是在满足一定的约束条件下，使预定的目标达到最优。线性规划的发展历史线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支。随着人们对经济理论的研究，企业管理科学及系统工程学的重视，以及电子计算机的日益普及，线性规划也变得越来越重要，在实际生活中的应用也越来越多。线性规划的理论模型线性规划的求解方法图解法单纯形法软件求解第7页正文xc=min(f)ijij1i1jmnn,,2,1=jm,,,2,1=i0,≥xn,,2,1=,m,,2,1=i,xji1n1jijnijijijbxaA1A2AmB1B2Bn......1.运输问题：第8页2.车辆调度：𝑥𝑖𝑗𝑙𝑗=1=1,​​​​​​​​​​​ ​​​​​​​​​​​​​​​​​​​​​​​​​  𝑖=1,2,⋯,𝑚𝑥𝑖𝑗𝑚𝑖=1=1,​​​​​​​​​​​ ​​​​​​​​​​​​​​​​​​​​​​​​​  𝑗=1,2,⋯,𝑙1111min()**mlmlijjijijijijffcdx10ijx任务请求i可被调度的汽车j第9页3.车辆路径优化：在网络G（E，V）中，设某个配送中心有K车辆，需要对N个客户进行运输配送，每个客户的货物需求量是gi，每辆配送车的最大载重量Q。设表示客户i到客户j的运输成本，如时间、路程、花费等。取配送中心编号为0，各客户编号为i。V={0,1,2,…N｝𝐶𝑖𝑗𝑥𝑖𝑗𝑘=10𝑦𝑖𝑘=100001minNNKijijkkkijkZcxfy目标函数第10页𝑦𝑖𝑘𝐾𝑘=1=1    ​𝑖=1,2,...,N𝑦0𝑘𝐾𝑘=1=𝐾𝑥𝑖𝑗𝑘=𝑦𝑗𝑘   𝑁𝑖=0𝑗=0,1,2,...,N    𝑘=1,2,...,K𝑥𝑖𝑗𝑘=𝑦𝑖𝑘𝑁𝑗=0   𝑖=0,1,2,...,N     k=1,2,...,K𝑥𝑖𝑗𝑘=0  ∀𝑖=𝑗  k=1,2,...,K第11页iku000001,2,...,(1)iji=1,2..Nj=1,2..N0,1=0,1NiikiNNNikikijkijkkiijijijkkijkikgyQKtytxTuuNxNxy第12页讨论正文中的三个案例分别从运输问题，车辆调度，车辆路径优化这三个角度来描述了线性规划在车辆调度中的运用。并给出了每种问题所需要的模型。为了加深我们对线性规划在车辆调度中的理解，下面我们小组将对一个实际案例进行讨论，并运用之前案例中所介绍的模型，来解决这个实际案例，并给出了最后的结论。第13页讨论第14页第15页第16页第17页第18页结论[1]陈婷,何中元.线性规划算法在车辆调度中的应用[J].计算机工程与科学，2005,27(3):52-55.[2]G.B.Dantzig,回顾线性规划的起源，运筹学杂志，1984,3(1).[3]李银兴，线性规划发展的几个时期，宝鸡文理学院学报(自然科学版),1993.[4]马国瑜，线性规划的发展历史，北京化工学院学报，1985,(4).[5]中国运筹学会，中国运筹学发展研究报告，运筹学学报，2012,16(3).[6]运筹学教材编写组.运筹学(第4版)[M].北京:清华大学出版社,2012:15-58.参考文献ThankYou！