两种水资源调度算法
摘要：本文讨论了中国大陆的水资源调度问题。

水资源调度问题，本质是个运输问题。

本文在两种不同的假设下，利用线性规划和多目标规划的方法提出了相应的算法模型，并利用lingo语言，给出了相应的具体模拟结果。

关键词：水资源；调度问题
中图分类号：tp393.1
本文基于2013年美赛数学建模大赛b题[1]的假设，提出了两种水资源调度模型。

在水资源调度的过程中，我们首先以各地区距离和水资源紧缺情况为主要因素以线性规划的方法得到最优的调度方法，并灵活地采用加权的方法综合考虑各区域地势高低和水资源对其重要性等因素，对调度方案进行合理的优化，最后得到了令人满意的结果。

1 简单模型
由中国统计年鉴[2]，我们得到水资源有剩余的省份水资源供给量为2282，水资源缺乏的省份水资源需求量为2541，所以水资源的需求量大于供给量，为了使水资源得到充分的利用，我们进行如下的假设：i供给省份标识；j需求省份标识；cij供给省份i向需求省份j运输水的单位成本；xij供给省份i向需求省份j运输水量；ai供给省份供水量；bi需求省份需求量。

由于水资源应尽可能的得到充分利用，则各供给省份供给量用完，即。

由于水资源的需求量大于供给量，所以需求省份并一定
能满足需求，即。

而，则表示完成某次调度之后的总成本，为了使总成本最低，建立如下线性规划：
其中通过经纬度算出各省份省会距离近似取代供给省份i向需求省份j运输水的单位成本cij，然而实际问题中单位成本还需考虑地势的高低和水资源对各省份的重要性，我们采用公式：
newcij=0.6*k*old*cij+0.4*p*old*cij+r（其中0.6和0.4为地势的高低和水资源对各需求省份的重要性对运输水的单位成本影响
的权值，r为随机因子，视具体情况而定）其中p由上表数据我们可以得到水资源对各个需水省份的重要性指标，分为6个等级，取：p的数值越低，表示水资源对各个需水省份的重要性越大，单位成本越低，以增加供给省份向其供水的可能性。

相反p的数值越大，表示水资源对各个需水省份的重要性越小，单位成本则越大，供给省份满足其需求的可能性就有所降低，以此达到优化调度方案的策略。

k代表供给省份与需求省份地势上的差异对单位成本的影响，比如供给省份与需求省份地势相当，则k=1，供给省份地势高于需求省份，则k=0.5，供给省份地势低于需求省份，则k=2，即，从而从地势高的省份往地势低的省份运输水，k较小，单位成本较低，从地势低的地方往地势高的地方运输水，k较大，单位成本较高，这更加符合实际情况，使调度策略更优。

第一阶梯（地势最好）： xizang，qinghai。

第二阶梯（地势居中）： gansu，xinjiang，neimenggu，
ninghxia，shaanxi，shanxi，chongqing，sichuan，guizhou，guangxi，yunnan
第三阶梯（地势最低）： hunan，hubei，henan，guangzhou，fujian，zhejiang，jiangxi，anhui，jiangsu，shandong，hebei，liaoning，jilin，heilongjiang，beijing，tianjin，shanghai 通过以上论述我们可以计算得到新的cij，利用lingo算出结果：2 改进后的方案
我们都知道，在一个水资源系统中管道运河的架设维护费用占到了很大的比重。

因此必须考虑管道的架设费用。

我们的模型必须达到以下几个条件：（1）管道运河的架设能够联通中国大陆。

（2）各省架设方案成本尽量低。

我们考虑用最小生成树算法，首先标出各省省会，两两相连，形成网，以省会间的距离为权，然后用prim算法构造最小生成树。

伪代码如下：
prim算法如下：
（i）p={v}，q=φ；
（ii）whilep～=v
找最小边pv，其中p∈p，v∈v-p
p=p+{v}
q=q+{pv}
end
后得结果如下：
参考文献：
[1]2013美国数学建模大赛b题.2013，2.
[2]中国统计年鉴.
作者单位：湖南师范大学，长沙 410012；东北大学秦皇岛分校，河北秦皇岛 066004。