2003高教社杯全国大学生数学建模竞赛及其参考答案整理

2003高教社杯全国大学生数学建模竞赛

参考答案补充说明（2003年10月4日）

全国组委会在京部分委员应邀参加了北京赛区的阅卷工作，现将有关阅卷工作情况通报给你们，供你们参考。各评阅组应根据对题目的理解及学生的解答，自主地进行评阅。

A题

A题阅卷专家组进行了评分标准的讨论，大家达成的评分标准的共识大体如下：（以百分制打分）

1•分数分布

TOC\o"1-5"\h\z

⑴摘要5分

⑵对附件1中的模型的评价15分

⑶学生自己建立的模型40分

⑷对经济影响的建模25分

⑸短文10分

⑹机动分（或印象分）5分

2•上述各项指标评分基本原则

⑴对附件1中的模型的评价

对附件1中的模型的评价只限于一般性的议论，评差；

对附件1中的模型的缺点（不足）论述得比较清楚，评中

把该模型实际上的假设说得比较清楚，评优。

⑵学生自己建立的模型

估计大体上有两类建模方法，即基于机理的（例如:SIR模型，差分模型等）和统计建模（包括：时间序列，马尔柯夫链，神经网络等）。

在建模的过程中应注意分阶段考虑（在阅卷时应充分强调这一点），比如：潜伏期，隔离期，疑似病例，预测功能等。

直接的单变量回归拟合，评差；时间序列（自回归）等，评优

⑶对经济影响的建模

SARS对经济影响的预测，数据拟合，评中；联系到SARS情况，评优以上仅是北京赛区阅卷中对A题评判标准的大致共识。同时，阅卷专家还强调，各位专家要在保证公平的基础上有自己的见解。

在评卷的过程中，希望各位专家能够注意有特色和创新亮点的论文。在碰到有关专业性强的问题时建议找组内有关方面专家讨论。组长要组织有关非共识（有争议）论文的讨论，以争取达到共识，不漏掉一份好论文。

B题

对电铲能力约束的理解：可以认为只要在8小时中能装上车就能完成生产，即每个铲位产量可以达到96车（亦即原参考答案中第2页上的约束（2）可以取到等号）。由于实际生产中各班次之间是连续的，可以认为这样假设有一定合理性。当然，如果论文中通过分析说明铲位不能满负荷生产（即每个铲位产量可能达不到96车），也是可以的。

对卸点能力约束也可类似理解。

2.原参考答案中第2页上对L=AxB,B=1<8x60-（A-1）x5）/T」的定义是一种比

jjjijijU

较“保守”的估计，如果论文中采用其他计算方式，只要合理，也是可以的。如定义

Bx60/T」以后，对问题二的结果影响较明显，总产量可以达到670车（其中岩

ijj

石产量仍为320车，矿石产量可以达到350车），最小总运量为146917.5吨公里,最佳物流相对应的各个路线上的最佳运输车次为（可能不唯一）：

铲位1

铲位2

铲位3

铲位4

铲位5

铲位6

铲位7

铲位8

铲位9

铲位10

矿石漏

40

20

20

倒装场I

22

57

13

68

岩场

12

76

72

岩石漏

74

28

32

26

倒装场II

11

11

64

24

3.对第2问中目标函数可以有另外一种理解：首先使总产量最大；其次使岩石产量最大;

最后使总运量最小。这种理解下计算得到的结果，与原参考答案相同（如按照2中对

B的新定义，结果与2相同）。

j

原参考答案中第3页上提到“背包问题”，应改为“装箱问题”为佳。

问题1、问题2和其他（摘要、表达等）三部分的比重大致是6：3：1。

再次提醒：

评卷时不能只看数值结果，更重要的是模型和方法，以及论文的分析和表达。

2003高教社杯全国大学生数学建模竞赛

B题参考答案

注意：以下答案是命题人给出的，仅供参考。各评阅组应根据对题目的理解及学生的解答，自主地进行评阅。

问题分析：

本题目与典型的运输问题明显有以下不同：

