最適化セミナーのご案内

2.7.1 Vector/Matrixを使用したSIMPLEモデル

　ここでは，Vector/Matrixクラスの記述を使ったモデルを紹介します．

　このモデルでは，グラフの接続行列を利用します．

　有向グラフ$G\left( {V,E} \right)$の接続行列とは，次のように定義されます．

定義　接続行列

　頂点集合$V = \{ v_1,\ldots,v_n\}$と有向辺集合$E = \{ e_1,\ldots,e_m\}$からなる有向グラフ$G(V,E)$に対して，

\[\begin{array}{@{}ll@{}} \mbox{頂点$v$が辺$e$の始点であるとき} & i_{ve} = 1, \\ \mbox{頂点$v$が辺$e$の終点であるとき} & i_{ve} = -1, \\ \mbox{それ以外は} & i_{ve} = 0\end{array}\]

となる$n \times m$行列$I(i_{ve})$を，有向グラフ$G(V,E)$の接続行列という．

　最大流問題では，ネットワークの終点から始点へ向かう辺$flow$を加えた次の図を考えます．辺$flow$の輸送量の上限は，他の辺の輸送量の上限の総和とします．

　図のグラフの接続行列を$I$，各辺の輸送量を成分とするベクトルを$\boldsymbol{x}$，各辺の輸送量の上限値を成分とするベクトルを$\boldsymbol{upper}$とおくと，

\[\begin{array}{@{}ll@{}} \max & x_{flow} \\ {\rm s.t} & I\boldsymbol{x} = \boldsymbol{0}, \\ & \boldsymbol{x} \le \boldsymbol{upper}, \\ & \boldsymbol{x} \ge 0 \end{array}\]

という線形計画問題に帰着できます．

　定式化については以下のように書き直します．

集合
$City = \{ A,B,C,D,X,Y \}$ 都市の集合
$Edge = \{e1,e2,e3,e4,e5,e6,e7,flow\}$ 辺の集合
　
変数
$x_e, e \in Edge$ 各辺の輸送量
　
定数
$I(v,e), v \in City, e \in Edge$ 接続行列
$upper_e, e \in Edge$ 各辺の輸送量の上限
　
目的関数（最大化）
$x_{flow}$ 総輸送量
　
制約条件
$I\boldsymbol{x} = \boldsymbol{0}$ 輸送量の保存則
$\boldsymbol{x} \le \boldsymbol{upper}$ 各輸送量の上限
$\boldsymbol{x} \ge 0$ 各輸送量の下限

　これにより，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
2.7 最大流問題
2.7.2 最小カット問題

 

 

上に戻る