消防站选址问题（数学建模）
消防站选址问题（数学建模）
十二个地点中,选三个地点,每个点上还有权.要求,十二个点到这个三个点的加权距离最短.
距离矩阵
v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12
v1 0 15 37 45 24 60 18 33 48 40 58 67
v2 15 0 22 40 38 52 33 48 42 55 61 61
v3 37 22 0 18 16 30 43 28 20 58 39 39
v4 45 40 18 0 34 12 61 46 24 62 43 34
v5 24 38 16 34 0 36 27 12 24 49 43 43
v6 60 52 30 12 36 0 57 42 12 50 31 22
v7 18 33 43 61 27 57 0 15 45 22 40 61
v8 33 48 28 46 12 42 15 0 30 37 25 46
v9 48 42 20 24 24 12 45 30 0 38 19 19
v10 40 55 58 62 49 50 22 37 38 0 19 40
v11 58 61 39 43 43 31 40 25 19 19 0 21
v12 67 61 39 34 43 22 61 46 19 40 21 0
权
w1 15
w2 10
w3 12
w4 18
w5 5
w6 24
w7 11
w8 16
w9 13
w10 22
w11 19
w12 20
对于选三个点,我想应该是,选每个点到这三个点的距离选最短的作为该点距离,再乘以权重,最后使加权的总距离最小.
上面的思路对不对,如果对的话,我能不能不用穷举的方法来解决这个问题?如果有,请不吝赐教,
你的思路是可行的.用lingo数学优化软件,建立的模型代码：
model:
sets:
PL/1..12/:w,T;!T为决策变量,T(i)=1表示i点选择;
DS(PL,PL):d;
endsets
data:
w=15 10 12 18 5 24 11 16 13 22 19 20;
d=0 15 37 45 24 60 18 33 48 40 58 67
15 0 22 40 38 52 33 48 42 55 61 61
37 22 0 18 16 30 43 28 20 58 39 39
45 40 18 0 34 12 61 46 24 62 43 34
24 38 16 34 0 36 27 12 24 49 43 43
60 52 30 12 36 0 57 42 12 50 31 22
18 33 43 61 27 57 0 15 45 22 40 61
33 48 28 46 12 42 15 0 30 37 25 46
48 42 20 24 24 12 45 30 0 38 19 19
40 55 58 62 49 50 22 37 38 0 19 40
58 61 39 43 43 31 40 25 19 19 0 21
67 61 39 34 43 22 61 46 19 40 21 0;
enddata
min=@sum(PL(i):w(i)*@sum(PL(j):w(j)*d(i,j)*T(i)));!我认为加权值应为w1*w2*d12;
@for(PL:@bin(T));
@sum(PL:T)=3;
end
运行结果是：
加权最短距离是162380；
选择的3个点是v3、v5、v9.您认为加权值应为w1*w2*d12，能不能具体解释一下？按你的意思加权距离应当如何理解，如果选择v1点，那么v1到v2的加权距离，是w1*d12吗？我认为这样不妥。我的想法是：如果选择v1点，那么v1到v2的加权距离是w2*d12，不知道为什么还要乘以一个w1？那程序需要改动一句话：min=@sum(PL(i):@sum(PL(j):w(j)*d(i,j)*T(i)));运行结果为：加权最短距离是16138；选择的3个点是v6、v9、v11。