《2003年全国赛b题参考答案[中国科大]露天矿生产的车辆安排》由会员分享，可在线阅读，更多相关《2003年全国赛b题参考答案[中国科大]露天矿生产的车辆安排（8页珍藏版）》请在金锄头文库上搜索。
1、B 题参考答案第 1 页，共 8 页2003 高教社杯全国大学生数学建模竞赛B 题参考答案注意：以下答案是命题人给出的，仅供参考。各评阅组应根据对题目的理解及学生的解答，自主地进行评阅。问题分析：本题目与典型的运输问题明显有以下不同：1 运输矿石与岩石两种物资；2 产量大于销量的不平衡运输；3 在品位约束下矿石要搭配运输；4 产地、销地均有单位时间的流量限制；5 运输车辆每次都是满载，154 吨/车次；6 铲位数多于铲车数意味着最优的选择不多于 7 个产地；7 最后求出各条路线上的派出车辆数及安排。运输问题对应着线性规划，以上第 1、2、3、4 条可通过变量设计、调整约束条件实现；第 5 条使
2、其变为整数线性规划；第 6 条用线性模型实现的一种办法，是从 个整数1207C规划中取最优的即得到最佳物流；对第 7 条由最佳物流算出各条路线上的最少派出车辆数（整数） ，再给出具体安排即完成全部计算。对于这个实际问题，要求快速算法，计算含 50 个变量的整数规划比较困难。另外，这是一个二层规划，第二层是组合优化，如果求最优解计算量较大，现成的各种算法都无能为力。于是问题变为找一个寻求近优解的近似解法，例如可用启发式方法求解。调用 120 次整数规划可用三种方法避免：（1）先不考虑电铲数量约束运行整数线性规划，再对解中运量最少的几个铲位进行筛选；（2）在整数线性规划的铲车约束中调用函数来实现；
3、（3）增加 10 个 01 变量来标志各个铲位是否有产量。sign这是一个多目标规划，第一问的目标有两层：第一层是总运量（吨公里）最小，第二层是出动卡车数最少，从而实现运输成本最小。第二问的目标有：岩石产量最大；矿石产量最大；运量最小，三者的重要性应按此序。合理的假设主要有：1. 卡车在一个班次中不应发生等待或熄火后再启动的情况；2. 在铲位或卸点处因两条路线（及以上）造成的冲突时，只要平均时间能完成任务即可，不进行排时讨论；3. 空载与重载的速度都是 28km/h，耗油相差却很大，因此总运量只考虑重载运量；4. 卡车可提前退出系统。符号：x ij 从 i 号铲位到 j 号卸点的石料运量 单位
4、 吨；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 B 题参考答案第 2 页，共 8 页cki i 号铲位的铁矿石储量 万吨cyi i 号铲位的岩石储量 万吨fi: 描述第 i 号铲位是否使用的 0
5、-1 开关变量，取 1 为使用；取 0 为关闭。模型建立、算法设计与模型求解：问题一、求运输成本最小的生产计划一以总运量最小为目标函数求解最佳物流-第一层规划（1）道路能力约束：一个电铲（卸点）不能同时为两辆卡车服务，一条路线上最多能同时运行的卡车数是有限制的。卡车从 i 号铲位到 j 号卸点运行一个周期平均所需时间为（分钟）。由于装车时间 5 分钟大于卸车时间 3 分钟，53/2平 均 速 度 距 离到 jiTj所以这条路线上在卡车不等待条件下最多能同时运行的卡车数为： ；其中最后5/ijijTA开始发车的一辆卡车一个班次中在这条路线上最多可以运行的次数为（其他卡车可能比此数多 1 次） ，
6、这里 是开始装车时最后一辆车的延ijijij TAB/)1(608 )1(ijA时时间。一个班次中这条固定路线上最多可能运行的总车次大约为： ，总吨数ijijBL。ijL54（2）电铲能力约束：一台电铲不能同时为两辆卡车服务，所以一台电铲在一个班次中的最大可能产量为 860/5154（吨）。（3）卸点能力约束：卸点的最大吞吐量为每小时 60/3=20 车次，于是一个卸点在一个班次中的最大可能产量为 820154（吨）。（4）铲位储量约束：铲位的矿石和岩石产量都不能超过相应的储藏量。（5）产量任务约束：各卸点的产量不小于该卸点的任务要求。（6）铁含量约束：各矿石卸点的平均品位要求都在指定的范围内
7、。（7）电铲数量约束：电铲数量约束无法用普通不等式表达，可以引入 10 个 01 变量来标志各个铲位是否有产量。（8）整数约束：当把问题作为整数规划模型时，流量 xij 除以 154 为非负整数。（9）卡车数量约束：不超过 20 辆。得到的一种模型为（0）cxijij105mns.t. （1）5,1,0,4LjiBAjijij（2）15/60851fiji（3）,20jijx（4）10,104351 Licykiii（5）,01LjqijB 题参考答案第 3 页，共 8 页（6）5,21,0)5.28(310 jpxiijiij. （7）,4Ljijij（8）710iif（9）254,jiij
8、Bx二对最佳物流的结果进行派车-第二层规划这是组合优化中的一维背包模型，针对快速算法的要求，用启发式方法求近优解。先用最佳物流修正 Bij, 确定卡车一个班次中在这条路线上实际最多可以运行的次数。然后在以目标为出动总卡车数最少的各路线派车中，把各路线需要的卡车数分成整数部分 和小数部分 ，进而可以分配任务让 辆车)*154/(ijijijxeijeijijeije在 i 到 j 路线上，每辆往返运输 Bij 次。为了最后实现第二层规划的目标，只需联合处理所有的 时把这些小数组合成最少的整数卡车数。所需总卡车数的下界显然是ij。如果某种派车方案恰好派出 Y0 辆车实现了所有的 xij，则其即为第
9、二层目标意jieY,0义下近优解的最优方案。但由于有联合派车而总公里数不一定最小,故不一定为全局意义下的最佳方案。出动卡车数最少，意味着出动的卡车利用率要最大。容易出现的一辆卡车为两个以上路线服务的联合派车，可分为两种情况：有共同铲位（或卸点）的联合派车（V 字形或更复杂）；不同铲位且不同卸点之间的联合派车（Z 字形或四边形或更复杂）。派车方案的空载路线应尽量安排在第一层规划的最佳物流路线内，即使有的超出也要保证超出的路程总和最小，这样才能实现重载路程最小且使卡车空载路程也最小。而情况的路线不会超出第一层规划的最佳物流路线。只有情况才会有一部分不在第一层规划的最佳物流路线内。问题：各路线都是小
10、数的需车数，如何组合使总卡车数最少且如果出现情况时空载超出部分总和尽量小。如果存在情况，则整体考虑情况形路线需要的卡车数相加的和,先确定和的整数部分的车数并对这些车分配任务（任务的形式为在哪条路线上运几趟，再在哪条路线上运几趟，等等）。之后已无情况了，再对各个小数进行组合相加试探，在所有动用卡车数最少的情况中，选择超出第一层最佳物流路线的总和最小的，即为最后派车方案，再对这些车分配任务。由于属情况的为多数，故后面的组合搜索比较简单，常常只有一两个任务属情况。根据最后派车方案，回代计算出各车辆在各路线的运输次数。由于整数部分已分配完运输次数,小数乘以对应路线上的 Bij 取整计算出小数部分对应的
11、具体运输次数 .进一步计算出实际总运量与矿石和岩石的产量。三、求解过程：（一） 第一层规划求解前面给出的整数规划模型可计算出最优值为总运量 85628.62吨公里。B 题参考答案第 4 页，共 8 页最佳物流相对应的各个路线上的最佳运输车次：铲位 1 铲位 2 铲位 3 铲位 4 铲位 5 铲位 6 铲位 7 铲位 8 铲位 9 铲位 10矿石漏 13 54 11倒装场 42 43岩场 70 15岩石漏 81 43倒装场 13 2 70（二）第二层规划用具体流量计算卡车在各个路线上一个班次最多可以运行的次数：（即修正的 Bij）铲位 1 铲位 2 铲位 3 铲位 4 铲位 5 铲位 6 铲位
12、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
13、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 车。
14、第 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 车，铲位 1
15、0 到矿石漏运 5 车。对这道题的数据来说，只有共卸点或位情况，没出现型联合派车。铲位 1、2、3、4、8、9、10 处各放置一台电铲。一共使用 13 辆卡车；总运量为 85628.62 吨公里；岩石产量为 32186 吨；矿石产量为 38192 吨。问题二、利用现有车辆运输而获得最大的产量一. 在卡车不等待条件下利用现有车辆资源运输，获得最大的产量（岩石产量优先，在产量相同的情况下，取总运量最小的解）卡车不发生等待，即每条路线的车不能过多，否则将增加空载耗油，同时降低设备利B 题参考答案第 5 页，共 8 页用率，所以不一定全部车都用。第二问的解法和第一问类似，也采用多目标二层规划算法，第一层用整数线性规划，第二层用求派出车辆数最小的启发式方法。下面是第二问解法与第一问的不同之处。（一）第一层目标函数的确定由于岩石产量优先，第一层规划计算前先做目标函数取岩石产量最大（）的试算，来判断岩石产量
