最適化セミナーのご案内

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

 

 

上に戻る