《防洪物资调运问题1》由会员分享，可在线阅读，更多相关《防洪物资调运问题1（17页珍藏版）》请在金锄头文库上搜索。
1、防洪物资调运问题摘 要我们的模型主要用于解决如何在最少运费的情况下将必需物资调运到各个仓库以达到防洪的目的。对于问题一：我们采用赋权连通图的图论法，把两地的运费作为它们之间线路的权值，然后利用“画圈去大”原则进行最小总权值的求解。然后，我们又引入了动态规划中的顺序递推法进行两地之间运费最短路的选择。对于问题二：我们首先利用顺序递推法求解出任两地之间的运费最短路径。同时，由于要重点保证国家储备库，我们引进加权系数、进行调运量的限制。由于仓库3与仓库5的现有库存量大于预测库存量，我们考虑是否应将两库超过预测库存量的那部分空闲物资进行调运，进而建立了两个模型。然后，我们分别运用线性规划的方法，给出目
2、标函数，归纳如下：结合各自的约束条件，我们利用LINDO软件进行解模，求出两者的最优调运量及总运费。之后，进行两者总运费的比较，得出最终的最优调运方案。对于问题三：我们利用问题二的结果求出每个企业必要的最低生产天数，若企业的20天，则它所供给的仓库以及储备库就已达到预测库存量。若企业的20天，则可以用比例求解出20天后该企业向每个仓库以及储备库的调运量，进而可以求出20天后各库的库存量。对于问题四：当某路段遭破坏而不能保证某仓库的储存量时，我们考虑了三种方案。一为寻找次短路线进行物资的重新调运；二为从其他企业向供应源中断的仓库进行物资调配；三为进行整体线路的重新调配。最后进行三者总运费的比较，
3、确定了最经济合理的调配方案。一、问题重述（略）二、模型假设1、各企业的生产日期为无限。即在洪水之前各个企业均已将全部物资调运到相应的仓库。2、在整个的生产过程中，生产费用不予考虑。3、仓库的物资的储存费、转运费不予考虑。4、各个企业向仓库转运的过程不予考虑，即转运的时间抽象为0。5、预测库存即为能够满足最低保障的防洪物资量，最低库存的物资量包含于其中。6、各企业的物资调运在每天的分配里是均匀的，为线性递增的。7、为了重点保证国家级储备库，我们引进两个满足一定关系的权值系数、，这辆合格系数在一定程度上是切合实际的。三、符号说明： 阶段： 从起点到第阶段的状态的最少费用。： 之间的距离： 从地到地
4、的最少运费： 20天之后第个仓库的库存量： 从个企业到个仓库每天的调运量： 从个企业到个仓库的总调运量： 第个企业生产物资的天数： 从个企业到个仓库调运物资的天数： 前部指标函数： 从起点到第阶段的状态的最少费用。： 之间的距离、： 加权系数： 总费用四、问题的分析对于问题一，我们要求解该地区的公路交通网的数学模型，即在此公路网中找出求解点对点的最短路径，就可以使运输费用最低。于是，我们想到了动态规划的方法。另外，还可以运用一些其他的方法，如图论连通附权值法。对于问题二，我们认为可以不考虑企业的生产成本、企业生产天数的限制，而只需保证各仓库储存量以及国家级储备库的存储量。又因需要重点保证国家储
5、备库。我们可以附权值系数、进行调运量的限制。然后，我们可以根据问题一中的动态规划的方法找到点对点的最短路径。进而，运用线性规划的方法，约定目标函数然后进行求解即可。对于问题三，我们可以利用问题二的结果求出了每个企业必要的最低生产天数，若某企业的20天，则它相应的仓库就已达到预测库存量。若某企业的20天，则可以用比例法求解出20天后该企业向每个仓库以及储备库的运输量，进一步可以求出20天后各库的库存量；。对于问题四，当某路段遭破坏而不能保证某仓库的储存量时，为求出其当前的最短路径，我们可以分析三个企业分别向该仓库的运费情况，通过比较，得出哪个企业向其供给才使得总运费成本最低。五、模型的建立与求解
6、（一）、对于问题一：我们主要从附权连通图和图论、动态规划中的顺序递推法建立该地区公路交通网的数学模型。（1）、将生产企业，物资仓库及国家级储备库计为相应的顶点，将顶点之间的长度用输送单位物资量所需要的运输费用来表示，计为边的权，组合该运输问题所对应的赋权连通图，进而求到该图的最小树，即为点对点运输成本最低的路线。其中的原则是：在点对点的运输过程中，尽量不要走回头路。下面我们就以企业 1 向仓库 5 和企业 1 向仓库 2 的输送最佳路径的求解为例，阐释一下我们的具体算法：根据附件2：1、我们得出企业 1 向仓库 5 的简图为接下来，我们求出费用最短的路线，即运输路线。在此之前，我们引入上述算法
7、：在赋权图中任取一个圈，然后去掉这个圈中权最大的边，如果相等可以任去一条边，如此继续进行下去直到图中不再有圈为止。这时剩下的边组成的子图就是最小树。从企业1到仓库5有两条路可走，分别为：路径路程所需费用24202213015624261922130156由以上的算法可知：由于两条路径相等，任意去掉一条，比如是242022，那么运输的最佳路线为24261922。即路线图为：2、我们得出企业 1 向仓库 2 的简图为即路线图由以上的算法可知：任取一个闭合曲线，比如23181623，其中，1816运费最大，故舍去；再取23181922211623，其中，211623运费最大，故舍去；再取242022
8、192624，其中，24202219运费最大，故舍去，那么运输的最佳路线为2426191823。为：对于我们引用的此种图论方法，我们来证明这种方法的可行性：设在第一次去掉的边为e,第二次去掉的边为e,，最后去掉的边为e,与这些边对应的圈为C,C,C,即每个e是C中权最大的边。这里C是去掉边e,e,e后剩下的图中的圈，对于ij，C不属于C。设去掉边e, e, e后剩下的子图为H，那么H是一棵树。这是因为每次去掉的边e都是圈中的边，故去掉e后，图仍是连通的。又去掉e后图中没有圈，因此剩下的子图是一个无圈的连通图，故是一棵树。在H中任取一条边e,S(e)=e,e, e, e且不妨设iir,有L(e)
9、L(e),及L( t)L(e)显然， e CS(e)e故e或等于e或等于e。由上面的假设，有L(e)L(e)这与eC中权最大的边矛盾，由定理:设T是G的一棵生成树，T是G的唯一最小树的充要条件是下列两个条件中的任一个成立：对任意eG T,e是C(e)的唯一权最大的边。对任意e T, e是S( e)的唯一权最小的边。可知，H是最小树。（2）、对于两点间的路径寻找，我们可以用动态规划的顺序递推方法寻找费用的最短路径。顺序动态规划方程的原理为：我们可以考虑前部指标函数及最优值函数。当时，得 于是得： （ * ）式中，或。其求解过程，根据边界条件k=2开始，由前向后顺推，最后求出时，就得到整个问题的最
10、优解。（ * ）式称为顺序动态规划方程。（二）、对于问题二：要设计最合理的调运方案，我们采用的衡量指标为：总运费最少。我们可以利用上题的第二种的动态规划的顺序解法求解个两点间的运费最短路问题：我们以求解企业1仓库2的总运费最少时对应的路径为例：（1）、当=1时， =,（2）、当=2时， =30*1.2=36元（3）、当=3时，（4）、当=4时，（5）、当=5时，故：当费用最少时，为150元，与其相对应的路径为24-26-19-18-23。同样地，我们可以得出任何一个企业往任何一个储备库或者任一个仓库进行物资调运时的最合理的路径：企业1仓库/储备库企业2仓库/储备库企业3仓库/储备库储备库1仓库
11、储备库2仓库 在设计该物资的调运方案时，我们要重点保证国家级储备库。为了实现此目标，我们引进两个加权值和，8个仓库的加权系数为同一个优先等级的，两个储备库的加权系数为同一个优先等级的。于是，有：即：又因在同等情况下，我们要更大可能地给国家储备库进行物资的调运以重点保证国家级储备库，于是，在保证最小运费的情况下，有：，即：，从而：我们取：，因为预测库存为最低保障下的库存量，我们只需保证各库的最终库存量不少于预测库存即可。而仓库3与仓库5的现存量大于预测量。于是，企业和储备库没有必要再向仓库3和仓库5进行物资的调运，并且我们可以考虑将两库的超过预测库存量的那部分空闲物资进行调运。下面，我们分两种情
12、况来看究竟有没有必要把仓库3与仓库5的那部分空闲物资进行调运。方案一：把仓库3与仓库5的那部分空闲物资进行调运： 要使总运费最小，我们对此问题进行如下的线性规划：我们利用LINDO软件进行求解（具体代码及结果见附录一），得到： （单位：百件） 在此种情况下，总的运费为： =363816(元) 方案二：不把仓库3与仓库5的那部分空闲物资进行调运：要使总运费最小，我们对此问题进行如下的线性规划：我们利用LINDO软件进行求解（具体代码及结果见附录二），得到： （单位：百件） 在此种情况下，总的运费为： =317076(元) 由上，我们可以看出： 于是，我们应该选择第二种方案。即：不把仓库3与仓库5
13、的那部分空闲物资进行调运。综上：在最合理的物资调运方案中，各物资的调运线路和调运量为：调运起始点调运线路调运量（百件）总运费(元)企业1仓库22426191823330317076企业1储备库12426271000企业2仓库141-42-28300企业2仓库741-42-28-29110企业3仓库434-32-31120企业3仓库634-1-33-3620企业3仓库834-32-38100企业3储备库234-32-39-30700（三）、对于问题三：在计算出各个调运线路及其调运量之后，我们利用各企业的调运量来对各企业的物资生产时间进行限制。因为企业的总库存量应该始终小于最大库存量，即：对于企业一：0 40 +600-1300 800 17.537.5对于企业二：0 30+360-410600 3.6736.7对于企业三：0 20+500-940600 2252我们对各个企业的生产过程只要求达到各个仓库的预测库存量，于是，我们只要取各企业的生产时间的最小值即可。即：=18 =4 =22于是，在20天后，企业1与企业2已将全部物资运完，此时，一些仓库的库存量为（单位：百件） ， ， ， ， 。而在20天后，企业3还未将全部物资调运完，且上述第（2）种方案提出的结果为全部调运完时的总调运物资量，又由于我们假设企业向仓库每天
