实用文档
大全
《数学实验》实验报告
（ 2012 年 4 月 8 日）
一、实验问题
1．（指派问题）
考虑指定n个人完成n项任务（每人单独承担一项任务），使所需的总完成时间（成本）尽可能短. 已知某指派问题的有关数据（每人完成各任务所需的时间）如下表所示，试建模并求解该指派问题。
2．（二次指派问题）
某公司指派n个员工到n个城市工作（每个城市单独一人），希望使所花费的总费用尽可能少。n个员工两两之间每个月通话的时间表示在下面的矩阵的上三角部分（因为通话的时间矩阵是对称的，没有必要写出下三角部分），n个城市两两之间通话费率表示在下面的矩阵的下三角部分（同样道理，因为通话的费率矩阵是对称的，没有必要写出上三角部分）. 试求解该二次指派问题。
3、金星第四章课后习题第1或3题任选一题。
二、问题的分析（涉及的理论知识、数学建模与求解的方法等）
1)根据实际问题，建立数学优化模型
2)根据优化模型，利用LINGO 来求解模型。
实用文档
大全三、计算过程、结论和结果分析
1.模型：
ij
44
11
4
1
4
1
: 1,2,3,4
: 1234
1 i j
a
0 i j
x:i j
model min
1 j=1,2,3,4
..
1 i=1,2,3,4
ij
ij ij
i j
ij
i
ij
j
m
n
a x
a
s t
a
==
=
=
?
=?
?
?
=
?
?
?
?=
??
∑∑
∑
∑
工人
任务，，，
第个人完成第项任务
第个人不完成第项任务
第个工人完成第项任务所用的时间
model:
sets:
m/1..4/;
n/1..4/;
link(m,n):a,x;
endsets
min=sum(link(i,j):x(i,j)*a(i,j));
for(m(i):sum(n(j):a(i,j))=1);
for(n(j):sum(m(i):a(i,j))=1);
data:
x=15 18 21 24
19 23 22 18
26 18 16 19
19 21 23 17;
enddata
end
结果：Global optimal solution found.
Objective value: 70.00000 Infeasibilities: 0.000000
Total solver iterations: 7
Variable Value Reduced Cost
A( 1, 1) 0.000000 0.000000
A( 1, 2) 1.000000 0.000000
A( 1, 3) 0.000000 5.000000
A( 1, 4) 0.000000 10.00000
A( 2, 1) 1.000000 0.000000
实用文档
大全
A( 2, 2) 0.000000 1.000000
A( 2, 3) 0.000000 2.000000
A( 2, 4) 0.000000 0.000000
A( 3, 1) 0.000000 11.00000
A( 3, 2) 0.000000 0.000000
A( 3, 3) 1.000000 0.000000
A( 3, 4) 0.000000 5.000000
A( 4, 1) 0.000000 1.000000
A( 4, 2) 0.000000 0.000000
A( 4, 3) 0.000000 4.000000
A( 4, 4) 1.000000 0.000000
X( 1, 1) 15.00000 0.000000
X( 1, 2) 18.00000 0.000000
X( 1, 3) 21.00000 0.000000
X( 1, 4) 24.00000 0.000000
X( 2, 1) 19.00000 0.000000
X( 2, 2) 23.00000 0.000000
X( 2, 3) 22.00000 0.000000
X( 2, 4) 18.00000 0.000000
X( 3, 1) 26.00000 0.000000
X( 3, 2) 18.00000 0.000000
X( 3, 3) 16.00000 0.000000
X( 3, 4) 19.00000 0.000000
X( 4, 1) 19.00000 0.000000
X( 4, 2) 21.00000 0.000000
X( 4, 3) 23.00000 0.000000
X( 4, 4) 17.00000 0.000000
Row Slack or Surplus Dual Price
1 70.00000 -1.000000
2 0.000000 -14.00000
3 0.000000 -18.00000
4 0.000000 -14.00000
5 0.000000 -17.00000
6 0.000000 -1.000000
7 0.000000 -4.000000
8 0.000000 -2.000000
9 0.000000 0.000000
第1个人完成第2项，第2人完成第1项，第3人完成第3项，第4人完成第4项。最短时间为70.
2.模型：
实用文档
大全
ab
ai
bj
mn
ij
: 12345
ci : 12345
d:i j
c:a b
1 i a
x=
0 i a
i j a b
1 j b
x=
0 j b
1 m n
x=
0 m n
mod el min d*
ij
pe
?
?
?
≠≠?
?
?
?
?
?
员工，，，，
城市，，，，
第人与第人的通话时间
城市与城市的通话费率
人去城
人不去城
（，）人去城
人不去城
人去城
人不去城
：
5555
ab ai bj
i=1j=1i=1j=1
5
1
5
1
c*x*x
1 n=1,2,3,4,5
s.t.
1 m=1,2,3,4,5
mn
m
mn
n
x
x
=
=
?
=
??
?
?=
??
∑∑∑∑
∑
∑
（）
model:
sets:
pe/1,2,3,4,5/;
ci/1,2,3,4,5/;
lin(pe,ci):x;
lin1(pe,pe):d;
lin2(ci,ci):c;
endsets
min=sum(lin1(i,j):d(i,j)*sum(lin2(a,b):c(a,b)*x(a,i)*x(b,j)));
for(pe(m):sum(ci(n):x(m,n))=1);
for(ci(n):sum(pe(m):x(m,n))=1);
for(lin:bin(x));
data:
d=0 1 1 2 3
1 0
2 1 2
1 2 0 1 2
2 1 1 0 1
3 2 2 1 0;
c=0 5 2 4 1
5 0 3 0 2
2 3 0 0 0
实用文档
大全
4 0 0 0 5
1 2 0 5 0;
enddata
end
结果：Local optimal solution found.
Objective value: 50.00000
Objective bound: 50.00000 Infeasibilities: 0.000000
Extended solver steps: 18
Total solver iterations: 802
Variable Value Reduced Cost
X( 1, 1) 0.000000 14.00000
X( 1, 2) 0.000000 0.000000
X( 1, 3) 1.000000 5.999996
X( 1, 4) 0.000000 0.000000
X( 1, 5) 0.000000 6.000000
X( 2, 1) 0.000000 16.00000
X( 2, 2) 0.000000 9.999992
X( 2, 3) 0.000000 0.000000
X( 2, 4) 1.000000 1.999992
X( 2, 5) 0.000000 0.000000
X( 3, 1) 0.000000 14.00000
X( 3, 2) 0.000000 6.000000
X( 3, 3) 0.000000 0.8523365E-08
X( 3, 4) 0.000000 0.000000
X( 3, 5) 1.000000 0.000000
X( 4, 1) 1.000000 7.999996
X( 4, 2) 0.000000 0.000000
X( 4, 3) 0.000000 5.999996
X( 4, 4) 0.000000 6.000000
X( 4, 5) 0.000000 14.00000
X( 5, 1) 0.000000 0.000000
X( 5, 2) 1.000000 1.999981
X( 5, 3) 0.000000 0.000000
X( 5, 4) 0.000000 9.999981
X( 5, 5) 0.000000 15.99998
D( 1, 1) 0.000000 0.000000
D( 1, 2) 1.000000 0.000000
D( 1, 3) 1.000000 0.000000
D( 1, 4) 2.000000 0.000000
D( 1, 5) 3.000000 0.000000
D( 2, 1) 1.000000 0.000000
D( 2, 2) 0.000000 0.000000
D( 2, 3) 2.000000 0.000000
D( 2, 4) 1.000000 0.000000
D( 2, 5) 2.000000 0.000000
实用文档
大全D( 3, 1) 1.000000 0.000000 D( 3, 2) 2.000000 0.000000 D( 3, 3) 0.000000 0.000000 D( 3, 4) 1.000000 0.000000 D( 3, 5) 2.000000 0.000000 D( 4, 1) 2.000000 0.000000 D( 4, 2) 1.000000 0.000000 D( 4, 3) 1.000000 0.000000 D( 4, 4) 0.000000 0.000000 D( 4, 5) 1.000000 0.000000 D( 5, 1) 3.000000 0.000000 D( 5, 2) 2.000000 0.000000 D( 5, 3) 2.000000 0.000000 D( 5, 4) 1.000000 0.000000 D( 5, 5) 0.000000 0.000000 C( 1, 1) 0.000000 0.000000 C( 1, 2) 5.000000 0.000000 C( 1, 3) 2.000000 0.000000 C( 1, 4) 4.000000 0.000000 C( 1, 5) 1.000000 0.000000 C( 2, 1) 5.000000 0.000000 C( 2, 2) 0.000000 0.000000 C( 2, 3) 3.000000 0.000000 C( 2, 4) 0.000000 0.000000 C( 2, 5) 2.000000 0.000000 C( 3, 1) 2.000000 0.000000 C( 3, 2) 3.000000 0.000000 C( 3, 3) 0.000000 0.000000 C( 3, 4) 0.000000 0.000000 C( 3, 5) 0.000000 0.000000 C( 4, 1) 4.000000 0.000000 C( 4, 2) 0.000000 0.000000 C( 4, 3) 0.000000 0.000000 C( 4, 4) 0.000000 0.000000 C( 4, 5) 5.000000 0.000000 C( 5, 1) 1.000000 0.000000 C( 5, 2) 2.000000 0.000000 C( 5, 3) 0.000000 0.000000 C( 5, 4) 5.000000 0.000000 C( 5, 5) 0.000000 0.000000 Row Slack or Surplus Dual Price
1 50.00000 -1.000000
2 0.000000 -10.00000
3 0.000000 -6.000000
4 0.000000 8.000000
5 0.000000 0.000000