数学实验 实践题目
巡山小妖精
667次浏览
2021年01月30日 01:01
最佳经验
本文由作者推荐
年度考核总结-七里香简谱
1
、
(
最短路问题
)
在纵横交错的公路网中，
货 车司机希望找到一条从一个城市到另一个城市
的最短路
.
下图表示的是公路网
,
节点表示货车可以停靠的城市
,
弧上的权表 示两个城市之
间的距离
(
百公里
).
那么
,
货车 从城市
S
出发到达城市
T,
如何选择行驶路线
,
使所经过的 路程
最短
?
S
A
1
5
6
6
A
2
8
3
6
7
3
A
3
4
B
1
6
7
8
B
2
9
C
1
5
T
C
2
6
分析：
此例中可把从
S
到
T
的行驶过程分成
4
个阶段,
即
S
→
A
i
(
i
=1,2
或
3), A
i
→
B
j
(
j
=1
或
2), B
j
→
C
k
(
k
=1
或
2), C
k
→
T.
记
d
(
Y,
X
)
为城市
Y
与城市
X
之间的直接距离(
若这两个城市
之间没有道路直接相连，
则可以认为直接距离为∞
)，
用
L
(X)
表示城市
S
到城市
X
的 最优行
驶路线的路长
:
1
L
S
0;
L
X
m
in
L
Y
Y
X
model
:
d
Y
,
X
,
X
S
.
2
SETS
:
CITIES
/S,A1,A2,A3,B1,B2,C1,C2,T/:
L;
!
属性
L
(i)
表示城市
S
到城市
i
的最优行驶路线
的路长
;
ROADS(CITIES, CITIES)/
!
派生集合
ROADS
表示的是网络中的道路（弧）
;
S,A1
S,A2
S,A3
!< br>由于并非所有城市间都有道路直接连接，
所以将弧具
体列出
;
A1,B1
A1,B2
A2,B1
A2,B2
A3,B1
A3,B2
B1,C1
B1,C2
B2,C1
B2,C2
C1,T
C2,T/: D;
!
属性
D( i, j)
是城市
i
到
j
的直接距离（已知）
;
ENDSETS
DATA
:
D =
6
3
3
6
5
8
6
7
4
6
7
8
9
5
6;
L= 0, , , , , , , ,
!
因为
L(S)=0;
ENDDATA
@FOR
( CITIES( i)|i#GT#
@index
(S):
!
这行中
可以直接写成
;
L( i) =
@MIN
( ROADS( j, i): L( j) + D( j, i)); );
!
这就是前面写出的最短路关系式
;
end
2
、建筑工地的位置
(
用平面坐标
a
,
b
表示，距离单位：公里
)
及水泥日用量
d
(
吨
)
下表给出。
2
、有两个临时料场位于
P (5,1), Q (2, 7),
日储量各有
20
吨。从
A, B
两料场分别向各工地运
送多少吨水泥，
使总的吨公里数最小。
两个新的料场应建在何处，
节省的吨公里数有 多大？
a
b
d
１
1.25
1.25
3
２
8.75
0.75
5
３
0.5
4.75
4
４
5.75
5
7
５
3
6.5
6
６
7.25
7.75
11
数学模型：
2
6
2
2
M
IN
f
c
ij
x
j
a
i
y
j
a
i
j
1
i
1
2
s.t.
c
ij
d
i
,
i
1,
2,
,
6
j
1
6
c
ij
e
j
,
j
1,
2
i
1
Lingo
模型
MODEL
:
Title
Location Problem;
sets
:
demand/1..6/:a,b,d;
supply/1..2/:x,y,e;
link(demand,supply):c;
endsets
data
:
1
2
3
!locations for the demand(
需求点的位置
);
a=1.25,8.75,0.5,5.75,3,7.25;
b=1.25,0.75,4.75,5,6.5,7.75;
!quantities of the demand and supply
（供需量）
;
d=3,5,4,7,6,11; e=20,20;
enddata
init
:
!initial locations for the supply
（初始点）
;
x,y=5,1,2,7;
endinit
!Objective function
（目标）
;
[OBJ]
min
=
@sum
(link(i,j):
c(i,j)*((x(j)-a(i))^2+(y(j)-b(i))^2)^(1/2) );
!demand constraints
（需求约束）
;
@for
(demand(i):[DEMAND_CON]
@sum
(supply(j):c(i,j)) =d(i););
!supply constraints
（供应约束）
;
@for
(supply(i):[SUPPLY_CON]
@sum
(demand(j):c(j,i)) <=e(i); );
@for
(supply:
@bnd
(0.5,X,8.75);
@bnd
(0.75,Y,7.75); );
END