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

《2003高教社杯全国大学生数学建模竞赛B题竞赛参考答案甄选.pdf》由会员分享，可在线阅读，更多相关《2003高教社杯全国大学生数学建模竞赛B题竞赛参考答案甄选.pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品 word.2003 高教社杯全国大学生数学建模竞赛 B 题竞赛参考答案（优选.)20032003 高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛B B 题参考答案题参考答案注意：以下答案是命题人给出的，仅供参考。各评阅组应根据对题目的理解及学生的解答，自主地进注意：以下答案是命题人给出的，仅供参考。各评阅组应根据对题目的理解及学生的解答，自主地进行评阅。行评阅。问题：问题：钢铁工业是国家工业的基础之一，铁矿是钢铁工业的主要原料基地。许多现代化铁矿是露天开采的，它的生产主要是由电动铲车（以下简称电铲）装车、电动轮自卸卡车（以下简称卡车）运输来完成。提高这些大型设备的利用率是增

2、加露天矿经济效益的首要任务。露天矿里有若干个爆破生成的石料堆，每堆称为一个铲位，每个铲位已预先根据铁含量将石料分成矿石和岩石。一般来说，平均铁含量不低于 25%的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲 位至多能安置一台电铲，电铲的平均装车时间为 5 分钟。卸货地点（以下简称卸点）有卸矿石的矿石漏、2 个铁路倒装场（以下简称倒装场）和卸岩石的岩石漏、岩场等，每个卸点都有各自的产量要求。从保护国家资源的角度及 矿山的经济效益考虑，应该尽量把矿石按矿石卸点需要的铁含量（假设要求都为 29.5%1%，称为品位限制）搭配起来送到卸点，搭配的量在一

3、个班次（8 小时）内满足 品位限制即可。从长远看，卸点可以移动，但一个班次内不变。卡车的平均卸车时间为 3 分钟。所用卡车载重量为 154 吨，平均时速 28kmh。卡车的耗油量很大，每个班次每台车消耗近 1 吨柴油。发动机点火时需要消耗相当多的电瓶能量，故一个班次中只在开始 工作时点火一次。卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发 生卡车等待的情况。电铲和卸点都不能同时为两辆及两辆以上卡车服务。卡车每次都是满载运输。每个铲位到每个卸点的道路都是专用的宽 60 m 的双向车道，不会出现堵车现象，每段道路的里程都是已知的。一个班次的生产计划应该包含以下内容：出动几台电铲，分别

4、在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次（因为随机因素影响，装卸时间与运输时间都不精确，所以排时计划无效，只求出各条路线上的卡车数及安排即可）。一个合格的计划要在卡车不等待条件下满足产量和质量（品位）要求，而一个好的计划还应该考虑下面两条原则之一：1.总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最小；2.利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。请你就两条原则分别建立数学模型，并给出一个班次生产计划的快速算法。针对下面的实例，给出具体的生产计划、相应的总运量及岩石和矿石产量。某露天矿有铲位 10 个，卸点 5 个，现有铲车

5、 7 台，卡车 20 辆。各卸点一个班次的 产量要求：矿石漏 1.2 万吨、倒装场1.3 万吨、倒装场1.3 万吨、岩石漏 1.9 万吨、岩场 1.3 万吨问题分析：问题分析：本题目与典型的运输问题明显有以下不同：1运输矿石与岩石两种物资；2产量大于销量的不平衡运输；3在品位约束下矿石要搭配运输；1/10doc 格式 可编辑精品 word.4产地、销地均有单位时间的流量限制；5运输车辆每次都是满载，154 吨/车次；7 个产地；6铲位数多于铲车数意味着最优的选择不多于7最后求出各条路线上的派出车辆数及安排。运输问题对应着线性规划，以上第 1、2、3、4 条可通过变量设计、调整约束条件实现；第

