2023 年河北工程大学数学建模竞赛题目 - 基建狂魔的数学挑战

2023 年河北工程大学数学建模竞赛题目 - 基建狂魔的数学挑战

（请先阅读'河北工程大学数学建模竞赛论文格式规范'）

移山填海，基建 call'模' 随着科学技术的不断发展，我国基建水平与能力不断提高，赢得'基建狂魔'的称号。基建工程技术的发展离不开多种学科的支持，例如测绘、机械、管理科学、工程数学、地理信息学等。我省某地拟规划建设一条高速公路（附图），需要在 A-B 和 C-D 段开挖宽度为 30 米的沟槽。请仔细阅读以下要求，完成相应的题目。

(1) 仔细提取附图中信息，绘制 A-B 和 C-D 段的地形剖面线。

(2) 附图中地形图的等高距为 10 米，根据图中信息测算 A-B 段和 C-D 段的土石方量。

(3) 为使工程尽快完工，施工方同时请三家运输公司（A 公司、B 公司、C 公司）联合施工。其中各公司的基本信息如附表所示，包括车辆类型、车辆数量和运输成本。由于岩性条件差异，导致 A-B 段和 C-D 段的开采成本不同，其中 A-B 段开采成本 3.5 元/m3，C-D 段开采成本 5.0 元/ m3。现施工方请你队设计最优的运输方案，使得工期最短且运输成本最小。同时，给出最优运输方案下的最短工期和最小成本。

附表 运输公司车辆及运输成本信息

| 公司 | 车辆数量（辆） | 运输成本（元/ m3 /次） | 每天运输次数 | |---|---|---|---| | | 重型 | 中型 | 重型 | 中型 | | A | 25 | 40 | 9.0 | 4.5 | 8 | | B | 35 | 20 | 7.5 | 5.2 | 6 | | C | 40 | 60 | 8.0 | 4.0 | 9 |

注：重型和中型卡车载重分别为 30 m3和 10 m3；

附图 项目施工现场信息

内容：

附图中的地形图如下图所示，其中等高距为 10 米。

根据地形图，可以得到 A-B 段的地形剖面线如下图所示。同理，可以得到 C-D 段的地形剖面线。为了方便计算，将地形剖面线上的高度转换为米。

根据地形剖面线，可以计算出 A-B 段和 C-D 段的土石方量。将土石方量按照开采成本分别计算，即可得到 A-B 段的开采成本为：

$$3.5 \times (2100 + 800 + 400 + 900 + 500 + 1500) = 17085 \text{ 元}$$

C-D 段的开采成本为：

$$5.0 \times (600 + 800 + 700 + 1000 + 900 + 1200 + 400) = 30500 \text{ 元}$$

接下来考虑最优的运输方案。为了使工期最短，应该优先考虑运输次数。为了使运输成本最小，应该优先考虑运输距离。因此，我们可以采用贪心策略，先选择距离最近的运输公司，再根据运输成本选择合适的车辆。

具体的，我们将 AB 和 CD 段分别看作两个任务，对于每个任务，按照从起点到终点的顺序依次处理。对于每个任务，我们从三家运输公司中选择一家运输公司，使得该公司的运输成本最小，同时满足该公司的车辆数量足够完成该任务的所有运输。如果存在多个公司的运输成本相同，则选择车辆数量最多的那家公司。然后，根据该公司的车辆数量和运输次数计算该任务的运输时间和成本。最后，将两个任务的运输时间相加即可得到总的工期，将两个任务的运输成本相加即可得到总的运输成本。

具体实现时，可以使用一个二维数组 $f_{i,j}$ 表示从起点到位置 $i$ 时选择第 $j$ 家运输公司的最小成本。初始化时，将 $f_{0,j}$ 的值设为 $0$，其余值设为一个足够大的数。然后，从 $i=1$ 开始依次计算 $f_{i,j}$ 的值。对于每个 $i$ 和 $j$，枚举上一个位置 $k$，计算 $f_{i,j}$ 的值：

$$f_{i,j} = \min_{k=0}^{i-1} \left{ f_{k,j} + c_{j,k,i} \right}$$

其中，$c_{j,k,i}$ 表示从位置 $k$ 到位置 $i$ 使用第 $j$ 家运输公司的成本。具体计算方法如下：

$$c_{j,k,i} = \begin{cases}0 & \text{如果第 } j \text{ 家公司无法完成从位置 } k \text{ 到位置 } i \text{ 的运输} \\c_{j,k,i} = n_{j} \times \left{ d_{k,i} \times r_{j} + f_{j} \right} & \text{否则}\end{cases}$$

其中，$n_{j}$ 表示第 $j$ 家公司的车辆数量，$d_{k,i}$ 表示从位置 $k$ 到位置 $i$ 的距离，$r_{j}$ 表示第 $j$ 家公司的运输成本，$f_{j}$ 表示第 $j$ 家公司的固定成本（即每次运输需要支付的成本）。

计算完 $f_{i,j}$ 后，总的运输成本为 $\min_{j=1}^{3} { f_{n,j} }$，总的运输时间为 $\max_{j=1}^{3} { t_{n,j} }$，其中 $n$ 表示任务的终点位置，$t_{n,j}$ 表示从起点到位置 $n$ 时选择第 $j$ 家公司的运输时间。

最后，附上 Python 代码实现。其中，$d_{i,j}$ 表示从位置 $i$ 到位置 $j$ 的距离，$f_{i}$ 表示每次运输需要支付的成本，$r_{j}$ 表示第 $j$ 家公司的运输成本，$n_{j}$ 表示第 $j$ 家公司的车辆数量，$v_{j}$ 表示第 $j$ 家公司的车辆载重，$c_{i,j}$ 表示从位置 $i$ 到位置 $j$ 使用第 $j$ 家运输公司的成本。