物资紧急调运问题-.doc

论文的写作能力大有进步，整体布局较合理，解决问题也较全面，并且都有程序说明，最后还作出了调运路线图，希望再接再厉！1摘要部分应尽量精简，不超过一页，注意行距！不要有分析的语句，并确认所使用的字体准确统一！2. 是否涉及矩阵，其它格式问题请注意！物资紧急调运问题摘 要本文就防洪救灾物资调运问题，运用了线性规划模型和图论的相关知识，结合已知数据和现实生活情况，作出了合理的物资调运方案。针对问题一，根据FLOYD算法加路费权值改进编程语言要言简意赅，但表述必须清楚求出个企业，个仓库，个储备库，共可去掉个关键点之间运输资金最少的各条具体线路，然后建立了线性规划模型，利用MATLAB求解出各个点之间具体的调运量与调运线路。由此知去掉具体调运方案如下：企业到储备库（百件）：-箭头使用准确，可用公式编译器输入- ；企业到储备库（百件）：-；企业到储备库（百件）：-； 仓库到储备库（百件）：-；仓库到储备库（百件）：-；仓库到储备库（百件）：-；仓库到储备库（百件）：-。针对问题二，在问题一的求解基础上，以花费总时间最少为目标函数建立了非线性规划模型，利用MATLAB编程求解出完成调运任务最好好还是少？用时小时（天）。由此知去掉具体车辆分配方案如下：企业到储备库需辆；企业到储备库需辆；企业到储备库需辆；仓库到储备库需辆；仓库到储备库需辆；仓库到储备库需辆；仓库到储备库需辆。针对问题三，在对去掉问题一的求解基础上，建立了总车数最少和总运费最少的双目标规划模型，再通过赋适当的权值将双目标规划模型转化为单目标的去掉规划模型。利用MATLAB编程求解出了车辆安排的具体方案如下：企业到储备库：用车9辆 ；企业到储备库：用车7辆；企业到储备库：用车7辆； 仓库到储备库：用车5辆；仓库到储备库：用车10辆；仓库到储备库：用车3辆；仓库到储备库：用车10辆。共用51辆车，返回时额外最小花费2554.3元。针对问题四，利用FLOYD算法加时间权值改进编程求解出个企业，个仓库，个储备库共个供货点到号点的最短时间行走路线。同h1用MATLAB编程求解出能够满足百件物资需求且用时最短的调运量与调运线路。具体方案是：仓库到号点（百件）：-；企业到号点（百件）：-；仓库到号点（百件）：-;企业到号点（百件）：-。在天之内最少车辆的限制条件下，为了第一时间满足号点物资需求，必须考虑企业在这几天中生产量。分析的语句可以不用，或者尽量少用。最后建立非线性规划模型，利用MATLAB编程求解出具体车辆安排计划及行走线路：仓库到号点（百件）：-，辆车；企业到号点（百件）：-，辆车；仓库到号点（百件）：-，辆车；共车添“辆”用来调运，用时天。关键词： 线性规划模型 非线性规划模型 MATLAB编程 Floyd算法1.问题的重述 我国是一个气候多变的国家，各种自然灾害频频发生，其中各流域的洪涝灾害尤其严重。为了尽可能的减小国家和人民的损失，各级政府通过气象预报及历史经验要提前做好防洪物资的储备工作。已知该换为“某”地区现有家该物资的生产企业，个不同规模的物资储存仓库，个国家级物资储备库，相关数据如表所示，其位置分布和道路情况如图所示。是表1、图1吗？经测算该物资的运输费用为高等级公路元/公里百件，普通公路元/公里百件。各企业、物资仓库及国家级储备库的物资需要时可以通过公路运输相互调运。研究下列问题：（1）根据未来的需求预测，在保证最低库存量和不超过最大容许库存量的情况下，还要重点保证国家级储备库的储存量，试设计给出该物资合理的紧急调运方案，包括调运线路及调运量。（2）如果用于调运这批防洪救灾物资车辆共有辆，每辆车每次能装载件，平均在高等级公路上时速为公里/小时，在普通公路上时速为公里/小时。平均装与卸一辆车的物资各需要小时，一天按小时计算。按照问题（1）的调运方案，如何来调度车辆，大约需要多少天能完成调运任务？（3）若时间容许，希望尽量地减少运输成本，请给出最佳的调运方案，最少需要多少车辆？大约需要多少天能够完成调运任务？162332253426251116 21（4）若在调运中，正好遇到灾害使下列路段意外中断： 1616 ， ， ， 和 。而且 号地区严重受灾，急需向 号地区调运万件救灾物资，请给出相应的紧急调运方案。必要时可动用国家级储备库的物资，也可以不考虑库量的最低限制。如果要求必须在天内完成这次调运任务，那么最少需要多少辆车，并给出车辆的调度方案。 2.问题的分析2.1问题（1）的分析该问题是一个大规模的优化调度问题，根据未来的需求预测，在保证最低库存量和不超过最大容许库存量的情况下，若要重点保证国家级储备库的储存量，在紧急调运的过程中救灾物资必须严格满足其预测需求量，而仓库的库存量只需满足不低于最低库存量即可。合理地解决该问题需要考虑两个原则建立前加“在此基础上建立”模型，原则一：由于是在非汛期，时间相对充裕，在调度物资的过程中要求考虑到总运输费用最小。“；”原则二：紧急调运方案中要重点保证国家级储备库的储存量，必须达到储备库的预测量。按上述的思路建立的规划模型，其规模是比较大的，这是由于各企业、物资仓库及国家级储备库的物资可以通过公路运输相互调运，在求解过程中会涉及许多变量，求解会有很大的难度。因此，需要合理地简化模型。事实上，企业在调度过程中起着供应货物的角色，若企业1向企业2调运100件物资，企业2再向仓库调运100件物资，实质是企业1通过企业2的道路向仓库调运了100件物资，而两企业之间其实是没有本质上的调运的，所以不必考虑企业之间的调运问题；同理若仓库1通过向仓库2调运100件物资，仓库2再向储备库调运100件物资，实质是仓库1向储备库通过仓库2调运了100件物资，而仓库1,2之间是没有调运的，这样可以不必考虑这些仓库间的调运；另外由于所有仓库的现有库存量全部都能满足最低需求量，因此可不必考虑企业与仓库间的调运。经过上述的分析，模型最终只考虑企业及仓库对储备库的调运，形成了11个供应点，2个接受点的模型。求解运货路线时，可根据求解出的调运量找出供货点，然后采用FLOYD算法，并把路费作为路线的权重，求解最优调运路线。字体？2.1问题（2）的分析问题（2）在给出确切车辆的条件下，要求结合问题（1）中的模型求解车辆的调度方案。由于卡车的运货路线在问题（1）中已找出，因此以完成所有调运任务所需时间最短为目标函数建立优化模型。其中完成调运任务所需的时间由所有的最优路线中，完成调运所需最长的时间确定。2.3问题（3）的分析 解决该问题需要建立运输成本最少、调运车辆最少的双目标规划模型。由于问题（1）中已经求解出了确切的去掉紧急调运路线和调运量，结合题中给出的运输费用一定，这样运输这些物资所需的运输费用就是固定的值，而题中要求尽可能的减少运输费用，这样就只能尽可能的减少车辆空载返回的过程中花费的路费。从网上查阅了有关空载卡车的路费收取标准，就一般卡车而言，高等级公路元/公里，普通公路元/公里。这样题中要求的双目标就转化成如下原则，一是满足总的调运车辆最少；二是每条路线中空载的车辆在返回的途中总的花费路费去掉最低。为了使模型求解的难度降低，我们将双目标函数通过加权转变成单目标，这样就简化了模型。去掉在加权的过程中必须科学的把握权值的大小，因为车量的数量级与费用的数量级不同，因此在赋权值前需要估算两权值大概相差多大，然后再将两目标函数赋权值，并整合成单目标函数求解。2.4问题（4）的分析在汛期时,由于灾区受灾严重，无论在什么情况下，都要以时间为第一目标，即要满足调运时所走路线的时间花费最少。在紧急调用期间，不仅不用考虑调用的经济问题,而且不用考虑仓库和储备库库量的最低限制。根据FLOYD算法，并把路程折合成时间赋权值，由追踪法找出从供货点到受灾地点时间最短的路径。字体？因受灾地区急需万件救灾物资，这就要求所建立的模型必须满足两个基本原则，一是离受灾地区最近的供货地点尽可能的向受灾地区运送货物；二是企业在运送物资的过程中应该边生产，边运输，这样就能确保受灾地区不会发生缺货现象。模型（1）上面没有（1），这里最好不要涉及建立以运送时间最短为目标函数，求解出满足受灾地区所需的万件救灾物资的调运路线，即在保证调运时间最小的前提下，运送万件物资由哪几条路线就可满足需求。该问题还提出最少需要多少辆车来完成调运任务，要想减少车辆的投入，就必须延长调运的时间，因为题中要求天内完成这次调运任务，所以将总调运货物的时间定为天。不简洁最终模型（2）同h21以调运的车辆数最少为目标函数，求解每条路线的调运量和所需的车辆数。3.模型的假设与符号说明3.1 模型的假设 （1）缩进到标题后面救灾物资在运输过程中正常，不会出现偶然事故；叙述不清楚（2）卡车在一天的时间内均在运货，没有休息的时间；（3）卡车在满载和空载的车速是一样的；（4）企业、仓库和储备库均可同时给卡车装载或卸载货物，不考虑卡车装、卸物资的等待时间；3.2 符号说明 表示从第个企业到第个储备库的调运量； 表示从第个仓库到第个储备库的调运量；斜体？ 表示第个仓库的最低需求库存量； 表示第个企业的现有库存量； 表示第个储备库的最大库存量； 表示第个储备库的预测需求量； 表示第个储备库的现有库存量； 表示第个仓库的现有库存量； 表示从第个企业到第个储备库的路费权重； 表示从第个仓库到第个储备库的路费权重； 表示第条路线的物资调运量； 表示第条路线配置的车辆数； 表示第条路线配置的车辆数； 表示第个供货点的现有库存量； 表示第条路线中一辆车完成装载、运送、卸货并返回拉货地点的周期；4.模型的建立（和求解）4.1 问题（1）的模型建立与求解4号黑体4.1.1 建立合理的物资紧急调运方案的去掉模型小4号黑体由于是在非汛期，时间相对充裕，因此以总运费最小为目标，建立规划模型如下：目标函数为：缩进不够 公式的标号（1.1）应当与右边最后一列对齐 约束条件为：同h28 约束条件此前可以再次对模型中的量进行说明（1.2）为储备库的库存量至少满足预测需求量，又不超出最大容许量。约束条件（1.3）为仓库的物资调运出去后，剩余库存量不能低于仓库的最低需求量。约束条件（1.4）为企业的最大调运量不能超出企业的现有库存量。其中目标函数代表的是总的运费。4.1.2模型的求解小4号黑体 对于缩进？该模型，本质上是一个线性规划的去掉模型。约束条件为线性不等式约束。所以采用MATLAB编程优化工具箱中的相应函数linprog（）来编写程序求解，其结果为：共有7条线路参与调运任务，总调运量为1700百件，具体的安排车次如表1-1所示。(见程序1)表1-1 问题一中调运任务安排对象及路线表应该是5号黑体调运对象及调运量调运路线企业到储备库（大小？百件）-用公式编译器输入箭头符号-企业到储备库（百件）-企业到储备库（百件）-仓库到储备库（百件）-仓库到储备库（百件）-仓库到储备库（百件）-仓库到储备库（百件）- 从表1-1中去掉可以看出，储备库的物资均是由离它较近的仓库和企业提供。如仓库4和企业1向储备库1调运物资。同时企业3距离储备库1很远，从经济效益上来讲，企业3未向储备库1运输物资。而储备2的物资主要由距离其较近的给个仓库如仓库7，仓库8来保障。对于仓库1到储备库2（100百件）这条线路，经过了29号点（仓库7），说明了仓库1可能向仓库7有供给，在由仓库7向储备库2供给，这也很好的符合了我们在问题分析中对模型简化的依据。对表的结果有阐述，希保持4.2 问题（2）的模型建立与求解应是4号黑体4.2.1车辆调度模型的建立小4号黑体在缩进？给出确切车辆的条件下，要求结合问题（1）中的模型求解车辆的调度方案，以完成所有调运任务所需时间最短为目标，建立优化模型。 目标函数为 同h30 约束条件为约束条件同h32（2.2）为一辆车完成第条路线的调运量所需最大的运输车次数。约束条件（2.3）为第条路线中一辆车完成装载、运送、卸货并返回拉货地点的周期，其中、分别代表车辆行驶过的普通公路和高速公路的距离，为卡车行驶的速度。约束条件（2.4）为完成所有调运任务所需的车辆总数不超过给定的车辆数。5.2.2模型的求解4号黑体 对于该模型，实质上是非线性规划模型，在求解该非线性规划时，先用MATLAB编程计算，由于非线性规划的求解没有很成熟的算法，一般算法的求解结果都依赖于相应的初值，在此用MATLAB求解该非线性规划问题，取车辆变量步长为1，取遍实际的？区间进行求解得到结果。对应问题一中调运方案的调运路线，可知企业到储备库需辆运输车；企业到储备库需辆运输车；企业到储备库需辆运输车；仓库到储备库需辆运输车；仓库到储备库需辆运输车；仓库到储备库需辆运输车；仓库到储备库需辆运输车，共18辆运输车。总用时717小时，大约30天。结果可设计表格表叙。（见程序2） 4.3 问题（3）的模型建立与求解4号黑体4.3.1 车辆的调运方案模型小4号黑体若缩进时间容许，希望既要尽量地减少运输成本，又要求调度较少的车辆，因此以车辆最少、车辆空载返回运货地点的路途花费最少这两个目标函数，建立如下模型：目标函数 （3.1）同 h30约束条件 （3.2）4.3.2模型的求解小4号黑体该问题实质上是一个非线性规划问题，由MATLAB编程求解结果如下（见程序3）：表3-1 问题三中车辆调运任务安排及返程花费表格式调运对象调运用车（单位：辆）车辆返回途中的花费（单位：元）企业到储备库9390.00企业到储备库7452.20企业到储备库7429.20仓库到储备库5231.80仓库到储备库10450.80仓库到储备库3179.80仓库到储备库10420.504.4 问题（4）的模型建立与求解格式4.4.1（1） 模型（1）的建立 格式当遇到灾害时，受灾地区需要大量的急救物资，这时可把企业、仓库以及储备库看作供货点，并且由这个供货点向灾区调运物资。假设一个变量用来记录在送往灾区的条最短路中，哪些是必须往灾区运送物资，哪些是没有必要运送灾区的路线。且1，2， ,13以运送总时间最短为目标，建立如下模型：目标函数为乘号太大 约束条件为目标函数（4.1）为运送救灾物资所需的总时间，其中为第条路线的时间权重。约束条件（4.2）为总的物资供应量至少满足灾区的需求量。约束条件（4.3）为每个供货点的供应量不能超出它的现有库存量。4.4.1（2） 模型（2）的建立 格式以调运的车辆数最少为目标，建立如下模型：目标函数为同30约束条件为约束条件缩进（4.5）中为模型（1）中初步求解出可满足灾区供应的四个供货点，它们总的供货量与产量的和满足灾区的要求。其中、分别代表满足模型（1）要求的企业、的日产量。约束条件（4.6）为完成第条路的调运任务所需的时间（单位：天）。约束条件（4.7）为每个供货点的供应量不能超出它的现有库存量。约束条件（4.8）为完成所有物资调运的时间最多，花费天。4.4.2（1）模型（1）的求解格式针对问题四，首先利用FLOYD算法对每段路线加上时间权值改进编程求解出个企业，个仓库，个储备库共个供货点到号点的最短时间行走路线。具体方案如表4-1所示。（见程序4）字体表4-1 问题四（1）所有调运路线、最大调运量及调运时间表格式调运对象调运路线每趟调运时间(单位：小时)可调运量（百件）企业1至16号点24-同h3826-19-18-162.5375360企业2至16号点41-9-15-18-163.1775600企业3至16号点31-1-2-7-27-26-19-18-166.9125500仓库1至16号点28-8-15-18-163.1975200仓库2至16号点23-18-161.8375270仓库3至16号点35-39-5-6-11-15-18-165.885450仓库4至16号点31-42-27-26-19-18-165.1775800仓库5至16号点22-19-18-162.8175230仓库6至16号点36-3-10-7-27-26-19-18-166.6525280仓库7至16号点29-4-5-6-11-15-18-164.1725390仓库8至16号点38-32-39-5-6-11-157.21500储备库1至16号点27-26-19-18-163.33752000储备库2至16号点30-39-5-6-11-15-18-164.911800再用冒泡法的思想用MATLAB编程求解出13条供货路线中能够满足百件物资需求且用时最短的调运量与调运线路。求解结果为：仓库到号点运送百件物资，运送路线为：-；企业到号点运送百件物资，运送路线为：-；仓库到号点运送百件物资，运送路线为：-;企业到号点运送百件物资，运送路线为：-。具体方案如表4-2所示。（见程序5）字体，箭头表4-2 问题四（1）调运任务安排及路线表格式调运量调运路线仓库到号点运送百件物资-箭头-企业到号点运送百件物资-仓库到号点运送百件物资-企业到号点运送百件物资-4.4.2（2）模型（2）的求解格式针对问题四中的第二个小问建立的模型，实质上模型（1）是确定哪几条路线就可初步满足灾区的物资需求，而模型（2）考虑了企业的日生产量并结合了各供货点的调运问题，解决了车辆的调度方案。与第二个问题类似，利用MATLAB编程，将每条线路的车辆数从1辆取步长为1，遍历到最大车辆数，求解出每条线路具体车辆安排计划及行走线路：仓库到号点运输百件物资，运输路线为：-，需辆车；企业到号点运输百件物资，运输路线为：-，需辆车；仓库到号点运输百件物资，运输路线为：-，需辆车。由于考虑了企业的每日生产量，所以在编程求解过后，企业2到16号点这条线路被取消了。总计用辆运输车调运，用时天。具体方案如表4-3所示。（见程序6）字体表4-3 问题四（2）车辆安排及行走路线表格式调运量调运路线车辆数仓库到号点运输百件物资-？-企业到号点运输百件物资-仓库到号点运输百件物资-5.模型的优缺点 对于整个问题，模型能够很好的体现出对国家级重点仓库需求量的重视。在非受灾期间，由于时间不是第一位的，文章能够巧妙地以经济为目标建立模型并同时满足各个仓库的基本需求，而且重点保障了储备库的需求。但此模型不足的是，在紧急调运中，由于适当考虑了调运过程的紧迫性，模型只考虑了满足国家级仓库的预测需求，而其他仓库只考虑了满足其最小需求量，并未达到他们各自的预测需求。这样模型很难兼顾到所有的仓库需求。另外，在第一问题中，没有考虑时间，所以并没有考虑每个企业的日产量，这和实际还是有所出入的。在第三问中，由于要将双目标规划模型转变为单目标规划模型，利用权值转化，在确定权值大小时也不免有些主观因素。6.模型的推广与改进方向6.1 模型扩展方向格式本文采用了线性、非线性规划的方法，从实际问情况出发,针对不同情况下的要求和不同侧重点建立了不同的模型，按问题顺序层层深入思考，让结果更合理。此外，模型的实用性较强、速度快，可以对突发事件作出及时的调整。同时，利用FLOYD算法，可以将节点数推广，解决节点数更多的同类模型。6.2模型的改进模型的改进，在本文中我们假设了车辆在满载和空载时的速度相同，而在实际过程中速度是不可能相同的。根据两者速度的比值对交通网络图中的路程数据作相应的处理，然后在按同样的模型求解，可以得到更好的实际调运方案。同时，由于车辆在运输过程之中，不免发生一些事故和问题，在模型的建立之中我们也可以将风险度的评估考虑在内，在满足风险度最小，经济效益最好的情况下求解模型，这样对实际的知道？意义更大。另外，在考虑车辆运输时，我们考虑的是车辆没有等待装载的时间，即是车辆到位后就可装载，这与实际也是有所出入的，我们可以在模型之中设置车辆数与等待数之间的函数关系式，这样更加贴合实际。由于为了突出储备库的重要性，我们针对其他的一般仓库，只考虑了满足最低需求量即可，在实际问题中，如果时间允许，能够最大满足预测需求量是最好的，所以模型在改进是？可以追诉考虑预测需求量的求解方法。7.附录程序（1）：调运任务安排对象及路线C=120 321.6 157.6 177.6 288 210 227.2 146.4 198 342 288 210 110.4 152.4 204 400.8 224.4 296.4 216 74.4 252 174 ;A=zeros(15,22);A(1,1)=1; A(1,3)=1; A(1,5)=1; A(1,7)=1; A(1,9)=1; A(1,11)=1; A(1,13)=1; A(1,15)=1; A(1,17)=1;A(1,19)=1; A(1,21)=1; A(2,1)=-1; A(2,3)=-1; A(2,5)=-1; A(2,7)=-1; A(2,9)=-1; A(2,11)=-1;A(2,13)=-1; A(2,15)=-1; A(2,17)=-1; A(2,19)=-1; A(2,21)=-1; A(3,2)=1; A(3,4)=1; A(3,6)=1;A(3,8)=1; A(3,10)=1; A(3,12)=1; A(3,14)=1; A(3,16)=1; A(3,18)=1; A(3,20)=1; A(3,22)=1; A(4,2)=-1;A(4,4)=-1; A(4,6)=-1; A(4,8)=-1; A(4,10)=-1; A(4,12)=-1; A(4,14)=-1; A(4,16)=-1; A(4,18)=-1;A(4,20)=-1; A(4,22)=-1; A(5,7)=1; A(5,8)=1; A(6,9)=1; A(6,10)=1; A(7,11)=1; A(7,12)=1; A(8,13)=1;A(8,14)=1; A(9,15)=1; A(9,16)=1; A(10,17)=1; A(10,18)=1; A(11,19)=1; A(11,20)=1; A(12,21)=1;A(12,22)=1; A(13,1)=1; A(13,2)=1; A(14,3)=1; A(14,4)=1; A(15,5)=1; A(15,6)=1;b=2000;-1000;1200;-700;100;70;250;500;130;80;90;300;360;600;500;Aeq=;beq=;vlb=zeros(22,1);vub=;x,fval=linprog(C,A,b,Aeq,beq,vlb,vub)程序（2）：车辆调度方案function y= M( a,b,c,d,e,f,g )t=a;if bt t=b;endif ct t=c;end if dt t=d;end if et t=e;end if ft t=f;end if gt t=g;end y=t;%t=inf;for a=1:12 for b=1:12 for c=1:12 for d=1:12 for e=1:12 for f=1:12 for g=1:12 if a+b+c+d+e+f+g=18 ta=(ceil(360/a)-0.5)*2*(1+100/50); tb=(ceil(140/b)-0.5)*2*(1+78/50+32/80); tc=(ceil(210/c)-0.5)*2*(1+148/50); td=(ceil(100/d)-0.5)*2*(1+122/50); te=(ceil(500/e)-0.5)*2*(1+92/50); tf=(ceil(90/f)-0.5)*2*(1+62/50); tg=(ceil(300/g)-0.5)*2*(1+145/50); m=M(ta,tb,tc,td,te,tf,tg); if mt t=m; x1=a;x2=b;x3=c;x4=d;x5=e;x6=f;x7=g; end end end end end end end endendx1x2x3x4x5x6x7t程序（3）：车辆调运任务安排及返程花费money=inf;k=0;for a=1:12 for b=1:12 for c=1:12 for d=1:12 for e=1:12 for f=1:12 for g=1:12 ma=(ceil(360/a)-1)*100*0.1; mb=(ceil(140/b)-1)*(78*0.1+32*0.5); mc=(ceil(210/c)-1)*0.1*148; md=(ceil(100/d)-1)*0.1*122; me=(ceil(500/e)-1)*0.1*92; mf=(ceil(90/f)-1)*62*0.1; mg=(ceil(300/g)-1)*145*0.1; m=(ma+mb+mc+md+me+mf+mg)*0.02+(a+b+c+d+e+f+g)*0.98; if mmoney money=m; x1=a;x2=b;x3=c;x4=d;x5=e;x6=f;x7=g; a1=ma;a2=mb;a3=mc;a4=md;a5=m