2023年高教社杯全国大学生数学建模竞赛B题竞赛参考答案

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

B题参考答案

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

生的解答，自主地进行评阅。

问题：

钢铁工业是国家工业的基础之一，铁矿是钢铁工业的重要原料基地。许多现代化铁矿是

露天开采的，它的生产重要是由电动铲车（以下简称电铲）装车、电动轮自卸卡车（以

下简称卡车）运送来完毕。提高这些大型设备的运用率是增长露天矿经济效益的首要任

务。

露天矿里有若干个爆破生成的石料堆，每堆称为一个铲位，每个铲位已预先根据铁含

量将石料提成矿石和岩石，一般来说，平均铁含量不低于25%的为矿石，否则为岩石。每个

铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多能

安顿一台电铲，电铲的平均装车时间为5分钟。卸货地点（以下简称卸点）有卸矿石的矿石

漏、2个铁路倒装场（以下简称倒装场）和卸岩石的岩石漏、岩场等，每个卸点都有各自的

产量规定。从保护国家资源的角度及矿山的经济效益考思，应当尽量把矿石按矿石卸点需要

的铁含量（假设规定都为29.5%1%,称为品位限制）搭配起来送到卸点，搭配的量在•个班

次（8小时）内满足品位限制即可。从长远看，卸点可以移动，但一个班次内不变。卡车的

平均卸车时间为3分钟。所用卡车载重量为154吨，平均时速28kmh。卡车的耗油量很大,

每个班次每台车消耗近1吨柴油。发动机点火时需要消耗相称多的电瓶能量，故一个班次中

只在开始工作时点火一次。卡车在等待时所花费的能量乜是相称可观的，原则上在安排时不

应发生卡车等待的情况。电铲和卸点都不能同时为两辆及两辆以上卡车服务。卡车每次都

是满载运送。

每个铲位到每个卸点的道路都是专用的宽60m的双向车道，不会出现堵车现象，每段

道路的里程都是已知的。一个班次的生产计划应当包含以下内容：出动几台电铲，分另！在哪

些俨位上；出动几辆卡车、分别在哪些路线上各运送多少次（由于随机因素影响，装卸时间

与运送时间都不精确，所以排时计划无效，只求出各条路线上的卡车数及安排即可）。一个

合格的计划要在卡车不等待条件下满足产量和质量（品位）规定，而一个好的计划还应当考

虑下面两条原则之一：

1.总运量（吨公里）最小，同时出动最少的卡车，从而运送成本最小；

2.运用现有车辆运送，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运

量最小的解）。

请你就两条原则分别建立数学模型，并给出•个班次生产计划的快速算法。针对下面的

实例，给出具体的生产计划、相应的总运量及岩石和矿石产量。

某露天矿有铲位10个，卸点5个，现有铲车7台，卡车20辆。各卸点一个班次的产量规定:

矿石漏1.2万吨、倒装场I1.3万吨、倒装场II1.3万吨、岩石漏1.9万吨、岩场1.3万吨

问题分析：

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

2.运送矿石与岩石两种物资；

3.产量大于销量的不平衡运送；

4.在品位约束下矿石要搭配运送；

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

6.运送车辆每次都是满载，154吨/车次；

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

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

运送问题相应着线性规划，以上第123.4条可通过变量设计、调整约束条件实现；第5

条使其变为整数线性规划：第6条用线性模型实现的一种办法，是从个整数规划中取最优

的即得到最佳物流；对第7条由最佳物流算出各条路线上的最少派出车辆数（整数），再给

出具体安排即完毕所有计算。

对于这个实际问题，规定快速算法，计算含50个变量的整数规划比较困难。此外，这是

••个二层规划，第二层是组合优化，假如求最优解计算量较大，现成的各种算法都无能为

力。于是问题变为找一个寻求近优解的近似解法，例如可用启发式方法求解。

调用120次整数规划可用三种方法避免：（I）先不考虑电铲数量约束运营整数线性规划,

再对解中运量最少的几个讲位进行筛选：（2）在整数线性规划的铲车约束中调用函数来实

现；（3）增长10个（）一1变量来标志各个铲位是否有产量。

这是一个多月的规划.第一问的目的有两层：第一层是总运量（吨公里）最小，第二层

是出动卡车数最少，从而实现运送成本最小。第二问的目的有：岩石产量最大；矿石产最最

大；运量最小，三者的重要性应按此序。

1.合理的假设重要有：

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

3.在铲位或卸点处因两条路线（及以上）导致的冲突时，只要平均时间能完毕任务即

可，不进行排时讨论；

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

5.卡车可提前退出系统。

符号：xij~从i号铲位到j号卸点的石料运量单位吨;

句~从，・号铲位到/号卸点的距离公里；

T.j-从/・号铲位到/号卸点路线上运营一个周期平均所需时间分；

从i号铲位到/号卸点最多能同时运营的卡车数辆；

Bii~从，•号铲位到/号卸点路线上一辆车最多可以运营的次数次；

Pi-i号铲位的矿石铁含量。%

p=（30,28,29,32,31,33,32,31,33,31）

./号卸点任务需求吨

q=（1.2,1.3,1.3,1.9,1.3）*10000

ch~i号铲位的铁矿石储量万吨

i号铲位的岩石储量万吨

