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

1、2003年高等教育俱乐部杯全国大学生数学建模竞赛对问题B的参考答案注：以下答案由投标人提供，仅供参考。每个复习小组应该根据对题目的理解和学生的回答独立复习。问题：钢铁工业是国家工业的基础之一，铁矿石是钢铁工业的主要原料基地。许多现代铁矿都是露天开采的，其生产主要由电动叉车(以下简称电铲)和电动轮自卸车(以下简称以下简称卡车)。提高这些大型设备的利用率是提高露天矿经济效益的首要任务。露天矿有几个爆破产生的岩堆，每个岩堆称为一个铲位，每个铲位都预先按含铁量将岩石分为矿石和岩石。一般来说，铁的平均含量不低于25%，否则就是岩石。每把铲中矿石、岩石的数量和矿石的平均含铁量(称为品位)是已知的。每个铲位

2、最多可放置一把电铲，电铲的平均装载时间为5分钟。卸矿场(以下简称卸矿场)包括卸矿漏矿、两个铁路反转场(以下简称反转场)、卸矿漏岩、岩场等。每个卸载站点都有自己的输出要求。从保护国家资源和考虑矿山经济效益的角度出发，矿石应根据卸矿点要求的含铁量(假设要求均为29.5%1%，称为品位极限)，进行配矿并送至卸矿点，配矿量应在一个班次(8小时)内达到品位极限。从长远来看，卸载点可以移动，但在一个班次内保持不变。卡车的平均卸货时间是3分钟。所用的卡车载重量为154吨，平均速度为28公里小时。卡车消耗大量石油，每辆车每班消耗近一吨柴油。当发动机点火时，它需要消耗大量的电池能量，所以它在换档开始时只被点燃一

3、次。卡车在等待时消耗的能量也相当可观。原则上，卡车不应在安排期间等待。无论是铲还是卸载点都不能同时为两辆或多辆卡车服务。每次都有卡车装载。从每个铲到每个卸货点的道路是一条专用的双向车道，宽度为60米，因此不会有交通堵塞，并且每条道路的里程是已知的。一个班次的生产计划应包括以下内容：调度几台电铲，电铲在哪个位置；几辆卡车在哪个路线上被调度和运输多少次(由于随机因素的影响，装卸时间和运输时间不准确，所以调度计划无效，只能计算每条路线上卡车的数量和安排)。合格的计划应满足产量和质量(等级)的要求，无需等待卡车，好的计划还应考虑以下两个原则之一：1.总运输量(吨公里)最小，同时调度的卡车最少，因此运输

4、成本最小；2.使用现有车辆运输并获得最大产量(最好是岩石产量；在相同的输出条件下，取总流量最小的方案)。请为这两个原则建立数学模型，并给出轮班生产计划的快速算法。根据以下实例，给出了具体的生产计划、相应的总运输量和岩矿产量。一个露天矿有10个铲位和5个卸载点。有7辆叉车和20辆卡车。每个卸载点一个班次的产量要求：12000吨矿石泄漏、13000吨倒装一号料场、13000吨倒装二号料场、19000吨岩石泄漏和13000吨岩石料场问题分析：本主题与典型的运输问题明显不同，如下所示：1.矿石和岩石的运输；2.产量大于销售量的不平衡运输；3.矿石运输应结合品位限制；4.原产地和销售地有单位时间的流量限

5、制；5.运输车辆每次满载，154吨/列；6.铲子的数量多于叉车的数量，这意味着最好的选择不超过7个运输问题对应于线性规划，上述第1、2、3、4项可以通过变量设计和约束条件的调整来实现；第五条将其转化为整数线性规划；第六条用线性模型实现物流的一种方法是从一个整数规划中取其精华，得到最好的物流；对于第7条，从最佳物流出发，计算每条路线上派遣车辆的最小数量(整数)，然后给出完成所有计算的具体安排。对于这个实际问题，需要一个快速算法，并且很难计算50个变量的整数规划。另外，这是一个两级规划，第二级是组合优化。如果有大量的计算来寻找最优解，现有的算法是无能为力的。因此，问题变成了寻找一个近似的解决办法，

