数理最適化セミナーのご案内

2.14 二次割当問題

　二次割当問題とは，1957年KoopmansとBeckmannにより考案された，目的関数が二次式となる割当問題です．

例題

　工場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})_{1 \leq i,j \leq n}$，地区間の距離行列を$D=(d_{kl})_{1 \leq k,l \leq n}$とすると，二次割当問題は以下の整数計画問題に定式化されます．

集合
$Fac$ 工場の集合
$Loc$ 地区の集合
　
定数
$f_{ij}, i, j \in Fac$ 各工場間のフロー
$d_{kl}, k, l \in Loc$ 各地区間の距離
　
変数
$x_{ik}, i \in Fac, k \in Loc$ 工場$i$を地区$k$に配置する場合1それ以外は0
　
目的関数（最小化）
$\sum_{i, j, k, l} f_{ij} d_{kl} x_{ik}x_{jl}$ 輸送コストの総和
　
制約条件
$\displaystyle \sum_{i} x_{ik} = 1, k = 1, 2, \ldots, n$ 各地区に割り当てられる工場は一つ
$\displaystyle \sum_k x_{ik} = 1, i = 1, 2, \ldots, n$ 各工場に割り当てる地区は一つ

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

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

// パラメータ
Parameter f(index=(i,j));
Parameter d(index=(k,l));

// 変数
IntegerVariable x(index = (i, k), type = binary);

// 目的関数
Objective total_cost(type = minimize);
total_cost = sum(f[i,j]*d[k,l]*x[i,k]*x[j,l],(i,j,k,l));

// 制約条件
sum(x[i,k], k) == 1;
sum(x[i,k], i) == 1;

// 求解
options.method = "wcsp";
options.maxtim = 10;
solve();

// 結果出力
simple_printf("工場 %d を地区 %s に配置する\n", i, k, x[i,k].val == 1);

　以下が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.3 仕事割当問題
2.15 設備計画問題

 

 

上に戻る