0

私の問題は次のとおりであり、そのルーツはガスネットワークのモデリングにあります。

ガス ネットワークをグラフ (E, V) としてモデル化します。ソースは主要なガス生産国であり、シンクはガス消費国であり、両方とも V 頂点セットに属します。最大制約はすべてのエッジに設定され、ネットワークの技術的能力を表します。「非現実的」すぎるソリューションを回避するために、最小制約がエッジのサブセットに設定されます。コストはデフォルトでは使用されません。

ここでの問題は次のように定式化できます。このネットワークの標準ネットワーク フロー問題の解空間で、特定のソースから特定のシンクへのフローを最大化する解を見つけます。このために、ガスを目的の宛先に「プッシュ」するために、エッジ コストを変更するか、新しいエッジ最小値を追加することができます。

どんな助けでも大歓迎です...

4

1 に答える 1

1

これは、複数商品フロー問題のバリエーションです。

これらの問題は、フローが整数である必要がある場合に特に解決が困難です。つまり、1 つのソースs_dから 1 つのデマンドへのフローを からへt_dの複数のパスに「分割」することはできません。s_dt_d

これがあなたの問題の場合だと思います。つまり、1 つのソースから 1 つの宛先への複数のパスを介して gaz を送信できますが、これは「合理的」と思われます。

このトピックに関する広範な文献があり、主に整数バージョンまたは問題の非常に大きなインスタンス (通信ネットワークや輸送の問題で発生する) の解決に焦点を当てています。問題が小さい場合は、単純な線形ソルバーで十分です。

ネットワーク グラフは(E,V)、質問のように示されます。有向頂点を想定しています。

それぞれが source 、 destination 、 valueである一連Dの要求を考えます。この値を最大化する特定の需要を除いて、値は定数です。させて：d in Ds_dt_dV_dV_dd0

  • 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 に答える