1、1灌溉问题模型的建立与分析AbjectTo reduce the cost of agricultural activities and build the Conservation-minded Society.In this article,we set up a mathematical model about irrigation in the agricultural activities and discuss how to channel so that all the field can be irrigated.Moreover,we can confirm the sche
2、mes that cost smallest in various of schemes.In the aspect of algorithms ,we make use of Minimal spanning tree here to obtain the way to connect all the fields in minimum wages.The essay,which based on two algorithms:Prim and Kruskal.We form the article in three parts:Firstly,abstract the farmer fie
3、ld into connected graph;Then,create the weight matrix;Lastly,we try to find the way to connect all the fields in minimum cost by Prim and Kruskal.Index TermsMinimal spanning tree, Prim , Kruskal摘要为了减少农民生产活动成本，创造节约型社会，我们对农业生产中的灌溉问题建立了数学模型，来讨论怎样开渠能使所有农田都能被灌溉，进一步将确定各种连接方式中最小成本的连接方案。从算法上来说，这是一个最小生成树问题，将
4、一个连通图形取最小连接方式连接成一体。对于这种问题，有两种算法：kruskal 算法和 prim算法。本文所描述的模型正是分别基于这两种算法所建立的，大致分为如下三个部分：首先，将灌溉问题的农田抽象成连通图的形式，并将连通方式输入。其次，将输入的矩阵转化为边权矩阵。最后，用 kruskal算法和 prim算法 找出最短路径1并输出连接方案。关键字：最小生成树 kruskal 算法 prim 算法一问题的概述中国是世界上最大的农业国之一，耕地面积 18.37亿亩，占世界现有耕地2面积的 7%左右。为了加快中国经济的发展，创造节约型社会，不仅仅要在工商业方向中寻找机会，同时也要着眼于农业生产中的问
5、题。在农业生产中，灌溉是很重要，也很复杂的一步。现在的灌溉技术大概有十几种之多，其中应用灌溉渠将水库的水引到农田中灌溉的方式还是应用的比较广泛的。对于这种方式，计算开凿灌溉渠的成本就是最重要的问题，如何开凿能使所有农田都能连成一体并且开凿费用最少。基于这一农业生产问题，本文提出以下的两种数学模型。题中已给出了一块农田的缩略图，如图 2.1，要求将图中的边（田埂）挖开，使所有农田可以连成一体。图 1.1本文根据以上问题进行了如下两点拓展：1.该模型变为带权的无向连通图模型，即挖开每条边所需的费用不同，要求在原题的基础上使开凿整个灌溉渠的费用最小。2.该模型变为带权的有向连通图模型，即从 A到 B
6、的路与从 B到 A是不同的，建造的成本也不相同，在此条件下，将原来的农田连接起来，并使建造成本最低。二.模型部分1基本假设进行如下假设：3 用灌溉渠将两农田连接上就能使农田被灌溉，灌溉渠不会损坏，堵塞。 连接一块农田的每条灌溉渠灌溉效果相同。 相邻的农田之间边权矩阵对应元素为 1，不相邻表示为 0。2模型建立及求解2.1模型一：基于 kruskal算法的灌溉问题模型。2.1.1模型思路首先将 n个顶点看成 n个孤立的连通分支（n 个孤立点）并将所有的边按权从小大排序。按照边权值递增顺序，如果加入边后存在圈则这条边不加，直到形成连通图。以下是具体实现说明：首先将上图 1.1的实物图抽象为连通图并
7、标号。接下来将用 kruskal算法求解上面连通图的最小生成树，即能将上面 12个节点连接在一起的连接方案。本模型中应用的 kruskal算法其实是贪心算法的一种，其主要的想法是：首先将连通图的连接方式与权重表示为一个边权矩阵，这里的边权矩阵为一个 0-1权值矩阵，元素 是从 到 开凿灌溉渠的权值jia,ij（其中 为 0） ；接下来在边权矩阵中从左上开始找元素为 1的坐标，并将),(ia该边的权值改为无穷大，即又生成了一个新的边权矩阵，在这个新的边权矩阵中再从左上开始寻找元素为 1的边，并重复上面的步骤。其中要说明的是不能循环连接，这样一定不是最优的连接方案。例如：若已经确定 1和 2连接,
8、2 和3连接，那么在接下来的边权矩阵中即使 的权为 1，也不应该选这条边。),3(a因为若是将这条边选中，那么 1,2,3将循环连接，造成资源浪费。在这个模型中用到一个计数矩阵来保证不循环链接，在后面的模型建立中将会说到。最后将通过 kruskal算法找到的结果输出，并画出图像，就可以求出最小成本。2.1.2 模型建立及求解首先将上图转化如图 2.1.14图 2.1.1接下来将如图 2.1.1中的连接方式以及权值用矩阵表示出来，表示时只需将直接相连的两个节点表示出来即可。矩阵第一列为起点，第二列表示终点，第三列表示权值。则可表示为如图 2.1.2图 2.1.2将上图输入的权值赋值给一新的零矩阵
9、 B，此时的 B就是前面所说的边权矩阵，下一步将矩阵中的 0全部改为无穷大，表示不能连接。接下来在上面的矩阵中找第一个权值为 1的元素，确定其坐标并将其改为无穷大，表示将横5纵坐标表示的节点相连接。然后在另一个计数向量中将的得到的两个节点的原有编号均赋值成其中的最小值，表示该两点已经相连城一棵树，并此时的编号为其节点的最小值。然后重复上述的步骤，直到将所有的节点都连成一棵树，此时的标志即是计数向量的数值均为 1，即其和为节点的个数。这是就表示找到了将所有农田连接起来的连接方案。根据上面的方法写出了 MATLAB程序（见附件 1） ，运行上面数据后可以得到结果，如图 2.1.3所示，其中 w变量
10、记录了最优方案开凿灌溉渠的数量，path变量记录了边权矩阵中权值为 1的坐标，即最优方案的连接方法。图 2.1.3则根据上面得到的结果画出的图形如图 2.1.4所示6图 2.1.42.1.3模型的现实应用2.1.3.1在现实生活中，开凿灌溉渠将会产生一定的费用，而且开凿不同的灌溉渠由于地理位置、地形特点、灌溉渠长度等因素将会导致费用有所不同，因此下面我们将修建费用这一条件引入模型，于是模型将变为求解在原有的农田模型中修建能将所有的农田连接起来的灌溉渠的最小费用。接下来，在原题中的边上随机分配修建所需费用，如图 2.1.5所示，模型思路大致不变，只是每条边的权值不同了，模型的边权矩阵由原来的 0
11、-1矩阵变为一个元素为修建费用的对称矩阵。图 2.1.5按照前面的输入方式将图 2.1.5的连接方式与权值输入，这时输入矩阵第三列就改为修建费用，如图 2.1.6所示7图 2.1.6对于输入数据的处理方式仍然与前面的方式相同，将权值输入并将矩阵中的 0元素全部改为无穷大，即可得到此时的边权矩阵。然后从左上开始找矩阵中的最小元素，记录其横纵坐标，用变量 w记录其大小并将边权矩阵中的该元素改为无穷大。同样的，按照上面所说的方式，应用一个计数矩阵防止其循环连接。最后即可得到最少修建费用的连接方案和最少连接费用 w。按照上面方式写出 MATLAB程序（见附件一） ，运行后，输出的结果为如图2.1.7所
12、示，其中 w变量记录了每次开凿灌溉渠所需费用，最后即可得到整个灌溉工程完成所需的最小费用；path 变量记录了边权矩阵中权值为 1的坐标，即最优方案的连接方式。8图 2.1.7根据上面输出的结果，我们可以画出如下连接图，如图 2.1.8图 2.1.82.1.3.2在现实生活中，由于农田的地势高低不同，开凿的灌溉渠只能从高处流向低处，而要让水流从低处流向高处就需要借助仪器，最终导致在同一条灌溉渠上不同方向的修建费用不同。在下面的模型中，将引入上述问题，并予以解决。将原题的连通图增加两个方向不同的修建费用，如图 4.1.9，其中红色线表示从低地势向高地势方向，绿色线表示从高地势向低地势方向，相应的
13、费用也用相同的颜色标出。9图 2.1.9将如图 2.1.9的连接方式以及修建费用前面的方式输入，这里的输入矩阵将变为四列，前两列仍然是起点与终点，第三列是从起点到终点的修建费用，第四列则是从终点到起点的修建费用，所以按照上面的图形来说，输入的矩阵为如下的矩阵。如图 2.1.10所示图 2.1.10按照上面的处理输入数据的方式将输入矩阵变为边权矩阵，这时的边权矩阵将不是一个对称矩阵。几点下来的处理方式同上面的处理方法相同，最后可以得到对于这种不同方向的修建费用不同的最优连接方案以及最小费用。运行附件一中的 MATLAB程序得到的结果如图 2.1.11所示10图 2.1.11根据图 2.1.11所示将得到最优方案的连接方法，如图 2.1.12图 2.1.122.2模型二：基于 prim算法的灌溉问题模型。2.2.1 模型思路首先将 n个顶点看成 n个孤立的连通分支（n 个孤立点） ，并随意选取一个点当做起点。从起点出发，加入与已知点相连的最小权值最小而且与以选取的点不构成圈的边，直到形成连通图。以下是具体实现说明：对图形的预处理与上面的模型相同，可以得到一个 0-1的边权矩阵，这里
