防洪物资调运的优化模型第四届苏北数学建模联赛

物资紧急调运优化方案1. 背景介绍物资紧急调运是在灾难、紧急情况下，为了满足人们的基本生活需求而进行的物资运输工作。

在灾难发生后，物资的及时运输对于受灾地区的救援工作至关重要。

然而，由于种种原因，物资紧急调运常常存在着效率低下、资源浪费等问题。

因此，有必要对物资紧急调运进行优化，提高其效率和灵活性。

2. 问题分析在物资紧急调运中，存在着以下几个问题： 1. 物资调度不及时：由于信息传递不畅、调度指令不明确等原因，导致物资的调度时间缺乏及时性。

2. 路线选择不合理：由于缺乏综合考虑，经常出现运输距离过长、运输路径不畅等情况，导致运输成本和时间增加。

3. 运输方式选择不科学：在物资紧急调运中，应考虑到不同物资的特点，选择合适的运输方式，以提高运输效率。

4. 缺乏资源共享机制：在灾难发生后，多个组织可能同时参与物资调运工作，但缺乏资源共享机制，导致资源利用不充分。

3. 优化方案提出为了解决上述问题，提高物资紧急调运的效率和灵活性，可以采取以下优化方案： 1. 建立物资紧急调运信息平台：通过建立统一的信息平台，实现各个组织之间的信息共享和调度指令的及时传递。

同时，可以利用物联网和大数据技术，对物资位置、运输时间等进行实时监控和管理，提高调度的准确性和效率。

2. 优化运输路径规划：利用现代地理信息技术，结合实时交通信息、地理地形等因素，进行运输路径优化。

通过选择最短路径、避免拥堵点等方式，降低物资调运的时间和成本。

3. 智能运输方式选择：根据不同物资的特点和紧急程度，选择合适的运输方式。

对于体积较小、重量较轻的物资，可以采用无人机等快速运输方式；对于大批量物资调运，可以利用铁路和水路等大规模运输方式，避免交通堵塞。

4. 建立资源共享机制：在灾难发生后，各个组织之间应建立起资源共享的机制，以确保物资的充分利用。

通过共享运输工具、人力资源等，提高资源利用效率，避免资源浪费。

4. 实施步骤步骤一：建立物资紧急调运信息平台1.搭建信息平台：建立一个统一的信息平台，用于物资位置、运输时间等数据的收集和管理。

数学建模王迪 B09010601 通信工程郑佳佳 B09010603 通信工程孟天舒 B09010604 通信工程题目旅游线路旳优化设计摘要本题为经典旳旅行商问题（TSP），是组合数学中一种古老而又困难旳问题，它易于描述却难以完全处理，属于NP完全问题。

对于规模较小旳旅行商问题，可以通过穷举得到最优解，但伴随问题规模旳增大空间复杂度急剧增长，需要通过启发式算法求解。

由意大利学者M.Dorigo于1992年首先提出旳蚁群系统(AntColonySystem, ACS)是一种新生旳仿生进化算法, 合用于求解复杂组合优化问题, 在处理TSP 问题方面获得了较为理想旳效果。

在此，我们以改善旳蚁群算法为基础建立数学模型来设计这些旅游者在五一开始旳路线，试图能得到某些合理旳结论。

(1)第一问是经典旳费用TSP问题。

对于此问题我们套用基本蚁群算法，查找到都市坐标以及旅游费用，并建立求解矩阵。

通过MATLAB软件旳模拟，求出若干优化解，取相对最优解作为计算成果。

所求得旳路线为徐州出发——洛阳市龙门石窟——西安市秦兵马俑——山西祁县乔家大院——青岛市崂山——北京八达岭长城——江西九江庐山——黄山市黄山——常州中华恐龙园——舟山市普陀山——武汉市黄鹤楼——返回徐州，合计3201元。

(2)第二问为时间TSP问题。

由于时间在详细操作上旳波动性，根据数据所得结论将时间旳TSP转化为距离TSP问题。

求解出旳路线为：徐州出发——常州中华恐龙园——舟山市普陀山——黄山市黄山——九江市庐山——武汉市黄鹤楼——洛阳市龙门石窟——西安市秦始皇兵马俑——祁县乔家大院——北京市八达岭长城——青岛市崂山——返回徐州，总计用时11天12小时20分。

(3)第三问为有费用约束下旳TSP问题。

对于此问题运用了试探法和最小元素得到近似解，再用基本蚁群算法进行优化。

求解出旳路线为：徐州——西安——山西——武汉——黄山——北京——洛阳——徐州，所花费用1839元，游览了5个景点。

某大学数学建模作业应急运输调度方案设计模型应急运输调度是指在突发事件发生时，为了迅速响应和处置，对物资、人员等进行紧急运输和调度的一种临时性工作。

在大学数学建模作业中设计应急运输调度方案，需要考虑到人员、物资和交通等诸多因素，确保在最短时间内，最高效地完成救援任务。

首先，我们需要建立数学模型来描述应急运输调度问题。

该模型应包括：选择运输路径的决策变量，计算路径的时间和消耗的成本的目标函数，以及约束条件等。

在选择运输路径的决策变量方面，我们可以将每个可能的路径表示为一个二进制变量。

假设有n个重点地点需要紧急运输，那么我们可以定义一个n x n的二进制矩阵，其中每个元素表示从一个地点到另一个地点的路径是否存在。

如果路径存在，则相应的元素为1，否则为0。

通过设置适当的约束条件，可以保证所选择的路径满足救援任务的要求。

目标函数方面，我们可以将救援任务的时间和成本作为目标函数的衡量指标。

时间是非常重要的因素，因为在紧急情况下，迅速抵达目的地可以最大程度地减少潜在的损失。

成本是指运输所需的费用，包括车辆、人员和燃料等方面的成本。

我们可以通过计算路径的时间和成本，将其作为目标函数的值进行最小化。

约束条件方面，我们需要考虑到人员和物资之间的依赖关系，以及交通和道路的限制。

在大规模的应急情况下，通常需要多个车辆同时运输物资和人员。

我们需要确保不同车辆之间的调度不会发生冲突，并且每个车辆都能够按时到达目的地。

另外，我们还需要考虑到交通和道路的限制。

在某些情况下，道路可能会因为事故、地震等原因而中断或受损，这对应急运输调度造成了一定的挑战。

我们需要在模型中加入相应的限制条件，以确保选择的路径是可行的。

在建立了数学模型之后，我们可以使用数学建模软件对模型进行求解。

通过输入不同的参数和数据，我们可以得到最优的调度方案，以最短的时间和最低的成本完成救援任务。

最后，为了验证模型的有效性，我们可以使用历史数据或者通过一些模拟实验来评估所设计的应急运输调度方案的性能。

防洪物资调运问题模型的建立及求解王晓星卜浪杨兵（中国矿业大学，徐州221008）摘要本文将题目所给出的防洪物资调运问题转化为图论中的最短路问题求解及一个多目标规划问题求解。

关于问题一，本文建立了关于交通网络的最短路问题，并分别采取了dijkstra算法和floyd算法对其进行了求解。

求解得出了任意一对起点和终点之间运输费用最小的路线，建立了该地区的交通网络数学模型。

对于问题二，根据客观需要，建立各仓库及储备库最终库存的合理度函数，并结合目标建立多目标规划模型，通过求解模型，得到具体的调运方案。

我们将问题三调运过程看成是一个多阶段性的静态过程。

讨论运输周期的长短（即阶段的数量）对整个模型的影响，最终得出最合适的方案。

问题四仍旧通过问题一和问题二的模型建立过程，根据新情况重新建立该地区的交通网络数学模型，并利用新模型解决新问题。

最后我们分析了最终解的稳定性，可延拓性等，提出了该模型所具有的优缺点。

本文的最终模型稳定，可扩展性好，算法简单，复杂度低，有效的解决了本文所提出的所有问题。

一．问题的重述（略）二．模型的假设1．一定要满足各个仓库的最低库存量，否则整个问题系统就是一个极不稳定合理的系统。

2．运输使用的运输工具足够多，可以一次性满足运输的需求。

3．运输费用没有规模成本，小规模运输和大规模运输中单位数量的物资运输成本相等。

4．每条公路都没有承载上限，既在不中断情况下不会出现因为堵车原因不能同多的情况。

5．运输的速度足够快，任何一次运输调度都可以在一天内完成。

6．运输的最小单位为百件。

7．工厂的物资的生产以一天为最小周期，即每天统一将生产出来的物资入库。

8．本题只考虑运输费用，不考虑货物装卸、储存等其他费用。

三．符号系统inf:表示正无穷x(i=1~8)表示仓库1~8的库存，ix(i=9,10)表示储备库1，2的库存，iy(i=1,2,3)表示企业 1，2，3的库存，imi（i=1~8）表示仓库1~8的最小库存mi（i=9，10）表示储备库1，2的最小库存g(i=1~8)表示仓库1~8的预测库存，ig(i=9，10)表示储备库1，2的预测库存，iM(i=1~8)表示仓库1~8的最大库存，iM(i=9,10)表示储备库1,2的最大库存ih(i=1~8)为仓库1~8的合理度函数ih(i=9,10)为储备库的合理度函数i四．问题的分析1．将该地区的公路交通网转换为求解无向图中个节点间最短路问题。

数学建模防洪物资调运问题Document serial number【UU89WT-UU98YT-UU8CB-UUUT-目录摘要防洪物资调运问题实质是个运筹学网络规划中的最短路问题。

由于灾害发生地点和时间具有较大随机性，结合实际情况，我们对其建立了相应的模型。

前三问是提前做好物资的储备，所以我们假设时间相对较宽裕。

将运输分为三个阶段，分别为：“使储备库优先达到预测库存”、“使各库存都达到预测值”和“使各库存在允许最大库存范围内尽可能的多”。

使用图论中的方法将交通网络图转化成数学图形，并用Floyd算法求出企业至各储备库及仓库的运输资金最少的各条路线，即将高等公路转化为普通路线后的等效最短路线。

第一阶段：使储备库达到预测值，以总运费最少为目标建立模型，求出具体调运量。

第二阶段：达到预测库存前以调运时间最少为目标建立模型，求出每条路线前期的调运量。

再按照以当天库存与预测库存相对差值的最大值尽可能小为原则建立模型，如果相对差值相同，远距离优先运输建立模型，求出各路线每天的具体调运量。

第三阶段：达到预测后以调运费用最少为目标建立模型，求出每条路线后期的调运量。

在同等考虑储备库的情况下，以同样的原则建立模型，求出各路线每天的具体调运量。

