当前位置：文档库 › 露天铁矿生产的优化模型

露天铁矿生产的优化模型

秦鹏飞

(北方民族大学纪监审办公室，宁夏银川750021)

兰程蘧苤

[摘要]

多目标非线性规划通常是不好解决的。在此建立了连续的多目标非线性规划并向单目标线性整数规划的转化，在Li ndo 不能求

最优解的情况下退而求其次，将一个规划转化为两个规划，通过分析结合两个规划的最优解得到一组满足所有条件的近似最小总运量解和

通过将规划问题转化为排序问题得到最大产量解。

[关键词]多目标规划；线性规划；排序

此文解决的是露天铁矿生产的车辆安排问题。根据要求我们需要解决总运量最小，同时出动最少的卡车．从而降低运输成本，所以中心目标是使总运量最小和出动的卡车最少。这是一个多目标的非线性规划问题，因为问题所求的生产计划中设计到出动的电铲数、出动的卡车数、及卡车分别在那些路线上各运输次数，均要求是整数，所以此模型同时又属于整数规划问题。对问题的求解首先将多目标的非线性规划问题转化为单目标非线性规划问题。最终模型为一个单目标的线性整数规划问题。

1模型的建立

在已有的假设基础上，为了更好的解决问题，我们进行进一步假设。1)运输过程中，每一辆卡车只在一个卸点和～个铲位之间运输，因而在一个班次内只运矿石或只运岩石：2)不考虑卡车的不等待条件，认为卡车在运货过程中不会出现等待的情况：3)在班次开始时。车已经开到铲位的地点，运输工作班次开始时是针对每一辆车，从装车开始的。根据上面的分析和假设，我们分别建立基于两个原则的数学模型：

为了模型的建立，我们假设以下符号：丁表示总运量；no 表示铲位的总数；m 。表示卸点的总数；％表示第个j 铲位；m ．表示第i 个卸点；

L 表示铲位j 到卸点i 的距离；q 表示铲位j 到卸点i 的车辆数；b ，表示

一辆车在一个班次内，从铲位征0卸点i 所能运输的趟数；肘表示一辆

卡车的载重量：口表示每一辆卡车的平均时度；M 表示第i 个卸点所要求满足的产量数；n 表示实际使用中的铲位数：ao 表示卡车的总个数；“表示第．j 个铲位所拥有的矿石总量i 尼表示J 个铲位所拥有的岩石总量：肼表示卸点所需要的石料车次数；d ．，表示铲位所能铲出的矿石的车次数；如表示铲位i 所能铲出的岩石的车次数；T ．表示矿石的总运量；兀表示岩石的总运量：兀表示铲位j 运到卸点i 过程中的总运量；P 表示每个铲位的品位。

最少的总运量和最少的车完成最小的运输任务原则下的模型。

1．1在满足约束条件下建立模型(1)多目标非线性规划

我们将一条路上没有车辆运输表达为这条路上的车辆运输了0公里，假设向第i 个卸点运输的从第i 个铲位出发的卡车总共运输了玎吨公里，那么

,nO

总运量强乞乞t

(1J

I =，J ：，

瓦的运量用岛辆卡车来完成．这些卡车如果～直工作，而且运送的平均速度就是28km ／h ，也没有等待现象，那么它们这个班次所能运

『一一量一1

输的次数b ，由它们所在道路长度决定：6i =l j !』5L+墨三I ，其中是无量【

。60

纲整数，其中以下方括号表示取不大于里这个数的最大整数，这样，我

们得到野咖^M

(2)

其中，b 。，l 。都是常数，肘是常数。这样L 就咸了q 的线性函数，从而r 成了乜l I 的线性函数。将原题中的条件转化为这个优化问题的约束，得到一个多目标的优化问题，两个目标分别为最少的车辆数、最小的总运量。

这个多目标规划(规划～)是：

，，o

n O

棚神

m i n 仕∑∑Ⅱ，b ，1，M ＆m i n ∑∑铂(3)

‘，11

2，

5“=f

n O

s 上，∑咖以≥M ，i =l ，2…‰∑币∥≤凡，卸点i 是矿石卸点

J 。，

j =l ，2，。一，n o

∑咖∥≥易，卸点i 是矿石卸点，户l ，2，…，嘞

∑咖川e 一∑咖∥+0．285>t 0，卸点i 是矿石卸点，且，≤蔗，，l o

J =，

∑舻∥只一∑咖∥+0305≤o ，卸点j 是矿石卸点，且J ≤j ≤％

1=，

J=，

n 《no

。乏咖，≤品---96，j=l ，2，…，no ．；，；嘶≤嘞

哪为非负整数，苦1，2，…，m o ；户1，2，…，no

12在满足约束条件下建立模型国单目标线性规划

在上述规划中，既要减少总运量又要减少卡车数，但都要保证运输任务的完成，所以要将这个多目标规划转化为一个单目标规划。因而采用“极大极小法”。试想，如果辆卡车能够完成但辆卡车不能完成，我们只能用辆；但是也可以用多于辆的卡车完成。极大极小法即先将卡车数放到最坏的情况个，在这种情况下总运量的最小值，以保证运送石料任务的完成，然后看这些任务至少几辆卡车可以完成，得到车辆数的最小，从而得到两个目标的最小。这样，规划转化为单目标规划(规划二)：

m i n7’：∑∑唧6，z ∥睁)

