是
B.露天矿生产的车辆安排问题
摘要：
本文通过对原有的对多目标规划模型进行线性和加权，使得多目标的规划问题转化为单目标非线性规划问题，另外在选定7个铲点的时候，通过对于数据的处理和论证，预先选定了5个铲点，而在剩下的5个铲点中搜索最优的2个铲点，大大简化了运算量。而且搜索出的10组数据是很离散化的，涵盖了各种不同的情况，说明我们的搜索算法是可行的，是可以搜索出最优解的。而且由于采用线性加权和算法，所以能比较好的反映出各个目标函数的重要程度。另外，我们对于矿石的品位精度对于总运量和卡车数的影响进行了研究，得出的结果虽然比问题一的最优结果在运输成本上差很多，但是对于对矿石的品位精度有较高要求的时候（比如矿石的价格比较高），这种算法还是给出了最优解的。
通过在计算机上运行
程序，分别得到了问题一，二的最优解。
问题一所选用的铲点为1，2，3，4，8，9，10，共用了7辆铲车，13辆卡车，总运量为87964.8吨公里。 问题二所选用的铲点为1，2，3，4，8，9，10，共用了7辆铲车，20辆卡车，总产量为103488吨，其中岩石产量为49280吨，总运量为148771.7吨公里。
在得出最优解的同时，我们还大致排出了卡车的调度计划。
问题的提出：
钢铁工业是国家工业的基础之一，铁矿是钢铁工业的主要原料基地。许多现代化铁矿是露天开采的，它的生产主要是由电动铲车（以下简称电铲）装车、电动轮自卸卡车（以下简称卡车）运输来完成。提高这些大型设备的利用率是增加露天矿经济效益的首要任务。
露天矿里有若干个爆破生成的石料堆，每堆称为一个铲位，每个铲位已预先根据铁含量将石料分成矿石和岩石。一般来说，平均铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多能安置一台电铲，电铲的平均装车时间为5分钟。
卸货地点（以下简称卸点）有卸矿石的矿石漏、2个铁路倒装场（以下简称倒装场）和卸岩石的岩石漏、岩场等，每个卸点都有各自的产量要求。从保护国家资源的角度及矿山的经济效益考虑，应该尽量把矿石按矿
是
石卸点需要的铁含量（假设要求都为29.5%
1%，称为品位限制）搭配起来送到卸点，搭配的量在一个班次（8小时）内满足品位限制即可。从长远看，卸点可以移动，但一个班次内不变。卡车的平均卸车时间为3分钟。
所用卡车载重量为154吨，平均时速28
。卡车的耗油量很大，每个班次每台车消耗近1吨柴油。发
动机点火时需要消耗相当多的电瓶能量，故一个班次中只在开始工作时点火一次。卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。电铲和卸点都不能同时为两辆及两辆以上卡车服务。卡车每次都是满载运输。
每个铲位到每个卸点的道路都是专用的宽60
知的。
一个班次的生产计划应该包含以下内容：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次（因为随机因素影响，装卸时间与运输时间都不精确，所以排时计划无效，只求出各条路线上的卡车数及安排即可）。一个合格的计划要在卡车不等待条件下满足产量和质量（品位）要求，而一个好的计划还应该考虑下面两条原则之一：
1.总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最小；
2.利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。 请你就两条原则分别建立数学模型，并给出一个班次生产计划的快速算法。针对下面的实例，给出具体的生产计划、相应的总运量及岩石和矿石产量。
某露天矿有铲位10个，卸点5个，现有铲车7台，卡车20辆。各卸点一个班次的产量要求：矿石漏1.2万吨、倒装场Ⅰ1.3万吨、倒装场Ⅱ1.3万吨、岩石漏1.9万吨、岩场1.3万吨。
各铲位和各卸点之间的距离（公里）如下表：
的双向车道，不会出现堵车现象，每段道路的里程都是已
是
各铲位矿石、岩石数量(万吨)和矿石的平均铁含量如下表：
模型的假设：
1． 因为每个铲位到每个卸点的道路都是专用的宽60 2． 卡车每次都是满载运输的。 3． 因为产量限制的数量级是 吨以内，我们认为是没有误差的。
4． 在一个班次内的铲车固定在铲位，而且不进行移动。
5． 因为随机因素影响，装卸时间与运输时间都不精确，所以我们在安排车次的时候忽略时间的影响。
本文所用的变量和符号：
点 岩场 点 岩石漏 点 矿石漏 点 倒装场1
(吨)，而卡车满载的载重量为154吨，所以在运输结果中如果误差在10
的双向车道，所以不会出现堵车现象。
是
点 倒装场2
10个铲点分别用1，2，3….10编号 每个铲点的岩石量为
，其中
每个铲点的矿石量为
，其中
每个铲点的含铁量为
，其中
用
表示
点到铲点 的距离，其中
表示
比如：用
表示
点到铲点1的距离，
点到铲点2的距离….以此类推。
用
表示铲点 到
点卡车所跑的次数，其中
点卡车所跑的次数，
表示
所形成的矩阵。
表示卡车从铲点2到
比如：用
点所跑的次数….以此类推。
表示卡车从铲点
1到 用 用
表示在一个班次内卡车从铲点运到卸点的岩石或矿石的总质量，其中
表示在一个班次内卡车从铲点1运到卸点
的矿石的总质量
的岩石的总质量，
，
，
比如：
表示在一个班次内卡车从铲点
1运到卸点
表示矿石卸点的实际品位，其中
表示在一个班次内所有汽车的总路程
表示卸点的在一个班次内的实际产量，其中
表示卸点的在一个班次内的计划产量，其中
表示在理论上一个班次内所用卡车的总数
是
表示铲车的台数
表示第
辆汽车的工作时间。
问题的分析：
因为电铲和卸点都不能同时为两辆及两辆以上卡车服务，而且一个班次的工作时间是8个小时。电铲为卡车装车的时间为5分钟，所以一个铲点在8小时内不间断的装车，只能装
点卸车时间为3分钟，所以一个卸点在8小时内不间断的接收卡车的卸车，只能接受
一个班次总运量（吨公里）的定义为总运量的定义应该是运量与路程的乘积，也就是
，
。
（车次）。卡车在卸
（车次）。
下面针对总运量的定义给出一个结论，并给予证明：
结论：汽车在一个班次内的总运量应该近似的等于每辆汽车的满载量与总路程的1/2的乘积。 证明：
其中
，
，
，
而一个班次内所有汽车的总路程
等于
每台车转换铲点的路程，
，
，实际上这段路程全部加起来不会超过10，对于我们的总路程是不会产生太大影响的，而且车
在转换铲点的时候是空载，所以这部分实际上是没有运量的。所以
证明完毕。
所以要求一个班次内的总运量最小的问题，就可以转化为求一个班次内所有卡车的总路程最小的问题。
模型的建立：
是
根据题意,得出以下关于问题一的[1]多目标函数的最优化问题的原始数学模型:：
，
模型的转化：
在问题分析中我们已经给出证明
，除此之外，
理论上所需要的卡车总数和在一个班次内卡车在每个铲位和每个卸点之间所走
的路程
，以及卡车在每个铲位和每个卸点之间所走的次数
有关。从时间的角度考虑，为了使车辆数最小，
，
其中
，
, 再由问题的分析，一个铲点在8小时内不间断的装车，只能
，
，
，
假定每辆车都工作了8小时，则这时的
装96车次。一个卸点在8小时内不间断的接收卡车的卸车，只能接受160车次。也就是说，
这个约束条件可以转化为以下两个约束条件：
，
；
。各矿石卸点的实际品位
，
，
这个条件可以转化为矩阵
是
的非零列向量的个数小于等于7，又因为矩阵
中的每一个元素
（车次）都是大于等于0的，所以该条
件可以转化为[2]矩阵
的列元素的和大于0的列数小于等于7。这样模型的目标函数和约束条件都可以化成以
为自变量的函数。则原始模型可以转化为以下形式：
，
然后，再通过[3]线性加权和方法，对于目标函数
把这个多目标函数的最优化问题就转化成了关于单变量
模型的求解及计算机实现：
分别引入权系数
的单目标函数
，
的最优化问题。
是
铲位和卸点位置的二位示意图如下：
因为题目并没有要求我们考虑铲车的成本问题，所以在计算时我们先按照7台铲车全部被使用的时候开始计算的。
1． 铲车位置的确定：
因为一共有10个矿点，铲车只有7台，显然做不到每个铲位都安排一辆铲车。所以铲车位置的确定就是很重要的，他们的确定很可能会影响最终的结果。从最简单的角度来看，在运输的时候，铲位如果距离卸点的距离越近那么所需的成本则最小。在选取铲位的时候，我们应该优先考虑那些距离卸点较近的铲位。这样我们就把距离5个卸点最近的点先确定，这样，共有1，2，9，10四个点。（其中铲位10距离岩场和倒装场2的距离在10个铲位中都是最小的）。另外，运矿石的时候，因为品位限制铁的最高含量为30.5%,而大部分铲位的铁含量基本都比30.5%大，只有1，2，3铲位的铁矿石的铁含量是低于这30.5%的，所以为了达到铁矿石的品位要求，应该尽可能的把这3个铲位都考虑进去。而且3铲位距离卸点的距离也比较近，所以我们认为有必要把这3这个铲位作为首选进入7个铲位之中。
这样我们就在7个铲位中率先确定了1，2，3，9，10这五个点，剩下的两个铲位由于距离各个卸点的距离都比较远，在选定的时候无法确定，所以应该在剩下的4，5，6，7，8这五个点中每次选择2个点，计算其总运量和需要的总车数，这样共会得到10组不同的数据，在进行比较以后，再选取最优的一组作为我们最终确定的铲位方案。
2．权系数的确定：[4]权系数由试探和修正确定，我们发现当
得到的结果最优，而且满足题里所给出的各种条件。当
20或者品位不满足
的时候
，所
取别的权值的时候，要么理论上的卡车数大于
的要求，要不就是达不到最优解。
是
对权的说明：两个权值
反映了对万吨公里数和卡车数的对总成本重要程度。也就是说我们在搜索
的时候
，
和
的比值
的时候，卡车数是优先于万吨公里数的。当
约为1：10较符合实际。从实际的角度来讲，让较少的卡车多跑一些路程要比让较多的卡车少跑一些路程所需要的成本要少。
3．搜索算法初值的确定：通过计算机模拟试验得出一个符合要求的初始值。
4．铲位的搜索算法：每个铲位确定的时候，搜索每个铲位的在满足各个卸点的产量和品位的要求情况下，总运量最小的同时，总车数最小的方案。因为矿石的品位要求铁含量最高为30.5%，所以为了满足卸点的品位要求，从一个铲位向卸点运输显然是无法满足品位要求的。所以这就有必要从1，2，3这三个铲位也向矿石卸点运输，从而达到题目所要求的品位要求。在运矿石的时候，我们应该尽可能的从邻近的铲位向卸点运输，当达到一个品位所能允许的最大吨位的时候再靠1，2，3铲位的矿石来补足。所以为了能够找到最优解，我们尽可能的把满足每个矿石卸点所有的分配方案都计算出来。最后我们用[5]
优化函数 搜索了10组方案。如表一所示：
表一：以总运量和卡车数为目标函数搜索得到的结果
在选定最优解的时候，我们发现，如果总路程和总车数稍微放大一点的话，那么就会剩下一辆铲车，因为题目并没有给我们铲车的成本数值，所以铲车的数目并不是选取最优解的决定因素。而且从实际的角度考虑，车的耗油量很大，每个班次每台车消耗近1吨柴油。发动机点火时需要消耗相当多的电瓶能量，故一个班次中只在开始工作时点火一次，所以卡车运行的成本应该比铲车运行的成本要高，所以我们应该选择总运量和总车
是
数最小的解作为最优解。
对于程序搜索结果的分析，通过表一我们可以看到，该算法是比较好的，因为它尽可能的搜索到了各种情况的点。也就是说，它所选取的点是比较离散的，能够更好的描绘对于各个点的选取在总成本中的重要性。 最终我们选择了4，8点作为问题的最优点，也就是说7个铲点我们选择了1，2，3，4，8，9，10这7个铲点，选择这7个铲点得到总
路程和理论上所需 要的车次数都是最小的。至于实
际能不能够达到，既需要我们对这个方案进行调度。因为随机因素影响，装卸时间与运输时间都不精确，所以排时计划无效，我们只求出了一个大概的时间分配方案。如表二所示：
表二：问题一最优解的卡车调度计划
是
每条线路的运输车次所构成的矩阵
如表三：
表三：问题一每个铲点到矿点的运输车次
总运量为87964.8吨公里，共需要13台卡车，7台铲车。
在计算机进行搜索的时候，我们发现如果把卸点矿石的品位也作为一个目标函数进行加权的话，也可以得
到一系列的最优解。但是这组最优解除了矿石品位比表一中的数据更接近于29.5%,但是其余的数值（比如：总运量，卡车数）都远远大于表一中的数据。也就是说，为了使品位的精度控制更高，那么就要付出更多的运输成本。这与实际的吻合是相当好的。但是对于本题的要求，对于品位精度的控制没有那么严格的情况下，无疑表一中的数据是最好的。但是如果为了得到品位精度较高的矿石（矿石比较贵重，比一般的运输成本要高）的时候，这种算法就是比较有效的。
问题二的数学模型：
是
针对问题二的数学模型和问题一的数学模型基本一样，只是目标函数有所改变。约束条件其中的卡车数由原来的小于等于20变成等于20。铲车数由原来的小于等于7变成等于7（为了达到最大产量）。所以问题二的数学模型为：
经过类似于模型一的变换，也可以将模型二转化为目标函数和约束条件都以
再通过线性加权和的方法，对于目标函数
题就转化成了关于单变量
的单目标函数
分别引入权系数
为自变量的函数。然后，
，把这个多目标函数的最优化问
的最优化问题。
在经过试探和修正，我们发现
的时候，能得到岩石产量的极大值的同时，总产量也尽
（吨）
可能的大，这样的结果是比较好的。其中岩石产量的极大值=
由于模型一中我们的选择铲点的方案求出的结果很好，给予一中所论述的理由，我们在这里依然按照模型一中的选点规则进行选点。也就是说先确定1，2，3，9，10四个矿点，然后再对剩下的5个矿点每次取出两个矿点进行搜索，得到以下的表四：
是
表四：以总产量，岩石总产量和总运量为目标函数搜索得到的结果
通过该易得就找到点，依然是个铲点无论是从总运量都是最优题二所选用2，3，4，8，了7辆铲车，
总产量为103488吨，其中岩石产量为49280吨，总运量为148771.7吨公里。
以下是我们的调度大致计划，如表五所示：
表五：问题二最优解的卡车调度计划
表我们很容了最优的铲4，8，这两从总产量还的角度来看的。所以问的铲点为1，9，10，共用20辆卡车，
是
每条线路的
构成的矩阵 示： 表六：问题到矿点的运
运输次数所如表六所
一每个铲点输车次
模型评估：
优点：我们所建立的模型通过对原有的对多目标规划模型进行线性和加权，使得多目标的规划问题转化为单目标非线性规划问题，另外在选定7个铲点的时候，通过对于数据的处理和论证，预先选定了5个铲点，而在剩下的5个铲点中搜索最优的2个铲点，大大简化了运算量。而且搜索出的10组数据是很离散化的，涵盖了各种不同的情况，说明我们的搜索算法是可行的，是可以搜索出最优解的。而且由于采用线性加权和算法，所以能比较好的反映出各个目标函数的重要程度。另外，我们对于矿石的品位精度对于总运量和卡车数的影响进行了研究，得出的结果虽然比问题一的最优结果在运输成本上差很多，但是对于对矿石的品位精度有较高要求的时候（比如矿石的价格比较高），这种算法还是给出了最优解的。
缺点：由于采用线性加权和的算法，导致合理的权值的确定是很麻烦的，需要经过多次的调试才能最终确定最后的权值。而且模型在计算中作了一些舍入和取整，不可避免的产生了一些误差，但是这些误差的是可以
是
容忍的。
参考书目：
[1] 邢继祥 张春蕊等，最优控制应用基础，北京，科学出版社，2003年8月
[2] 北京大学数学系几何与代数教研室代数小组，高等代数，北京，高等教育出版社，1988年3月 [3] 胡达，多目标规划有效性理论，上海，上海科学技术出版社，1994年12月 [4] 郭晶，
辅助优化计算与设计，北京，电子工业出版社，2003年1月
[5] 萧树铁，数学实验，北京，高等教育出版社，1997年7月
附录：
源程序：
%目标与约束函数的实现程序 function [f,g]=yunkuang(x)
%x为自变量，f为优化目标，g为约束条件 Dis=[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
];
quan=[2000,1000]; hl=[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];
是
qudian=[1 2 3 4 8 9 10]; d=Dis([3 4 1 2 5],qudian); pin=hl(3,qudian); %f1为总路程函数 f1=0; for i=1:5 for j=1:7
f1=x((i-1)*7+j)*d(i,j)+f1; end end times=0; for i=1:35
times=times+x(i); end
%truck为卡车辆数
truck=(f1*2/28+times*8/60)/8; for i=3:5 for j=1:7
pei((i-3)*7+j)=pin(j)*x((i-1)*7+j); end end for i=1:3 peibi(i)=0;
是
timestot(i)=0; end for i=1:3 for j=1:7
timestot(i)=x((i+1)*7+j)+timestot(i); end end for i=1:3 for j=1:7
peibi(i)=pei((i-1)*7+j)+peibi(i); end
peibi(i)=peibi(i)/timestot(i); end cha=0; for i=1:3
cha=(peibi(i)-29.5)*(peibi(i)-29.5)+cha; end
f=(f1+truck*quan(1)+cha*quan(2)); for j=1:5 sumj(j)=0; end for j=1:5 for i=1:7
是
sumj(j)=sumj(j)+x((j-1)*7+i)*154; end end
%产量约束条件
sumjx=[1.3 1.9 1.2 1.3 1.3]*1e+4; for i=1:5
g(i)=sumjx(i)-sumj(i); end for i=1:7 sumi1(i)=0; sumi2(i)=0; sumi3(i)=0; end for i=1:7 for j=1:2
sumi1(i)=sumi1(i)+x((j-1)*7+i)*154; end end for i=1:7 for j=3:5
sumi2(i)=sumi2(i)+x((j-1)*7+i)*154; end end
是
for i=1:7
sumi3(i)=(sumi1(i)+sumi2(i))/154; end
sumi2x=hl(1,qudian)*1e+4; sumi1x=hl(2,qudian)*1e+4; %岩石矿石的最大运量约束 for i=1:7
g(i+5)=sumi1(i)-sumi1x(i); g(i+12)=sumi2(i)-sumi2x(i); end
%铲车装车时间约束 for i=1:7
g(19+i)=sumi3(i)-96; end
%卸车时间约束 for i=1:5
g(26+i)=sumj(i)/154-160; end
%卡车辆数约束 g(32)=truck-20;
%优化执行程序 %x0为初始值