最適化セミナーのご案内

2.7.2 最小カット問題

 最大流問題を,線形計画問題の一般形に定式化したことを利用して,その双対問題である,最小カット問題をSIMPLEで記述してみましょう.

 

 最大流問題の制約式$I\boldsymbol{x} = \boldsymbol{0}$$\boldsymbol{x} \le \boldsymbol{upper}$に対する双対変数を,それぞれ$\boldsymbol{y}$$\boldsymbol{z}$とします.

 また,最大流問題の目的関数$x_{flow}$は,

\begin{align*} & a_{flow} = 1, \\  & a_e = 0, e \ne flow \end{align*}

であるようなベクトル$\boldsymbol{a}$を用いて$\boldsymbol{a} \cdot \boldsymbol{x}$と表すことができます.

 よって最小カット問題は,

\[\begin{array}{@{}ll@{}} \min & \boldsymbol{upper} \cdot \boldsymbol{z}(= \boldsymbol{0} \cdot \boldsymbol{y} + \boldsymbol{upper} \cdot \boldsymbol{z}) \\ {\rm s.t} & I^{\rm T} \boldsymbol{y} + \boldsymbol{z} \ge \boldsymbol{a}, \\ & \boldsymbol{z} \ge 0.\end{array}\]

のように記述することができます.

 

 定式化については,次のようになります.

集合
$City = \{ A,B,C,D,X,Y \}$ 都市の集合
$Edge = \{ e1,e2,e3,e4,e5,e6,e7,flow\}$ 辺の集合
 
変数
$y_v, v \in City$  
$z_e, e \in Edge$  
 
定数
$I(v,e), v \in City, e \in Edge$ 接続行列
$upper_e, e \in Edge$ 各辺の輸送量の上限
$a_e = 0(e \ne flow), a_{flow} = 1$  
 
目的関数(最小化)
$\boldsymbol{upper} \cdot \boldsymbol{z}$ カット総量
 
制約条件
$I^{\rm T} \boldsymbol{y} + \boldsymbol{z} \ge \boldsymbol{a}$ 双対制約式
$\boldsymbol{z} \ge 0$ 不等号制約式に対する双対変数は0以上

 これより,SIMPLEの記述は次のようになります.

Set City, Edge;
Element v(set=City), e(set=Edge);

Matrix I((v,e));
Vector Upper(e);

Variable yvar(index=v), zvar(index=(e));
Vector y(v), z(e);
y[v] = yvar[v]; // ベクトル y に変数 yvar を詰め込む
z[e] = zvar[e]; // ベクトル z に変数 zvar を詰め込む

Objective cut(name="カットの総量",type=minimize);
cut = inprod(Upper,z);

Vector a(e);
a = zeros(Edge);
a["flow"] = 1;

trans(I) * y + z >= a;
z >= zeros(Edge) ;

options.method="simplex";

solve();
cut.val.print();

 入力データは,最大流問題と同じです.

 このモデルファイルを実行すると,

カットの総量=10

という表示がされ,最大流問題と同じ目的関数の値を得ることができます.


 

 

上に戻る