i =|，：i

砒，∑q6∥≥M ，苦l ，2，…，t T $0∑中∥≤n ，卸点i 是g ：fi

J =I

卸点，卢l ，2，…，nO

∑咖∥≥B ，卸点i 是矿石卸点，／=-l ，2，…，～

n O

∑中∥f 砰J 028习≥D ，卸点i 是矿石卸点，且』≤i ≤，～

J =J

n O

∑咖∥俨,,-0305)≤D ，卸点i 是矿石卸点，且J ≤i ≤，孙凡≤，10

1，

，，'。,n O 神

∑咖F ≤96，户l ，2，…，～，∑∑呜≤ⅡD

I =11

q 为非负整数，苦1，2，…，m o ；．|：=l ，2，…，no

这样转化，相当于被动的得到卡车数最小。同样思路，我们被动考虑电铲数的最少，将工作的电铲设成电铲总数，这样整个模型就会变成线性的。在n"=no 的条件下，no 变成常数，得到(规划三)如下：

,n O

m i nT=∑∑咖一∥(5)

I =11

2』

,nO ∞

t t O

规划三约束条件除∑∑q ≤nD 变成∑∑q 户嘶其它约束条件和

‘2

J =l

‘；|I =}

规划二约束条件一样。

13模型G )单目标线性整教规划根

假设，每一车次都是满载运输，每一个卸点的矿石或岩石又都

11狐H ∞咀』)GY l l 咖

是由卡车送去，所以，每一个卸点所需要的石料量，从铲位运到每一个卸点的量以及每一个铲位所能生产的矿石量和岩石量，都可以用车次来

衡量。严格地说，一个卸点i 所需要的石料的车次数为Dl=【鲁】(上方括号表示向上取整】，一个铲位j 所能生产的矿石车次数dF[鲁】，岩石车次数也=[争】。因而整个规划转化为单目标线性整数规划(规划

四)：

m ／n ∑Za,6以㈤

2…疗b ∑n 扣F ≤如，卸点i 是矿石卸点，户

∑呜6。≥如，卸点i 是矿石卸点，j =l ，2--伽

∑呜6F(e 一0285)≥o ，卸点i 是矿石卸点，且，≤i ≤‰J =I

110

∑q6，(￡一0305)G 0，卸点i 是矿石卸点，且，≤i ≤，，l o

r|D

m O 枷

∑n 声，≤96，j=l ，2j=l 2，…，～∑∑唧=no

乞咖，≤96，，，…，～乞乞唧=no J

2』

I =，，2

田，也，如，D ；均为非负整数，苦l ，2，…，，～：户l ，2，…，no

1-4模型(4)考虑卡车在工作时间内可以有空间的单目标线性整

数规划模型

假设在从某个卸点i 到铲位／的路段上有辆卡车就可以完成任务，那么如+l 辆卡车完全没有必要。因而就是某个车有空间，空间的时间也不会太长。不妨假设这条路上车可以有空闲时，只有一个车有空闲(如果两个车都有空闲而且都有运输的时间的话，就将一个车的工作量加到另外一个车上去，直到将那个车加的没有空闲时间或者这个车没有工作：如果是后者，说明这条路上的车可以减少一辆。因而几个车有空闲而且者几个车都有必要的情况是可以和只有一个车有空闲时间的工作量等价的)假设这个车的空闲时间还可以运送L 次，说明在这条路线上只需要运送次呜一6，一伽用呜一6，一r e 代替呜6，，使得卸点的产量刚好等于

最小允许的产量，得到(规划五)如下：

1，2，‘。‘，，功

㈨，一_)以，扛l ，2，…，，砌卸点i 是矿石卸点，，=

∑乜6，--,9≥南，卸点i 是矿石卸点，y=l ，2，…，，10

，

∑咖，吧一0．285)t >0，

J =』

n O

∑咖，吧一0．305)≤D ，