及〜描述第i号铲位是否使用的0-1开关变量、取1为使用;取。为关闭。

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

问题一、求送送成本量小的生产计划

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

（1）道路能力约束：一个电铲（卸点）不能同时为两辆卡车服务，一条路线上最多能同

时运营的卡车数是有限制的。卡车从i号铲位到j号卸点运营一个周期平均所需时间为（分

钟）。由于装车时间5分钟大于卸车时间3分钟，所以这条路线上在卡车不等待条件下最多

能同时运营的卡车数为：；其中最后开始发车的一辆卡车一个班次中在这条路线上最多可

以运营的次数为（其他卡车也许比此数多1次），这旦是开始装车时最后一辆车的延时

时间。一个班次中这条固定路线上最多也许运营的总车次大约为：，总吨数。

（2）电铲能力约束：一台电铲不能同时为两辆卡车服务，所以一台电铲在一个班次中

的最大也许产量为8X60/5X154（吨）。

（3）卸点能力约束：卸点的最大吞吐量为每小时60/3=20车次，于是一个卸点在一个

班次中的最大也许产量为8X20X154（吨九

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

（5）产量任务约束：各卸点的产量不小于该卸点的任务规定。

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

（7）电铲数量约束：电铲数量约束无法用普通不等式表达，可以引入10个0—1

变量来标志各个铲位是否有产量。

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

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

得到的一种模型为

105

n面之Sx/G（°）

r=l

S・t・・・・・・・・（1）

次工产/.x8x60/5xl54,i=l,…,10⑵

j=l1

10/o、

<8x20x154,./=1,•••,5（3）

1=1

++x10000

XiX2X5^C^；1in⑷

X3+X/C）/°0°°

10

(5)

Zx产q,，j=i，…，5

1=1

1()

Z羽x(〃,-30.5)40

1=1(6)

10

ZM,X(〃—28.5)N°

r-l

……(7)

10

(8)

2于尸

£—^<20(9)

勺154x8“

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

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

先用最佳物流修正Bij,拟定卡车一个班次中在这条路线上实际最多可以运营的次数。

然后在以目的为出动总卡车数最少的各路线派车中，把各路线需要的卡车数提成整数部分

二和小数部分」进而可以分派任务让□辆车在i到j路线上，每辆往返运送Bij次。为了

最后实现第二层规划的目的，只需联合解决所有的［时把这些小数组合成最少的整数卡车

数。所需总卡车数的下界显然是口。假如某种派车方案恰好派出Y0辆车实现了所有的xij,

则其即为第二层目的意义下近优解的最优方案。但由于有联合派车而总公里数不一定最小，

故不一定为全局意义下的最佳方案。

出动卡车数最少，意味着出动的卡车运用率要最大。容易出现的一辆卡车为两个以上

路线服务的联合派车，可分为两种情况：⑴有共同铲位（或卸点）的联合派车（V字形或

更复杂）：⑵不同铲位且不同卸点之间的联合派车（Z字形或四边形或更复杂）。派车方案

的空载路线应尽量安排在第一层规划的最佳物流路线内，即使有的超过也要保证超过的路

程总和最小，这样才干实现重载路程最小且使卡车空载路程也最小。而情况⑴的路线不会

超过第一层规划的最佳物流路线。只有情况⑵才会有一部分不在第一层规划的最佳物流路线

内。

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

过部分总和尽量小。

假如存在情况（I）,则整体考虑情况⑴形路线需要的K车数相加的和，先拟定和的整数部

分的车数并对这些车分派任务（任务的形式为在哪条路线上运几趟，再在哪条路线上运儿

趟，等等）。之后已无情况⑴了，再对各个小数进行组合相加试探，在所有动用卡车数最

少的情况中，选择超过第一层最佳物流路线的总和最小的，即为最后派车方案，再对这些

车分派任务。由于属情况⑴的为多数，故后面的组合搜索比较简朴，经常只有一两个任务

属情况⑵。

根据最后派车方案，回代计算出各车辆在各路线的运送次数。由于整数部分已分派完运

送次数，小数乘以相应路线上的Bij取整计算出小数部分相应的具体运送次数.

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

（-）三、求解过程：

（二）第一层规划

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

最佳

铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10

物

流

相

相

应

的

各

个

路

线

上

的

最

佳

运

送

车

次

：

矿石漏135411

倒装场I4243

岩场7015

岩石漏8143

倒装场II13270

（二）第二层规划

用

品

铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10

体

流

量

计

算

卡

车

在

各

个

路

线

上

一

个

班

次

最

多

可

以

运

营"勺

S

次数h

f

•

c

•

H

p

{

u

修E

的

\

j

7

Bi

35

45

29

26

24

19

18

15

漏

矿石

23

15

I

倒装场

21

28

33

27

36

37

30

39

30

22

岩场

46

37

26

26

20

21

17

15

15

14

14

16

20

18

24

30

35

44

泯

界布

）、

31

场H

倒装

47

32

42

24

27

22

20

36

19

根据18

6

铲位

铲位8

铲位5

铲位4

1

铲位

10

铲位

9

铲位

铲位7

铲位3

最佳铲位2

加E

计算

各路

线上

需要

的卡

车数

<实

如：

4

0.31

7

0.86

2

1.86

温

矿石

2

1.16

7

1.07

I

倒装场

.326

20

1.89

岩场

岩石漏