6、5 条使其变为整数线性规划；第 6 条用线性模型实现的一种办法，是从C120个整数规划中取最优的即得到最佳物710流；对第 7 条由最佳物流算出各条路线上的最少派出车辆数（整数），再给出具体安排即完成全部计算。对于这个实际问题，要求快速算法，计算含50 个变量的整数规划比较困难。另外，这是一个二层规划，第二层是组合优化，如果求最优解计算量较大，现成的各种算法都无能为力。于是问题变为找一个寻求近优解的近似解法，例如可用启发式方法求解。调用 120 次整数规划可用三种方法避免：（1）先不考虑电铲数量约束运行整数线性规划，再对解中运量最少的几个铲位进行筛选；（2）在整数线性规划的铲车约束中调用sig

7、n函数来实现；（3）增加 10 个 01变量来标志各个铲位是否有产量。这是一个多目标规划，第一问的目标有两层：第一层是总运量（吨公里）最小，第二层是出动卡车数最少，从而实现运输成本最小。第二问的目标有：岩石产量最大；矿石产量最大；运量最小，三者的重要性应按此序。合理的假设主要有：1.2.卡车在一个班次中不应发生等待或熄火后再启动的情况；在铲位或卸点处因两条路线（及以上）造成的冲突时，只要平均时间能完成任务即可，不进行排时讨论；空载与重载的速度都是 28km/h，耗油相差却很大，因此总运量只考虑重载运量；卡车可提前退出系统。3.4.符号：xij 从 i 号铲位到 j 号卸点的石料运量单位 吨；c

8、ij 从 i 号铲位到 j 号卸点的距离公里；Tij 从 i 号铲位到 j 号卸点路线上运行一个周期平均所需时间分；Aij 从 i 号铲位到 j 号卸点最多能同时运行的卡车数辆；Bij 从 i 号铲位到 j 号卸点路线上一辆车最多可以运行的次数次；pi i 号铲位的矿石铁含量。%p=(30,28,29,32,31,33,32,31,33,31)qjj 号卸点任务需求吨q=(1.2,1.3,1.3,1.9,1.3)*10000cki i 号铲位的铁矿石储量 万吨cyi i 号铲位的岩石储量万吨fi:描述第 i 号铲位是否使用的 0-1 开关变量，取 1 为使用；取 0 为关闭。2/10doc 格

9、式 可编辑精品 word.模型建立、算法设计与模型求解：模型建立、算法设计与模型求解：问题一、求运输成本最小的生产计划问题一、求运输成本最小的生产计划一以总运量最小为目标函数求解最佳物流-第一层规划（1）道路能力约束：一个电铲（卸点）不能同时为两辆卡车服务，一条路线上最多能同时运行的卡车数是有限制的。卡车从 i 号铲位到 j 号卸点运行一个周期平均所需时间为Tij i到j距离2/平均速度35（分钟）。由于装车时间 5 分钟大于卸车时间 3 分钟，所以这条路线上在卡车不等待条件下最多能同时运行的卡车数为：A T/5；其中最后开始发车的一辆卡车一个班次中在这条路线上最多可以运行的次数为（其他iji

10、j卡车可能比此数多 1 次）Bij(860(Aij1)5)/Tij，这里(Aij1)5是开始装车时最后一辆车的延时时间。一个班次中这条固定路线上最多可能运行的总车次大约大约为：L A B，总吨数154Lij。ijijij（2）电铲能力约束：一台电铲不能同时为两辆卡车服务，所以一台电铲在一个班次中的最大可能产量为 860/5154（吨）。（3）卸点能力约束：卸点的最大吞吐量为每小时 60/3=20 车次，于是一个卸点在一个班次中的最大可能产量为 820154（吨）。（4）铲位储量约束：铲位的矿石和岩石产量都不能超过相应的储藏量。（5）产量任务约束：各卸点的产量不小于该卸点的任务要求。（6）铁含量