同时根据问题三的要求，求得20天后各仓库和储存库的物资量如下表所示：问题四中的紧急调运的问题，我们的首要目标是使防洪物资尽可能早的运输到储备库及仓库。

此时，我们不再考虑运费资金问题，以实际路程最短为目标求出各企业与仓库间的最优路线。

同样将运输分为两个阶段（第一阶段为到达库存前，第二阶段达到预测库存后）都以调运时间最短即以最短路为目标建立模型，求出各路线的调运量。

本文通过以上模型结合处理实际问题时目标不同，分别求出了合理的运输路线和调运量以及调运时间和费用，同时还考虑到路线中断等其它情况，具有较大的灵活性和实用性。

关键词防洪物资调运线性规划模型 LINGO软件 Floyd算法一、问题重述与分析1、问题的重述我国是一个气候多变的国家，各种自然灾害频频发生，其中各流域的洪涝灾害尤其严重。

防洪物资调运问题黄权 解三健 曹兴进 （中国矿业大学，徐州 221008）摘 要我们的模型主要用于解决如何在最少运费的情况下将必需物资调运到各个仓库以达到防洪的目的。

对于问题一：我们采用赋权连通图的图论法，把两地的运费作为它们之间线路的权值，然后利用“画圈去大”原则进行最小总权值的求解。

然后，我们又引入了动态规划中的顺序递推法进行两地之间运费最短路的选择。

对于问题二：我们首先利用顺序递推法求解出任两地之间的运费最短路径。

同时，由于要重点保证国家储备库，我们引进加权系数1α、2α进行调运量的限制。

由于仓库3与仓库5的现有库存量大于预测库存量，我们考虑是否应将两库超过预测库存量的那部分空闲物资进行调运，进而建立了两个模型。

