B题参考答案
第一层是总运量（吨公里）最小，第二层是出动卡车数最少，从而实现运输成本最小。第二问的目标有：岩石产量最大；矿石产量最大；运量最小，三者的重要性应按此序。 合理的假设主要有：
1. 卡车在一个班次中不应发生等待或熄火后再启动的情况；
2. 在铲位或卸点处因两条路线（及以上）造成的冲突时，只要平均时间能完成任务即可，不进行排时讨论；
3. 空载与重载的速度都是28km/h，耗油相差却很大，因此总运量只考虑重载运量； 4. 卡车可提前退出系统。
符号：xij ~ 从i号铲位到j号卸点的石料运量 单位 吨；
cij ~ 从i号铲位到j号卸点的距离
公里；
Tij ~ 从i号铲位到j号卸点路线上运行一
个周期平均所需时间 分；
Aij ~ 从i号铲位到j号卸点最多能同时运
行的卡车数 辆；
Bij ~ 从i号铲位到j号卸点路线上一辆车
第6页，共21页
B题参考答案
最多可以运行的次数 次；
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)*10000 万吨
cyi ~ i万吨
fi: ~ 描述第i号铲位是否使用的0-1开
关变量，取1为使用；取0为关闭。
模型建立、算法设计与模型求解： 问题一、求运输成本最小的生产计划
一．以总运量最小为目标函数求解最佳物流—-第一层规划
（1）道路能力约束：一个电铲（卸点）不能同时为两辆卡车服务，一条路线上最多能同时
第7页，共21页
cki ~ i号铲位的铁矿石储量
号铲位的岩石储量
B题参考答案
运行的卡车数是有限制的。卡车从i号铲位到j号卸点运行一个周期平均所需时间为T?i到j距离?2/平均速度＋3＋5（分钟）。由于装车时间5分钟大于卸车时间3分钟，所以这条路线上在卡车不等待条件下最多能同时运行的卡车数为：A??T/5?；其中最后开始发车的一辆卡车一个班次中在这条路线上最多可以运行的次数为（其他卡车可能比此数多1次）B??(8?60－(A?1)?5)/T?，这里(A?1)?5是开始装车时最后一辆车的延时时间。一个班次中这条固定路线上最多可能运行的总车次大约为：L?A?B，总吨数154?L。
（2）电铲能力约束：一台电铲不能同时为两辆卡车服务，所以一台电铲在一个班次中的最大可能产量为8×60/5×154（吨）。
（3）卸点能力约束：卸点的最大吞吐量为
ijijijijijijijijijijij每小时60/3=20车次，于是一个卸点在一个班次中的最大可能产量为8×20×154（吨）。
（4）铲位储量约束：铲位的矿石和岩石产量都不能超过相应的储藏量。
（5）产量任务约束：各卸点的产量不小于该卸点的任务要求。
（6）铁含量约束：各矿石卸点的平均品位要求都在指定的范围内。
（7）电铲数量约束：电铲数量约束无法用
第8页，共21页
B题参考答案
普通不等式表达，可以引入10个0—1变量来标志各个铲位是否有产量。
（8）整数约束：当把问题作为整数规划模型时，流量xij除以154为非负整数。
（9）卡车数量约束：不超过20辆。 得到的一种模型为
min105??x?ci?1j?1ijij
（0）
s.t. （1）
（2）
（3）
?xj?15
?x?154?A?Bijijij,i?1,?,10,j?1,?,5
ijfi?8?60/5?154,i?1,?,10
?xi?110ij?8?20?154,j?1,?,5
?x?x?ck?10000x ,???10000cyxxi1i2i5ii3i4ii?1,?,10
（4）
（5）
?x?qi?1ij10j,j?1,?,5
??(?30.5)?0p?iji?i?1?,j?1,2,510?(p?28.5)?0??xiji?i?1??x10
（6）
第9页，共21页
B题参考答案
?xij?xij,i?1,?,10,j?1,?,5?????154??154.
（7）
?fi?110i?7（8）
?154x?Biji,j?20
ij（9）
二．对最佳物流的结果进行派车—-第二层规划
这是组合优化中的一维背包模型，针对快速算法的要求，用启发式方法求近优解。
先用最佳物流修正Bij, 确定卡车一个班次中在这条路线上实际最多可以运行的次数。然后在以目标为出动总卡车数最少的各路线派车中，把各路线需要的卡车数e?x/(154*B)分成整数部分?e?和小数部分e??e?，进而可以分配任务让?e?辆车在i到j路线上，每辆往返运输Bij次。为了最后实现第二层规划的目标，只需联合处理所有的e??e?时把这些小数组合成最少的整数卡车数。所需总卡车数的下界显然是Y????e??。如果某种派车
ijijijijijijijijij0?i,jij?方案恰好派出Y0辆车实现了所有的xij，则其即为第二层目标意义下近优解的最优方案。但由于有联合派车而总公里数不一定最小,故不一定为全局意义下的最佳方案。
出动卡车数最少，意味着出动的卡车利用率
第10页，共21页
2003高教社杯全国大学生数学建模竞赛B题竞赛参考答案
