最適化セミナーのご案内

2.14 二次割当問題

 二次割当問題とは,1957年KoopmansとBeckmannにより考案された,目的関数が二次式となる割当問題です.ここでは,V13より導入されたVector/Matrixクラスの表記を用いて,次の例題を考えてみます.

例題

 工場1,..,5を地区I,..,Vに配置することを考えます.ただし,各工場間での物資を輸送する量,頻度などのフロー量,および各地区間の距離が,以下のように与えられているとします.

各工場のフロー 各地域間の距離
  1 2 3 4 5   I II III IV V
1 0 15 12 8 7 I 0 4 7 6 10
2 15 0 14 2 4 II 4 0 2 5 4
3 12 14 0 6 6 III 7 2 0 8 7
4 8 2 6 0 11 IV 6 5 8 0 12
5 7 4 6 11 0 V 10 4 7 12 0

 

 物資の輸送コストを(フロー)×(距離)で与えるとき,最もコストがかからない配置を求めなさい.

 この問題は,工場間のフロー行列を$F(f_{ij})$,地区間の距離行列を$D(d_{kl})$とすると,

\begin{equation} \min_{\phi \in S_n} \sum_i \sum_j f_{ij} d_{\phi(i) \phi(j)}\end{equation}

と表現されます.ここで,$S_n$$n$次の置換群(この問題では$n = 5$)です.

 ここで,置換$\phi \in S_n$に対し,次のような変数$x_{ik}$

\[x_{ik} = \left\{ \begin{array}{ll@{}} 1 & {\rm if}\ \phi(i) = k \\ 0 & {\rm otherwise.} \end{array} \right.\]

を成分に持つ$n \times n$行列$X$を用いることで,(1)における$d_{\phi(i)\phi(j)}$

\[(d_{\phi(i)\phi(j)}) = (XDX^{\rm T})_{ij}\]

と表すことができます.

 よって(1)は,次のような整数計画問題に書き換えることができます.

\[\begin{array}{@{}ll@{}} \min & \displaystyle F \bullet (XDX)^T \left( = \sum_{i,j} f_{i,j} d_{\phi(i)\phi(j)} \right) \\ {\rm s.t.} & \displaystyle \sum_i x_{ik} = 1, k = 1,2,\ldots ,n, \\  & \displaystyle \sum_k x_{ik} = 1, i = 1,2,\ldots ,n,\\ & x_{ik} = \{0,1\}, i,k = 1,2,\ldots ,n.\end{array}\]

 以上より,定式化は次のようになります.

集合
$Fac$ 工場の集合
$Loc$ 地区の集合
 
定数
$F_{i}, i,j \in Fac$ 各工場間のフロー
$D_{mn}, m,n \in Loc$ 各地区間の距離
 
変数
$X_{im}, i \in Fac, m \in Loc$ 工場$i$を地区$m$に配置する場合1それ以外は0
 
目的関数(最小化)
$F \bullet (XDX^{\rm T})$ $\bullet$は要素ごとの積の和
 
制約条件
$Xe = e$

$X^{\rm T}e = e$
$e$は全成分1のベクトル

 定式化した結果をSIMPLEで記述すると以下のようになります.

// 集合と添字
Set Fac,Loc;
Element i(set=Fac),j(set=Fac),m(set=Loc),n(set=Loc);

// パラメータ
Matrix F((i,j)),D((m,n));

// 変数
IntegerVariable x(index=(i,m),type=binary);
Matrix X((i,m));
X[i,m] = x[i,m];// 変数を行列に詰める

// 目的関数
Objective total_cost(type=minimize);
total_cost = inprod(F,X*D*trans(X));

// 制約条件
X*ones(Loc) == ones(Fac);
trans(X)*ones(Fac)== ones(Loc);

options.method = "wcsp";
options.maxtim = 10;

solve();
simple_printf("工場 %d を地区 %s に配置する\n",i,m,X[i,m].val == 1);

 V12までのSIMPLEでは,この目的関数を

total_cost = sum(f[i,j]*d[k,l]*x[i,k]*x[j,l],(i,j,k,l));

と記述します.Vector/Matrixクラスにより,より簡潔に記述できることがわかります.

 以下がcsv形式の入力ファイルです.

F,1,2,3,4,5
1,0,15,12,8,7
2,15,0,14,2,4
3,12,14,0,6,6
4,8,2,6,0,11
5,7,4,6,11,0
D,I,II,III,IV,V
I,0,4,7,6,10
II,4,0,2,5,4
III,7,2,0,8,7
IV,6,5,8,0,12
V,10,4,7,12,0

 このモデルを実行すると次のような結果が得られます.

工場1を地区 II に配置する
工場2を地区 V に配置する
工場3を地区 III に配置する
工場4を地区 IV に配置する
工場5を地区 I に配置する

 

 

上に戻る