11、约束：各矿石卸点的平均品位要求都在指定的范围内。（7）电铲数量约束：电铲数量约束无法用普通不等式表达，可以引入 10 个 01 变量来标志各个铲位是否有产量。（8）整数约束：当把问题作为整数规划模型时，流量 xij除以 154 为非负整数。（9）卡车数量约束：不超过 20 辆。得到的一种模型为minxc（0）i1 j1ijijijijij105s.t.x154ABxj110,i 1,10,j 1,5（1）5ijfi860/5154,i 1,10（2）xi1ij 8 20 154,j 1,5（3）xxxck10000,xxcy10000i1i2i5ii3i4ii 1,10（4）xqi1ij10j

12、,j 1,5（5）(30.5)0piji（6）i1,j 1,2,510(p 28.5)0 xijii1x10 xijxij,i 1,10,j 1,5.（7）154154 fi110i 7（8）3/10doc 格式 可编辑精品 word.154Bi,jxij 20（9）ij二对最佳物流的结果进行派车-第二层规划这是组合优化中的一维背包模型，针对快速算法的要求，用启发式方法求近优解。先用最佳物流修正 Bij,确定卡车一个班次中在这条路线上实际最多可以运行的次数。然后在以目标为出动总卡车数最少的各路线派车中，把各路线需要的卡车数eijeijeij，进而可以分配任务让eij辆车在 xij/(154*B

13、ij)分成整数部分eij和小数部分i 到 j 路线上，每辆往返运输 Bij次。为了最后实现第二层规划的目标，只需联合处理所有的eijeij时把这些小数组合成最少的整数卡车数。所需总卡车数的下界显然是Y0eij。如果某种派车方案恰好派出i,jY0辆车实现了所有的 xij，则其即为第二层目标意义下近优解的最优方案。但由于有联合派车而总公里数不一定最小,故不一定为全局意义下的最佳方案。出动卡车数最少，意味着出动的卡车利用率要最大。容易出现的一辆卡车为两个以上路线服务的联合派车，可分为两种情况：有共同铲位（或卸点）的联合派车（V 字形或更复杂）；不同铲位且不同卸点之间的联合派车（Z 字形或四边形或更复

14、杂）。派车方案的空载路线应尽量安排在第一层规划的最佳物流路线内，即使有的超出也要保证超出的路程总和最小，这样才能实现重载路程最小且使卡车空载路程也最小。而情况的路线不会超出第一层规划的最佳物流路线。只有情况才会有一部分不在第一层规划的最佳物流路线内。问题：各路线都是小数的需车数，如何组合使总卡车数最少且如果出现情况时空载超出部分总和尽量小。如果存在情况，则整体考虑情况形路线需要的卡车数相加的和,先确定和的整数部分的车数并对这些车分配任务（任务的形式为在哪条路线上运几趟，再在哪条路线上运几趟，等等）。之后已无情况了，再对各个小数进行组合相加试探，在所有动用卡车数最少的情况中，选择超出第一层最佳物

15、流路线的总和最小的，即为最后派车方案，再对这些车分配任务。由于属情况的为多数，故后面的组合搜索比较简单，常常只有一两个任务属情况。根据最后派车方案，回代计算出各车辆在各路线的运输次数。由于整数部分已分配完运输次数,小数乘以对应路线上的 Bij取整计算出小数部分对应的具体运输次数.进一步计算出实际总运量与矿石和岩石的产量。三、求解过程：（一）第一层规划求解前面给出的整数规划模型可计算出最优值为总运量 85628.62 吨公里。最佳物流相对应的各个路线上的最佳运输车次：铲铲铲铲铲铲铲铲铲铲位 1 位 2位 3位 4位 5位 6位 7位 8位 9位10矿石漏倒装场岩场1313545411114242

16、4343707015154/10doc 格式 可编辑精品 word.岩石 8181漏倒装场434313132 27070（二）第二层规划用具体流量计算卡车在各个路线上一个班次最多可以运行的次数：（即修正的 Bij）铲铲铲铲铲铲铲铲铲铲位 1 位 2位 3位 4位 5位 6位 7位 8位 9位10矿石 15151819232426294535漏倒装 30393037362733282221场岩场 14151517212026263746岩石 44313530242518201614漏倒装 18192022272442323647场根据最佳物流，计算各路线上需要的卡车数（实数）：铲铲铲铲铲铲铲铲铲