6、如启发式方法。有三种方法可以避免调用120次整数规划：(1)首先，在不考虑电铲数量约束的情况下运行整数线性规划，然后筛选出解中流量最小的几个铲位；(2)调用整数线性规划叉车约束中的函数；(3)添加10个0-1变量，以标记每个铲是否有输出。这是一个多目标规划。第一个问题的目标有两个层次：第一个层次是最小总运输量(吨公里)，第二个层次是最小派遣卡车数量，从而实现最小运输成本。第二个问题的目标是：最大岩石产量；矿石产量最大；交通量是最小的，三者的重要性应按此顺序排列。合理的假设主要包括：1.卡车在一个班次停止后不应等待或重新启动；2.当铲位或卸载点两条路线(或以上)发生冲突时，只要平均时间能够完成任

7、务，就不进行调度讨论；3.空载和重载的速度为28公里/小时，但耗油量相差很大，因此总交通量中只考虑重载交通量；4.卡车可以提前退出系统。符号：xij 从铲位1到卸料点j的石料运输单位吨；从铲位置1到卸载点j的距离：Tij 在从铲位置I到卸载点j的路线上运行一个周期所需的平均时间；从铲位置1到卸载点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长江一号铲的铁矿石储量为1万

8、吨cyi i铲位的岩石储量为1万吨Fi: 0-1开关变量，描述是否使用铲位1，使用1；取消0。建模、算法设计和模型求解；首先，寻找运输成本最小的生产计划1.以总体积最小为目标函数的一级规划(1)道路通行能力限制：一个铲(卸载点)不能同时为两辆卡车服务，并且在一条路线上可以同时行驶的卡车的最大数量是有限的。卡车从铲1到卸载点J运行一个周期所需的平均时间为(分钟)。由于装载时间比卸载时间长5分钟，所以无需等待卡车就可以在该路线上同时运行的卡车的最大数量为：其中，最后一辆卡车在一个班次内可以在该路线上运行的最大次数为(其他卡车可能比该数量多一次)，这里是最后一辆卡车装载时的延迟时间。在一个班次中，在

9、该固定路线上运行的列车的最大可能总数约为：总吨位。(2)电铲的能力约束：一台电铲不能同时为两辆卡车服务，因此一个班次一台电铲的最大可能产量为860/5154(吨)。(3)卸货点的能力约束：卸货点的最大吞吐量为每小时60/3=20趟，因此一个卸货点一个班次的最大可能产量为820，154吨。(4)铲储量约束：铲位矿岩产量不能超过相应储量。(5)输出任务约束：每个卸载点的输出不小于卸载点的任务要求。(6)铁含量约束：各卸矿点的平均品位在规定范围内。(7)电铲的数量约束：电铲的数量约束不能用普通不等式来表示，可以引入10个0-1变量来表示每一铲是否有输出。(8)整数约束：当问题被视为整数规划模型时，流

10、xij除以154是非负整数。(9)卡车数量限制：不超过20辆卡车。获得的模型之一是(0)s.t. (1)(2)(3)(4)(5)(6)。(7)(8)(9)2.调度车辆以获得最佳物流效果-二级规划这是组合优化中的一维背包模型。针对快速算法的要求，采用启发式方法寻找近似最优解。首先，Bij被修改为最佳物流，以确定卡车在一个班次中可以在该路线上运行的实际最大次数。然后将每条路线所需的卡车数量划分为整数部分和小数部分，然后分配任务，使每辆车在一至二号路线上运输Bij次。为了最终实现二级规划的目标，只需要将所有这些小数组组合成最小整数卡车数。所需卡车总数的下限显然是。如果一个汽车调度方案碰巧调度Y0辆汽

