已知
本题主要是要建立旧井可利用判断模型
首先是按照题目建立两点距离符合误差
ϵ
\epsilon
ϵ范围内的判断模型
若一个已知点
P
i
P_i
Pi
(
a
i
,
b
i
)
(a_i,b_i)
(ai,bi)距某个网格结点
X
i
(
x
i
,
y
i
)
X_i(x_i,y_i)
Xi(xi,yi)的距离不超过给定误差
ϵ
\epsilon
ϵ
{
∣
a
i
−
x
i
∣
≤
ϵ
∣
b
i
−
y
i
∣
≤
ϵ
{|ai−xi|≤ϵ|bi−yi|≤ϵ
{∣ai−xi∣≤ϵ∣bi−yi∣≤ϵ
或者
max ( ∣ a i − x i ∣ , ∣ b i − y i ∣ ) ≤ ϵ \max{(|a_i-x_i|,|b_i-y_i|)}\le \epsilon max(∣ai−xi∣,∣bi−yi∣)≤ϵ
其次是网格平移模型,因为要研究的是网格平行对井的位置变化
设网格向右平移
x
x
x个单位,向上平移
y
y
y个单位;一个已知点
P
i
P_i
Pi
(
a
i
,
b
i
)
(a_i,b_i)
(ai,bi)
;网格平移后新点位置
P
j
(
a
j
,
b
j
)
P_j(a_j,b_j)
Pj(aj,bj)
有
{
a
j
=
a
i
+
x
b
j
=
b
i
+
y
{aj=ai+xbj=bi+y
{aj=ai+xbj=bi+y
综合上述模型和要可利用的旧井数尽可能大可得模型:
{ a n s = max ∑ i ∈ N 1 ≤ i ≤ n f i max ( ∣ a i + x − x i ∣ , ∣ b i + y − y i ∣ ) f i ≤ ϵ {ans=max∑i∈N1≤i≤nfimax(|ai+x−xi|,|bi+y−yi|)fi≤ϵ {ans=max∑i∈N1≤i≤nfimax(∣ai+x−xi∣,∣bi+y−yi∣)fi≤ϵ
现在还剩下一个问题某个网格结点
X
i
(
x
i
,
y
i
)
X_i(x_i,y_i)
Xi(xi,yi)是哪个网格点
这里问题就可以变成一个已知点
P
j
P_j
Pj
(
a
j
,
b
j
)
(a_j,b_j)
(aj,bj)求距离其最近的网格点
X
j
(
x
j
,
y
j
)
X_j(x_j,y_j)
Xj(xj,yj)
将一个小格子划分为四个区域观察规律可得
{
x
j
=
⌊
a
j
+
0.5
⌋
y
j
=
⌊
b
j
+
0.5
⌋
{xj=⌊aj+0.5⌋yj=⌊bj+0.5⌋
{xj=⌊aj+0.5⌋yj=⌊bj+0.5⌋
将这个式子带入我们的模型中可得
{
a
n
s
=
max
∑
i
∈
N
1
≤
i
≤
n
f
i
max
(
∣
a
i
+
x
−
⌊
a
i
+
x
+
0.5
⌋
∣
,
∣
b
i
+
y
−
⌊
b
i
+
y
+
0.5
⌋
∣
)
f
i
≤
ϵ
{ans=max∑i∈N1≤i≤nfimax(|ai+x−⌊ai+x+0.5⌋|,|bi+y−⌊bi+y+0.5⌋|)fi≤ϵ
{ans=max∑i∈N1≤i≤nfimax(∣ai+x−⌊ai+x+0.5⌋∣,∣bi+y−⌊bi+y+0.5⌋∣)fi≤ϵ
按照问题一给的模型,进行调整
{
a
n
s
=
max
∑
i
∈
N
1
≤
i
≤
n
f
i
max
(
∣
x
i
+
x
−
⌊
x
i
+
x
+
0.5
⌋
∣
,
∣
y
i
+
y
−
⌊
y
i
+
y
+
0.5
⌋
∣
)
f
i
≤
0.05
{ans=max∑i∈N1≤i≤nfimax(|xi+x−⌊xi+x+0.5⌋|,|yi+y−⌊yi+y+0.5⌋|)fi≤0.05
{ans=max∑i∈N1≤i≤nfimax(∣xi+x−⌊xi+x+0.5⌋∣,∣yi+y−⌊yi+y+0.5⌋∣)fi≤0.05
LINGO求解
sets:
aa/1..12/:a,b,f;
endsets
data:
a=0.50,1.41,3.00,3.37,3.40,4.72,4.72,5.43,7.57,8.38,8.98,9.50;
b=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(aa(i):f(i));
@for(aa(i):@bin(f(i)));
@for(aa(i):@smax(@abs(a(i)+x1-@floor(a(i)+x1+0.5)),@abs(b(i)+y1-@floor(b(i)+y1+0.5)))*f(i)<=0.05);
x1<1;
y1<1;
or
{
a
n
s
=
max
∑
i
∈
N
1
≤
i
≤
n
f
i
∣
x
i
+
x
−
⌊
x
i
+
x
+
0.5
⌋
∣
f
i
≤
0.05
∣
y
i
+
y
−
⌊
y
i
+
y
+
0.5
⌋
∣
f
i
≤
0.05
{ans=max∑i∈N1≤i≤nfi|xi+x−⌊xi+x+0.5⌋|fi≤0.05|yi+y−⌊yi+y+0.5⌋|fi≤0.05
⎩
⎨
⎧ans=max∑i∈N1≤i≤nfi∣xi+x−⌊xi+x+0.5⌋∣fi≤0.05∣yi+y−⌊yi+y+0.5⌋∣fi≤0.05
sets:
aa/1..12/:a,b,f;
endsets
data:
a=0.50,1.41,3.00,3.37,3.40,4.72,4.72,5.43,7.57,8.38,8.98,9.50;
b=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(aa(i):f(i));
@for(aa(i):@bin(f(i)));
@for(aa(i):@abs(a(i)+x1-@floor(a(i)+x1+0.5))*f(i)<=0.05);
@for(aa(i):@abs(b(i)+y1-@floor(b(i)+y1+0.5))*f(i)<=0.05);
x1<1;
y1<1;
答案如下
Objective value: 4.000000
Objective bound: 4.000000
F( 1) 0.000000 -1.000000
F( 2) 1.000000 0.000000
F( 3) 0.000000 -1.000000
F( 4) 1.000000 -1.000000
F( 5) 1.000000 0.000000
F( 6) 0.000000 -1.000000
F( 7) 0.000000 -1.000000
F( 8) 0.000000 -1.000000
F( 9) 0.000000 -1.000000
F( 10) 1.000000 0.000000
F( 11) 0.000000 -1.000000
F( 12) 0.000000 -1.000000