2.7.1 Vector/Matrixを使用したSIMPLEモデル
ここでは,Vector/Matrixクラスの記述を使ったモデルを紹介します.
このモデルでは,グラフの接続行列を利用します.
有向グラフの接続行列とは,次のように定義されます.
定義 接続行列
頂点集合と有向辺集合
からなる有向グラフ
に対して,
となる行列
を,有向グラフ
の接続行列という.
最大流問題では,ネットワークの終点から始点へ向かう辺を加えた次の図を考えます.辺
の輸送量の上限は,他の辺の輸送量の上限の総和とします.
図のグラフの接続行列を,各辺の輸送量を成分とするベクトルを
,各辺の輸送量の上限値を成分とするベクトルを
とおくと,
という線形計画問題に帰着できます.
定式化については以下のように書き直します.
集合 | |
都市の集合 | |
辺の集合 | |
変数 | |
各辺の輸送量 | |
定数 | |
接続行列 | |
各辺の輸送量の上限 | |
目的関数(最大化) | |
総輸送量 | |
制約条件 | |
輸送量の保存則 | |
各輸送量の上限 | |
各輸送量の下限 |
これにより,SIMPLEでの記述は次のようになります.
Set City, Edge; Element v(set=City), e(set=Edge); Matrix I((v,e)); Vector Upper(e); Variable xvar(index=e); Vector x(e); x[e] = xvar[e]; // ベクトル x に変数 xvar を詰め込む Objective total(type=maximize); total = xvar["flow"]; I * x == zeros(City); zeros(Edge) <= x; x <= Upper; options.method="simplex"; solve();
実行時のcsvファイルは以下の二つとなります.
I,e1,e2,e3,e4,e5,e6,e7,flow A,-1,0,1,0,0,0,0,0 B,0,-1,0,1,1,0,0,0 C,0,0,-1,-1,0,1,0,0 D,0,0,0,0,-1,0,1,0 X,1,1,0,0,0,0,0,-1 Y,0,0,0,0,0,-1,-1,1
e,Upper e1,4 e2,6 e3,5 e4,4 e5,3 e6,8 e7,5 flow,35
上に戻る