8. gw_min_cost_flow.exe の使用法

【概要】

ネットワークにて、その系の流量を最大にし、且つ、コストを最小にする経路を求める

  1. gw_min_cost_flow_new.cpp は、gw_min_cost_flow.cpp を少し改善しました。

    修正前は、エッジの値の表示としては、flow の値だけでしたが、修正後は、各エッジの側に、次の2つの情報を表示するようにした。

           flow = 29 .... そのエッジを流れる流量
           cost = 75 .... そのエッジに対するコスト

    gw_min_cost_flow_new.exe を起動すると、25個 (5行5列) のノードを持ったグラフが自動的に生成されるので、メニューの "Graph-> Clear" を選ぶ。
      
       以下の手順で、9個のノードを持つグラフを作成する。
      
    1. 左下端の画面上で、クリックすると1つのノード「N0」が生成される。
    2. さらに、右方向に順に2個のノード N1, N2 を追加する
    3. 少し上方に、前と同様の手順で3個のノード N3, N4, N5 を追加する
    4. その上方に、前と同様の手順で3個のノード N6, N7, N8 を追加する



  2. 9個のノードの上下左右を接続する。

    ・ノード「N0」をクリックして、選択状態にする
    ・マウスポインタを移動して、ノード「N1」をクリックすると、エッジ (N0 --> N1) が生成される
    ・同様にして、N1 --> N2, N3 --> N4, N4 --> N5, N6 --> N7, N7 --> N8 を作成する
    ・次に、縦方向の6個のエッジを作成する
     N0 --> N3, N3 --> N6, N1 --> N4, N4 --> N7, N2 --> N5, N5 --> N8


  3. 上記の操作を完了すると、"9 nodes, 12 edges" のグラフが生成される。

    グラフの各エッジには2つの情報が表示されている。例えば、"N7 --> N8" は次のようです。

      ・"N7 --> N8":
         flow = 29 .... そのエッジを流れる流量
         cost = 75 .... そのエッジに対するコスト

      ・"N5 --> N8":
         flow = 23 .... そのエッジを流れる流量
         cost = 37 .... そのエッジに対するコスト

    N0」がスタート・ノード "" で、「N8」がターゲット・ノード "" です。
    ターゲット・ノード "" に流入する流量は2つのエッジから流入する flow の和となります。

          この系の最大流量 = 29 + 23 = 52
         この系の総コストは、各エッジの (flow * cost) の和です。



  4. 例えば、エッジ「N3 --> N6」のコストを 53 --> 29 に減少させてみます。

    すると、下図のように4つのエッジの流量が変化します。

         "N3 --> N4": flow= 12 --> flow= 0
         "N4 --> N7": flow= 29 --> flow= 17
         "N3 --> N6": flow= 0 --> flow= 12
         "N6 --> N7": flow= 0 --> flow= 12

    即ち、2つの経路で次のように流量が変化しました。

         経路:"N3 --> N4 --> N7" にて、flow= -12,
                削減されたコスト 12*33 + 12*33 = 792

         経路:"N3 --> N6 --> N7" にて、flow= +12
                増加されたコスト 12*36 + 12*29 = 780

    従って、上記の流量の変化によって 792 - 780 = 12 のコストが削減されました。