2003全国大学生数学建模竞赛b题参考答案.docx

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

1、2003全国大学生数学建模竞赛b题参考答案2003大学生数学建模竞赛B题参考答案注意：下面答案是命题人给出的，仅供参考。各评阅组应根据对题目的理解及学生的解答，自主地进行评阅。问题分析：此题目与典型的运输问题明显有下面不同：1运输矿石与岩石两种物资；2产量大于销量的不平衡运输；3在档次约束下矿石要搭配运输；4产地、销地均有单位时间的流量限制；5运输车辆每次都是满载，154吨/车次；6铲位数多于铲车数意味着最优的选择不多于7个产地；7最后求出各条道路上的派出车辆数及安排。运输问题对应着线性规划，以上第1、2、3、4条可通过变量设计、调整约束条件实现；第5条使其变为整数线性规划；第6条用线性模型实

2、现的一种办法，是从120710C个整数规划中取最优的即得到最佳物流；对第7条由最佳物流算出各条道路上的最少派出车辆数整数，再给出详细安排即完成全部计算。对于这个实际问题，要求快速算法，计算含50个变量的整数规划比拟困难。另外，这是一个二层规划，第二层是组合优化，假如求最优解计算量较大，现成的各种算法都无能为力。于是问题变为找一个寻求近优解的近似解法，例如可用启发式方法求解。调用120次整数规划可用三种方法避免：1先不考虑电铲数量约束运行整数线性规划，再对解中运量最少的几个铲位进行挑选；2在整数线性规划的铲车约束中调用sign函数来实现；3增加10个01变量来标志各个铲位能否有产量。这是一个多目

3、的规划，第一问的目的有两层：第一层是总运量吨公里最小，第二层是出动卡车数最少，进而实现运输成本最小。第二问的目的有：岩石产量最大；矿石产量最大；运量最小，三者的重要性应按此序。合理的假设主要有：1.卡车在一个班次中不应发生等待或熄火后再启动的情况；2.在铲位或卸点处因两条道路及以上造成的冲突时，只要平均时间能完成任务即可，不进行排时讨论；3.空载与重载的速度都是28km/h，耗油相差却很大，因而总运量只考虑重载运量；4.卡车可提早退出系统。符号：xij从i号铲位到j号卸点的石料运量单位吨；cij从i号铲位到j号卸点的距离公里；Tij从i号铲位到j号卸点道路上运行一个周期平均所需时间分；Aij从

4、i号铲位到j号卸点最多能同时运行的卡车数辆；Bij从i号铲位到j号卸点道路上一辆车最多能够运行的次数次；pii号铲位的矿石铁含量。%p=(30,28,29,32,31,33,32,31,33,31)qjj号卸点任务需求吨q=(1.2,1.3,1.3,1.9,1.3)*10000ckii号铲位的铁矿石储量万吨cyii号铲位的岩石储量万吨fi:描绘第i号铲位能否使用的0-1开关变量，取1为使用；取0为关闭。模型建立、算法设计与模型求解：问题一、求运输成本最小的生产计划一以总运量最小为目的函数求解最佳物流-第一层规划1道路能力约束：一个电铲卸点不能同时为两辆卡车服务，一条道路上最多能同时运行的卡车数