运输矿石与岩石两种物资；

产量大于销量的不平衡运输；

在品位约束下矿石要搭配运输；

产地、销地均有单位时间的流量限制；

运输车辆每次都是满载，154吨/车次；

铲位数多于铲车数意味着最优的选择不多于7个产地；

最后求出各条路线上的派出车辆数及安排。

运输问题对应着线性规划，以上第1、2、3、4条可通过变量设计、调整约束条件实现;第5条使其变为整数线性规划；第6条用线性模型实现的一种办法，是从C7=120个整数规划中取最优的即得到最佳物流；对第7条由最佳物流算出各条路线上的最少派出车辆数（整数），再给出具体安排即完成全部计算。

对于这个实际问题，要求快速算法，计算含50个变量的整数规划比较困难。另外，这是一个二层规划，第二层是组合优化，如果求最优解计算量较大，现成的各种算法都无能为力。于是问题变为找一个寻求近优解的近似解法，例如可用启发式方法求解。

调用120次整数规划可用三种方法避免：（1）先不考虑电铲数量约束运行整数线性规划,再对解中运量最少的几个铲位进行筛选；（2）在整数线性规划的铲车约束中调用sign函数来实现；(3)增加10个0—1变量来标志各个铲位是否有产量。

这是一个多目标规划，第一问的目标有两层：第一层是总运量(吨公里)最小，第二层是出动卡车数最少，从而实现运输成本最小。第二问的目标有：岩石产量最大；矿石产量最大；运量最小，三者的重要性应按此序。

合理的假设主要有：

卡车在一个班次中不应发生等待或熄火后再启动的情况；

在铲位或卸点处因两条路线(及以上)造成的冲突时，只要平均时间能完成任务即可，不进行排时讨论；

空载与重载的速度都是28km/h，耗油相差却很大，因此总运量只考虑重载运量；

卡车可提前退出系统。

符号：x..~从i号铲位到j号卸点的石料运量单位吨；

cj〜从i号铲位到j号卸点的距离公里；

TOC\o"1-5"\h\z

T..〜从i号铲位到j号卸点路线上运行一个周期平均所需时间分；

A：〜从i号铲位到j号卸点最多能同时运行的卡车数辆；

B；〜从i号铲位到j号卸点路线上一辆车最多可以运行的次数次；

p.〜i号铲位的矿石铁含量。%丄I

p=(30,28,29,32,31,33,32,31,33,31)

q.~j号卸点任务需求吨

0=(1.2,1.3,1.3,1.9,1.3)*10000

ck.〜i号铲位的铁矿石储量万吨

I

cy.~i号铲位的岩石储量万吨

f：〜描述第i号铲位是否使用的0-1开关变量，取1为使用；取0为关闭。

模型建立、算法设计与模型求解：

问题一、求运输成本最小的生产计划

以总运量最小为目标函数求解最佳物流一第一层规划