17、铲位 1 位 2位 3位 4位 5位 6位 7位 8位 9位10矿石0.860.861.861.860.310.31漏7 72 24 4倒装1.071.071.161.16场7 72 2岩场1.891.890.320.322 26 6岩石 1.841.841.221.22漏1 19 9倒装0.680.680.10.11.481.48场4 49 9所有路线所需卡车数（实数）的和为 12.84312.843。各路线上需要的整数卡车数为 7（这些卡车在一个班次内一直在固定路线上运输）：铲铲铲铲铲铲铲铲铲铲位 1 位 2位 3位 4位 5位 6位 7位 8位 9位105/10doc 格式 可编辑精品

18、word.矿石漏倒装场岩场1 11 11 11 1岩石 1 1漏倒装场1 11 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

19、 到倒装场运 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.62856

20、28.62 吨公里；吨公里；岩石产量为岩石产量为 3218632186 吨；矿石产量为吨；矿石产量为 3819238192 吨。吨。问题二、利用现有车辆运输而获得最大的产量问题二、利用现有车辆运输而获得最大的产量一.在卡车不等待条件下利用现有车辆资源运输，获得最大的产量（岩石产量优先，在产量相同的情况下，取总运量最小的解）卡车不发生等待，即每条路线的车不能过多，否则将增加空载耗油，同时降低设备利用率，所以不一定全部车都用。第二问的解法和第一问类似，也采用多目标二层规划算法，第一层用整数线性规划，第二层用求派出车辆数最小的启发式方法。下面是第二问解法与第一问的不同之处。（一）第一层目标函数的确定

21、4由于岩石产量优先，第一层规划计算前先做目标函数取岩石产量最大（max10）的试算，来判断i1j3xij4岩石产量是否能达到上限8201542 49280。如果是，把岩石的总产量取最大值,即10 49280加入到i1j3xij约束条件中，以矿石产量最大为目标；如果否，把岩石产量最大做为目标，求解最佳物流。为了求岩石（或矿石）产量最大的同时，保证总运量(吨公里)较小，还不影响轻重顺序，运量的加权系数很小。如6/10doc 格式 可编辑精品 word.maxi1(xi1xi2xi5)0.0001i1j1xijcij10105（10）105或max10()0.0001i1j1xijcij（11）xi

22、4i1xi3为目标函数。（二）第一层约束条件的确定以（10）或（11）为目标，（1）至（9）为约束求解。第一层规划采用结合线性规划来求解整数规划：（1）在现有条件下岩石产量能否达到上限以岩石产量最大为目标函数试算整数线性规划，可得岩石卸点总产量达到了约束上限。下面用岩石产量达到上限为约束，矿石产量最大为目标函数求解最佳物流。（2）计算整数线性规划，以得到最大矿石产量及最佳物流由于这个整数规划的复杂性，所以必须考虑快速算法。先求解去掉整数约束的相应的线性规划线性规划，目标值为 341.2807 车次。由于求的是整数线性规划，矿石的最大产量（车次）必然应为一整数。因为线性规划的最优解是整数规划最优

23、解的上界，逐个减一地依次求“矿石产量等于比 342 小的整数”加到约束条件中，目标为总运量最小的整数规划。第一个出现可行解的规划的最优解必为原整数规划的最优解，且总运量最小。由于等式约束造成可行域的减小，运算量已大幅度减少。把矿石卸点的最大产量为 341 车次作为约束条件加入到整数线性规划中，没有可行解。把矿石卸点的最大产量为 340 车次作为约束条件加入到整数线性规划中，得出的结果如下，即为所求。最佳物流相对应的各个路线上的最佳运输车次为：铲铲铲铲铲铲铲铲铲铲位 1 位 2位 3位 4位 5位 6位 7位 8位 9位10矿石漏383824241818倒装 1616场岩场54542222686