5、是有限制的。卡车从i号铲位到j号卸点运行一个周期平均所需时间为53/2平均速度距离到?=jiTij分钟。由于装车时间5分钟大于卸车时间3分钟，所以这条道路上在卡车不等待条件下最多能同时运行的卡车数为：?5/ijijTA=；其中最后开场发车的一辆卡车一个班次中在这条道路上最多能够运行的次数为其他卡车可能比此数多1次?ijijijTAB/)5)1(608(?-?=，这里5)1(?-ijA是开场装车时最后一辆车的延时时间。一个班次中这条固定道路上最多可能运行的总车次大约为：ijijijBAL?=，总吨数ijL?154。2电铲能力约束：一台电铲不能同时为两辆卡车服务，所以一台电铲在一个班次中的最大可能

6、产量为860/5154吨。3卸点能力约束：卸点的最大吞吐量为每小时60/3=20车次，于是一个卸点在一个班次中的最大可能产量为820154吨。4铲位储量约束：铲位的矿石和岩石产量都不能超过相应的储藏量。5产量任务约束：各卸点的产量不小于该卸点的任务要求。6铁含量约束：各矿石卸点的平均档次要求都在指定的范围内。7电铲数量约束：电铲数量约束无法用普通不等式表达，能够引入10个01变量来标志各个铲位能否有产量。8整数约束：当把问题作为整数规划模型时，流量xij除以154为非负整数。9卡车数量约束：不超过20辆。得到的一种模型为cxijijij?=10151min0s.t.5,1,10,1,154=?

7、jiBAxijijij110,1,1545/60851=?=ifxijij25,1,154208101=?=jiijx310,1,100001000043521=?+?+icyxxckxxxiiiiiii45,1,101=jqxjiij55,2,1,0)5.28(0)5.30(101101=?-?-?=jpxpxiiijiiij65,1,10,1,154154=?jixxijij.77101=iif820214,?jiijijBx9二对最佳物流的结果进行派车-第二层规划这是组合优化中的一维背包模型，针对快速算法的要求，用启发式方法求近优解。先用最佳物流修正Bij,确定卡车一个班次中在这条道路上

8、实际最多能够运行的次数。然后在以目的为出动总卡车数最少的各道路派车中，把各道路需要的卡车数)*154/(ijijijBxe=分成整数部分?ije和小数部分?ijijee-，进而能够分配任务让?ije辆车在i到j道路上，每辆往返运输Bij次。为了最后实现第二层规划的目的，只需联合处理所有的?ijijee-时把这些小数组合成最少的整数卡车数。所需总卡车数的下界显然是?=jiijeY,0。假如某种派车方案恰好派出Y0辆车实现了所有的xij，则其即为第二层目的意义下近优解的最优方案。但由于有联合派车而总公里数不一定最小,故不一定为全局意义下的最佳方案。出动卡车数最少，意味着出动的卡车利用率要最大。容易

9、出现的一辆卡车为两个以上道路服务的联合派车，可分为两种情况：有共同铲位或卸点的联合派车V字形或更复杂；不同铲位且不同卸点之间的联合派车Z字形或四边形或更复杂。派车方案的空载道路应尽量安排在第一层规划的最佳物流道路内，即便有的超出也要保证超出的路程总和最小，这样才能实现重载路程最小且使卡车空载路程也最小。而情况的道路不会超出第一层规划的最佳物流道路。只要情况才会有一部分不在第一层规划的最佳物流道路内。问题：各道路都是小数的需车数，怎样组合使总卡车数最少且假如出现情况时空载超出部分总和尽量小。假如存在情况，则整体考虑情况形道路需要的卡车数相加的和,先确定和的整数部分的车数并对这些车分配任务任务的形

10、式为在哪条道路上运几趟，再在哪条道路上运几趟，等等。之后已无情况了，再对各个小数进行组合相加试探，在所有动用卡车数最少的情况中，选择超出第一层最佳物流道路的总和最小的，即为最后派车方案，再对这些车分配任务。由于属情况的为多数，故后面的组合搜索比拟简单，经常只要一两个任务属情况。根据最后派车方案，回代计算出各车辆在各道路的运输次数。由于整数部分已分配完运输次数,小数乘以对应道路上的Bij取整计算出小数部分对应的详细运输次数.进一步计算出实际总运量与矿石和岩石的产量。三、求解经过：一第一层规划求解前面给出的整数规划模型可计算出最优值为总运量85628.62吨公里。所有道路所需卡车数实数的和为12.

11、843。各道路上需要的整数卡车数为7这些卡车在一个班次内一直在固定道路上运输：第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到倒装场运3车，铲位4到倒装场运6车，铲位2到倒装场运13车，铲位3到倒装场运1车。第6辆：从铲位3到倒装场、岩石漏和从铲位10到矿石漏、岩场、倒装场，铲位3

12、到岩石漏运3车，铲位3到倒装场运1车，铲位10到倒装场运23车，铲位10到岩场运10车，铲位10到矿石漏运5车。对这道题的数据来讲，只要共卸点或共铲位情况，没出现型联合派车。铲位1、2、3、4、8、9、10处各放置一台电铲。一共使用13辆卡车；总运量为85628.62吨公里；岩石产量为32186吨；矿石产量为38192吨。问题二、利用现有车辆运输而获得最大的产量一.在卡车不等待条件下利用现有车辆资源运输，获得最大的产量岩石产量优先，在产量一样的情况下，取总运量最小的解卡车不发生等待，即每条道路的车不能太多，否则将增加空载耗油，同时降低设备利用率，所以不一定全部车都用。第二问的解法和第一问类似，

13、也采用多目的二层规划算法，第一层用整数线性规划，第二层用求派出车辆数最小的启发式方法。下面是第二问解法与第一问的不同之处。一第一层目的函数确实定由于岩石产量优先，第一层规划计算前先做目的函数取岩石产量最大=10143maxijijx的试算，来判定岩石产量能否能到达上限492802154208=?。假如是，把岩石的总产量取最大值,即4928010143=ijijx参加到约束条件中，以矿石产量最大为目的；假如否，把岩石产量最大做为目的，求解最佳物流。为了求岩石或矿石产量最大的同时，保证总运量(吨公里)较小，还不影响轻重顺序，运量的加权系数很小。如cxxxxijijijiiii?-+=1015110

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

15、大产量车次必然应为一整数。由于线性规划的最优解是整数规划最优解的上界，逐个减一地依次求“矿石产量等于比342小的整数加到约束条件中，目的为总运量最小的整数规划。第一个出现可行解的规划的最优解必为原整数规划的最优解，且总运量最小。由于等式约束造成可行域的减小，运算量已大幅度减少。把矿石卸点的最大产量为341车次作为约束条件参加到整数线性规划中，没有可行解。把矿石卸点的最大产量为340车次作为约束条件参加到整数线性规划中，得出的结果如下，即为所求。最佳物流相对应的各个道路上的最佳运输车次为：第二层规划仍用启发式算法：用实际流量，计算卡车在各个道路上一个班次最多能够运行的次数：所有道路所需卡车数实数

16、的和，为19.66。第1辆：从铲位1到倒装场、岩石漏，铲位1到倒装场运5车，到岩石漏运36车。第2辆：从铲位2到倒装场、岩石漏，铲位2到倒装场运2车，到岩石漏运28车。第3辆：从铲位3到倒装场、岩石漏，铲位3到倒装场运2车，到岩石漏运32车。第4辆:从铲位4到倒装场、岩石漏，铲位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车，铲位

17、3到倒装场运4车，铲位8到倒装场运1车。第8辆：从铲位8、10到倒装场，铲位8到倒装场运28车，铲位10到倒装场运4车。第9辆：从铲位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、2、3、4、8、9、10处各放置一台电铲。一共使用20辆卡车；总运量为142385.3吨公里；岩石产量为49280吨；矿石产量为52360吨。附注：此题主要难点1各

18、道路上安排的车辆数应有一个最大值限制。假如在一个道路上的车辆太多就会出现题意不允许发生的等待情况。假如这一点没想到，后面的结果很难正确。2从铲位i到卸点j的流量为154吨的整数倍。这题的核心问题之一是怎样用近似算法求解NPC问题。整数规划的现有解法不是快速算法，无法保证在任何数据下都能在短时间内算完。对这题的数据而言，从竞赛的时间和软件上来讲最优解是求不出来的，必须想办法巧妙地使用规划软件减少运行整数规划消耗的时间。比方：求解相对应的线性规划，最优解取整，假如还可行作为整数规划的近优解，等等。3如何处理在10个铲位安排7台电铲的问题。4关于派车算法中的一些问题。派车问题本质为组合优化问题，学生需要想办法快速得到最优解或近优解。可能还要考虑卡车的初始位置和终止位置，十分是两种联合派车时。另外由于装车造成的延时可能造成后面的卡车运行的次数与前面的卡车不同。5多目的规划的处理方法；二层规划的处理方法。以上是解题经过中不好解决的难点问题，看答卷怎么处理的是评阅时的重点。评卷时不能只看数值结果，更重要的是模型和方法，还有结果的可行性。