2003高教社杯全国大学生数学建模竞赛及其参考答案整理

参考答案（补充）第1页，共9页2003高教社杯全国大学生数学建模竞赛参考答案补充说明（2003年10月4日）全国组委会在京部分委员应邀参加了北京赛区的阅卷工作，现将有关阅卷工作情况通报给你们，供你们参考。各评阅组应根据对题目的理解及学生的解答，自主地进行评阅。A题A题阅卷专家组进行了评分标准的讨论，大家达成的评分标准的共识大体如下：（以百分制打分）1．分数分布⑴摘要5分⑵对附件1中的模型的评价15分⑶学生自己建立的模型40分⑷对经济影响的建模25分⑸短文10分⑹机动分（或印象分）5分2．上述各项指标评分基本原则⑴对附件1中的模型的评价①对附件1中的模型的评价只限于一般性的议论，评差；②对附件1中的模型的缺点（不足）论述得比较清楚，评中；③把该模型实际上的假设说得比较清楚，评优。⑵学生自己建立的模型估计大体上有两类建模方法，即基于机理的（例如：SIR模型，差分模型等）和统计建模（包括：时间序列，马尔柯夫链，神经网络等）。在建模的过程中应注意分阶段考虑（在阅卷时应充分强调这一点），比如：潜伏期，隔离期，疑似病例，预测功能等。直接的单变量回归拟合，评差；时间序列（自回归）等，评优。⑶对经济影响的建模SARS对经济影响的预测，数据拟合，评中；联系到SARS情况，评优。以上仅是北京赛区阅卷中对A题评判标准的大致共识。同时，阅卷专家还强调，各位专家要在保证公平的基础上有自己的见解。在评卷的过程中，希望各位专家能够注意有特色和创新亮点的论文。在碰到有关专业性强的问题时建议找组内有关方面专家讨论。组长要组织有关非共识（有争议）论文的讨论，以争取达到共识，不漏掉一份好论文。参考答案（补充）第2页，共9页B题1.对电铲能力约束的理解：可以认为只要在8小时中能装上车就能完成生产，即每个铲位产量可以达到96车（亦即原参考答案中第2页上的约束（2）可以取到等号）。由于实际生产中各班次之间是连续的，可以认为这样假设有一定合理性。当然，如果论文中通过分析说明铲位不能满负荷生产（即每个铲位产量可能达不到96车），也是可以的。对卸点能力约束也可类似理解。2.原参考答案中第2页上对ijijijBAL，ijijijTAB/)5)1(608(－的定义是一种比较“保守”的估计，如果论文中采用其他计算方式，只要合理，也是可以的。如定义ijijTB/608以后，对问题二的结果影响较明显，总产量可以达到670车（其中岩石产量仍为320车，矿石产量可以达到350车），最小总运量为146917.5吨公里，最佳物流相对应的各个路线上的最佳运输车次为（可能不唯一）：铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏402020倒装场Ⅰ22571368岩场127672岩石漏74283226倒装场Ⅱ111164243.对第2问中目标函数可以有另外一种理解：首先使总产量最大；其次使岩石产量最大；最后使总运量最小。这种理解下计算得到的结果，与原参考答案相同（如按照2中对ijB的新定义，结果与2相同）。4.原参考答案中第3页上提到“背包问题”，应改为“装箱问题”为佳。5.问题1、问题2和其他（摘要、表达等）三部分的比重大致是6：3：1。再次提醒：评卷时不能只看数值结果，更重要的是模型和方法，以及论文的分析和表达。2003高教社杯全国大学生数学建模竞赛B题参考答案注意：以下答案是命题人给出的，仅供参考。各评阅组应根据对题目的理解及学生的解答，自主地进行评阅。参考答案（补充）第3页，共9页问题分析：本题目与典型的运输问题明显有以下不同：1．运输矿石与岩石两种物资；2．产量大于销量的不平衡运输；3．在品位约束下矿石要搭配运输；4．产地、销地均有单位时间的流量限制；5．运输车辆每次都是满载，154吨/车次；6．铲位数多于铲车数意味着最优的选择不多于7个产地；7．最后求出各条路线上的派出车辆数及安排。运输问题对应着线性规划，以上第1、2、3、4条可通过变量设计、调整约束条件实现；第5条使其变为整数线性规划；第6条用线性模型实现的一种办法，是从120710C个整数规划中取最优的即得到最佳物流；对第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)*10000cki~i号铲位的铁矿石储量万吨cyi~i号铲位的岩石储量万吨fi:~描述第i号铲位是否使用的0-1开关变量，取1为使用；取0为关闭。模型建立、算法设计与模型求解：问题一、求运输成本最小的生产计划一．以总运量最小为目标函数求解最佳物流—-第一层规划参考答案（补充）第4页，共9页（1）道路能力约束：一个电铲（卸点）不能同时为两辆卡车服务，一条路线上最多能同时运行的卡车数是有限制的。卡车从i号铲位到j号卸点运行一个周期平均所需时间为53/2＋平均速度＋距离到jiTij（分钟）。由于装车时间5分钟大于卸车时间3分钟，所以这条路线上在卡车不等待条件下最多能同时运行的卡车数为：5/ijijTA；其中最后开始发车的一辆卡车一个班次中在这条路线上最多可以运行的次数为（其他卡车可能比此数多1次）ijijijTAB/)5)1(608(－，这里5)1(ijA是开始装车时最后一辆车的延时时间。一个班次中这条固定路线上最多可能运行的总车次大约为：ijijijBAL，总吨数ijL154。（2）电铲能力约束：一台电铲不能同时为两辆卡车服务，所以一台电铲在一个班次中的最大可能产量为8×60/5×154（吨）。（3）卸点能力约束：卸点的最大吞吐量为每小时60/3=20车次，于是一个卸点在一个班次中的最大可能产量为8×20×154（吨）。（4）铲位储量约束：铲位的矿石和岩石产量都不能超过相应的储藏量。（5）产量任务约束：各卸点的产量不小于该卸点的任务要求。（6）铁含量约束：各矿石卸点的平均品位要求都在指定的范围内。（7）电铲数量约束：电铲数量约束无法用普通不等式表达，可以引入10个0—1变量来标志各个铲位是否有产量。（8）整数约束：当把问题作为整数规划模型时，流量xij除以154为非负整数。（9）卡车数量约束：不超过20辆。得到的一种模型为cxijijij10151min（0）s.t.5,,1,10,,1,154jiBAxijijij（1）10,,1,1545/60851ifxijij（2）5,,1,154208101jiijx（3）10,,1,100001000043521icyxxckxxxiiiiiii（4）5,,1,101jqxjiij（5）5,2,1,0)5.28(0)5.30(101101jpxpxiiijiiij（6）5,,1,10,,1,154154jixxijij.（7）7101iif（8）20154,jiijijBx（9）参考答案（补充）第5页，共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矿石漏135411倒装场Ⅰ4243岩场7015岩石漏8143倒装场Ⅱ13270（二）第二层规划用具体流量计算卡车在各个路线上一个班次最多可以运行的次数：（即修正的Bij）铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏15151819232426294535倒装场Ⅰ30393037362733282221岩场14151517212026263746岩石漏44313530242518201614参考答案（补充）第6页，共9页倒装场Ⅱ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所有路线所需卡车