1=，

卸点i 是矿石卸点，且J ≤i ≤胁

卸点i 是矿石卸点，且，≤i ≤，，l 。

∑㈨，一。)≤96，

户1，2，…，m ∑∑吩=ao

J=，

i =0=I

嘞，西，如，D l 均为非负整数，扛l ，2…m o ；户1，2．。‘no

2模型的求解规划四求解：

根据提供的材料，对规划四求解。规划四的求解主要使用Li ndo 软件解线性规划和整数规划的功能。由于Li ndo 可以容纳的整数变量的个有限，只能退而求其次，将求总运量的最小分解为求矿石总运量与岩石总运量最小两个目标。但是如果这样，电铲的工作时间不超过8小时和电铲

不超过7台，因此真正用Li ndo 解的规划省去了两个约束条

2009年6月l 上)

件。而且删去了只约束岩石运输的两个条件。所以在保证电铲工作不超时的前提下，矿石与岩石是可以同时在一个铲点拉的，但如果所得结果可能是电铲的工作时间超时，则对结果进行适当的调整。

求总运量最小的目标函数：

I O

m i n ∑∑咖南00)

柚

“，∑舻。≥n ，亡=1，2…5，∑a #b 。≤也，卸点i i 是矿石卸点，扛

“，上舻。≥n ，亡=1，2…5，乞≤也，卸点是矿石卸点，扛J =J

l ，2...5；卢1，2 (10)

柑

艺中，(￡-0285)>10，／=1，2…5，呜，嘞，D 。均为非负整数，户

J =I

l ，2…10；亡=1，2。‘5；

由于不允许卡车在完成任务后提前离开工地的条件比较苛刻，在使用L i ndo 求整数规划时没有得到最优解，所以将有一个变量无法定义为整型，因此在计算过程中则需要先判断出对结果影响较小的几个变

量，将这几个变量分别从整数变量中删去然后对得到的结果进行比较，

得出针对这一实例最好的解为：运输矿石需要出动6台电铲，分别在2，3，4，5，8，10六个铲位上，出动了10辆卡车，分别是Ⅱ12=1，d110-2，衄=1，％=l ，a-z=l ，锄-2，妇-2。求岩石总运量最小的目标：

m i n 乃=∑咖j l ,M +a 《b 《l {M (』，)

J=』10

“∑时{M >，M 3∑咖∥≥帆咖j 朋乜6∥≤乃(芦1，2，3…1o)

求解方法与上同，

(求解过程见62求岩石最小总运量的Li ndo 程

序】。最终的解为：运输岩石需出动5台电铲，分别在1，2，3，9，10五个铲位上，与上面的矿石的铲位进行比较新增加了2个铲位，因为只有7辆电铲可以使用，所以在考虑总运量较小的前提下进行调整。出动了7辆卡车，分别走的路线是％=2，啦l o=l ，幽l =l ，％=1，呦_2，L i ndo 计算出的结果与矿石的意义相同也是表示这10辆卡车分别对应这5种路线的总运量的最大值乃=28158x 154=433633

3模型改进

本文中的假设条件(1)让中间问题简化不少，但是同时也杜绝了一个卡车同时在几条路上运输的可能，当一条路上的任务完成时只能提前离开工地，从而可能增加了参加运输的车辆数。如能既将问题简化又可以让卡车在多条路上运输，不失能达到一个更好的办法。

作者简介：秦鹏飞，1978年生，男，藏族，甘肃天祝人，助教，

学士学位，宁夏大学数学与计算机学院研究生，主要从事优化理论与方

法等研究。

惨考变献]

嘲I 高教社杯垒国大学生数学建模竞赛试题．高等教育出版社，2003．

【2】飞恩科技彦品研发中心49页极大极小法M A T LA B 6．5辅助优化计算与设计【M 】，北京：电子工业出版社，2003．

趔q 户咖

m ∑“幽

嘞

，■

‘

■"

M ∑“

m ∑“访。