然后，我们分别运用线性规划的方法，给出目标函数，归纳如下：∑∑∑===++=310099318112)(i i i i i i j ij ij b C b C b C MinZ αα结合各自的约束条件，我们利用LINDO 软件进行解模，求出两者的最优调运量及总运费。

之后，进行两者总运费的比较，得出最终的最优调运方案。

对于问题三：我们利用问题二的结果求出每个企业必要的最低生产天数i t ，若企业的i t ＜20天，则它所供给的仓库以及储备库就已达到预测库存量。

若企业的i t ＞20天，则可以用比例求解出20天后该企业向每个仓库以及储备库的调运量，进而可以求出20天后各库的库存量。

对于问题四：当某路段遭破坏而不能保证某仓库的储存量时，我们考虑了三种方案。

一为寻找次短路线进行物资的重新调运；二为从其他企业向供应源中断的仓库进行物资调配；三为进行整体线路的重新调配。

最后进行三者总运费的比较，确定了最经济合理的调配方案。

一、问题重述（略）二、模型假设1、各企业的生产日期为无限。

即在洪水之前各个企业均已将全部物资调运到相应的仓 库。

2、在整个的生产过程中，生产费用不予考虑。

3、仓库的物资的储存费、转运费不予考虑。

防洪物资调运的优化模型本文首先将题中所给的交通图抽象成一张无向图,以每百件物资在各边上运输所需费用为权值赋给各边.利用弗洛伊德(Floyd)算法求出各点之间的最短路径,滤去无用数据,找出我们需要的两单位之间的最短路径,所得结果即为问题1所要求的最优公路交通网数学模型(见表2和图3).对于问题2,在重点保证国家储备库的前提下,将问题抽象为一个多阶段单目标的规划问题,以总的运输费用最低为目标,采用带模糊条件的物资调运系统(GTSWFC)模型并且引入惩罚函数对物资进行优化调运.其具体调运过程分成四个阶段:第一阶段,只给储备库调运物资,使其达到预测库存量;第二阶段,只给八个仓库调运物资,直到满足其预测库存量;第三阶段,重新考虑储备库,只给它们调运物资,并使其达到最大库存量;第四阶段,只给八个仓库调运物资,直至所有仓库及企业自己的库存都达到最大.对于问题3,运用问题2中带模糊条件的物资调运系统(GTSWFC)模型可以解答出问题3,得到20天后各库的库存量为对于问题4,在汛期来临后,需改进对问题2所建的模型,即在其基础上分三种情况来考虑:情况一,灾情在调运过程的第一阶段发生;情况二,灾情在第二阶段发生;情况三,灾情在调运过程的第三阶段或第四阶段发生.在情况一和情况二中,各个仓库或储备库未达到其预测库存量,此时情况紧急,根据问题1的方法,求出两个单位之间运输所耗时间最少的路径.通过引入“虚拟”运输时间量化“紧急程度越大的单位,就尽量多运输”这一模糊行为,以总的运输所耗时间最少为目的改进带模糊条件的物资调运系统(GTSWFC)模型.在情况三中,由于各个仓库和储备库都已达到预测库存量,此时视为情况不紧急状态,可以以总运输费用最少为目标确定路径.通过所建防洪物资调运的优化模型,在现实生活中,可以根据实际情况,做出合理的决策,使得总的运输费用或所耗时间达到最优,减少损失,为防洪抗洪工作提供可性行方法.1.问题的重述（略）2.模型的假设1.为了简化问题,我们按照题中附件1所示按照各单位的顺序依次标号,如1表示企业1,5表示仓库2,13表示储备库2等;2.取企业1、企业2和企业3的预测库存和最低库存都为0;3.为了做好某种防洪抗涝物资的储备,假设在问题2的解决中没有发生洪灾,并且公路交通不受影响;4.根据实际情况,假设高速公路的平均速度是普通公路的两倍;5.假设有充足的运输车供调运物资;6.由于企业是输出单位,故假设各企业之间是不运输物资的.3.符号说明ijk x : 表示在灾情未发生时,第k 阶段从单位i 到单位j 的每天调运量,其中(,1,,13;1,,4)i j k ==; ij x : 表示灾情发生后, 从单位i 到单位j 的每天调运量;i a : 表示单位i 的现有库存量,其中(1,,13)i =; i b : 表示单位i 的预测库存量,其中(1,,13)i =; i c : 表示单位i 的最大库存量,其中(1,,13)i =; i e : 表示单位i 的最小库存量,其中(1,,13)i =;ij d : 表示在灾情未发生时,从单位i 到单位j 的每百件物资的最低运费, ij d (,1,,13)i j =可以表示为:22;ij i j d i j i j ⨯+⨯⎧⎪=⨯⎨⎪⨯⎩高速公路路程普通公路路程 1.2,(从到需要经过高速公路和普通公路)高速公路路程(从到只经过高速公路)普通公路路程 1.2(从到只经过普通公路)ij d ': 表示在灾情发生后,从单位i 到单位j 的每百件物资的最低运费; k n : 表示在灾情未发生时,第k 阶段调运方案所需的时间; n : 表示在灾情发生后,调运物资所耗费的时间;ij t : 表示在灾情未发生时,从单位i 到单位j 调运每百件物资所耗费的时间; ij t : 表示在灾情发生后,从单位i 到单位j 调运每百件物资所耗费的时间;i h ：表示在灾情发生后,(4,,13)i =地的物资相对紧缺程度;k z : 表示在灾情未发生时,第k 阶段总的运费; z : 表示在灾情发生后,总的运输所耗时量.4.问题的分析及模型的建立与求解4.1 问题1的解答 4.1.1 问题1的分析题中指出,现在是提前为防洪抗涝做准备.我们可以认为,在这个过程中,灾情还未发生,时间比较充裕.因此,在决定交通网络的模型时,我们只考虑两个单位之间运输成本最低的路线.很显然,可以把问题抽象成求任意两点间的最小路径问题.4.1.2 问题1模型的建立与求解在题目所给的交通图中,以标有数字的公路交汇点为顶点,交汇点之间的连线为边,将其余无用边和顶点删除,形成一幅无向图.再以每百件物资在各边上运输所需费用为权值赋给各边,有以下两种情况:图 1 图 2 情形1.两公路交汇点之间是普通公路(如图1):在图1中，我们给交汇点20和交汇点22之间的路线重新赋予权值,新的权值=两交汇点之间的距离⨯普通公路的单位运输成本,即80⨯1.2=96;情形2.两公路交汇点之间是高速公路(如图2):在图2中，我们给交汇点7和交汇点27之间的路线重新赋予权值,新的权值=两交汇点之间的距离⨯高速公路的单位运输成本,即70⨯2=140.从而,我们得到了任意两交汇点间路线新的权值(见表1):表1路线权值路线权值路线权值路线权值[1]～[2] 48 [6]～[11] 64 [14]～[17]112 [25]～[26] 21.6[1]～[33] 72 [7]～[10] 96[15]～[42]33.6 [26]～[27] 84[1]～[34] 54 [7]～[27] 140 [15]～[18]69.6 [27]～[40] 64[2]～[3] 42 [8]～[15] 76 [15]～[25]55.2 [28]～[29] 72[2]～[7] 60 [8]～[14] 72 [16]～[21]69.6 [28]～[42] 38.4[2]～[9] 74.4 [8]～[28] 100 [16]～[23]78 [29]～[30] 74.4[3]～[10] 50.4 [9]～[27] 48 [16]～[18]150 [30]～[39] 18[3]～[36] 60 [9]～[40] 33.6 [17]～[23]62.4 [31]～[32] 60[4]～[6] 36 [9]～[31] 62.4 [18]～[19]26.4 [32]～[34] 30[4]～[5] 20 [10]～[12]62.4[18]～[23]54 [32]～[39] 74.4[4]～[29] 80 [11]～[25] 80 [18]～[25] 60 [32]～[38] 81.6[4]～[30] 84 [11]～[27] 96 [19]～[22] 86.4 [32]～[35] 117.6 [5]～[6] 56 [11]～[15] 112 [19]～[26] 33.6 [33]～[36] 48 [5]～[40] 76 [12]～[13] 96 [20]～[22] 96 [33]～[37] 45.6 [5]～[39] 170 [13]～[27] 100 [20]～[24] 60 [35]～[39] 204 [6]～[40] 36 [13]～[20] 81.6 [21]～[22] 54 [37]～[38] 42 [6]～[41]57.6[14]～[23]60[24]～[26]36[41]～[42]31.2问题转化为求该无向图的任意两点的最小路径.针对该无向图,我们利用弗洛伊德(Floyd)算法[4]来求出各点之间的最短路径,其基本思想是:假设求从顶点i v 到j v 的最短路径.（i v ，…，k v ）和（k v ，…，j v ）分别是从i v 到k v 和从k v 到j v 的中间顶点的序号不大于1k -的最短路径,则将（i v ，…，k v ，…，j v ）和已经得到的从i v 到j v 且中间顶点序号不大于1k -的最短路径相比较,其长度较短者便是从i v 到j v 的中间顶点的序号不大于k 的最短路径.这样,在经过n 次比较后,最后求得的必是从i v 到j v 的最短路径.按此方法,可以同时求得各对顶点间的最短路径.由此可根据该算法,用C++语言编写程序（见附件）求出每对顶点之间的最短路径.在得到的结果中,将无用的结果滤去,筛选出我们需要的各单位之间的最短路径,见表2:表2路 线权值路 线权值 企业1→仓库1 24→26→25→15→42→28 184.8仓库1→储备库1 28→42→41→6→40→27 227.2 企业1→仓库2 24→26→19→18→23 150仓库1→储备库2 28→29→30146.4 企业1→仓库3 24→26→27→9→31→32→35408仓库2→仓库3 23→18→19→26→27→9→31→32→35486 企业1→仓库4 24→26→27→9→31 230.4仓库2→仓库423→18→19→26→27→9→31308.4 企业1→24→26→19→22204 仓库2→23→18→19→22166.8仓库5仓库5企业1→仓库624→26→27→9→2→3→36344.4仓库2→仓库623→18→19→26→27→9→2→3→36422.4企业1→仓库724→26→25→15→42→28→29256.8仓库2→仓库723→18→15→42→28→29267.6企业1→仓库824→26→27→9→31→32→38372仓库2→仓库823→18→19→26→27→9→31→32→38450企业1→储备库124→26→27120仓库2→储备库123→18→19→26→27198企业1→储备库224→26→25→11→6→4→3321.6仓库2→储备库223→18→15→42→28→29→30342企业2→仓库141→42→2869.6仓库3→仓库435→32→31177.6企业2→仓库241→42→15→18→23188.4仓库3→仓库535→32→31→9→27→26→19→22492企业2→仓库341→6→40→9→31→32→35367.2仓库3→仓库635→32→34→1→33→36321.6企业2→仓库441→6→40→9→31189.6仓库3→仓库735→32→39→30→29284.4企业2→仓库541→42→15→18→19→22247.2仓库3→仓库835→32→38199.2企业2→仓库641→6→40→9→2→3→36 303.6仓库3→储备库135→32→31→9→27288企业2→仓库741→42→28→29141.6仓库3→储备库235→32→39→30210企业2→仓库841→6→40→9→31→32→38331.2仓库4→仓库531→9→27→26→19→22314.4企业2→储备库141→6→40→27157.6仓库4→仓库631→9→2→3→36238.8企业2→储备库241→6→4→30177.6仓库4→仓库731→32→39→30→29226.8企业3→仓库134→32→39→30→29→28268.8仓库4→仓库831→32→38141.6企业3→仓库234→32→31→9→27→26→19→18→23486仓库4→储备库131→9→27110.4企业3→仓库334→32→35147.6仓库4→储备库231→32→39→30152.4企业3→仓库434→32→3190仓库5→仓库622→19→26→27→9→2→3→36428.4企业3→仓库534→32→31→9→27→26→19→22404.4仓库5→仓库722→19→18→15→42→28→29326.4企业3→仓库634→1→33→36174仓库5→仓库822→19→26→27→9→31→32→38456企业3→仓库734→32→39→30→29196.8仓库5→储备库122→19→26→27204企业3→仓库834→32→38111.6仓库5→储备库222→19→18→15→42→28→29→30400.8企业3→储备库134→32→31→9→27200.4仓库6→仓库736→3→2→9→40→6→4→29362企业3→储备库234→32→39→30122.4仓库6→仓库836→33→37→38135.6仓库1→仓库228→42→15→18→23195.6仓库6→储备库136→3→2→9→27252仓库1→仓库328→29→30→39→32→35356.4仓库6→储备库236→33→1→34→32→39→3296.4仓库1→仓库428→42→41→6→40→9→31259.2仓库7→仓库829→30→39→32→38248.4仓库1→仓库528→42→15→18→19→22254.4仓库7→储备库129→4→6→40→27216仓库1→仓库628→42→41→6→40→9→2→3→36373.2仓库7→储备库229→3074.4仓库1→仓库728→2972仓库8→储备库138→32→31→9→27252仓库1→仓库828→29→30→39→32→38320.4仓库8→储备库238→32→39→30174储备库1→储备库227→40→6→4→30220表2中,只给出了从单位i到单位j(i j)的最短路径, 单位j到单位i的最短路径可将从单位i到单位j的最短路径反序排列便可得到,单位成本相同.下面,再将上面求得的各单位之间最短路径综合起来,算出它们的合集,所得结果即为该地区公路交通网的模型.如图3所示:图34.2 问题2的解答 4.2.1 问题2的分析问题2要求我们在重点保证国家级储备库的情况下,给出包括调运量及调运路线的合理的调运方案. 我们可以综合各企业、仓库和储备库的不同情形,考虑灾情未发生时,以总的运输费用最低为目标,将调运过程分成四个阶段:首先,重点考虑储备库,只给储备库调运物资,达到其预测库存量为止.第二个阶段只给八个仓库调运物资,以满足它们的预测库存.第三个阶段,重新重点考虑储备库,只给它们调运物资,直到满足它们的最大库存;第四阶段,将多余的物资调往八个仓库,直至所有仓库及企业自己的库存都到达最大.4.2.2 问题2模型的建立我们规定第k 阶段从单位i 到单位j 的调运量为ijk x ,每百件最低运输成本为ij d .若满足i j =,则0ijk x =,且0ij d =.经过计算从单位i 到单位j 的运输成本ij d 如下:000184.8150408230.4204344.4256.8372120321.600069.6188.4367.2189.6247.2303.6141.6331.2157.6177.6000268.8486147.690404.4174196.8111.6200.4122.4184.869.6268.80195.6356.4259.2254.4373.272320.4227.21()ij d =46.4150188.4486195.60486308.4166.8422.4267.6450198342408367.2147.6356.44860177.6492321.6284.4199.2288210230.4189.690259.2308.4177.60314.4238.8226.8141.6110.4152.4204247.2404.4254.4166.8492314.40428.4326.4456204400.8344.4303.6174373.2422.4321.6238.8428.40362135.6252296.4256.8141.6196.872267.6284.4226.8326.43620248.421674.4372331.2111.6320.4450199.2141.6456135.6248.40252174120157.6200.4227.2198288110.42042522162520220321.6177.6122.4146.4342210152.4400.8296.474.41742200⎛⎫⎪⎪ ⎪⎪⎪ ⎪ ⎪⎪ ⎪⎪⎪ ⎪⎪ ⎪⎪⎪ ⎪⎪⎝⎭这里我们引入在k 阶段从单位i 到单位j 调运量ijk x 的惩罚函数[6]()ijk f x ,当i i a b >时, ()0ijk f x >(惩罚函数为正值,即表示当单位i 的现有库存量i a 大于其预测库存量i b ,需从单位i 向单位j 调运防洪物资);如果i i a b ≤,那么()0ijk f x =(惩罚函数为0,表示无需从单位i 向单位j 调运防洪物资).其函数如下:0(),0ijk i i ijk i ix a b f x a b >>⎧⎪=⎨≤⎪⎩问题2强调在重点保证国家级储备库的情况下,选择合理的调运方案{}ijk x .该方案需要满足以下四个条件:(1).先对国家级储备库进行调运;(2).依次满足各储备库和仓库的预测库存量,并且最终不能超过其最大库存量;(3).总运费最小;(4).日产量多的企业,适当多运输.满足条件(1)～(4)的物资调运系统称为带模糊条件的系统[5],简记作GTSWFC.系统必须要在优先满足条件(1)的情况下,依次满足各储备库和仓库的预测库存量、最大库存量.因为题中已给出三个企业的日产量,所以要使得系统的总运费最小时,本题中我们认为条件(3)和(4)也应当综合考虑.因为要优先保证国家储备库的库存量,所以我们将调运过程分为四个阶段进行考虑:第一阶段:当国家储备库未达到其预测库存量,此时优先考虑给国家储备库调运物资,即只考虑由可调运出物资的企业或仓库向这两个储备库调运物资,为了满足调运成本最低,可得GTSWFC 模型为:1113111112min ij ij i j z n d x ===∑∑111,12,112121111,13,1131311 0(1,,11;12,13)i i i i ij n x b a n x b a s t x i j ==⎧=-⎪⎪⎪=-⎨⎪⎪⎪≥==⎩∑∑第二阶段:当国家储备库已达到其预测库存量时,此时考虑只给仓库1到仓库8中需要调运物资的仓库调运物资,直到它们的库存量达到预测库存量,并且满足调运过程中所花的费用最小;其GTSWFC 模型为:111122211min ij ij i j z n d x ===∑∑13131113121112121121313124411131122112231212()(403020)()(403020)...4,,11,1,,11i i ij i i i j i ii i ij ij ji i i j j j ij a n n b n x a n n b s t n x n x n x b a i x i j =========⎧++++≥-⎪⎪⎪++++≤⎪⎨⎪⎪+-≤-=⎪⎪≥=⎩∑∑∑∑∑∑∑∑∑第三阶段:完成前两阶段的调运方案后,所有的储备库和仓库都已达到它们的预测量;此时对于多余的物资,仍然按照优先保证国家储备库的原则,在未达到国家储备库的最大库存量的前提下,保证运输费用最低;其GTSWFC 模型是:313333112min ij ij i j z n d x ===∑∑131312314131112312134433,12,31212133,13,3131313()(403020)()(403020) 01,2,3;12,13i ii i i i i i i i i i ij a n n n b a n n n b c c n x b c s t n x b c x i j ======⎧+++++≥⎪⎪⎪+++++≤++⎪⎪⎪⎪+≤⎨⎪⎪+≤⎪⎪⎪⎪≥==⎪⎩∑∑∑∑∑∑ 第四阶段:前三阶段完成后,各个仓库都已达到它们的预测库存量,并且两个储备库已达到其最大库存量.此时我们考虑怎样调运物资,使这8个仓库的库存也达到最大库存,而且所花费的运费最小.具体的GTSWFC 模型为:111144414min ij ij i j z n d x ===∑∑13111234121311131312341134414()(403020)()(403020)...04,,11i i i i i i i i ij j j i ij a n n n n b c c a n n n n c s t n x b c x j =====⎧++++++≥++⎪⎪⎪++++++≤⎪⎨⎪⎪+≤⎪⎪≥=⎩∑∑∑∑∑ 用LINGO 对这四个阶段的模型进行求解,得出在完成各个阶段的调运方案后,每天的调运量ijk x .具体数值如下列表所示:表4(第一阶段每天的调运量1ij x )单位 储备库1 储备库2企业1 600 0 企业2 310 50 企业3 0 500 仓库3 0 150 仓库590完成第一阶段的调运方案,共需费用240796元.表5(第二阶段每天的调运量2ij x )单位 仓库1 仓库2 仓库4 仓库6 仓库7 仓库8 企业1 25 3 12 0 0 0 企业2 15 0 0 0 15 0 企业3 0 0 4 3 0 13 仓库542完成第二阶段的调运方案,共需费用150902.3元.表6(第三阶段每天的调运量3ij x )单位 储备库1 储备库2企业1 40 0 企业2 20 10 企业320完成第三阶段的调运方案,共需费用202933.9元.表7(第四阶段每天的调运量4ij x )单位 仓库1 2 3 4 5 6 7 8 企业1 0 13 0 0 36 0 0 1 企业2 13 0 2 2 0 8 4 0 企业3 0 0 11 0 0 0 0 9完成第四阶段的调运方案,共需费用320643.1元.由前面的模型可以解出经过1234n n n n +++天,各个储备库和仓库都已经达到它们的最大库存量;若此时3个企业继续生产物资,则不到70天,可使3个企业的仓库也达到它们的最大库存量,本题中因为灾害还未发生,物资没有消耗,所以我们认为这3 个企业暂时停止生产.4.3 问题3的解答根据问题2的调运方案模型模型,我们可以解出执行第一阶段的调运方案的时间为11(01)n n <<天,前两个阶段的调运方案所需天数为12n n +,前三个阶段的调运方案所需天数为123n n n ++,这四个阶段的调运方案都执行所需天数为1234n n n n +++天后.当调运方案已经执行了20天时,根据前面的调运方案可知1212320[,]n n n n n ∈+++,所以我们认为方案已经实施20天后,正在执行第三阶段的调运方案.此时仓库1到仓库8已经达到预测库存量,并且在这个阶段仅给两个储备库,所以由问题2的第三阶段调运方案的GTSWFC 模型可以解出第三阶段已向储备库1和储备库2调运的物资量为:33,12,3,13,311879,251.i i i i xx====∑∑从而我们可知20天后各个储备库和仓库的储存量,具体如表8:表8(单位:百件)单位企业 1 企业 2 企业3仓库 1 仓库 2 仓库 3 仓库 4 仓库 5 仓库 6 仓库 7 仓库 8 储备库1储备库2储存量0 0 3 500 600 300 350 400 300 500 600 3879 27514.4 问题4的解答 4.4.1问题4的分析问题4指出因洪水而使得部分交通中断,此时灾情已经发生,我们所给的模型必须考虑解决紧急调运的问题.而在问题2中,我们假设灾情没有发生,是以运输成本最低为目的,分四个阶段来调运物资的.灾情发生后,由于部分路线中断和情况紧急,所以问题2中的模型不再适用于问题4.为此我们在问题2模型的基础上分三种情况来考虑:情况一、灾情在调运过程的第一阶段发生;情况二、灾情在调运过程的第二阶段发生;情况三、灾情在调运过程的第三阶段或第四阶段发生.4.4.2 问题4模型的建立在情况一和情况二中,由于各个仓库和储备库未达到其预测库存量,这里我们为了在最短时间内将防洪物资运送到各个仓库及储备库,只考虑运输所耗的时间,耗时最短的路线为最优路线.由前面的假设可知,灾情发生后高速公路的速度是普通公路的两倍.以任意两顶点间所需时间为其边的权值,除去洪水冲断的路外,应用弗洛伊德(Floyd)算法[1],得出最优路线(见表9):表9i j→路线时间i j→路线时间企业1→仓库1 24→26→25→15→8→28138仓库1→储备库128→8→15→11→2796企业1→仓库2 24→26→25→18→23108仓库1→储备库228→29→30122企业1→仓库3 24→26→25→15→11→6→5→39→35245．5仓库2→仓库323→18→15→11→6→5→39→35254．5企业1→仓库4 24→26→25→15→11→6→5→39→32→31306．5仓库2→仓库423→18→15→11→6→5→39→32→31315．5企业1→仓库5 24→20→22130仓库2→仓库523→18→19→22139企业1→仓库6 24→20→13→27→7→10→3→36294仓库2→仓库623→18→15→11→27→7→10→3→36306企业1→仓库7 24→26→25→15→11→6→5→4→29177仓库2→仓库723→17→14→8→28→29183企业1→仓库8 24→26→25→15→11→6→5→39→32→38324．5仓库2→仓库823→18→15→11→6→5→39→32→38333．5企业1→储备库1 24→20→13→27143仓库2→储备库123→18→15→11→27155企业1→储备库2 24→26→25→15→11→6→5→39→30209．5仓库2→储备库223→18→15→11→6→5→39→30218．5企业2→仓库1 41→42→2858仓库3→仓库435→32→31148企业2→仓库2 41→42→15→18→23157仓库3→仓库535→39→5→40→27→13→20→22301．5企业2→仓库3 41→6→5→39→35155．5仓库3→仓库635→32→34→1→33→36368企业2→仓库4 41→6→5→39→32→31216．5仓库3→仓库735→39→5→4→29118．5企业2→仓库5 41→42→15→18→19→22206仓库3→仓库835→32→38166企业2→仓库6 41→6→11→27→7→10→3→36239仓库3→储备库135→39→5→40→27128．5企业2→仓库7 41→6→5→4→2987仓库3→储备库235→39→3066企业2→仓库8 41→6→5→39→32→38234．5仓库4→仓库531→32→39→5→40→27→13→20→22362．5企业2→储备库1 41→6→11→2788仓库4→仓库631→32→34→1→33→36220企业2→储备库2 41→6→5→39→30119．5仓库4→仓库731→32→39→5→4→29179．5企业3→仓库1 34→32→39→5→4→29→28214．5仓库4→仓库831→32→38118企业3→仓库2 34→32→39→5→6→11→15→18→23290．5仓库4→储备库131→32→39→5→40→27189．5企业3→仓库3 34→32→35123仓库4→储备库231→32→39→30127企业3→仓库4 34→32→31102仓库5→仓库622→20→13→27→7→10→3→36324企业3→仓库5 34→32→39→5→40→27→13→20→22337．5仓库5→仓库722→20→13→27→40→5→4→29233企业3→仓库6 34→1→33→36145仓库5→仓库822→20→13→27→40→5→39→32→38380．5企业3→仓库7 34→32→39→5→4→29154．5仓库5→储备库122→20→13→27173企业3→仓库8 34→32→3895仓库5→储备库222→20→13→27→40→5→39→30265．5企业3→储备库1 34→32→39→5→40→27164．5仓库6→仓库736→3→10→7→27→40→5→4→29211企业3→储备库2 34→32→39→30102仓库6→仓库836→33→37→38113仓库1→仓库2 28→8→14→17→23123仓库6→储备库136→3→10→7→27151仓库1→仓库3 28→29→4→5→39→35178．5仓库6→储备库236→3→10→7→27→40→5→39→30243．5仓库1→仓库4 28→29→4→5→39→32→31239．5仓库7→仓库829→4→5→39→32→38197．5仓库1→仓库5 28→8→15→18→19→22196仓库7→储备库129→4→5→40→2760仓库1→仓库6 28→8→15→11→27→7→10→3→36247仓库7→储备库229→3062仓库1→仓库7 28→2960仓库8→储备库138→32→39→5→40→27207．5仓库1→仓库8 28→29→4→5→39→32→38257．5仓库8→储备库238→32→39→30145储备库1储备库227→40→5→39→3092．5下面,再将上面求得的各单位之间最快路径综合起来,算出它们的合集,所得结果即为该地区公路交通网的模型.如图4所示:图4情况一、灾情在调运过程的第一阶段发生:在问题2的第一阶段中,我们优先考虑国家储备库,只给这两个储备库调运物资,这里我们假设在调运之前,灾情已经发生.所以原来问题2中的模型在这里已不再适用.此时我们根据各个储备库和仓库的物资相对紧缺程度进行物资调运.比较各个储备库和仓库的紧缺程度i h ,如果预测库存量小于现有库存量,我们认为其紧缺程度为0;否则,当i h 的值越大,其紧缺程度越大.其中i h 可以表示为:i h -=-第i 个单位的预测库存量现有库存量第i 个单位的现有库存量最低库存量.经计算,可得各个单位的紧缺程度(见表10):表10单位 4 5 6 7 8 9 10 11 12 13i h 3 547 0 1213 0 14 219 1 178即各个储备库和仓库的相对紧缺程度为:仓库2>仓库1>仓库7>仓库8=储备库1>仓库4>储备库2>仓库6.考虑到当某单位的紧缺程度越大,应调运给该单位的物资也就越多.为了量化“紧缺程度越大的单位,就尽量多运输”这一模糊行为.我们作如下处理:对(4,,13)i h i =大的单位,调整调运物资到该单位所耗的时间(1,,13)ji t j =,形成“虚拟”运输时间ji t ,其中ji t 满足i h 越大,相应的ji t 就越小.用ji t 代替ji t 后进行规划,使得调运方案满足总的运输耗时最少.现选取ji t 为:(1)(4,,13;1,,13),ij ij i t t h i j βμ=-==其中β是正参数,反映了紧缺程度和总运输所耗时间在决策中的重要程度.由于这里灾情已经发生,我们认为紧缺程度是很重要的,于是这里β取值要满足一定的情况,本题的情况可以表示为图4:图4记()1()i i f h h βμ=-,则()ij ij i t t f h =.对于01β<<,11ββ=>和,函数()i f h 类似于[0,1]上的“降半凹(凸)分布”(如图4),下面说明ij t 的合理性:(1)显然,ij t 满足0ij ij t t <<;(2)ij t 时连续递减的,即μ越大,则相应的ij t 越小;(3)参数β的选取可使紧缺程度和运输所耗时间的“重要程度”这一模糊概念得到量化;(4)ij t 的选取便于计算和控制.于是综合考虑上面的分析,我们得到GTSWFC 模型为:131314min ij ij i j z n t x ===∑∑1β=1β> 01β<<11()i f h()i h μ1311313131414,,13()(403020) 0,1,,13;ij j ji ij i i i j i ij n x b a j n x b e n s t x i j ====⎧≥-=⎪⎪⎪⎪≤-+++⎨⎪⎪⎪≥=⎪⎩∑∑∑∑情况二、灾情在调运过程的第二阶段发生:第一阶段的调运方案结束后,两个国家储备库已达到其预测库存量,我们认为它们的紧缺程度为0.此时类似情况一的分析,我们只考虑8个仓库的物资相对紧缺程度.可得各单位的相对紧缺程度为(见表11):表11单位 4 5 6 7 8 9 10 11i h 3 547 0 1213 014 2191通过“虚拟”运输时间ji t 来量化“紧缺程度越大的单位,就尽量多运输”这一模糊行为.在满足调运过程中所消耗的时间最少的前提下,得到其GTSWFC 模型为:111111min ij ij i j z n t x ===∑∑1111111111313111411214,,11()(403020) 0,1,,11ij j ji ij ij i i i j i j i ij n x b a j n x n x b a n n s t x i j ======⎧≥-=⎪⎪⎪⎪+≤-++++⎨⎪⎪⎪≥=⎪⎩∑∑∑∑∑∑情况三、灾情在调运过程的第三阶段或第四阶段发生:无论是第三阶段还是第四阶段,各个储备库和仓库都已达到了预测库存量,这里我们认为预测库存量即发生灾情下,物资充足够用的量.此时,按照问题一中的讨论,以总运输费用最低为目标,进行物资调运的分配.此时,除去洪水冲断的路外,利用弗洛伊德(Floyd)算法可得新的路线为(见表11):表11i j →路 线 成本i j →路 线成本 企业1→24→26→25→15→42→28 184.8 仓库1→28→42→41→6→40→27227.2企业1→仓库2 24→26→19→18→23150仓库1→储备库228→29→30146.4企业1→仓库3 24→26→25→15→42→28→29→30→39→32→35541.2仓库2→仓库323→18→15→42→28→29→30→39→32→35552企业1→仓库4 24→26→25→15→42→28→29→30→39→32→31483.6仓库2→仓库423→18→15→42→28→29→30→39→32→31494.4企业1→仓库5 24→20→22156仓库2→仓库523→18→19→22166.8企业1→仓库6 24→20→13→12→10→3→36410.6仓库2→仓库623→18→15→42→41→6→40→9→2→3→36492企业1→仓库7 24→26→25→15→42→28→29256.8仓库2→仓库723→18→15→42→28→29267.6企业1→仓库8 24→26→25→15→42→28→29→30→39→32→38505.2仓库2→仓库823→18→15→42→28→29→30→39→32→38516企业1→储备库1 24→20→13→27241.6仓库2→储备库123→18→15→11→27331.6企业1→储备库2 24→26→25→15→42→28→29→30331.2仓库2→储备库223→18→15→42→28→29→30342企业2→仓库1 41→42→2869.6仓库3→仓库435→32→31177.6企业2→仓库2 41→42→15→18→23188.4仓库3→仓库535→32→39→30→29→28→42→15→18→19→22610.8企业2→仓库3 41→6→4→30→39→32→35387.6仓库3→仓库635→32→34→1→33→36321.6企业2→仓库4 41→6→4→30→39→32→31330仓库3→仓库735→32→39→30→29284.4企业2→仓库5 41→42→15→18→19→22247.2仓库3→仓库835→32→38199.2企业2→仓库6 41→6→40→9→2→3→36 303.6仓库3→储备库135→32→34→1→2→9→27372企业2→仓库7 41→42→28→29141.6仓库3→储备库235→32→39→30210企业2→仓库8 41→6→4→30→39→32→38351.6仓库4→仓库531→32→39→30→29→28→42→15→18→19→22553.2企业2→储备库1 41→6→40→27157.6仓库4→仓库631→32→34→1→33→36264企业2→储备库2 41→6→4→30177.6仓库4→仓库731→32→39→30→29226.8企业3→仓库1 34→32→39→30→29→28268.8仓库4→仓库831→32→38141.6企业3→仓库2 34→32→39→30→29→28→42→15→18→23464.4仓库4→储备库131→32→34→1→2→9→27314.4企业3→34→32→35147.6 仓库4→31→32→39→30152.4企业3→仓库4 34→32→3190 仓库5→仓库6 22→20→13→12→10→3→36446.4 企业3→仓库5 34→1→2→9→27→13→20→22 502 仓库5→仓库7 22→19→18→15→42→28→29326.4 企业3→仓库6 34→1→33→36 174 仓库5→仓库8 22→19→18→15→42→28→29→30→39→32→38 574.8 企业3→仓库7 34→32→39→30→29 196.8 仓库5→储备库1 22→20→13→27277.6 企业3→仓库8 34→32→38 111.6 仓库5→储备库2 22→19→18→15→42→28→29→30400.8 企业3→储备库1 34→1→2→9→27 224.4 仓库6→仓库7 36→3→2→9→40→6→4→29362 企业3→储备库2 34→32→39→30 122.4 仓库6→仓库8 36→33→37→38 135.6 仓库1→仓库2 28→42→15→18→23195.6仓库6→储备库1 36→3→2→9→27 224．4 仓库1→仓库3 28→29→30→39→32→35 356.4 仓库6→储备库2 36→33→1→34→32→39→30296.4 仓库1→仓库4 28→29→30→39→32→31 298.8 仓库7→仓库8 29→30→39→32→38 248.4 仓库1→仓库5 28→42→15→18→19→22 254.4 仓库7→储备库1 29→4→6→40→27 216 仓库1→仓库6 28→42→41→6→40→9→2→3→36 373.2 仓库7→储备库2 29→3074.4 仓库1→仓库7 28→2972仓库8→储备库1 38→37→33→1→2→9→27 330 仓库1→仓库8 28→29→30→39→32→38 320.4 仓库8→储备库238→32→39→30 174 储备库1储备库227→40→6→4→30220此时的GTSWFC 模型是:313'11min ij ij i j z d x ===∑∑3131431(403020)4,,13 0,1,2,3ij i j ij j ji ij n x n n x b c j s t x i j ===⎧=++⎪⎪⎪⎪+≤=⎨⎪⎪⎪≥=⎪⎩∑∑∑5.模型优缺点及改进方向5.1 模型的优点(1)本文首先将题中所给的交通图抽象成一张无向图,然后以每百件物资在各边上运输所需费用为权值赋给各边.并利用弗洛伊德(Floyd)算法求出我们所需要的各单位之间的最短路径,从而得出最优的公路交通网数学模型(见表2和图3);(2)在问题2的解答中,为重点保证国家储备库,我们抽象出一个多阶段单目标的规划的GTSWFC模型,运用此模型还可以解出问题3;(3)对于问题4,在汛期来临后,在改进问题2模型的基础上,分三种情况来考虑调运,以使情况紧急和情况不紧急时,相应的总运输耗时和总运输费用最优.5.2 模型的缺点(1)在问题2的建模过程中,我们考虑的是灾情未发生时的情况;(2)在问题4的建模过程中,我们认为情况一的灾情发生时,调运方案还未执行.5.3 模型的改进方向本文的模型只是从单方面(总运输费用或总运输耗时量)考虑最优运输方案.在实际问题中,可以将两方面综合考虑建立一个多阶段多目标的带模糊条件的物资调运系统(GTSWFC)模型.从而使得总运输费用和总运输耗时量同时达到最优,以提高物资调运的综合效率,并能在紧急情况下,保证物资缺乏严重的地方在最短时间内获得它们所需要的物资,以缓解各地的灾情.这样模型的可操作性会更好.。

物资调运问题的优化模型肖凤莲 涂礼才 何三才摘 要:本题所说的是防洪抗涝物质调运问题。

在此问题中我们求各企业、物资仓库及国家级储备库之间物资的运费每一百件最少的路线，把附件2（生产企业，物资仓库及国家级储备库分布图）的分布图转化为数学直观简图（见模型求解中图1），所得图是连通图，设为()E V G ,=，各个边的权为相连两点每百件物资的运费。

我们利用“破圈法”和“最短路”求任意企业、物资仓库及国家级储备库两两之间及仓库与仓库之间的最优路线，显然我们建立的数学（简单图形）模型是可行的、合理的。

得出最优路线见表二、三、四、五。

我们根据实际情况，在保证国家级储备库的情况下，采用就近原则，在此基础上建立线性规划模型（如下）：)))()(())()()(((min 1111111111∑∑∑∑∑∑∑∑∑∑=++==++==++=====⋅+⋅+⋅+⋅+⋅⨯=bi cb b k k i ki a i cb b k k i ikbi cb b k j i b i bj j i j i ji ai bj j i j i w zy xq w z w zy x p A F运用Lingo 软件对我们所建立线性规划问题进行计算。

再把天数为20带入上述线性规划，运用Lingo 运用软件进行计算，可以得到企业2—6—40—储备库1，其他中断路段对物资运输的路线无影响。

建立线性规划，运用Lingo 运用软件求解，其结果见问题4的求解。

此模型简单易懂，容易推广。

运用了LINGO 数学软件，提高了计算的速度。

解得的结果符合实际。

关键词：破圈法、最短路、线性规划模型、Lingo.一、问题的重述我国地域辽阔，气候多变，各种自然灾害频频发生，特别是每年在长江、淮河、嫩江等流域经常爆发不同程度的洪涝灾害，给国家和人民财产带来重大损失，防洪抗涝成为各级政府的一项重要工作。

某地区为做好今年的防洪抗涝工作，根据气象预报及历史经验，决定提前做好某种防洪抗涝物资的储备。

物资调运问题的优化模型肖凤莲 涂礼才 何三才摘 要:本题所说的是防洪抗涝物质调运问题.在此问题中我们求各企业、物资仓库及国家级储备库之间物资的运费每一百件最少的路线，把附件2（生产企业，物资仓库及国家级储备库分布图）的分布图转化为数学直观简图（见模型求解中图1），所得图是连通图，设为()E V G ,=，各个边的权为相连两点每百件物资的运费。

我们利用“破圈法”和“最短路"求任意企业、物资仓库及国家级储备库两两之间及仓库与仓库之间的最优路线,显然我们建立的数学(简单图形)模型是可行的、合理的。

得出最优路线见表二、三、四、五。

我们根据实际情况，在保证国家级储备库的情况下,采用就近原则，在此基础上建立线性规划模型（如下）：)))()(())()()(((min 1111111111∑∑∑∑∑∑∑∑∑∑=++==++==++=====⋅+⋅+⋅+⋅+⋅⨯=bi cb b k k i ki a i cb b k k i ikbi cb b k j i b i bj j i j i ji ai bj j i j i w zy xq w z w zy x p A F运用Lingo 软件对我们所建立线性规划问题进行计算。

再把天数为20带入上述线性规划，运用Lingo 运用软件进行计算，可以得到业2—6—40—储备库1，其他中断路段对物资运输的路线无影响。

建立线性规划，运用Lingo 运用软件求解，其结果见问题4的求解。

此模型简单易懂，容易推广。

运用了LINGO 数学软件,提高了计算的速度.解得的结果符合实际.关键词：破圈法、最短路、线性规划模型、Lingo 。

一、问题的重述我国地域辽阔,气候多变，各种自然灾害频频发生,特别是每年在长江、淮河、嫩江等流域经常爆发不同程度的洪涝灾害，给国家和人民财产带来重大损失，防洪抗涝成为各级政府的一项重要工作。

某地区为做好今年的防洪抗涝工作，根据气象预报及历史经验，决定提前做好某种防洪抗涝物资的储备。

目次摘要2一.问题重述与剖析41.问题的重述42.问题剖析5二.模子假设与符号解释61.模子假设62.符号解释6三.模子的剖析.树立与求解71.关于问题（1）的剖析与求解：72.关于问题（2）模子的剖析.树立和求解83.关于问题（3）的剖析与求解：134.关于问题（4）的剖析和模子的树立.求解：17四.模子的评价与改良20参考文献：21附录21摘要防洪物质调运问题本质是个运筹学收集计划中的最短路问题.因为灾祸产生地点和时光具有较大随机性,联合现实情形,我们对其树立了响应的模子.前三问是提前做好物质的储备,所以我们假设时光相对较裕如.将运输分为三个阶段,分离为：“使储备库优先达到猜测库存”.“使各库存都达到猜测值”和“使各库消失许可最大库存规模内尽可能的多”.应用图论中的办法将交通收集图转化成数学图形,并用Floyd算法求出企业至各储备库及仓库的运输资金起码的各条路线,即将高级公路转化为通俗路线后的等效最短路线.第一阶段：使储备库达到猜测值,以总运费起码为目标树立模子,求出具体调运量.第二阶段：达到猜测库存前以调运时光起码为目标树立模子,求出每条路线前期的调运量.再按照以当天库存与猜测库存相对差值的最大值尽可能小为原则树立模子,假如相对差值雷同,远距离优先运输树立模子,求出各路线天天的具体调运量.第三阶段：达到猜测后以调运费用起码为目标树立模子,求出每条路线后期的调运量.在一致斟酌储备库的情形下,以同样的原则树立模子,求出各路线天天的具体调运量.同时依据问题三的请求,求得20天后各仓库和储存库的物质量如下表所示：问题四中的紧迫调运的问题,我们的重要目标是使防洪物质尽可能早的运输到储备库及仓库.此时,我们不再斟酌运费资金问题,以现实旅程最短为目标求出各企业与仓库间的最优路线.同样将运输分为两个阶段（第一阶段为到达库存前,第二阶段达到猜测库存后）都以调运时光最短即以最短路为目标树立模子,求出各路线的调运量.本文经由过程以上模子联合处理现实问题时目标不合,分离求出了合理的运输路线和调运量以及调运时光和费用,同时还斟酌到路线中止等其它情形,具有较大的灵巧性和适用性.症结词防洪物质调运线性计划模子 LINGO软件 Floyd算法一.问题重述与剖析1.问题的重述我国事一个气候多变的国度,各类天然灾祸一再产生,个中各流域的洪涝灾祸尤其轻微.为了尽可能的减小国度和人平易近的损掉,各级当局经由过程气候预告及汗青经验要提前做好防洪物质的储备工作.该地区临盆该物质的三家企业和八个大小物质仓库.两个国度级储备库,以及附件1中各库库存.需求情形和附件2中其散布情形.别的已知各路段的运输成本,高级级公路2元/公里••百件.研讨如下问题：（1）依据附件2中给出的临盆企业.物质仓库及国度级储备库散布图,树立该地区交通网数学模子.（2）在优先包管国度级储备库的情形下,树立一种调运量及调运路线的计划模子.（3）依据本身所树立的调运计划,求出20天后各库存量.（4）假如汛期下列路段因洪水交通中止,可否用问题二14--- 23 11--- 25 26--- 27 9--- 31的模子解决紧迫调运的问题,假如不克不及,请修正你的模子.中止路段： , , ,2.问题剖析（1）我们可以依据标题及附件2的数据信息加以剖析,把现实图形（曲线图）转化为幻想的纯数学图,再依据图论常识,想办法把幻想的纯数学图放在图论中,加以假设,从而得到可以求解的数学模子.（2）合理的调运计划现实上就是在知足仓库.储备库各自的需求下,请求总运费起码,其实是一个线性计划问题.路线可以依据模子图统计出来.（3） 20天后,先求出每个企业总的临盆量,依据（2）的计划得出各个库的物质量.（4）依据（2）的调运计划中的调运路线看是否经由断桥的地方,假如不经由（2）的调运计划是可行的,假如经由那么要再斟酌其它的路线,我们可以在图一的模子中去掉落桥所对应的边,再反复（2）的步调求解.二.模子假设与符号解释1.模子假设1.假定该猜测值是科学的靠得住的.2.假设公路交汇点27为储备库1,交汇点30为储备库2,将交汇点15与28之间的交汇点9改为42.（参考材料2）3.假设车辆在高级级公路和通俗公路的调运速度雷同.4.假设当局有才能雇佣足够多的车辆将天天所要运的物质一次性的运往目标地.5.假设每次调运均以百件为单位.6.为了表述便利假设将两储备库分离处理为仓库9.10. 2.符号解释c：暗示企业i的日产量;ip：仓库j的猜测库存;jx：暗示企业i的现有库存;iz：暗示仓库j的猜测库存;jq：暗示第k天仓库j的库存量;kjw：暗示第k天仓库j的相对差量;kjy：暗示企业i向仓库j的调运量;ijyy：八天后企业i运往仓库j的总量;ijzz：第k天相对差量（kj w）的最大值;kx：暗示第i个企业在第k天运往第j个仓库的量;kijl：暗示处理后企业i到仓库j的最短旅程;ij三.模子的剖析.树立与求解1.关于问题（1）的剖析与求解：请求树立公路交通网数学模子,即用数学说话来描写各段公路的距离.附件2中的点经由假设处理后,得到42个公路交汇点,个中包含三个企业.八个仓库和两个储备库等.我们用两个极点及边线图表来描写这个交通网,把两点之间有直接公路衔接的描写为如下表格（极点无向图）：表-1：2.关于问题（2）模子的剖析.树立和求解因为发洪水具有随机性,为有用预防,要在最短的时光里包管各仓库的猜测库存,也就是说在达到猜测库存前我们以时光为第一目标树立模子.而在达到猜测库存后,各地区已有必定的戒备才能,所以我们以经济为第一目标树立模子.起首进行数据处理,将高级级公路长度按运费折算成通俗公路的等效长度,采取Floyd算法用C说话编程求出各企业到各仓库等效旅程最短的路线.其成果如下：表-2：第一阶段：我们使储备库达到猜测库存,由企业和超出猜测库存的仓库 3.5向储备库供给.对该阶段初步盘算,企业现存量和仓库超出猜测的量可以或许知足储备库的需求,所以此时不再以总调运时光最小为目标,而以该阶段的挪用费用起码为目标求各企业的调运路线及分派量.模子1的树立：目标函数：总的调运费用最小, 束缚前提：各企业(包含仓库3.5)向外运输量不大于现有的库存量, 使储备库要达到猜测库存,用LINGO 求解,得到第一阶段各企业向各储备库的具体分派量如下:表-3： 第二阶段：使其他各个仓库达到猜测库存.经由过程剖析第一阶段的成果,发明三个企业现存量已全体运完,仓库3刚好达到猜测库存,而仓库5超出猜测库存310.经由过程公式（-=预测库存总量现有库存总量时间三个企业的日产量和）得到各库存都达到猜测值时光为7.44天,即至少须要8天.然后我们把8天后各企业总产量处理为其在8天可调运的总量,树立以运费起码为目标的模子,得到每个企业向各仓库8天的总分派量. 模子2的树立：目标函数:束缚前提：各企业(包含仓库5)向外运输量不大于现有的库存量, 被运输的各仓库要达到准备库存,用LINGO 求解,得到第二阶段各企业向各仓库的具体分派量如下:表-4：第三阶段：在达到猜测库存之后,该地区已经具备了防御一般洪水的才能,为了防御更大的洪水,应当使库存物质尽可能多.经由过程公式（-=最大库存总量预测库存总量时间三个企业的日产量和）得到各库存都达到猜测值时光为38.8889天,即至少须要39天.然后我们把39天后各企业总产量处理为其在39天可调运的总量,树立以运费起码为目标的模子,得到每个企业向各仓库39天的总分派量. 树立模子3如下：目标函数：束缚前提：企业1.2.3在达到猜测库存后39天向外运输的总量分离不该超出4039⨯,⨯.2039⨯.3039各库存不超出其最大储存量,模子3求解的企业后期调运分派计划如下：表-5：3.关于问题（3）的剖析与求解：在模子 2.3中我们已经求得了各企业在两个阶段向各仓库的调运总量,如今的目标就是求出天天调运的先后次序和分派量.我们以为相干部分有才能将现有库存及第一天的产量都输送出去,即第一天就可以或许使储备库达到猜测库存值.对于调运的先后次序问题,在优先使储备库达到猜测库存之后,我们斟酌到仓库的现有库存与猜测库存的相对差值越大,则解释它抵抗洪涝灾祸的才能越小,应当优先赐与调运,进步整体防洪程度.假如上述相对差值雷同时,我们又斟酌到调运路线越长,则因洪水导致交通中止的概率越大,同时产生洪灾时紧迫调运的时光就越长,是以应当先给旅程远的优先调运.依据上述思绪,我们对二.三阶段树立调运先后次序和分派量的模子4：使天天各仓库与猜测值（后期为最大值）的相对差值中的最大值尽可能的小（相对差值雷同时,旅程远的优先调运）.目标函数:束缚前提：每一天各企业的产量都分派完,八天后各企业运输都要到位,即各仓库至少要达到猜测库存,w的求解表达式,kjq的求解办法,kj每一天的最大差量,用LINGO求解得到,811.9584 kkzz==∑.进一步剖析出前八天具体的分派计划模子5.目标函数：束缚前提：其他束缚同模子4.同理可求出后39天的分派计划.最终可得到47天的分派计划.下图是前20天的分派计划：表-6：进而得到20天后各库存量分离为：表-7：4.关于问题（4）的剖析和模子的树立.求解：在汛期时,相当于紧迫调运.与问题（2）的模子有所不合,此时,无论在什么情形下,都要以时光为第一目标,即要知足调运时所走路线的现实距离最短,不但不必斟酌挪用的经济问题,并且不必斟酌储备库优先的情形.分达到猜测前和猜测后两个阶段斟酌.个中,我们要把中止旅程处理为无路,再按照问题（2）中的Floyd算法求出响应的最短旅程和具体路线.表-8：第一阶段,到达猜测库存前.（模子6）目标函数：调运总时光最短,束缚前提：各企业(包含仓库3.5)向外运输量不大于现有的库存量,被运输的各仓库要达到准备库存,用LINGO求解,在达到准备前各企业向各仓库的具体分派量如下:表-9：第二阶段,达到猜测库存后.（模子7）在问题（2）的基本上要加以改良,目标有所不合.目标函数：调运总时光最短,束缚前提与问题（2）中的第三阶段雷同.求解得到分派量如下：表-10：四.模子的评价与改良本文采取了线性计划的办法,从现实问情形动身,针对不合情形下的要乞降不合着重点树立了不合的模子,把问题分阶段斟酌,让成果更合理.此外,模子的适用性强.速度快,可以对突发事宜作出实时的调剂.模子的改良,在本文中我们假设了车辆在高级级公路和通俗公路的速度雷同,而在现实进程中速度是不成能雷同的.依据两者速度的比值对交通收集图中的旅程数据作响应的处理,然后在按同样的模子求解,可以得到更好的现实调运计划.对于提前作好防洪物质储备的情形,应用模子2及模子3调运一段时光之后,假如此时产生洪涝灾祸须要紧迫调运时,我们可以以此时的库存量为起点,调剂为按模子5进行紧迫调运,以此来应对突发事宜.在现实问题中,对于紧迫调运问题,还可以斟酌让产生灾祸地区邻近的仓库.企业及储备库都向灾区供给适量的物质支援,节俭救助时光,尽量减小灾祸所造成的损掉.参考文献：[2][3]沙特 M.H.Alsuwaiyel 算法设计技能与剖析 2007年6月[4] 数学建模网：2008-6-23附录附件1：各库库存及需求情形（单位：百件）附件2：临盆企业,物质仓库及国度级储备库散布图注：高级级公路通俗公路河道1 2 3 12 13等暗示公路交汇点;30,50,28等暗示公路区间距离,单位：公里,如与之间距离为80公里.FLOYD算法FLOYD(int *L,int n){int *D=(int *)malloc((n+1)*(n+1)*sizeof(int));int i,j;for(i=1;i<=n;i++)for(j=1;j<=n;j++)D[i][j]=L[i][j];for(k=0;k<n;k++)for(i=0;i<n;i++)for(j=0;j<n;j++)D[i*n+j]=min(D[i*n+j], D[i*n+k]+D[k*n+j]);}模子一程序LINGO代码：model:sets:z/1,2/:c;x/1..5/:d;links(x,z):l,y;endsetsmin=@sum(links(i,j):l(i,j)*y(i,j)); @for(x(i):@sum(z(j):y(i,j))<d(i)); @for(z(j):@sum(x(i):y(i,j))=c(j)); data:d=600,360,500,450,800;c=3000 2500;l=100 268131.3 148161 152240 175170 338;enddataend模子二程序LINGO代码：model:sets:z/1..8/:c;x/1..4/:d;links(x,z):l,y;endsetsmin=@sum(links(i,j):l(i,j)*y(i,j)); @for(x(i):@sum(z(j):y(i,j))<d(i)); @for(z(j):@sum(x(i):y(i,j))=c(j)); data:d=600,360,500,800;c=500 600 300 350 400 300 500 600;l=164 125 340 192 130 287 224 31068 157 306 158 206 253 128 276298.7 332 123 75 337 145 238.67 93 222 139 410 262 0 357 282 380;enddataend模子三程序LINGO代码：model:sets:z/1..10/:m;x/1..3/;links(x,z):l,y;endsetsmin=@sum(links(i,j):l(i,j)*y(i,j));@sum(z(j):y(1,j))<40*39;@sum(z(j):y(2,j))<30*39;@sum(z(j):y(3,j))<20*39;@for(z(j):@sum(x(i):y(i,j))<m(j));data:m=800 900 600 400 1000 500 600 800 4000 3000; l=164 125 340 192 130 287 224 310 100 26868 157 306 158 206 253 128 276 131.3 148298.7 332 123 75 337 145 238.67 93 161 152;enddataend模子六程序LINGO代码：model:sets:z/1..8 /:c;x/1..5/:d;links(x,z):l,y;endsetsmin=@sum(links(i,j):l(i,j)*y(i,j)); @for(x(i):@sum(z(j):y(i,j))<d(i));@for(z(j):@sum(x(i):y(i,j))=c(j)); data:d=600,360,500,450,800;c=500 600 350 300 500 600 3000 2500; l=168 282 164 123 407 342 224 425 110 148 68 157 273 253 118 291187 102 272 391 75 145 212 93310 175 371.67 510 148 268 311.67 166198 338 222 139 415 393 282 433; enddataend模子七程序LINGO代码：model:sets:z/1..8/:m;x/1..3/;links(x,z):l,y;endsetsmin=@sum(links(i,j):l(i,j)*y(i,j)); @sum(z(j):y(1,j))<40*39;@sum(z(j):y(2,j))<30*39;@sum(z(j):y(3,j))<20*39;@for(z(j):@sum(x(i):y(i,j))<m(j)); data:m=800 900 400 500 600 800 4000 3000; l=168 282 164 123 407 342 224 425110 148 68 157 273 253 118 291187 102 272 391 75 145 212 93; enddataend工作分派情形：卢月英树立数学模子李小姣编写程序代码边汝坤汇集材料并整顿论文。

物资紧急调运优化模型摘要本文就物资紧急调运问题，在合理的假设下，采用了规划的理论和方法建立数学模型，针对实际问题给出了合理的调度方案。

在问题1中，将工作量（运输路程与运输量的乘积）作为衡量合理调度的标准。

利用Floyd 算法得到企业、仓库、储备库之间的最短路线。

考虑到重点保证国家级储备，分两步建立模型：（1）、建立所有企业和仓库向国家级储备库进行调运的线性规划模型；（2）、建立3个企业向8个仓库进行调运的线性规划模型。

最后对以上模型分别用LINGO 软件包进行求解，实现最小工作量为295520公里·百件调运方案，具体调运量见表4-3、4-4。

在问题2中，根据问题1已得到的调运方案，建立以时间最少的优化模型，利用LINGO 软件求解确定了18辆车的最佳调度方案所用的时间为64天。

18辆储备量基础上，建立物资调运运费线性规划模型，得出调运方案；再建立车辆的线性规划模型，利用LINGO 软件求解得出最少需要33辆车，调度方案见表4-11 。

在问题4中，属于紧急调运问题，任务是将物资尽快调运到 号地，此时不再优先考虑费用资金问题。

在5天期限内，建立仓库和储备库到 号地的最优调运模型，从而实现车辆调度最少的目标。

通过LINGO 软件求解得到最少需要关键词 Floyd 算法 线性规划 LINGO16 161 问题重述当前我国自然灾害频频发生，因此各项预防工作成为了国家和地方各级部门的一项重要工作。

某地区现有3家物资生产企业，8个不同规模的物资储存仓库，2个国家级物资储备库，他们的相关数据及其位置分布和道路情况分别见附表1和附图1。

又已知该物资的运输费用为高等级公路2元/公里·百件，普通公路1.2元/公里·百件。

各企业、物资仓库及国家级储备库的物资需要时可以通过公路运输相互调运。

在此基础上研究以下问题：（1）根据未来的需求预测，在保证最低库存量和不超过最大容许库存量的情况下，还要重点保证国家级储备库的储存量，试设计给出该物资合理的紧急调运方案，包括调运线路及调运量。

防洪物资调运问题我国地域辽阔，气候多变，各种自然灾害频频发生，国家和人民每年因此损失惨重，因此防洪抗涝工作至关重要，而防洪抗涝物资的调运与储备与物流管理息息相关。

所以，物资调运作为物流不可或缺的环节其重要性也日益呈现出来，其合理化也显得十分重要。

对于问题一，我们通过对交通网络的分析，构造了最短路权的二维矩阵'D，从而建立了这个地区公路交通网的数学模型，对于该模型的求解我们采用Dijkstra算法并按照一定的迭代规则进行n次迭代，得到了一个最短路权对称矩阵。

相比于其它算法，这种算法更易于实现和理解，且效率高，运行速度快。

在问题二中我们先从简单入手，将问题尽量的简化建立了一个简单的数学模型并得出了一个较为合理的结果，但是题中并没有对时间以及理想库存等影响决策变量的因素进行量化，这就需要我们对其模糊条件进行量化，从而建立了调运系统中模糊条件的量化模型，并选取了适当的“虚拟”运价和“虚拟”销地，他超越了以往经典问题的求法。

对于其解法我们又将规划()L转化为规划并建立了()2L相比于单纯形法，放宽了条件限制，也避免了由1于贮存空间大选用分枝界定法和割平面法带来的求解运算量大，计算效率低等问题，从而使得我们的模型更具有可靠性。

在计算过程中路径和运费作为基本出发点，在满足提设条件下以运费最小为参考。

最后，我们对这个调运问题提出了合理的调运方案并为该地提供了调运的科学依据。

一、问题重述（略）二、问题分析问题一：要建立该地区的交通网的数学模型，考虑其现实意义我们应当从任意两点间的最短路权来考虑，因此我们引出了交通网的最短路权矩阵，从而建立了交通网的最短路权举证模型。

问题二：要求合理的调运方案，我们应该在满足提设要求的情况下主要从时间、运费、路经等加以分析。

但是由于题中并没有对时间以及理想库存等量化，这就需要我们对其模糊条件进行量化，从而建立了调运系统中模糊条件的量化模型。

问题三：在问题二的基础上我们很容易得出结果。

物资调运方案的优化单纯形法清晨的阳光透过窗帘的缝隙，洒在了满是数据与图表的桌面上。

我深吸一口气，看着眼前这个复杂的物资调运问题，心中已经有了些眉目。

10年的方案写作经验告诉我，单纯形法将是解决这个问题的关键。

让我们明确一下目标。

我们的目标是在有限的资源下，实现物资从产地到消费地的最优分配。

这涉及到运输成本、运输时间、物资需求量等多个因素的考量。

传统的调运方案往往只能考虑到其中的几个因素，而单纯形法可以让我们全面考虑所有因素，找到最优解。

我们开始构建模型。

将物资的产地和消费地抽象为节点，将运输线路抽象为边，形成一个网络图。

然后，根据各节点间的距离、运输能力等因素，计算出每条边的运输成本。

这样，我们就得到了一个成本矩阵。

现在，让我们来定义一下变量。

假设有m个产地和n个消费地，我们可以用一个m×n的矩阵X来表示物资的调运方案。

其中，Xij 表示第i个产地到第j个消费地的物资调运量。

我们需要根据物资的需求量和产地的供应量，列出一系列的约束条件。

现在，我们来到了单纯形法的关键步骤——构建单纯形表。

将成本矩阵和约束条件代入单纯形表中，然后通过一系列的变换，找到最优解。

这个过程涉及到基变量、非基变量、检验数等概念，但对于我来说，这些已经是驾轻就熟了。

在构建好单纯形表后，我开始进行迭代。

每一次迭代，我都会根据当前的最优解，调整物资的调运方案。

这个过程就像是在解一个巨大的拼图，每一步都在向最优解迈进。

经过几次迭代，我发现单纯形表的检验数已经全部为非负数，这意味着我们已经找到了最优解。

根据最优解，我重新调整了物资的调运方案。

这个方案不仅考虑了运输成本，还考虑了运输时间和物资需求量等多个因素，是一个全面且高效的最优方案。

我将这个方案整理成了一份详细的报告。

报告中，我详细描述了模型的构建过程、单纯形法的应用步骤以及最终的最优解。

我知道，这份报告将会为公司的物资调运带来巨大的效益。

看着眼前的报告，我满意地笑了。

防洪物资调运的数学模型汪军;孙志红;刘信斌【摘要】首先构建防洪物资调运的交通网络矩阵模型,并利用Dijkstra算法寻找各调运节点之间的最优路线,然后在平时以追求最小总调运费用、紧急情况下以追求最快调运速度为目标建立了防洪物资调运的优化模型,在此过程中引入偏离控制量以便充分考虑各调运节点的需求,讨论了调运期、偏离控制量对调运费用的影响,为科学制定调运方案提供依据,较好地解决了防洪物资的调运问题.【期刊名称】《大学数学》【年(卷),期】2010(026)003【总页数】5页(P137-141)【关键词】物资调运;Dijkstra算法;偏离控制量;调运节点【作者】汪军;孙志红;刘信斌【作者单位】徐州空军学院,基础部,江苏,徐州,221000;徐州空军学院,基础部,江苏,徐州,221000;徐州空军学院,基础部,江苏,徐州,221000【正文语种】中文【中图分类】O221.12007年5月江苏省工业与应用数学学会及中国矿业大学联合主办了第四届苏北数学建模联赛,联赛得到包括武汉大学、国防科技大学、中国农业大学等跨及全国12个省市60多所高校的积极参与,本文诣在解决其中的C题——防洪物资调运问题.(i)高等级公路与普通级公路的调运速度是恒定且相等的;(ii)各企业、物资仓库及国家级仓储库之间的物资可以通过公路运输互相调运且所有公路均可双向运输;(iii)调运物资的运输车辆是充足的,即一旦确定调运方案,即刻可调运完毕;(iv)调运节点指生产企业、物资仓库、国家储备库共13个,调运期系指开始实施调运的时间;(v)只考虑运输费用,不考虑物资装卸、储存等其它费用.ri——调运节点i调运后的库存量(百件)xij——从调运节点i到调运节点j之间的物资调运量(百件) Mi——调运节点i的最大库存量(百件)fi——调运节点i的预测库存量(百件)vi——生产企业i的产量(百件/天),i=1,2,3ti——生产企业i在调运期的生产天数(天)z——总调运费用(元)通过对问题的分析,该地区的公路交通网络数学模型应该是指包含42个顶点的赋权图.所谓合理的调运方案就是要在尽可能地满足各个调运节点需求的前提下,平时尽量使调运费用最小,而在紧急情况下应尽快地将防洪物资调运到各需求点,这些都需要去寻找各调运节点之间的最优路径,所以这是一个优化问题,可以考虑建立该问题的规划模型.1.交通网络模型在该地区交通网络图中调运节点共有13个,包括企业三家、物资仓库八个、国家储备库两个,为表达方便,我们按企业1,企业2、企业3、物资仓库1、……、物资仓库8、国家储备库1、国家储备库2的顺序编号为1到13,防洪物资的调运只限于在13个节点之间进行调运,故需找到它们之间的最优调运路线,平时应以最少运输成本Wij(i,j=1,2,…,13)为优.这里寻找最优路线时我们用Dijkstra算法来解决.根据Dijkstra算法求出企业1与仓库1的之间的最优调运路线为24→26→25→15→42→28,每百件的运输成本W1,4=184.8(元/百件);企业1与国家储备库2的之间的最优调运路线为24→26→25→11→6→4→30,运输成本W1,13=321.6(元/百件)等,由此可以得到运输成本矩阵(Wij)13×13.2.问题2及问题3的模型建立及求解问题2要求设计一个在重点保证国家级储备库的情况下的合理调运方案,为此设从调运节点i到调运节点j的调运量为xij(百件),xij≥0,i,j=1,2,…,13.则调运结束后各个调运节点的库存量为为重点保证国家级储备库的库存,合理调运方案必须使国家级储备库的库存达到或者超过其预测值:ri≥fi,i=12,13.仓库1到仓库8的应尽量达到或超过预测库存,为此考虑用一个偏离控制量ε(ε＞0)来控制,即根据调运计划及各企业生产能力,调运期至少应为8天,才能满足基本要求,若给定ε=0.05,通过Lingo求解得调运方案见表1.按此方案调运的最低总运输费用为321680元.对于问题3,在问题2中令 T=20,可以计算求得新的调运方案,此时调运总费用为299763元, 20天后各个调运节点的库存情况如表2所示.3.问题4的模型建立及求解问题4要求解决汛期部分路段中断情况下的紧急调运问题,此时应该考虑速度尽可能快,而无须考虑运费.鉴于洪水导致路段中断,故应构建新的交通网络赋权图G(V,E′),其中每条边的权值为smn, E′为集合E中去除边○14○23,○11○25,○26○27,⑨○31的集合,利用Dijkstra算法计算各调运节点之间的最短路径Sij(i,j=1,2,…,13),在问题2中将目标函数修改为以8天为调运期,在约束条件不变的情况下,得到最优调运方案如表3.1.调运期的长短与运费的关系在求解问题2和问题3的时候,我们发现,在调运期为8天的时候,总运费为321680元,调运期为20天的时候,总运费为299763元.显然,调运期的长短对最终运费有着显著影响.我们希望能够找到一个最佳的时间,使得总运费能够达到最小,同时使各调运点的库存能够达到或超过预测值.为此对问题2中的模型进行修改,建立最佳时间模型如下. 在这个模型中,要求在调运完毕后,各库的库存都要达到或超过预测值.令T=8,9,10,…,计算得到调运期与总调运费用之间的关系如图1.从图1可以看出,随着调运期的增加,总的调运费用不断下降.当 T增加到22天的时候,调运费用趋于平衡,不再发生改变.造成这种情况的原因是,随着调运期限的增加,企业可用来生产的天数也增加,因而企业能够运出的物资量也增加,相应的输出选择面和灵活度也增加,从而使总运费降低.因此,根据此模型防汛部门可以科学制订调运期,特别是在准确预测汛期的情况下,对于提前做好科学决策有重要意义.2.调运期的长短、ε的取值对费用的影响ε的取值对于费用也有着重要的影响,我们希望能够找到ε和T对于总费用的影响效果.为此,在问题2的模型中,分别取不同的ε和T值从而得到总调运费用与ε及调运期T的关系如图2.从图2可以看到,总调运费用均随着偏离控制量ε和物资生产天数T的增加而减少.这是非常符合实际情况的,因为ε的增大使得约束条件减弱,因而总的调运费用降低;物资调运期 T的增加使得各个企业的产量增大,故导致调运任务的灵活性增加,因而总的调运费用降低.同时,从图2可以很明显地看出:ε波动对总调运费用的影响比物资调运期T的改变对总调运费用的影响要大.所以ε的控制效果是非常明显的.In this p rocess,in o rder to fully consider the needsof all transport node,the deviate control variable was introduced, and the impact of thetranspo rtation period,the deviate control variable on transpo rt costswere discussed,w hich p rovides the scientific basis fo r transferring p rogram,and give a better solution to flood-p reventing material dispatching p roblem.【相关文献】[1] 汪军,等.战时航空油料的优化调拨[J].南京航空航天大学学报,1999,31(1):112-115.[2] 姜启源,等.数学模型[M].北京:高等教育出版社,2004.[3] 钱颂迪,等.运筹学[M].北京:清华大学出版社,1990.[4] 袁新生,邵大宏,等.L INGO和Excel在数学建模中的应用[M].北京:科学出版社,2007.[5] 谢金星薛毅.优化建模与L INGO/L INDO软件[M].北京:清华大学出版社,2004.。

基于匈牙利算法的股道繁忙评判与列检分配优化模型孙鑫 王伟 张睿 （中国矿业大学，徐州 221008）摘 要本文建立了火车站股道和列检工作分配的优化模型，使得火车站在满足正常运行和最大安全效益的前提下，确保各股道的繁忙程度尽量平均以及职工分配列检工作能公平公正合理，并给出根据有关数据利用模型分析得到的优化方案。

对于问题一，首先应用统计学对列车时刻表数据进行了处理，然后应用模糊数学中F 综合评判理论进行模糊综合评判，得到了股道的繁忙情况：繁忙的股道是1、2、4、10，不繁忙的股道是3、5、7、8、9。

本文优先考虑每条股道上接待的列车数目尽量相等，再考虑局部繁忙时段的列车尽量在每条股道上分配均匀，由此选用空闲时间的方差为目标函数，采用匈牙利算法进行最小化优化，对应得到的最优解即为合理分配方案。

对于问题二，基于本题数据的特殊性，本文先按列车到站时间顺序，把和列检队数目相同的待检修列车分组讨论；然后以最大安全效益为首要目标函数，其次考虑工作量均衡，应用匈牙利算法进行优化分配，分别用手工和LINGO 软件计算得出了每个工作队应负责的车次并进行了对比。

最后依据手工解得到列检队的工作安排方案。

1问题的提出（略）2 符号说明2.1 问题一2.1.1 股道繁忙度评价k T 1：第k 股道空闲时间1t ：股道平均空闲时间期望ki T 2：股道内两辆相临列车的间隔时间k T 2：股道列车平均间隔时间L：车站可以停靠的股道的数目。

2.1.2 列车均衡分配股道模型mt ：第m 条股道上最后停靠列车的出站时间。

n T ：第n 列客车的进站时间。

nmc ：第n 列客车停靠第m 条股道时该股道的空闲时间与平均空闲时间的差值的平方。

t ：平均空闲时间。

2.2 问题二：c：求出第i个列检队检修第j列客车所需要跨越的股道数目。

ijz：各检修队所跨越的总股道数。

m：第i组列检队所在的股道。

iM：第j列客车到站停靠股道。

jt：第i组列检队列检结束的时间。