問題設定

既存の12口の油井の座標が以下の通り与えられています：

• x座標: [0.50, 1.41, 3.00, 3.37, 3.40, 4.72, 4.72, 5.43, 7.57, 8.38, 8.98, 9.50]
• y座標: [2.00, 3.50, 1.50, 3.51, 5.50, 2.00, 6.24, 4.10, 2.01, 4.50, 3.41, 0.80]

平面にn個の既存油井P_i (a_i, b_i) (i=1,2,...,n)があるとします。新しい油井は正方形グリッドNのすべての格子点に配置されます。各グリッドの辺長は1単位とします。グリッドは平面上で自由に移動できます。既存の油井P_iがグリッド点X_jの距離が許容誤差ε以内であれば、P_iの位置に新たな油井を掘る必要はありません。

問題1

グリッドの横方向と縦方向は固定されており、2点間の距離は横方向の差（x座標差の絶対値）と縦方向の差（y座標差の絶対値）の大きい方で定義されます。平面上でグリッドNを平行移動させて、利用可能な既存油井数を最大化する数値計算方法を提案してください。

数学的モデルの構築

まず、既知の点P_i (a_i, b_i)がグリッド点X_j (x_j, y_j)から許容誤差ε以内にあるかどうかを判定するモデルを構築します：

max(|a_i - x_j|, |b_i - y_j|) ≤ ε

グリッドを右方向にx単位、上方向にy単位平行移動させた場合、既存の油井P_i (a_i, b_i)の新しい位置はP_j (a_j, b_j)となり、以下の関係が成り立ちます：

a_j = a_i + x, b_j = b_i + y

これらのモデルを組み合わせ、利用可能な既存油井数を最大化するモデルは以下のようになります：

ans = max ∑ f_i
制約条件: max(|a_i + x - x_j|, |b_i + y - y_j|) × f_i ≤ ε

ここで、グリッド点X_j (x_j, y_j)は、既存の油井P_j (a_j, b_j)から最も近いグリッド点です。グリッドの特性から、以下の式で計算できます：

x_j = floor(a_j + 0.5), y_j = floor(b_j + 0.5)

この式をモデルに代入すると：

ans = max ∑ f_i
制約条件: max(|a_i + x - floor(a_i + x + 0.5)|, |b_i + y - floor(b_i + y + 0.5)|) × f_i ≤ ε

数値解法

与えられた12口の油井の座標とε=0.05に対して、問題1のモデルを解きます。

LINGOを使用した最適化モデル：

sets:
    wells/1..12/:x_coord,y_coord,utilizable;
endsets

data:
    x_coord=0.50,1.41,3.00,3.37,3.40,4.72,4.72,5.43,7.57,8.38,8.98,9.50;
    y_coord=2.00,3.50,1.50,3.51,5.50,2.00,6.24,4.10,2.01,4.50,3.41,0.80;
enddata

max = @sum(wells(i):utilizable(i));
@for(wells(i):@bin(utilizable(i)));
@for(wells(i):@smax(@abs(x_coord(i)+shift_x-@floor(x_coord(i)+shift_x+0.5)),@abs(y_coord(i)+shift_y-@floor(y_coord(i)+shift_y+0.5)))*utilizable(i)<=0.05);
shift_x<1;
shift_y<1;

別のアプローチとして、x方向とy方向の制約を分離することもできます：

@for(wells(i):@abs(x_coord(i)+shift_x-@floor(x_coord(i)+shift_x+0.5))*utilizable(i)<=0.05);
@for(wells(i):@abs(y_coord(i)+shift_y-@floor(y_coord(i)+shift_y+0.5))*utilizable(i)<=0.05);

最適解

LINGOによる最適化の結果は以下の通りです：

• 目的関数値: 4.000000
• 目的関数の境界値: 4.000000

利用可能な油井の選択状況：

• 油井1: 利用不可
• 油井2: 利用可能
• 油井3: 利用不可
• 油井4: 利用可能
• 油井5: 利用可能
• 油井6: 利用不可
• 油井7: 利用不可
• 油井8: 利用不可
• 油井9: 利用不可
• 油井10: 利用可能
• 油井11: 利用不可
• 油井12: 利用不可

この結果から、グリッドを適切に平行移動させることで、12口の既存油井のうち4口を利用可能にすることができることがわかります。