道路能力约束：一个电铲(卸点)不能同时为两辆卡车服务，一条路线上最多能同时运行的卡车数是有限制的。卡车从i号铲位到j号卸点运行一个周期平均所需时间为I,.=i到j距离X2/平均速度+3+5(分钟)。由于装车时间5分钟大于卸车时间3分钟，所以这条路线上在卡车不等待条件下最多能同时运行的卡车数为：A=[r/5」；其中最后开

ijj

始发车的一辆卡车一个班次中在这条路线上最多可以运行的次数为(其他卡车可能比此数多

1次)B=[<8x60—(A-1)x5)/T」，这里(a..-1)X5是开始装车时最后一辆车的延时时间。jjjj

一个班次中这条固定路线上最多可能运行的总车次大约为：L=AxB，总吨数154xL..。

jjjj

电铲能力约束：一台电铲不能同时为两辆卡车服务，所以一台电铲在一个班次中的最大可能产量为8X60/5X154(吨)。

卸点能力约束：卸点的最大吞吐量为每小时60/3=20车次，于是一个卸点在一个班次中的最大可能产量为8X20X154(吨)。

铲位储量约束：铲位的矿石和岩石产量都不能超过相应的储藏量。

产量任务约束：各卸点的产量不小于该卸点的任务要求。

铁含量约束：各矿石卸点的平均品位要求都在指定的范围内。

电铲数量约束：电铲数量约束无法用普通不等式表达，可以引入10个0—1变量来标志各个铲位是否有产量。

整数约束：当把问题作为整数规划模型时，流量x..除以154为非负整数。

j

卡车数量约束：不超过20辆。

得到的一种模型为

min艺艺XxC

ijij

i=1j=1

s.t.x<154xAxB,i=1,…,10,j=1,…,5ijijij

工X<fx8x60/5x154,i=l,・..,10

iji

j=1

艺X<8x20x15,4j=1,...,5

i=1ij

X+X+X<ckx10000

i1i2i5j、,ii=1・・・10

X+X<cyx10000,1,,10

i3i4i

艺x>q,j=1,…,5

i=iijj

艺Xx(P—30.5)<0

.=iji

龙Xx(p—28.5)>0

i=1iji

X

——j

j=125

X

154-154,i=j'」0,j=1,.,5.

(0)

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

X

工-j<20(9)

154xB

i,jij

对最佳物流的结果进行派车——第二层规划

这是组合优化中的一维背包模型，针对快速算法的要求，用启发式方法求近优解。

先用最佳物流修正B,确定卡车一个班次中在这条路线上实际最多可以运行的次数。然后在以目标为出动总卡车数最少的各路线派车中，把各路线需要的卡车数e=x/（154*B）分成整数部分9」和小数部分e—Le」，进而可以分配任务让Le.」辆车

ijijijiJijijij

在i到j路线上,每辆往返运输Bq次。为了最后实现第二层规划的目标，只需联合处理所有的e—Le」时把这些小数组合'成最少的整数卡车数。所需总卡车数的下界显然是ijj

Y=Ze。如果某种派车方案恰好派出Y0辆车实现了所有的xi.，则其即为第二层目标意0ijj

义下近优解的最优方案。但由于有联合派车而总公里数不一定最小，故不一定为全局意义下的最佳方案。

出动卡车数最少，意味着出动的卡车利用率要最大。容易出现的一辆卡车为两个以上路线服务的联合派车，可分为两种情况：（1）有共同铲位（或卸点）的联合派车V字形或更复杂）；⑵不同铲位且不同卸点之间的联合派车（Z字形或四边形或更复杂）。派车方案的空载路线应尽量安排在第一层规划的最佳物流路线内，即使有的超出也要保证超出的路程总和最小，这样才能实现重载路程最小且使卡车空载路程也最小。而情况⑴的路线不会超出第一层规划的最佳物流路线。只有情况⑵才会有一部分不在第一层规划的最佳物流路线内。

问题：各路线都是小数的需车数，如何组合使总卡车数最少且如果出现情况⑵时空载超

出部分总和尽量小。

如果存在情况（1）,则整体考虑情况⑴形路线需要的卡车数相加的和，先确定和的整数部分的车数并对这些车分配任务（任务的形式为在哪条路线上运几趟，再在哪条路线上运几趟，等等）。之后已无情况⑴了，再对各个小数进行组合相加试探，在所有动用卡车数最少的情况中，选择超出第一层最佳物流路线的总和最小的，即为最后派车方案，再对这些车分配任务。由于属情况⑴的为多数，故后面的组合搜索比较简单，常常只有一两个任务属情况⑵。

根据最后派车方案，回代计算出各车辆在各路线的运输次数。由于整数部分已分配完运输次数，小数乘以对应路线上的B..取整计算出小数部分对应的具体运输次数.

j

进一步计算出实际总运量与矿石和岩石的产量。

三、求解过程：

（一）第一层规划

求解前面给出的整数规划模型可计算出最优值为总运量85628.62吨公里。

最佳物流相对应的各个路线上的最佳运输车次：

铲位1

铲位2

铲位3

铲位4

铲位5

铲位6

铲位7

铲位8

铲位9

铲位10

矿石漏

13

54

11

倒装场I

42

43

岩场

70

15

岩石漏

81

43

倒装场II

13

2

70

（二）第二层规划

用具体流量计算卡车在各个路线上一个班次最多可以运行的次数：（即修正的B.）

铲位1

铲位2

铲位3

铲位4

铲位5

铲位6

铲位7

铲位8

.

铲位9

铲位10

矿石漏

15

15

18

19

23

24

26

29

45

35

倒装场I

30

39

30

37

36

27

33

28

22

21

岩场

14

15

15

17

21

20

26

26

37

46

岩石漏

44

31

35

30

24

25

18

20

16

14

倒装场II

18

19

20

22

27

24

42

32

36

47

根据最佳物流，计算各路线上需要的卡车数（实数）：

铲位1

铲位2

铲位3

铲位4

铲位5

铲位6

铲位7

铲位8

铲位9

铲位10

矿石漏

0.867

1.862

0.314

倒装场I

1.077

1.162

岩场

1.892

0.326

岩石漏

1.841

1.229

倒装场II

0.684

0.1

1.489

所有路线所需卡车数（实数）的和为12.843。

各路线上需要的整数卡车数为7（这些卡车在一个班次内一直在固定路线上运输）：

铲位1

铲位2

铲位3

铲位4

铲位5

铲位6

铲位7

铲位8

铲位9

铲位10

矿石漏

1

倒装场I

1

1

岩场

1

岩石漏

1

1

倒装场II

1

各个路线上的联合派车的卡车数为6,方案为:

第1辆：从铲位1、3到岩石漏，铲位1到岩石漏运37车，铲位3到岩石漏运5车。

第2辆：从铲位9、10到岩场，铲位9到岩场运33车，铲位10到岩场运5车。

第3辆：从铲位8、10到矿石漏，铲位8到矿石漏运22车，铲位10到矿石漏运6车。

第4辆：从铲位2、8到矿石漏，铲位2到矿石漏运13车，铲位8到矿石漏运3车。

第5辆：从铲位2、4到倒装场I和从铲位2、3到倒装场II,铲位2到倒装场I运3车，铲位4到倒装场I运6车，铲位2到倒装场II运13车，铲位3到倒装场II运1车。

第6辆：从铲位3到倒装场II、岩石漏和从铲位10到矿石漏、岩场、倒装场II,铲位3到岩石漏运3车，铲位3到倒装场II运1车，铲位10到倒装场II运23车，铲位10到岩场运10车，铲位10到矿石漏运5车。

对这道题的数据来说，只有共卸点或共铲位情况，没出现⑵型联合派车。

铲位1、2、3、4、8、9、10处各放置一台电铲。

一共使用13辆卡车；总运量为85628.62吨公里；

岩石产量为32186吨；矿石产量为38192吨。

问题二、利用现有车辆运输而获得最大的产量

一.在卡车不等待条件下利用现有车辆资源运输，获得最大的产量（岩石产量优先，在产量相同的情况下，取总运量最小的解）

卡车不发生等待，即每条路线的车不能过多，否则将增加空载耗油，同时降低设备利用率，所以不一定全部车都用。

第二问的解法和第一问类似，也采用多目标二层规划算法，第一层用整数线性规划，第二层用求派出车辆数最小的启发式方法。下面是第二问解法与第一问的不同之处。

（一）第一层目标函数的确定

由于岩石产量优先，第一层规划计算前先做目标函数取岩石产量最大

（max工10工4X）的试算，来判断岩石产量是否能达到上限8X20X154X2=49280。

i二1j二3j

如果是，把岩石的总产量取最大值，即工10工4x二49280加入到约束条件中，以矿石产

i=1j=3ij

量最大为目标；如果否，把岩石产量最大做为目标，求解最佳物流。为了求岩石（或矿石）产量最大的同时，保证总运量（吨公里）较小，还不影响轻重顺序，运量的加权系数很小。如max£10（X+X+X）一0.0001工10工5XxC（10）

i=1i1i2i5i=1j=1ijij

或maxE10（X+X）一0.0001工10工5XxC（11）

i=1i3i4i=1j=1ijij

为目标函数。

（二）第一层约束条件的确定

以（10）或（11）为目标，（1）至（9）为约束求解。

第一层规划采用结合线性规划来求解整数规划：

（1）在现有条件下岩石产量能否达到上限

以岩石产量最大为目标函数试算整数线性规划，可得岩石卸点总产量达到了约束上限。下面用岩石产量达到上限为约束，矿石产量最大为目标函数求解最佳物流。

（2）计算整数线性规划，以得到最大矿石产量及最佳物流由于这个整数规划的复杂性，所以必须考虑快速算法。

先求解去掉整数约束的相应的线性规划，目标值为341.2807车次。由于求的是整数线性规划，矿石的最大产量（车次）必然应为一整数。因为线性规划的最优解是整数规划最优解的上界，逐个减一地依次求“矿石产量等于比342小的整数”加到约束条件中，目标为总

运量最小的整数规划。第一个出现可行解的规划的最优解必为原整数规划的最优解，且总运量最小。由于等式约束造成可行域的减小，运算量已大幅度减少。

把矿石卸点的最大产量为341车次作为约束条件加入到整数线性规划中，没有可行解。把矿石卸点的最大产量为340车次作为约束条件加入到整数线性规划中，得出的结果如

下，即为所求。

最佳物流相对应的各个路线上的最佳运输车次为:

铲位1

铲位2

铲位3

铲位4

铲位5

铲位6

铲位7

铲位8

铲位9

铲位10

矿石漏

38

24

18

倒装场I

16

54

22

68

岩场

12

74

74

岩石漏

80

28

32

20

倒装场II

14

4

60

22

第二层规划仍用启发式算法：

用实际流量，计算卡车在各个路线上一个班次最多可以运行的次数:

铲位1

铲位2

铲位3

铲位4

铲位5

铲位6

铲位7

铲位8

铲位9

铲位10

矿石漏

15

16

18

19

23

24

26

29

44

36

倒装场I

29

39

29

37

36

27

33

28

22

21

岩场

14

15

15

17

21

20

26

26

37

45

岩石漏

44

30

35

30

24

25

18

20

16

14

倒装场II

18

19

20

22

27

24

42

31

36

47

根据最佳物流计算各路线上需要的卡车数:

铲位1

铲位2

铲位3

铲位4

铲位5

铲位6

铲位7

铲位8

铲位9

铲位10

矿石漏

2.1111

0.8276

0.4091

倒装场I

0.55

17

1.3846

0.7586

1.8378

岩场

0.4615

2

1.6444

岩石漏

1.81

82

0.9333

0.9143

0.6667

倒装场II

0.7368

0.2

1.9355

0.4681

所有路线所需卡车数（实数）的和，为19.66。

各路线上需要的整数卡车数为9（这些卡车在一个班次内一直在固定路线上运输）：

铲位1

铲位2

铲位3

铲位4

铲位5

铲位6

铲位7

铲位8

铲位9

铲位10

矿石漏

2

倒装场I

1

1

岩场

2

1

岩石漏

1

倒装场II

1

各个路线上的联合派车的卡车数为11,方案为:

第1辆：从铲位1到倒装场I、岩石漏，铲位1到倒装场I运5车，到岩石漏运36车。第2辆：从铲位2到倒装场I、岩石漏，铲位2到倒装场I运2车，到岩石漏运28车。第3辆：从铲位3到倒装场I、岩石漏，铲位3到倒装场I运2车，到岩石漏运32车。第4辆:从铲位4到倒装场I、岩石漏，铲位4到倒装场I运12车，到岩石漏运20车。第5辆：从铲位1、2、3到倒装场I,铲位1到倒装场I运11车，铲位2到倒装场I运13车，铲位3到倒装场I运8车