最適化セミナーのご案内

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 に配置する
2.13.4 施設配置問題
2.15 設備計画問題

 

 

上に戻る