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

20232023 高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛 B B 题参考答案题参考答案 注意：以下答案是命题人给出的，仅供参考。各评阅组应根据对题目的理注意：以下答案是命题人给出的，仅供参考。各评阅组应根据对题目的理解及学生的解答，自主地进行评阅。解及学生的解答，自主地进行评阅。问题：问题：钢铁工业是国家工业的基础之一，铁矿是钢铁工业的重要原料基地。许多现代化铁矿是露天开采的，它的生产重要是由电动铲车（以下简称电铲）装车、电动轮自卸卡车（以 下简称卡车）运送来完毕。提高这些大型设备的运用率是增长露天矿经济效益的首要任务。露天矿里有若干个爆破生成的石料堆，每堆称为一个铲位，每个铲位已预先根据铁含量将石料提成矿石和岩石。一般来说，平均铁含量不低于 25%的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲 位至多能安顿一台电铲，电铲的平均装车时间为 5 分钟。卸货地点（以下简称卸点）有卸矿石的矿石漏、2 个铁路倒装场（以下简称倒装场）和卸岩石的岩石漏、岩场等，每个卸点都有各自的产量规定。从保护国家资源的角度及 矿山的经济效益考虑，应当尽量把矿石按矿石卸点需要的铁含量（假设规定都为 29.5%1%，称为品位限制）搭配起来送到卸点，搭配的量在一个班次（8 小时）内满足 品位限制即可。从长远看，卸点可以移动，但一个班次内不变。卡车的平均卸车时间为 3 分钟。所用卡车载重量为 154 吨，平均时速 28kmh。卡车的耗油量很大，每个班次每台车消耗近 1 吨柴油。发动机点火时需要消耗相称多的电瓶能量，故一个班次中只在开始 工作时点火一次。卡车在等待时所花费的能量也是相称可观的，原则上在安排时不应发 生卡车等待的情况。电铲和卸点都不能同时为两辆及两辆以上卡车服务。卡车每次都是满载运送。每个铲位到每个卸点的道路都是专用的宽 60 m 的双向车道，不会出现堵车现象，每段道路的里程都是已知的。一个班次的生产计划应当包含以下内容：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运送多少次（由于随机因素影响，装卸时间与运送时间 都不精确，所以排时计划无效，只求出各条路线上的卡车数及安排即可）。一个合格的计划要在卡车不等待条件下满足产量和质量（品位）规定，而一个好的计划还应当考虑下面两条原则之一：1.总运量（吨公里）最小，同时出动最少的卡车，从而运送成本最小；2.运用现有车辆运送，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。请你就两条原则分别建立数学模型，并给出一个班次生产计划的快速算法。针对下面的实例，给出具体的生产计划、相应的总运量及岩石和矿石产量。某露天矿有铲位 10 个，卸点 5 个，现有铲车 7 台，卡车 20 辆。各卸点一个班次的 产量规定：矿石漏 1.2 万吨、倒装场1.3 万吨、倒装场1.3 万吨、岩石漏 1.9 万吨、岩场 1.3 万吨 问题分析：问题分析：本题目与典型的运送问题明显有以下不同：1 运送矿石与岩石两种物资；2 产量大于销量的不平衡运送；3 在品位约束下矿石要搭配运送；4 产地、销地均有单位时间的流量限制；5 运送车辆每次都是满载，154 吨/车次；6 铲位数多于铲车数意味着最优的选择不多于 7 个产地；7 最后求出各条路线上的派出车辆数及安排。运送问题相应着线性规划，以上第 1、2、3、4 条可通过变量设计、调整约束条件实现；第 5 条使其变为整数线性规划；第 6 条用线性模型实现的一种办法，是从120710C个整数规划中取最优的即得到最佳物流；对第 7 条由最佳物流算出各条路线上的最少派出车辆数（整数），再给出具体安排即完毕所有计算。对于这个实际问题，规定快速算法，计算含 50 个变量的整数规划比较困难。此外，这是一个二层规划，第二层是组合优化，假如求最优解计算量较大，现成的各种算法都无能为力。于是问题变为找一个寻求近优解的近似解法，例如可用启发式方法求解。调用 120 次整数规划可用三种方法避免：（1）先不考虑电铲数量约束运营整数线性规划，再对解中运量最少的几个铲位进行筛选；（2）在整数线性规划的铲车约束中调用sign函数来实现；（3）增长 10 个 01 变量来标志各个铲位是否有产量。这是一个多目的规划，第一问的目的有两层：第一层是总运量（吨公里）最小，第二层是出动卡车数最少，从而实现运送成本最小。第二问的目的有：岩石产量最大；矿石产量最大；运量最小，三者的重要性应按此序。合理的假设重要有：1.卡车在一个班次中不应发生等待或熄火后再启动的情况；2.在铲位或卸点处因两条路线（及以上）导致的冲突时，只要平均时间能完毕任务即可，不进行排时讨论；3.空载与重载的速度都是 28km/h，耗油相差却很大，因此总运量只考虑重载运量；4.卡车可提前退出系统。符号符号：xij 从 i 号铲位到 j 号卸点的石料运量 单位 吨；cij 从 i 号铲位到 j 号卸点的距离 公里；Tij 从 i 号铲位到 j 号卸点路线上运营一个周期平均所需时间 分；Aij 从 i 号铲位到 j 号卸点最多能同时运营的卡车数 辆；Bij 从 i 号铲位到 j 号卸点路线上一辆车最多可以运营的次数 次；pi i 号铲位的矿石铁含量。%p=(30,28,29,32,31,33,32,31,33,31)qj j 号卸点任务需求 吨 q=(1.2,1.3,1.3,1.9,1.3)*10000 cki i 号铲位的铁矿石储量 万吨 cyi i 号铲位的岩石储量 万吨 fi:描述第 i 号铲位是否使用的 0-1 开关变量，取 1 为使用；取 0 为关闭。模型建立、算法设计与模型求解：模型建立、算法设计与模型求解：问题一、求运送成本最小的生产计问题一、求运送成本最小的生产计划划 一以总运量最小为目的函数求解最佳物流-第一层规划（1）道路能力约束：一个电铲（卸点）不能同时为两辆卡车服务，一条路线上最多能同时运营的卡车数是有限制的。卡车从 i 号铲位到 j 号卸点运营一个周期平均所需时间为53/2平均速度距离到jiTij（分钟）。由于装车时间 5 分钟大于卸车时间 3 分钟，所以这条路线上在卡车不等待条件下最多能同时运营的卡车数为：5/ijijTA；其中最后开始发车的一辆卡车一个班次中在这条路线上最多可以运营的次数为（其他卡车也许比此数多1 次）ijijijTAB/)5)1(608(，这里5)1(ijA是开始装车时最后一辆车的延时时间。一个班次中这条固定路线上最多也许运营的总车次大约大约为：ijijijBAL，总吨数ijL154。（2）电铲能力约束：一台电铲不能同时为两辆卡车服务，所以一台电铲在一个班次中的最大也许产量为 860/5154（吨）。（3）卸点能力约束：卸点的最大吞吐量为每小时 60/3=20 车次，于是一个卸点在一个班次中的最大也许产量为 820154（吨）。（4）铲位储量约束：铲位的矿石和岩石产量都不能超过相应的储藏量。（5）产量任务约束：各卸点的产量不小于该卸点的任务规定。（6）铁含量约束：各矿石卸点的平均品位规定都在指定的范围内。（7）电铲数量约束：电铲数量约束无法用普通不等式表达，可以引入 10 个 01 变量来标志各个铲位是否有产量。（8）整数约束：当把问题作为整数规划模型时，流量 xij除以 154 为非负整数。（9）卡车数量约束：不超过 20 辆。得到的一种模型为 cxijijij10151min （0）s.t.5,1,10,1,154jiBAxijijij （1）10,1,1545/60851ifxijij （2）5,1,1 5 4208101jiijx （3）10,1,100001000043521icyxxckxxxiiiiiii （4）5,1,101jqxjiij （5）5,2,1,0)5.28(0)5.30(101101jpxpxiiijiiij （6）5,1,10,1,154154jixxijij.（7）7101iif （8）20154,jiijijBx （9）二对最佳物流的结果进行派车-第二层规划 这是组合优化中的一维背包模型，针对快速算法的规定，用启发式方法求近优解。先用最佳物流修正 Bij,拟定卡车一个班次中在这条路线上实际最多可以运营的次数。然 后在 以目的 为出 动总 卡车 数最少 的各 路线 派车 中，把 各路 线需 要的 卡车数)*154/(ijijijBxe 提成整数部分 ije和小数部分 ijijee，进而可以分派任务让 ije辆车在 i 到 j 路线上，每辆往返运送 Bij次。为了最后实现第二层规划的目的，只需联合解决所有的 ijijee 时把这些小数组合成最少的整数卡车数。所需总卡车数的下界显然是jiijeY,0。假如某种派车方案恰好派出 Y0辆车实现了所有的 xij，则其即为第二层目的意义下近优解的最优方案。但由于有联合派车而总公里数不一定最小,故不一定为全局意义下的最佳方案。出动卡车数最少，意味着出动的卡车运用率要最大。容易出现的一辆卡车为两个以上路线服务的联合派车，可分为两种情况：有共同铲位（或卸点）的联合派车（V 字形或更复杂）；不同铲位且不同卸点之间的联合派车（Z 字形或四边形或更复杂）。派车方案的空载路线应尽量安排在第一层规划的最佳物流路线内，即使有的超过也要保证超过的路程总和最小，这样才干实现重载路程最小且使卡车空载路程也最小。而情况的路线不会超过第一层规划的最佳物流路线。只有情况才会有一部分不在第一层规划的最佳物流路线内。问题：各路线都是小数的需车数，如何组合使总卡车数最少且假如出现情况时空载超过部分总和尽量小。假如存在情况，则整体考虑情况形路线需要的卡车数相加的和,先拟定和的整数部分的车数并对这些车分派任务（任务的形式为在哪条路线上运几趟，再在哪条路线上运几趟，等等）。之后已无情况了，再对各个小数进行组合相加试探，在所有动用卡车数最少的情况中，选择超过第一层最佳物流路线的总和最小的，即为最后派车方案，再对这些车分派任务。由于属情况的为多数，故后面的组合搜索比较简朴，经常只有一两个任务属情况。根据最后派车方案，回代计算出各车辆在各路线的运送次数。由于整数部分已分派完运送次数,小数乘以相应路线上的 Bij取整计算出小数部分相应的具体运送次数.进一步计算出实际总运量与矿石和岩石的产量。三、求解过程：（一）第一层规划 求解前面给出的整数规划模型可计算出最优值为总运量85628.62吨公里。最佳物流相相应的各个路线上的最佳运送车次：铲位 1 铲位 2 铲位 3 铲位 4 铲位 5 铲位 6 铲位 7 铲位 8 铲位 9 铲位 10 矿石漏 1313 5454 1111 倒装场 4242 4343 岩场 7070 1515 岩石漏 8181 4343 倒装场 1313 2 2 7070 （二）第二层规划 用品体流量计算卡车在各个路线上一个班次最多可以运营的次数：（即修正的 Bij）铲位 1 铲位 2 铲位 3 铲位 4 铲位 5 铲位 6 铲位 7 铲位 8 铲位 9 铲位 10 矿石漏 15 15 18 19 23 24 26 29 45 35 倒装场 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 倒装场 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 倒装场 1.077 1.162 岩场 1.892 0.326 岩石漏 1.841 1.229 倒装场 0.684 0.1 1.489 所有路线所需卡车数（实数）的和为 12.843。各路线上需要的整数卡车数为 7（这些卡车在一个班次内一直在固定路线上运送）：铲位 1 铲位 2 铲位 3 铲位 4 铲位 5 铲位 6 铲位 7 铲位 8 铲位 9 铲位 10 矿石漏 1 倒装场 1 1 岩场 1 岩石漏 1 1 倒装场 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 到倒装场和从铲位 2、3 到倒装场，铲位 2 到倒装场运 3车，铲位 4 到倒装场运 6 车，铲位 2 到倒装场运 13 车，铲位 3 到倒装场运 1 车。第 6 辆：从铲位 3 到倒装场、岩石漏和从铲位 10 到矿石漏、岩场、倒装场，铲位3 到岩石漏运 3 车，铲位 3 到倒装场运 1 车，铲位 10 到倒装场运 23 车，铲位 10 到岩场运 10 车，铲位 10 到矿石漏运 5 车。对这道题的数据来说，只有共卸点或共铲位情况，没出现型联合派车。铲位铲位 1 1、2 2、3 3、4 4、8 8、9 9、1010 处各放置一台电铲。处各放置一台电铲。一共使用一共使用 1313 辆卡车；总运辆卡车；总运量为量为 85628.6285628.62 吨吨公里；公里；岩石产量为岩石产量为 3218632186 吨；矿石产量为吨；矿石产量为 3819238192 吨。吨。问题二、问题二、运用现有车辆运送而获得最大的产量运用现有车辆运送而获得最大的产量 一.在卡车不等待条件下运用现有车辆资源运送，获得最大的产量（岩石产量优先，在产量相同的情况下，取总运量最小的解）卡车不发生等待，即每条路线的车不能过多，否则将增长空载耗油，同时减少设备运用率，所以不一定所有车都用。第二问的解法和第一问类似，也采用多目的二层规划算法，第一层用整数线性规划，第二层用求派出车辆数最小的启发式方法。下面是第二问解法与第一问的不同之处。（一）第一层目的函数的拟定 由 于 岩 石 产 量 优 先，第 一 层 规 划 计 算 前 先 做 目 的 函 数 取 岩 石 产 量 最 大（10143maxijijx）的试算，来判断岩石产量是否能达成上限492802154208。假如是，把岩石的总产量取最大值,即4928010143 ijijx加入到约束条件中，以矿石产量最大为目的；假如否，把岩石产量最大做为目的，求解最佳物流。为了求岩石（或矿石）产量最大的同时，保证总运量(吨公里)较小，还不影响轻重顺序，运量的加权系数很小。如 cxxxxijijijiiii 101511015210001.0)(max （10）或 cxxxijijijiii 10151101430001.0)(max （11）为目的函数。（二）第一层约束条件的拟定 以（10）或（11）为目的，（1）至（9）为约束求解。第一层规划采用结合线性规划来求解整数规划：（1）在现有条件下岩石产量能否达成上限 以岩石产量最大为目的函数试算整数线性规划，可得岩石卸点总产量达成了约束上限。下面用岩石产量达成上限为约束，矿石产量最大为目的函数求解最佳物流。（2）计算整数线性规划，以得到最大矿石产量及最佳物流 由于这个整数规划的复杂性，所以必须考虑快速算法。先求解去掉整数约束的相应的线性规划线性规划，目的值为341.2807 车次。由于求的是整数线性规划，矿石的最大产量（车次）必然应为一整数。由于线性规划的最优解是整数规划最优解的上界，逐个减一地依次求“矿石产量等于比 342 小的整数”加到约束条件中，目的为总运量最小的整数规划。第一个出现可行解的规划的最优解必为原整数规划的最优解，且总运量最小。由于等式约束导致可行域的减小，运算量已大幅度减少。把矿石卸点的最大产量为 341 车次作为约束条件加入到整数线性规划中，没有可行解。把矿石卸点的最大产量为 340 车次作为约束条件加入到整数线性规划中，得出的结果如下，即为所求。最佳物流相相应的各个路线上的最佳运送车次为：铲位 1 铲位 2 铲位 3 铲位 4 铲位 5 铲位 6 铲位 7 铲位 8 铲位 9 铲位 10 矿石漏 38 24 18 倒装场 16 54 22 68 岩场 12 74 74 岩石漏 80 28 32 20 倒装场 14 4 60 22 第二层规划仍用启发式算法：用实际流量，计算卡车在各个路线上一个班次最多可以运营的次数：铲位 1 铲位 2 铲位 3 铲位 4 铲位 5 铲位 6 铲位 7 铲位 8 铲位 9 铲位 10 矿石漏 15 16 18 19 23 24 26 29 44 36 倒装场 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 倒装场 18 19 20 22 27 24 42 31 36 47 根据最佳物流计算各路线上需要的卡车数：铲位 1 铲位 2 铲位 3 铲位 4 铲位 5 铲位 6 铲位 7 铲位 8 铲位 9 铲位 10 矿石漏 2 2.11111111 0 0.82768276 0 0.40914091 倒装场 0 0 55175517 1 1.38463846 0.75860.7586 1 1.83788378 岩场 0 0.46154615 2 2 1 1.64446444 岩石漏 1 1 81828182 0 0.93339333 0 0.91439143 0 0.66676667 倒装场 0 0.73687368 0 0.2 2 1 1.93559355 0 0.46814681 所有路线所需卡车数（实数）的和，为 19.66。各路线上需要的整数卡车数为 9（这些卡车在一个班次内一直在固定路线上运送）：铲位 1 铲位 2 铲位 3 铲位 4 铲位 5 铲位 6 铲位 7 铲位 8 铲位 9 铲位 10 矿石漏 2 2 倒装场 1 1 1 1 岩场 2 2 1 1 岩石漏 1 1 倒装场 1 1 各个路线上的联合派车的卡车数为 11，方案为：第 1 辆：从铲位 1 到倒装场、岩石漏，铲位 1 到倒装场运 5 车，到岩石漏运 36 车。第 2 辆：从铲位 2 到倒装场、岩石漏，铲位 2 到倒装场运 2 车，到岩石漏运 28 车。第 3 辆：从铲位 3 到倒装场、岩石漏，铲位 3 到倒装场运 2 车，到岩石漏运 32 车。第 4 辆:从铲位 4 到倒装场、岩石漏，铲位 4 到倒装场运 12 车，到岩石漏运 20 车。第 5 辆：从铲位 1、2、3 到倒装场，铲位 1 到倒装场运 11 车，铲位 2 到倒装场运 13 车，铲位 3 到倒装场运 8 车。第 6 辆：从铲位 3、4 到倒装场和铲位 3 到矿石漏，铲位 3 到倒装场运 12 车，铲位4 到倒装场运 19 车，铲位 3 到矿石漏运 1 车。第 7 辆：从铲位 2、3、8 到倒装场，铲位 2 到倒装场运 14 车，铲位 3 到倒装场运 4 车，铲位 8 到倒装场运 1 车。第 8 辆：从铲位 8、10 到倒装场，铲位 8 到倒装场运 28 车，铲位 10 到倒装场运4 车。第 9 辆：从铲位 10 到岩场、倒装场，铲位 10 到岩场运 27 车，铲位 10 到倒装场运18 车。第 10 辆：从铲位 8、10 到岩场和从铲位 8 到矿石漏，铲位 8 到岩场运 12 车，铲位 10到岩场运 2 车，铲位 8 到矿石漏运 14 车。第 11 辆：从铲位 3、8、9 到矿石漏，铲位 3 到矿石漏运 1 车，铲位 8 到矿石漏运 10车，铲位 9 到矿石漏运 18 车。铲位铲位 1 1、2 2、3 3、4 4、8 8、9 9、1010 处各放置一台电铲。处各放置一台电铲。一共使用一共使用 2020 辆卡车；总运辆卡车；总运量量为为142385.3吨吨公里；公里；岩石产量为岩石产量为 4928049280 吨；矿石产量为吨；矿石产量为 5236052360 吨。吨。附注：本题重要难点附注：本题重要难点 1各路线上安排的车辆数应有一个最大值限制。假如在一个路线上的车辆过多就会出现题意不允许发生的等待情况。假如这一点没想到，后面的结果很难对的。2从铲位 i 到卸点 j 的流量为 154 吨的整数倍。这题的核心问题之一是如何用近似算法求解 NPC 问题。整数规划的现有解法不是快速算法，无法保证在任何数据下都能在短时间内算完。对这题的数据而言，从竞赛的时间和软件上来说最优解是求不出来的，必须想办法巧妙地使用规划软件减少运营整数规划花费的时间。比如：求解相相应的线性规划，最优解取整，假如还可行作为整数规划的近优解，等等。3如何解决在 10 个铲位安排 7 台电铲的问题。4关于派车算法中的一些问题。派车问题本质为组合优化问题，学生需要想办法快速得到最优解或近优解。也许还要考虑卡车的初始位置和终止位置，特别是两种联合派车时。此外由于装车导致的延时也许导致后面的卡车运营的次数与前面的卡车不同。5多目的规划的解决方法；二层规划的解决方法。以上是解题过程中不好解决的难点问题，看答卷怎么解决的是评阅时的重点。评卷时不以上是解题过程中不好解决的难点问题，看答卷怎么解决的是评阅时的重点。评卷时不能只看数值结能只看数值结果，更重要的是模型和方法，尚有结果的可行性。果，更重要的是模型和方法，尚有结果的可行性。