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

B题参考答案

矿石漏 铲位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车。

第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车，铲位10到矿石漏运5车。

对这道题的数据来说，只有共卸点或共铲位情况，没出现⑵型联合派车。 铲位1、2、3、4、8、9、10处各放置一台电铲。 一共使用13辆卡车；总运量为85628.62吨公里； 岩石产量为32186吨；矿石产量为38192吨。

问题二、利用现有车辆运输而获得最大的产量

一. 在卡车不等待条件下利用现有车辆资源运输，获得最大的产量（岩石产量优先，在产量相同的情况下，取总运量最小的解）

卡车不发生等待，即每条路线的车不能过多，否则将增加空载耗油，同时降低设备利用率，所以不一定全部车都用。

第二问的解法和第一问类似，也采用多目标二层规划算法，第一层用整数线性规划，第二层用求派出车辆数最小的启发式方法。下面是第二问解法与第一问的不同之处。

（一）第一层目标函数的确定

由于岩石产量优先，第一层规划计算前先做目标函数取岩石产量最大（max?10i?1?xj?34ij）的试算，来判断岩石产量是否能达到上限8?20?154?2?49280。

如果是，把岩石的总产量取最大值,即

??xi?1j?3104ij?49280加入到约束条件中，以矿石产

量最大为目标；如果否，把岩石产量最大做为目标，求解最佳物流。为了求岩石（或矿石）产量最大的同时，保证总运量(吨公里)较小，还不影响轻重顺序，运量的加权系数很小。如

max?i?1(xi1?xi2?xi5)?0.0001?i?1?j?1xij?cij （10）

或 max?10105??10(?xi4)?0.0001?i?1?j?1i?1xi3105?x?c? （11）

ijij为目标函数。

（二）第一层约束条件的确定

以（10）或（11）为目标，（1）至（9）为约束求解。 第一层规划采用结合线性规划来求解整数规划： （1）在现有条件下岩石产量能否达到上限

以岩石产量最大为目标函数试算整数线性规划，可得岩石卸点总产量达到了约束上限。

第5页，共7页

B题参考答案

下面用岩石产量达到上限为约束，矿石产量最大为目标函数求解最佳物流。 （2）计算整数线性规划，以得到最大矿石产量及最佳物流 由于这个整数规划的复杂性，所以必须考虑快速算法。

先求解去掉整数约束的相应的线性规划，目标值为341.2807车次。由于求的是整数线性规划，矿石的最大产量（车次）必然应为一整数。因为线性规划的最优解是整数规划最优解的上界，逐个减一地依次求“矿石产量等于比342小的整数”加到约束条件中，目标为总运量最小的整数规划。第一个出现可行解的规划的最优解必为原整数规划的最优解，且总运量最小。由于等式约束造成可行域的减小，运算量已大幅度减少。

把矿石卸点的最大产量为341车次作为约束条件加入到整数线性规划中，没有可行解。 把矿石卸点的最大产量为340车次作为约束条件加入到整数线性规划中，得出的结果如下，即为所求。

最佳物流相对应的各个路线上的最佳运输车次为： 矿石漏 倒装场Ⅰ 岩场 岩石漏 倒装场Ⅱ 铲位1 铲位2 铲位3 铲位4 铲位5 铲位6 铲位7 铲位8 铲位9 铲位10 16 54 38 22 68 80 28 14 32 4 20 24 18 12 74 74 60 22 第二层规划仍用启发式算法：

用实际流量，计算卡车在各个路线上一个班次最多可以运行的次数：

矿石漏 铲位1 铲位2 铲位3 铲位4 铲位5 铲位6 铲位7 铲位8 铲位9 铲位10 15 16 18 19 23 倒装场Ⅰ 29 39 29 37 36 岩场 14 15 15 17 21 岩石漏 44 30 35 30 24 倒装场Ⅱ 18 19 20 22 27 根据最佳物流计算各路线上需要的卡车数： 矿石漏 铲位1 铲位2 铲位3 铲位4 铲位5 24 27 20 25 24 铲位6 26 33 26 18 42 铲位7 29 28 26 20 31 铲位8 44 22 37 16 36 铲位9 36 21 45 14 47 铲位10 倒装场Ⅰ 0．5517 岩场 岩石漏 1．8182 倒装场Ⅱ 1.3846 0.9333 0.7368 2.1111 0.7586 0.9143 0.2 1.8378 0.6667 0.8276 0.4615 1.9355 0.4091 2 1.6444 0.4681 所有路线所需卡车数（实数）的和，为19.66。 各路线上需要的整数卡车数为9（这些卡车在一个班次内一直在固定路线上运输）：

矿石漏 铲位1 铲位2 铲位3 铲位4 铲位5 铲位6 铲位7 铲位8 铲位9 铲位10 倒装场Ⅰ 岩场 岩石漏 1 倒装场Ⅱ 1 2 1 1 2 1 各个路线上的联合派车的卡车数为11，方案为： 第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车。

第6页，共7页

B题参考答案

第7辆：从铲位2、3、8到倒装场Ⅱ，铲位2到倒装场Ⅱ运14车，铲位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．各路线上安排的车辆数应有一个最大值限制。

如果在一个路线上的车辆过多就会出现题意不允许发生的等待情况。如果这一点没想到，后面的结果很难正确。

2．从铲位i到卸点j的流量为154吨的整数倍。

这题的核心问题之一是如何用近似算法求解NPC问题。整数规划的现有解法不是快速算法，无法保证在任何数据下都能在短时间内算完。对这题的数据而言，从竞赛的时间和软件上来说最优解是求不出来的，必须想办法巧妙地使用规划软件减少运行整数规划耗费的时间。比如：求解相对应的线性规划，最优解取整，如果还可行作为整数规划的近优解，等等。

3．怎样处理在10个铲位安排7台电铲的问题。 4．关于派车算法中的一些问题。 派车问题本质为组合优化问题，学生需要想办法快速得到最优解或近优解。可能还要考虑卡车的初始位置和终止位置，特别是两种联合派车时。另外由于装车造成的延时可能造成后面的卡车运行的次数与前面的卡车不同。

5．多目标规划的处理方法；二层规划的处理方法。 以上是解题过程中不好解决的难点问题，看答卷怎么处理的是评阅时的重点。评卷时不能只看数值结果，更重要的是模型和方法，还有结果的可行性。

第7页，共7页