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 |
物資の輸送コストを(フロー)×(距離)で与えるとき,最もコストがかからない配置を求めなさい.
この問題は,工場間のフロー行列を,地区間の距離行列を
とすると,
と表現されます.ここで,は
次の置換群(この問題では
)です.
ここで,置換に対し,次のような変数
を成分に持つ行列
を用いることで,(1)における
は
と表すことができます.
よって(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 に配置する
上に戻る