数学建模论文定稿

《数学建模论文定稿》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数学建模一周论文论文题目：费用分担问题的最优方案队长1:牛科科学号:1021620122电话：18770057382队员2:程兴其学号:1021620105队员3:谭术升学号：1021620125专业：地理信息系统班级：10216201指导教师：张文2012年06月10日摘要在当今资源稀缺的市场经济时代,如何优化配置各种有限资源对一个公司或国家来说越来越重要。谁能够找出合理最优的配置方案谁就有可能在激烈的市场竞争环境中生存下来。本案例针对问题8:费用分担问题提供出了一种合理的模型。问题8中提供了2种方案，第一种方案是每个城镇独立建污水处理厂，这种方案最简单，计算较为方便。直

2、接利用常规数学知识就可以得出最后需要的费用。每个城镇最后的费用W[i]=Cl*Q[i]，（i=l，2,3）即最后的总的费用M=W[1]+W[2]+W[3];由于每个城镇的污水量都有区别，所以每个城镇都独立建厂显然不能充分利用资源。所以我们考虑是否可以采用第二种方案。第二种方案，第二种方案又有4种可能：1.三个城镇共用一个污水处理厂；2.城镇一和城镇二共用一个；3.城镇二和城镇三共用一个；4.城镇一和城镇三共用一个；针对这四种可能我们可以抽象用一种模型来处理，我们可以将其抽象为一个图的问题，在具体一点就是一个求最短路径问题，那么我们就可以利用迪杰斯特拉（Dijkstra）算法

3、就可以找出其最优解。进而就可以找出其最优方案。费用分担问题及其最优解决方案:据结构时间复杂度关键词最短路径迪杰斯特拉算法一、问题重述与分析1.1问题的重述随着经济的高速发展以及人类社会的飞快进步，人类对自然的破坏也愈加严重，其中尤为严重的就是环境污染。而污水的污染毫无疑问在其中占有极大的比重,但是怎样来平衡经济利益与污水处理成本以经成为一个关键性问题。现有临近一条河流的三个城镇，城镇一，城镇二，城镇三；给出了一些基本费用的经验公式，以及三个城镇的相互距离。根据这些信息，进行合理的模型假设，利用数学建模的方法，进行计算找出费用最少的合理配置方案。1.2问题的分析首先，从政府的

4、角度出发，每年财政收入是一定的，在针对环境治理污水处理这一块肯定是以最少的费用达到最好的效果是最好的。所以这里的资源的最优配置就是资金的合理配置。其它类似资源的配置可根据本模型类似求解。明白了本例中的资源配置下一步就要分析其中的决定因子，显然决定费用多少的决定因子有多种，但是不可能就所有的决定因子进行讨论，所以必须进行必要及合理的假设。假设其由建厂费用C1，管道费用C2,维护运营费用C3及效益回报值P决定。本例要解决的就是怎样合理配置才能以较小代价达到比较理想的回报。其实种问题类似线性规划问题中的求最优界问题，但是由于其中涉及的决定因子（变量）较多并且其中涉及到许多非线性问

5、题,所以利用一般的线性规划已经无法解决。所以必须要找到一种能够表示多个因子或者说多个量间关系的模型，这个模型不仅能够表示出其中的复杂的关系同时也能进行一定的逻辑运算进而得出最优解。这是我们的最终目的此我们由此联想到数据结构中的相关知识，利用数据结构中的图的模型就可以轻松解决该问题。二、基本假设1.假设三个城镇距河流的距离相等；2.假设如果分别独立建厂的话，每个厂的规模都相同且都能够满足需要；3.假设每个城镇的污水量是固定不变的；4.假设污水处理厂的地址只能在三个城镇中选；5.假设污水处理厂无论在那个城镇其运营费用都是不变的；6.假设无论哪个城镇其污水处理后的效益回报值是一样

6、的；7.假设城镇承担的费用与其污水量间的比例呈线性关系；三、符号的约定C1:污水处理厂的建厂费用;L:污水管道长度；C2：管道费用；P：污水处理后的效益回报值W:开支总费用；W[i]:第i个城镇建厂的费用;Q[i]：第i个城镇的污水量；A:城镇1;B:城镇2;C:城镇3;、原理与模型4.1迪杰斯特拉最短路径模型首先我们必须明确图的基本概念，图是一种较线性表和树更为复杂的一种数据结构，他可以表示各个要素间的相互关系。而迪杰斯特拉最短路径模型提出了一个按路径长度递增的次序产生最短路径的算法。首先，引进一个辅助向量D，他的每个分量D[i]表示当前所找到的从始点v到每个终点v[i]

7、的最短路径的长度。它的初态为：若从v到v[i]有弧（即v与v[i]间有关系，有路径），则D[i]为弧上的权值;否则置D[i]为00。显然，长度为：D[j]=Min{D[i]lv[i]eV（这里V指的是所有关系元素的集合）};的路径就是从V出发的长度最短的一条最短路径。此路径为G，v[i]）。那么，下一条长度次短的最短路径是那一条呢？假设该次短路径的终点是v[k]，则可想而知，这条路径或则是（v，v[k]），或则是（V，v[j]，v[k]）。它的长度或则是从V到v[k]的弧上的权值，或则是D[j]和从v[j]到v[k