0

我的问题如下，其根源在于气体网络的建模。

我们将天然气网络建模为图 (E,V)，其中源是主要的天然气生产国，汇是天然气消费国，两者都属于 V 顶点集。最大约束设置在所有边上，代表网络的技术能力。最小约束设置在边缘的子集上，以避免过于“不切实际”的解决方案。默认情况下不使用成本。

这里的问题可以表述为：在该网络的标准网络流量问题的解空间中找到使从特定源到特定汇的流量最大化的解。为此，我们可以改变边缘成本或添加新的边缘最小值，以便将气体“推”到所需的目的地。

任何帮助将不胜感激...

4

1 回答 1

1

这是多商品流动问题的变体。

当要求流量为整数时，这些问题尤其难以解决，即从一个源s_d到一个需求的流量t_d不能“拆分”为从s_d到的多条路径t_d。

我认为您的问题就是这种情况，即您可以通过多条路径将 gaz 从一个来源发送到一个目的地，这似乎是“合理的”。

关于该主题有大量文献，主要侧重于解决问题的整数版本或非常大的实例（出现在电信网络和运输问题中）；如果您的问题很小，一个简单的线性求解器就足够了。

网络图(E,V)在问题中表示；我假设有向顶点。

我考虑了一组D需求，每个需求都有d in D一个 source s_d，一个 destinationt_d和一个 value V_d。这些值是常数，除了您希望最大化该值V_d的特定需求。d0让：

  • c^{min}_e是边缘的最大容量e in E
  • c^{max}_e是具有这种容量的边e子集中的边上的最小容量E'

对于v中的节点V：

  • delta_{vd}如果是 1，如果是v = t_d-1 v = s_d，否则为 0
  • E^+_v是带头的边的集合v
  • E^-_v是带尾边的集合v

我为每个边缘e和每个需求引入了d一个变量，它表示通过边缘x_{ed}的流量。de

该问题可以写成以下形式的线性（连续）模型：

maximize V_{d0} on x and V_{d0}

subject to:

       // flow constraints
       forall v in V, d in D:
         sum_{e in E^+_v x_{ed} - sum_{e in E^-_v} x_{ed} = V_d delta_{vd}

       // max capacity constraints
       forall e in E:
         sum_{d in D} x_{ed} <= c^{max}_e

       //  min capacity constraints
       forall e in E':
         sum_{d in D} x_{ed} >= c^{min}_e

       //  bound constraints on the variable `x`
       forall d in D, forall e in E:
         0 <= x_{ed} <= V_d
于 2013-10-24T02:09:32.580 回答