行建杯,数学建模.pdfVIP

一、问题重述 本题是根据供水网络的示意图以及限制条件求解最大流量和最小费用的。问题一是 单一水库和单一居民区，在一个水库和一个居民区之间又有2~9八个结点，代表泵站。 结点之间的连线上又有容量数据作为限制条件。水库的供水能力为35千立方/小时，居 民区的用水量为25千立方/小时，试求出这个网络上的一个最大流；问题二是一个多水 库多居民区的供水网络，其中结点用1到10标记，表示由水管网络连接起来的居民区， 水库，及泵站。两个水库的供水能力分别为35千立方/小时和26千立方/小时，三个居 民区的用水量分别为17、15和25千立方/小时，问题是求出这个网络上的一个最大流， 并将这个最大流和三个居民点的用水量进行比较，看能否满足居民的用水需求。问题三 是考虑运输成本的情况：由于输水管道的长短不一或地质等原因，使得每条管道上运行 费用也不相同，因此除考虑输水管道的最大流外，还需考虑输水管道的最大流的最小费 用。每条线路的容量及费用（单位：百元/千吨）都表示在示意图节点的连线上。让求 出这个网络上的一个最小费用的最大流。问题四是基于问题三的供水网络，提高水库 和水库二的供水能力到40和30吨，让求出三个居民区的用水量提高的情况及最小费用。 二、模型假设 1.假设水库供水量不受外界因素影响 2.假设各管道之间互不干扰 3.假设居民区用水量相对稳定 4.在该网络图中，有唯一的一个源点S （一个水库）有唯一的一个汇点T （一个居 民区）， 且S的流入量等于T处的流出量。 三、问题分析 设有向图 G = (V, E )中：有唯一的一个源点S （入度为0：出发点），有唯一的 一个汇点 T （出度为0：结束点），图中每条弧 (u,v) 都有一非负容量 c (u, v ) 对于问题 ，设连通网络网络的起点（水库）为S，网络的终点为T，在连通网络 G(S, T) 中有10个节点,19条弧, 弧 e 上的流量上界为 c , 求从起始节点 vs 到终点 vt ij ij 的最大流量的问题就是最大流问题。 对于问题二，可在多个水库的源点处在建立一个源点S，从而将S看作是一个大水 库，而将水库S看做是源点S的两个结点，同理建立等效终点T，将三个居民区也看作 是结点。如图1所示 1 图 1 这就转化为了问题一时的情形，解法同问题一。 对于问题三，设网络D=(V,A,U), 每条弧除了容量u 以外，还给出单位流量的费用 0 c(u,v)(简记为c ).这样，D就成为一个带费用的网络，记为D=(V,A,U,C), 其中,C称 i j ij C(X)  c x 为费用函数。设X为D上的一个可行流，称 ij ij 为X 的费用流。 (v ,v )A i j 最小费用最大流问题，即要求一个最大流X，使总运输费用最小。 即 minC(X)  cx ij ij (v ,v )A i j