数学建模社区-数学中国

标题: 求助一个网络流相关的问题 [打印本页]

作者: dididada 时间: 2011-9-18 22:46
标题: 求助一个网络流相关的问题

一个代表军区的带权无向图G，V分两个集合，度=1的兵营顶点组成集合V1，其它的度>1的顶点代表关卡构成集合为V2，边集合E代表兵营之间的道路。对于G中的顶点E和边V，均带有权值。

现有若干个规模不等的兵团，需要放置在V1上的若干个兵营（顶点）内，但是每个兵营有食物和饮水两个量的限制，要求多个兵团若放置在一个兵营，则对需求的总和不能超过这两个限制。

同时，兵团和兵团之间会彼此运送一些物资f，因此要求打开G2内一些关卡，保证物资运送的通畅，但是每条道路（边）有容量限制c，需要保证对于每条道路，物资f运送总和不能超过c。

现在需要求解如何分布兵团得到G的子图G’ （其顶点由V1中的所有兵营顶点，以及V2中打开的关卡顶点组成），使得G'中所有兵团之间彼此是连通的，且对于每个兵营来说其食物和饮水两方面的限制不被超出，边的容量c不被f超出，并且 cost = （G‘中被打开的关卡的权值总和 + G'中所有边的权值总和）最小。

此问题是对传统的网络流问题的扩展，即考虑流（flow）的收发器的摆放位置对网络流问题的影响。传统的网络流问题主要考虑容量和费用这两个问题，并且每个顶点一般只存在独一无二的一个流收发器（一收一发），而没有考虑（多收多发）的多个流收发器的情况。所以，感觉有点困难，不能单纯地考虑为multi-commodity flow问题。

请教！

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)