一、问题重述
许多现代化铁矿是露天开采的，它的生产主要是由电动铲车（以下简称电铲）装车、电动轮自卸卡车（以下简称卡车）运输来完成。提高这些大型设备的利用率是增加露天矿经济效益的首要任务。露天矿里有若干个爆破生成的石料堆，每堆称为一个铲位，每个铲位已预先根据铁含量将石料分成矿石和岩石。每个铲位至多能安置一台电铲，电铲的平均装车时间为5分钟。卸货地点（以下简称卸点）有卸矿石的矿石漏、2个铁路倒装场（以下简称倒装场）和卸岩石的岩石漏、岩场等，每个卸点都有各自的产量要求。从保护国家资源的角度及矿山的经济效益考虑，应该尽量把矿石按矿石卸点需要的铁含量（假设要求都为29.5% 1%，称为品位限制）搭配起来送到卸点，搭配的量在一个班次（8小时）内满足品位限制即可。从长远看，卸点可以移动，但一个班次内不变。卡车的平均卸车时间为3分钟。所用卡车载重量为154吨，平均时速28 。发动机点火时需要消耗相当多的电瓶能量，故一个班次中只在开始工作时点火一次。卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。电铲和卸点都不能同时为两辆及两辆以上卡车服务。卡车不会出现堵车现象，每次都是满载运输。
问题：考虑下面两条原则之一：
1.总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最小；
2.利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。
就两条原则分别建立数学模型，并给出一个班次生产计划的快速算法。针对下面实例，给出具体的生产计划，相应的总运量及岩石和矿石产量。生产计划包含以下内容：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次。并给出一个班次生产计划的快速算法。
某露天矿有铲位10个，卸点5个，现有铲车7台，卡车20辆。各卸点一个班次的产量要求：矿石漏1.2万吨、倒装场Ⅰ1.3万吨、倒装场Ⅱ1.3万吨、岩石漏1.9万吨、岩场1.3万吨。
各铲位和各卸点之间的距离（公里）如下表：
铲位1 铲位2 铲位3 铲位4 铲位5 铲位6 铲位7 铲位8 铲位9 铲位10
矿石漏 5.26 5.19 4.21 4.00 2.95 2.74 2.46 1.90 0.64 1.27
倒装场Ⅰ 1.90 0.99 1.90 1.13 1.27 2.25 1.48 2.04 3.09 3.51
岩场 5.89 5.61 5.61 4.56 3.51 3.65 2.46 2.46 1.06 0.57
岩石漏 0.64 1.76 1.27 1.83 2.74 2.60 4.21 3.72 5.05 6.10
倒装场Ⅱ 4.42 3.86 3.72 3.16 2.25 2.81 0.78 1.62 1.27 0.50
各铲位矿石、岩石数量(万吨)和矿石的平均铁含量如下表：
铲位1 铲位2 铲位3 铲位4 铲位5 铲位6 铲位7 铲位8 铲位9 铲位10
矿石量 0．95 1．05 1．00 1．05 1．10 1．25 1．05 1．30 1．35 1．25
岩石量 1．25 1．10 1．35 1．05 1．15 1．35 1．05 1．15 1．35 1．25
铁含量 30% 28% 29% 32% 31% 33% 32% 31% 33% 31%
二、基本假设
①车辆在工作过程中不出故障，最初时卡车都从铲位出发，每辆卡车每个班次都只在最初铲位点火一次，运输途中不停车卡车行驶路线为两点间的直线，各路线的交通互不影响，也不会出现堵车现象，平均速度指卡车载石料在路上行驶时的平均速度且保持不变，卡车在铲位或卸点转弯调头所用时间忽略不计，卡车卸完石料后返回到铲位。
②卡车每次从铲位到卸点都满载，某铲点矿石余量或岩石余量不足一车时不再安排运输该点矿石或岩石，卡车一次运载不能混装岩石和矿石。卡车在原路线完成任务后可转向其他路线继续工作。
③某两点间的吨公里数认为是卡车在两点间运输石料的总吨数乘以这两点间的直线距离。
④生产计划的制定只考虑本班次生产计划。
⑤把矿石按矿石卸点需要的铁含量（假设要求都为29.5% 1%，称为品位限制）搭配起来送到卸点，搭配的量在一个班次（8小时）内满足品位限制。
⑥每个铲位至多安排一台电铲。
⑦电铲和卸点都不能同时为两辆以上卡车服务。
⑧一个班次内卸点固定不动。
三、名词解释和符号约定
铲位i：i=1,2,3,…9,10，分别对应相应的铲位
卸点j：j=1,2,3,4,5， j=1时为矿石漏， j=2时为倒装场I， j=3时为倒装场II，j=4时为岩石漏，j=5时为岩场
l ：铲位i到卸点j的距离
x ：第i个铲位向第j个卸点运送石料的总量（单位：万吨）
k ：第i个铲位矿石量
y ： 第i个铲位岩石量
q ：第j个卸点的产量要求
p ：第i个铲位矿石的铁含量（品位）
t ： 电铲装车所用时间 t =3分钟=1/20小时
t ： 卡车卸车所用时间 t =5分钟=1/12小时
t ：铲位i到卸点j路线上卡车完成一次运输所用时间
c ：铲位i到卸点j路线上运输的运量（车次数）
n ：铲点i到卸点j线路上的车辆数
m ：铲点i到卸点j线路上一辆卡车每个班次内最多能跑的次数
m =8/t
N ：铲点i到卸点j线路上最多能运行的车辆
m： 卡车最大载重量 m=0.0154万吨
v： 卡车平均速度 v=28km/h
四、问题的分析
考察问题的题设和要求，需根据两条原则分别建立数学模型寻求最优生产计划。制定生产计划就是要决定应该选择由哪几个铲位分别向哪些卸点运送石料，各条运输线路运输量多大，如何安排车辆使成本最低，两个原则下都要实现多个目标。第一条原则要达到两个目标，总运量最小并且出动最少的卡车。我们先在总运量最小的要求下建立起一个初始线路模型，来初步选取合适的铲位，并确定运输线路及每条线路的运输量，并根据卡车必须满载的要求，对结果进行修正，得到每条线路运输的总车次。得到各路线的车次后，还需要合理的分配适量的卡车到各线路，使卡车用量最少，达到原则的第二个目标。第二条原则要利用现有车辆获得最大产量，我们认为是在满足各卸点产量要求的前提下，尽量使卸点的产量再增多，要保证铲位和卸点的工作量不能超出它的限度，卡车用量不能超过现有卡车数，与第一条原则一样，要注意矿石品位的限制且卡车应该被充分利用,减少卡车等待的可能。
我们先考虑三种理想情形：
①如果每个铲位的铲车在8小时之内都一直在装车，则每个铲位最多能为8*60/5=96辆卡车装石料，所以卡车运输情况至少应满足
/0.0154<96
②如果每个卸点在8小时之内都一直有卡车在卸车，每个卸点最多能允许8*60/3=160辆卡车卸石料，所以卡车运输情况至少又应满足
/0.0154<160
③由于只有7辆铲车，最多有7个铲位被利用，假如7个铲位的电铲在8小时内都能一直装车，暂不考虑石料的运送时间和卸车时间，只考虑受装车时间的限制，则最多能装0.0154*(8*60*7)/5=10.3488万吨，显然总产量不可能达到这个数量，即
<10.3488
五、模型的建立和求解
⑴第一条原则下的模型
模型I——初始模型
我们先以最小总运量为目标建立有约束的单目标线性规划模型。
①要求总运量最小，即每条运输线路上的运输量x 分别乘以该线路长度l ,使乘积的总和最小，得到目标函数：
min
②从任一铲位向各卸点运出的石料总量应不多于该铲位的石料量，即得约束条件：
k 从铲位i运出的矿石总量要小于等于铲位i的矿石量；
y 从铲位i运出的岩石总量要小于等于铲位i的岩石量；
③如果铲位i向多个卸点运送石料，可能会导致装车拥挤，安排不开，而卸点只要求满足产量要求，不会出现这样的情况。这样又得到了一个约束条件是从铲位I向各卸点运出的石料总量应满足：
④各卸点都应该满足产量要求,每个卸点每个班次从各铲位所获的石料总量应不小于该卸点的产量要求,即得约束条件：
q 从各铲位运往卸点j的石料总量应大于等于j的产量要求；
⑤要尽量把不同品质的矿石搭配起来送到卸点，搭配的量应在本班次内满足卸点的品位限制，即得约束条件：
29.5%-1% ( )/ 29.5+1% (j=1,2,3) 整理后为
( ) 0.305* (j=1,2,3)
( ) 0.285* (j=1,2,3)
综上所述，我们就得到总运量最小的初始数学模型：
目标函数：min
st. k
y
q
( ) 0.305* (j=1,2,3)
( ) 0.285* (j=1,2,3)
我们用LINGO软件对模型求解，得到结果：
总运量最小为8.482917万吨公里，选用7个铲位为铲位1，2，3，4，8，9，10
运输线路为：
铲位 卸点 运输量（车次）
1 4 81.16883
2 1 12.98701
2 2 41.12554
2 3 14.06926
3 4 42.20779
4 2 43.29004
8 1 54.11255
9 5 69.58442
10 1 10.82251
10 3 70.34632
10 5 14.83117
共11条运输线路。对结果进行分析，根据初始模型满足总运量最小时，某些铲位的石料可能被大量运走最后还剩下不足一车，这一部分将不能再运到原定卸点。在分配各线路的运量时也可能会出现不满足卡车每次都满载的情况，实例已证实这一点。由于卡车要求满载，还需对结果进行修正。修正时还应特别注意不同品位矿石搭配运送以满足卸点品位的限制，在这一前提下，尽量使距卸点近的铲位多提供石料，以保证总运量最小，我们得到修正后的结果：
铲位 卸点 运输量（车次）
1 4 81
2 1 13
2 2 42
2 3 15
3 4 43
4 2 43
8 1 54
9 5 71
10 1 11
10 3 70
10 5 14
这样我们得到修正后的最小总运量为8.569176万吨公里，运送岩石量3.2186万吨，矿石量3.8192万吨。
模型II——车辆分配调度模型
由基本假设，根据模型I的修正后结果，对车辆进行分配。
①在铲位i到卸点j运输线路上卡车运送一次所需时间包括装车时间、行驶时间、卸车时间，这样
t = + t + t
②当一条线路车辆饱和时满足
N = t / t
也就是铲位i需要不停的装车。这样每条线路上最多可通过的车辆数就有了限制，即
n N
③因为我们假定当卡车在原线路完成任务后可以转向其它线路，这样我们考虑全部线路所用总车辆应能够足以完成所有运输任务，即
④现在要使卡车数最少，即得目标函数
min
这样我们由已经得到每条线路上的运量及题中已知数据可得到车辆分配模型：
min
st. n N
我们编写了C语言程序求解，得到结果为需要卡车最少12.29497辆，对结果进行优化得最少需要13辆卡车，卡车的具体分配如下表：
线路i j 所用车号 每辆车在该线上的运输次数
10 1 1 11
10 5 1 14
2 3 1 8
2 7
2 1 2 10
3 3
2 2 3 31
4 11
4 2 4 27
5 16
3 4 5 21
6 22
10 3 6 18
7 47
8 5
1 4 8 40
9 41
8 1 9 2
10 30
11 22
9 5 11 10
12 38
13 23
关于快速算法
考虑初始模型误差只在于每条路线上最后一车可能不满载，而0.0154万吨（卡车载重）相对于铲位原有矿石或岩石量很小，线路分配的误差可以忽略，只要对各线路最后一次运输稍作调整即可。而当卡车在一条线路上最后一次运输不必满载时，该模型所得各线路的运输量即为实际运输量的一种快速算法。
⑵第二条原则下的模型
模型III——最大产量模型
①首先我们把获得最大产量作为目标函数，即
max
②从铲位i运出的石料总量应满足：
③要求产量最大，卸点就可能出现拥挤等待，卸点j能从各铲位获得的最大石料量应满足：
/0.0154<160
④要求用现有车辆来安排运输，所以用卡车总数应不超过现有卡车数，即
⑤铲车不能超过7辆，也即
<10.3488
另外，模型一所需的约束条件也是本模型所必需的，到此我们就得到了获得最大产量的单目标线性规划模型：
max
st.
/0.0154<160
<10.3488
k
y
q
( ) 0.305* (j=1,2,3)
( ) 0.285* (j=1,2,3)
我们用LINGO软件进行求解，得到最大产量为10.3488，需要根据卡车满载的要求来改进结果
六、模型的误差分析
我们建立模型时给出的每个铲位最大装车量不超过96辆的约束条件，可能会有误差：当某铲位装车量很大达到95辆时，看似满足要求，但实际上最后一车，甚至于最后两车或更多车可能不能在本班次时间内把石料卸到目的卸点。有时在满足要求时，如果不能合适的安排运输次序也可能出现不能卸完的情况，所以我们应该尽量把离铲位最近的目的卸点安排为最后几次运送。如在本实例中，铲位10向卸点1，3，5共运送95车，如果我们安排卸点1为最后一次运送的目的卸点，由于卸点1离铲位10较远，最后一车将不能在本班次时间内运到卸点1，但如果安排离铲位10最近的卸点5为最后一次运送的目的卸点，最后一车将能够在本班次时间内运到卸点5并卸完。
七、模型的评价及改进
本模型的缺点：建立模型时只考虑到本次生产计划的制定，没有动态地涉及它在整个生产过程中的影响，例如下一个班次卸点可能换位置，如果我们能预知下个卸点的位置，这个位置将可能影响本次生产计划，但我们不知道下一个班次时卸点是否变动，更不知道卸点可能会变到何处，所以这种缺陷是难以避免的。模型I得到结果后还需进行修正，我们在模型I的基础上加以改进，重新优化建立一个车次模型，得到各条线路上应运送的车次。需要增加一个约束条件：各线路运量为卡车载重的整数倍，即x /0.0154 N (N为非负整数)。另外，正如我们在模型误差分析中所述，模型会有误差，由实例中所提供的数据，分析不能卸完的情况。卡车从任意铲位行驶到任意卸点最大用时13.1分钟，考虑它把石料卸完再返回原铲位用时也不会超过半小时，可以考虑让卡车司机加班干完，况且这种情况只是在该车最后的一次运输中才可能会发生，在我们的模型I中，只有铲位10的铲车能充分利用，这种情况比较少见，而且也不一定不可避免。但在模型II中，由于每台铲车都要充分利用，这种情况就必须给予重视了。
尽管如此，我们所建模型的优点还是明显的。首先，我们对问题进行了合理和必要的假设，根据题目要求建立了简单明了而有效的数学模型，我们将多目标的需求逐步实现，模型的求解方便，所得结果令人满意，其可靠性可以信赖，有很好的实用价值，对实际生产具有很好的指导意义。
参考文献:
[1] 萧树铁等，数学实验，北京：高等教育出版社，1999.
[2] 《运筹学》教材编写组，运筹学，北京：清华大学出版社，1990.
|
发表于 2003-9-26 22:10:49
楼主