11、车来实现所有的xij，则它是第二级目标意义上的具有近似最优解的最优方案。然而，由于车辆的联合调度，总公里数不一定是最小的，因此它不一定是全局意义上的最佳方案。被派遣卡车数量最少意味着被派遣卡车的利用率最高。卡车很容易在两条以上的路线上联合调度车辆，这可以分为两种情况：(1)联合调度具有共同铲位(或卸载点)(V形或更复杂)的车辆；不同铲位和不同卸载点(之字形或四边形或更复杂)之间的车辆联合调度。调度方案的空载路线应尽可能安排在一楼规划的最佳物流路线上，即使超过部分也应尽量减少超出路线的总和，以实现最小重载路线和最小货车空载路线。情况(1)中的路线不会超过一楼规划的最佳物流路线。只有在第(2)种情

12、况下，零件才会不在一楼规划的最佳物流路线中。问题：每条路线都要求车辆的十进制数，如何组合以在情况(2)下最小化卡车的总数和最小化空载多余部件的总数。如果情况(1)存在，将路线(1)所需的卡车数量的总和视为一个整体，首先确定总和的整数部分中的车辆数量，并将任务分配给这些车辆(任务的形式是运输几次的路线，然后运输几次的路线，等等)。)。之后，没有情况(1)，然后小数被合并和测试。在所有使用的卡车数量最少的情况下，超过一楼最佳物流路线总和的是最终的汽车调度方案，然后这些汽车被分配任务。由于大多数属于案例(1)，随后的组合搜索相对简单，并且通常只有一个或两个任务属于案例(2)。根据最终调度方案，计算每

13、条路线上每辆车的运输次数。由于整数部分已经分配了运输时间，因此小数部分在相应的路线上乘以Bij，以舍入出与小数部分相对应的特定运输时间。进一步计算实际总运输量及矿石和岩石产量。第三，解决过程：(一)第一层规划通过求解上面给出的整数规划模型，最优值可以计算为总运输量85628.62吨/公里。与最佳物流相对应的每条路线上的最佳运输行程：铲位置1铲位置2铲位置3铲位置4铲位置5铲位置6铲位置7铲位置8铲位置9铲位置10矿石泄漏135411倒置场4243岩石场7015岩石渗漏8143倒置场13270(二)第二层规划计算卡车在特定流量下每条路线上一个班次可以行驶的最大次数：(即修正的Bij)铲位置1铲位

14、置2铲位置3铲位置4铲位置5铲位置6铲位置7铲位置8铲位置9铲2426294535倒置场30393037362733282221岩石场14151517212026263746岩石渗漏44313530242518201614倒置场18192022272442323647根据最佳物流，计算每条路线所需的卡车数量(实际数量):铲位置1铲位置2铲位置3铲位置4铲位置5铲位置6铲位置7铲位置8铲位置9铲位置10矿石泄漏0.8671.8620.314倒置场1.0771.162岩石场1.8920.326岩石渗漏1.8411.229倒置场0.6840.11.489所有路线所需的卡车总数(实数)为12.843辆

15、。每条路线所需卡车的整数数量为7辆(这些卡车在一个班次内在固定路线上运输):铲位置1铲位置2铲位置3铲位置4铲位置5铲位置6铲位置7铲位置8铲位置9铲位置10矿石泄漏1倒置场11岩石场1岩石渗漏11倒置场1每条路线上联合调度的卡车数量为6辆，方案如下：第一辆车：从铲位置1和3到岩石泄漏，37辆车从铲位置1到岩石泄漏，5辆车从铲位置3到岩石泄漏。第二辆车：33辆车从9号铲位和10号铲位运送到采石场，5辆车从9号铲位运送到采石场。第三辆车：从铲位8和10到漏矿，22辆车从铲位8到漏矿，6辆车从铲位10到漏矿。第四辆车：从铲位2和8到漏矿，13辆车从铲位2到漏矿，3辆车从铲位8到漏矿。第五辆车：3辆车从铲位2和4运送到倒装芯片场，3辆车从铲位2运送到倒装芯片场，6辆车从铲位4运送到倒装芯片场，13辆车从铲位2运送到倒