最適化セミナーのご案内

2.13.2 基礎的なマス埋め割当問題

 ここではまず,マス目を埋めるだけの問題を考えていきます.

例題

 4×4のマス目があります.このマスに石を置きたいのですが,全ての縦横に関して石の数が2つになるように配置します.さてどのように置けば良いでしょうか.

 この問題を定式化するためには,0-1変数を用いる必要があります.この問題の場合以下の図のように,各マスに対して0-1変数を対応させます.

  1 2 3 4
1 x11 x12 x13 X14
2 x21 x22 x23 X24
3 x31 x32 x33 X34
4 x41 x42 x43 X44

 

 定式化をすると以下のようになります.

0-1変数
$x_{11}$, $x_{12}$, $x_{13}$, $x_{14}$

$x_{21}$, $x_{22}$, $x_{23}$, $x_{24}$

$x_{31}$, $x_{32}$, $x_{33}$, $x_{34}$

$x_{41}$, $x_{42}$, $x_{43}$, $x_{44}$
それぞれのマスに石を置くならば1置かないならば0.
 
目的関数
  この問題には目的関数はない
 
制約条件
$x_{11} + x_{12} + x_{13} + x_{14} = 2$ 1行目を横に見たときに石を2つ置く
$x_{21} + x_{22} + x_{23} + x_{24} = 2$ 2行目を横に見たときに石を2つ置く
$x_{31} + x_{32} + x_{33} + x_{34} = 2$ 3行目を横に見たときに石を2つ置く
$x_{41} + x_{42} + x_{43} + x_{44} = 2$ 4行目を横に見たときに石を2つ置く
$x_{11} + x_{21} + x_{31} + x_{41} = 2$ 1列目を縦に見たときに石を2つ置く
$x_{12} + x_{22} + x_{32} + x_{42} = 2$ 2列目を縦に見たときに石を2つ置く
$x_{13} + x_{23} + x_{33} + x_{43} = 2$ 3列目を縦に見たときに石を2つ置く
$x_{14} + x_{24} + x_{34} + x_{44} = 2$ 4列目を縦に見たときに石を2つ置く

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

IntegerVariable x_11(type = binary);
IntegerVariable x_21(type = binary);
IntegerVariable x_31(type = binary);
IntegerVariable x_41(type = binary);

IntegerVariable x_12(type = binary);
IntegerVariable x_22(type = binary);
IntegerVariable x_32(type = binary);
IntegerVariable x_42(type = binary);

IntegerVariable x_13(type = binary);
IntegerVariable x_23(type = binary);
IntegerVariable x_33(type = binary);
IntegerVariable x_43(type = binary);

IntegerVariable x_14(type = binary);
IntegerVariable x_24(type = binary);
IntegerVariable x_34(type = binary);
IntegerVariable x_44(type = binary);

x_11 + x_12 + x_13 + x_14 == 2;
x_21 + x_22 + x_23 + x_24 == 2;
x_31 + x_32 + x_33 + x_34 == 2;
x_41 + x_42 + x_43 + x_44 == 2;

x_11 + x_21 + x_31 + x_41 == 2;
x_12 + x_22 + x_32 + x_42 == 2;
x_13 + x_23 + x_33 + x_43 == 2;
x_14 + x_24 + x_34 + x_44 == 2;

// 以下は出力用のプログラム
solve();
simple_printf("%d %d %d %d\n",x_11,x_12,x_13,x_14);
simple_printf("%d %d %d %d\n",x_21,x_22,x_23,x_24);
simple_printf("%d %d %d %d\n",x_31,x_32,x_33,x_34);
simple_printf("%d %d %d %d\n",x_41,x_42,x_43,x_44);

 このモデルをNumerical Optimizerで実行すると,最後に

0 1 0 1
0 0 1 1
1 1 0 0
1 0 1 0

という表示がされ,この例題の答えを確認できます.どの縦横にも二箇所ずつ石が置いてある(1と表示されている)のが分かります.

 さて,次にこの問題をSIMPLEの添字機能を用いてモデル化してみます.定式化は以下のように変更します.

集合
$I = \{ 1,2,3,4 \}$
$J = \{ 1,2,3,4 \}$
 
0-1変数
$x_{ij}, i \in I, j \in J$ マス$(i,j)$に石を置くならば$x_{ij} = 1$,置かないならば$x_{ij} = 0$とする.
 
目的関数
  この問題には目的関数はない
 
制約条件
$\displaystyle \sum_i x_{ij}  = 2, \forall j \in J$ 各列$j$は横に見たときに石を2つ置く
$\displaystyle \sum_j x_{ij}  = 2, \forall i \in I$ 各行$i$は縦に見たときに石を2つ置く

 添字を用いることにより,以下のように簡単にモデル記述することができます.

Set I = "1 2 3 4";
Set J = "1 2 3 4";
Element i(set = I);
Element j(set = J);
IntegerVariable x(type = binary,index = (i,j));
sum(x[i,j],i) == 2;
sum(x[i,j],j) == 2;

// 以下は出力用のプログラム
solve();
simple_printf("%d %d %d %d\n",
x[i,j],x[i,j+1],x[i,j+2],x[i,j+3],j == 1);

 

 

上に戻る