24、8121274747474岩石 8080漏倒装场28283232202014144 460602222第二层规划仍用启发式算法：用实际流量，计算卡车在各个路线上一个班次最多可以运行的次数：铲铲铲铲铲铲铲铲铲铲7/10doc 格式 可编辑精品 word.位 1 位 2位 3位 4位 5位 6位 7位 8位 9位10矿石 15161819232426294436漏倒装 29392937362733282221场岩场 14151517212026263745岩石 44303530242518201614漏倒装 18192022272442313647场根据最佳物流计算各路线上需要的卡车数：铲铲铲铲铲

25、铲铲铲铲铲位 1 位 2位 3位 4位 5位 6位 7位 8位 9位10矿石2.112.110.820.820.400.40漏111176769191倒装 0 0 1.381.380.750.751.831.83场 5515514646868678787 7岩场0.460.462 21.641.6415154444岩石 1 1 0.930.930.910.910.660.66漏8188183333434367672 2倒装0.730.730.20.21.931.930.460.46场686855558181所有路线所需卡车数（实数）的和，为 19.66。各路线上需要的整数卡车数为 9（这些卡车

26、在一个班次内一直在固定路线上运输）：铲铲铲铲铲铲铲铲铲铲位 1 位 2位 3位 4位 5位 6位 7位 8位 9位10矿石2 2漏倒装1 11 1场岩场2 21 18/10doc 格式 可编辑精品 word.岩石 1 1漏倒装场1 1各个路线上的联合派车的卡车数为 11，方案为：第 1 辆：从铲位 1 到倒装场、岩石漏，铲位 1 到倒装场运 5 车，到岩石漏运 36 车。第 2 辆：从铲位 2 到倒装场、岩石漏，铲位 2 到倒装场运 2 车，到岩石漏运 28 车。第 3 辆：从铲位 3 到倒装场、岩石漏，铲位 3 到倒装场运 2 车，到岩石漏运 32 车。第 4 辆:从铲位 4 到倒装场、岩石

27、漏，铲位 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 辆：从铲位

28、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.3142385.3 吨公里；吨公里；岩石产

29、量为岩石产量为 4928049280 吨；矿石产量为吨；矿石产量为 5236052360 吨。吨。附注：本题主要难点附注：本题主要难点1各路线上安排的车辆数应有一个最大值限制。如果在一个路线上的车辆过多就会出现题意不允许发生的等待情况。如果这一点没想到，后面的结果很难正确。2从铲位 i 到卸点 j 的流量为 154 吨的整数倍。这题的核心问题之一是如何用近似算法求解 NPC 问题。整数规划的现有解法不是快速算法，无法保证在任何数据下都能在短时间内算完。对这题的数据而言，从竞赛的时间和软件上来说最优解是求不出来的，必须想办法巧妙地使用规划软件减少运行整数规划耗费的时间。比如：求解相对应的线性规划

30、，最优解取整，如果还可行作为整数规划的近优解，等等。3怎样处理在 10 个铲位安排 7 台电铲的问题。4关于派车算法中的一些问题。9/10doc 格式 可编辑精品 word.派车问题本质为组合优化问题，学生需要想办法快速得到最优解或近优解。可能还要考虑卡车的初始位置和终止位置，特别是两种联合派车时。另外由于装车造成的延时可能造成后面的卡车运行的次数与前面的卡车不同。5多目标规划的处理方法；二层规划的处理方法。以上是解题过程中不好解决的难点问题，看答卷怎么处理的是评阅时的重点。评卷时不能只看数值结以上是解题过程中不好解决的难点问题，看答卷怎么处理的是评阅时的重点。评卷时不能只看数值结果，更重要的是模型和方法，还有结果的可行性。果，更重要的是模型和方法，还有结果的可行性。赠人玫瑰，手留余香。感谢您使用本店文档 您的满意是我们的永恒的追求！（本句可删）-10/10doc 格式 可编辑