B题参考答案
2003高教社杯全国大学生数学建模竞赛
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． 产地、销地均有单位时间的流量限制；
第1页，共7页
B题参考答案
5． 运输车辆每次都是满载，154吨/车次； 6． 铲位数多于铲车数意味着最优的选择不多于7个产地； 7． 最后求出各条路线上的派出车辆数及安排。
运输问题对应着线性规划，以上第1、2、3、4条可通过变量设计、调整约束条件实现；
7第5条使其变为整数线性规划；第6条用线性模型实现的一种办法，是从C10?120个整数规划中取最优的即得到最佳物流；对第7条由最佳物流算出各条路线上的最少派出车辆数（整数），再给出具体安排即完成全部计算。
对于这个实际问题，要求快速算法，计算含50个变量的整数规划比较困难。另外，这是一个二层规划，第二层是组合优化，如果求最优解计算量较大，现成的各种算法都无能为力。于是问题变为找一个寻求近优解的近似解法，例如可用启发式方法求解。
调用120次整数规划可用三种方法避免：（1）先不考虑电铲数量约束运行整数线性规划，再对解中运量最少的几个铲位进行筛选；（2）在整数线性规划的铲车约束中调用sign函数来实现；（3）增加10个0－1变量来标志各个铲位是否有产量。
这是一个多目标规划，第一问的目标有两层：第一层是总运量（吨公里）最小，第二层是出动卡车数最少，从而实现运输成本最小。第二问的目标有：岩石产量最大；矿石产量最大；运量最小，三者的重要性应按此序。
合理的假设主要有：
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号卸点运行一个周期平均所需时间为Tij?i到j距离?2/平均速度＋3＋5（分钟）。由于装车时间5分钟大于卸车时间3分钟，所以这条路线上在卡车不等待条件下最多能同时运行的卡车数为：Aij??Tij/5?；其中最后开始发车的一辆卡车一个班次中在这条路线上最多可以运行的次数为（其他卡车可能比此数多1次）这里(Aij?1)?5是开始装车时最后一辆车的延时时间。Bij??(8?60－(Aij?1)?5)/Tij?，
第2页，共7页
B题参考答案
一个班次中这条固定路线上最多可能运行的总车次大约为：Lij?Aij?Bij，总吨数154?Lij。 （2）电铲能力约束：一台电铲不能同时为两辆卡车服务，所以一台电铲在一个班次中的最大可能产量为8×60/5×154（吨）。
（3）卸点能力约束：卸点的最大吞吐量为每小时60/3=20车次，于是一个卸点在一个班次中的最大可能产量为8×20×154（吨）。
（4）铲位储量约束：铲位的矿石和岩石产量都不能超过相应的储藏量。 （5）产量任务约束：各卸点的产量不小于该卸点的任务要求。 （6）铁含量约束：各矿石卸点的平均品位要求都在指定的范围内。
（7）电铲数量约束：电铲数量约束无法用普通不等式表达，可以引入10个0—1变量来标志各个铲位是否有产量。
（8）整数约束：当把问题作为整数规划模型时，流量xij除以154为非负整数。 （9）卡车数量约束：不超过20辆。 得到的一种模型为
min??x?ci?1j?1ijij105ij （0）
s.t.
x?154?A?Bijij,i?1,?,10,j?1,?,5 （1）
?xj?110i?15ij?fi?8?60/5?154,i?1,?,10 （2）
j?1,?,5 （3）
?xi1ij?8?20?154,
x?x?x?ck?10000,x?x?cy?10000i2i5ii3i4ii?1,?,10 （4）
?x?qi?1ij10j,j?1,?,5 （5）
??(?30.5)?0p?xij?i? （6） i?1?,j?1,2,510?(p?28.5)?0??xiji?i?1?10?xij?xij,i?1,?,10,j?1,?,5. （7） ?????154??154?fi?110i?7 （8）
?154?Bi,jxij?20 （9）
ij二．对最佳物流的结果进行派车—-第二层规划
这是组合优化中的一维背包模型，针对快速算法的要求，用启发式方法求近优解。 先用最佳物流修正Bij, 确定卡车一个班次中在这条路线上实际最多可以运行的次数。然后在以目标为出动总卡车数最少的各路线派车中，把各路线需要的卡车数eij?xij/(154*Bij)分成整数部分?eij?和小数部分eij??eij?，进而可以分配任务让?eij?辆车
第3页，共7页
2003高教社杯全国大学生数学建模竞赛B题竞赛参考答案
