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

B题参考答案B题参考答案第第#页,共7页下面用岩石产量达到上限为约束，矿石产量最大为目标函数求解最佳物流。（2）计算整数线性规划，以得到最大矿石产量及最佳物流由于这个整数规划的复杂性，所以必须考虑快速算法。先求解去掉整数约束的相应的线性规划，目标值为341.2807车次。由于求的是整数线性规划，矿石的最大产量（车次）必然应为一整数。因为线性规划的最优解是整数规划最优解的上界，逐个减一地依次求“矿石产量等于比342小的整数”加到约束条件中，目标为总运量最小的整数规划。第一个出现可行解的规划的最优解必为原整数规划的最优解，且总运量最小。由于等式约束造成可行域的减小，运算量已大幅度减少。把矿石卸点的最大产量为341车次作为约束条件加入到整数线性规划中，没有可行解。把矿石卸点的最大产量为340车次作为约束条件加入到整数线性规划中，得出的结果如下，即为所求。最佳物流相对应的各个路线上的最佳运输车次为：铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏382418倒装场I16542268岩场127474岩石漏80283220倒装场II1446022第二层规划仍用启发式算法：用实际流量，计算卡车在各个路线上一个班次最多可以运行的次数：铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏15161819232426294436倒装场I29392937362733282221岩场14151517212026263745岩石漏44303530242518201614倒装场II18192022272442313647根据最佳物流计算各路线上需要的卡车数：铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏2.11110.82760.4091倒装场I0.55171.38460.75861.8378岩场0.461521.6444岩石漏1.81820.93330.91430.6667倒装场II0.73680.21.93550.4681所有路线所需卡车数（实数）的和，为19.66。各路线上需要的整数卡车数为9（这些卡车在一个班次内一直在固定路线上运输）：铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏2倒装场I11岩场21岩石漏1倒装场II1各个路线上的联合派车的卡车数为11，方案为：第1辆：从铲位1到倒装场I、岩石漏，铲位1到倒装场I运5车，到岩石漏运36车。第2辆：从铲位2到倒装场I、岩石漏，铲位2到倒装场I运2车，到岩石漏运28车。第3辆：从铲位3到倒装场I、岩石漏，铲位3到倒装场I运2车，到岩石漏运32车。第4辆:从铲位4到倒装场I、岩石漏，铲位4到倒装场I运12车，到岩石漏运20车。第5辆：从铲位1、2、3到倒装场I,铲位1到倒装场I运11车，铲位2到倒装场I运13车，铲位3到倒装场I运8车。第6辆：从铲位3、4到倒装场I和铲位3到矿石漏，铲位3到倒装场I运12车，铲位4到倒装场I运19车，铲位3到矿石漏运1车。第7辆：从铲位2、3、8到倒装场H,铲位2到倒装场n运14车，铲位3到倒装场H运4车，铲位8到倒装场n运1车。第8辆：从铲位8、io到倒装场n,铲位8到倒装场n运28车，铲位io到倒装场n运4车。第9辆：从铲位io到岩场、倒装场n,铲位io到岩场运27车，铲位io到倒装场n运18车。第10辆：从铲位8、io到岩场和从铲位8到矿石漏，铲位8到岩场运i2车，铲位io到岩场运2车，铲位8到矿石漏运i4车。第11辆：从铲位3、8、9到矿石漏，铲位3到矿石漏运i车，铲位8到矿石漏运io车，铲位9到矿石漏运i8车。铲位1、2、3、4、8、9、10处各放置一台电铲。一共使用20辆卡车；总运量为142385.3吨公里；岩石产量为49280吨；矿石产量为52360吨。附注：本题主要难点.各路线上安排的车辆数应有一个最大值限制。如果在一个路线上的车辆过多就会出现题意不允许发生的等待情况。如果这一点没想到,后面的结果很难正确。.从铲位i到卸点j的流量为i54吨的整数倍。这题的核心问题之一是如何用近似算法求解NPC问题。整数规划的现有解法不是快速算法,无法保证在任何数据下都能在短时间内算完。对这题的数据而言,从竞赛的时间和软件上来说最优解是求不出来的,必须想办法巧妙地使用规划软件减少运行整数规划耗费的时间。比如：求解相对应的线性规划,最优解取整,如果还可行作为整数规划的近优解,等等。.怎样处理在io个铲位安排7台电铲的问题。4．关于派车算法中的一些问题。派车问题本质为组合优化问题,学生需要想办法快速得到最优解或近优解。可能还要考虑卡车的初始位置和终止位置,特别是两种联合派车时。另外由于装车造成的延时可能造成后面的