运筹学论文中英文翻译_运筹学论文的外文翻译

运筹学论文中英文翻译由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“运筹学论文的外文翻译”。

A maximum flow formulation of a multi-period open-pit

mining problem 多期露天采矿的最大流公式

Henry Amankwah • Torbjo¨rn Laron • Bjo¨rn Textorius

Abstract 摘要

We consider the problem of finding an optimal mining sequence for an open pit during a number of time periods subject to only spatial and temporal precedence constraints.This problem is of interest because such constraints are generic to any open-pit scheduling problem and, in particular, because it arises as a Lagrangean relaxation of an open-pit scheduling problem.We show that this multi-period open-pit mining problem can be solved as a maximum flow problem in a time-expanded mine graph.Further, the minimum cut in this graph will define an optimal sequence of pits.This result extends a well-known result of J.-C.Picard from 1976 for the open-pit mine design problem, that is, the single-period case, to the case of multiple time periods.我们认为在若干期间，找到一个最佳的露天采矿的开采顺序，只会受到空间和时间的优先约束。这个问题很有趣，因为这些约束通用于任何露天矿调度问题，特别是因为它是作为露天矿调度的拉格朗日松弛算法而出现的。我们可以将这种多期露天开采的问题作为一个时间扩张矿图的最大流问题来解决。此外，本图中的最小割集将定义的矿坑的最佳顺序。这个结果是J.C.Picard著名理论的延伸，J.C.Picard从1976年就研究露天矿设计问题，即，单周期的情况下，对多个时间段的研究。Introduction

Open-pit mining is a surface mining operation whereby ore, or waste, is excavated from the surface of the land, and in so doing a deeper and deeper pit is formed.Before the mining begins, the volume of the ore deposit is usually partitioned into blocks and the value of the ore in each block is estimated by using geological information from drill holes.The cost of mining and proceing each block is also estimated.A profit can thus be aigned to each block of the mine model, as illustrated in Fig.1 引言

露天开采是一个表面采矿作业，从地面挖掘出矿石或废物，因此形成一个越来越深的坑。在开始采矿前，通常把矿床划分成块，通过钻孔的地质信息估计每块矿床的价值。每块矿床的开采和加工成本也能估计。利润可以分配给每个矿山 模型，如图所示。

A fundamental problem in open-pit mine planning is to decide which blocks to mine.This is known as the problem of finding an open-pit mine design, or an ultimate contour for the pit.The only restrictions are spatial precedence relationships, stating that in order to extract any given block, so must all blocks immediately above and within a required wall slope angle.Lerchs and Gromann(1965)showed that the design problem can be stated as the problem of finding a maximal closure in a mine graph which represents the blocks and the precedence restrictions, as shown in Fig.1(for a safe slope angle of 45).Their algorithm for finding a maximal closure in the mine graph has over the years been commonly used by the mining industry for the design of open pits.在露天矿山规划中，一个基本问题是决定开采哪块矿。这被称为寻找露天矿山设计的问题，或矿井的最终轮廓问题。唯一的限制是空间优先的关系，指出为了提取任何给定的矿块，所有矿块必须在上面和在要求的壁面收敛角范围内。勒奇斯和格罗斯曼（1965）表明，设计问题可以表述为在矿图中寻找最大闭合的问题，这幅矿图能表现矿块和优先级限制，如图1所示（45°的安全坡度）。多年来，他们用来在矿图中寻找最大闭合的公式，在采矿业的露天矿设计中也被普遍使用。

The practical significance of the open-pit mine design problem makes it an important instance of the maximal closure problem(Picard and Queyranne, 1982).As shown by Picard(1976), the problem of finding a maximal closure in a mine graph can be solved as a maximum flow problem in a network derived from the mine graph, and where a minimum cut determines an optimal pit contour.Later, Hochbaum and Chen(2000)and Hochbaum(2001)developed efficient maximum flow algorithms for the open-pit mining problem.露天矿设计问题的实际意义是使其成为最大闭合问题中的一个重要实例（皮卡德和凯拉纳，1982）。皮卡德（1976）表明，在矿图中寻找最大闭合的问题

可以作为矿图中网状图的最大流问题来解决，矿图中，最小割集确定最佳矿井轮廓。后来，陈（2000）和霍赫鲍姆（2001）研究出高效的露天开采的最大流算法。

In reality, the profit of a block depends on when it is mined, for example due to discounting.This fact leads to another crucial iue in open-pit mine planning, namely scheduling.This is the proce of deciding how and when to mine the blocks so as to maximize profit(typically the net present value), while obeying the wall slope and precedence constraints, as well as various mining capacity restrictions.Contributions within open-pit mine scheduling, from the view of mathematical optimization, have been given by Gershon(1983), Dagdelen and Johnson(1986), Caccetta and Hill(2003), Ramazan(2007), Rafiee and Asghari(2008), Bley et al.(2010), and Cullenbine et al.(2011), among others.在现实中，一个矿块的利润取决于开采时，例如由于打折。这个事实导致了露天矿山规划的另一个关键问题，即调度。这是决定何时开采、如何开采并使利润最大化（通常是净现值）的过程，同时遵守墙坡和优先约束，并受到各种开采能力的限制。Gershon(1983), Dagdelen 和 Johnson(1986), Caccetta和Hill(2003), Ramazan(2007), Rafiee和Asghari(2008), Bley et al.Cullenbineetal(2011)等人已经从数学优化的角度给出了露天矿山调度的贡献。

We consider a multi-period open-pit mining problem with only spatial and temporal precedence constraints.The latter simply state that once a block has been mined, it shall remain mined.The spatial and temporal precedence constraints are generic to open-pit mine scheduling and the multi-period problem arises as a Lagrangean relaxed open-pit scheduling problem, when capacity restrictions are Lagrangean dualized.我们只考虑有空间和时间优先约束的多周期的露天开采问题。后者简单阐明，一旦矿块被开采，应当继续开采。空间和时间的优先约束通用于露天矿调度和多周期问题，它作为拉格朗日松弛的露天作业调度问题而出现，此时能力限制符合拉格朗日对偶。

It will be shown that this multi-period open-pit mining problem can be formulated as a maximum flow problem in a time-expanded mine graph, which has a copy of the mine graph for each time period.The expanded graph also contains directed arcs that model the temporal precedence relationships between the corresponding nodes in succeive copies of the mine graph;these arcs are analogous to those that model the spatial precedence relationships within each of the mine graphs.This maximum flow formulation extends the result of Picard(1976)to the case of multiple time periods.Figure 2 shows the time-expansion of the mine graph in Fig.1, for the case T = 3.可以表明，这个多期露天开采问题是可以当作时间扩张矿图中的最大流问题，时间扩张矿图中含有每个时期的矿图副本。扩张图还包含模仿矿图连续副本中相应节点间暂时优先关系的有向弧，这些弧与每幅矿图中模仿空间优先级关系的弧是相似的。这个最大流量公式是皮卡尔（1976）对于多期研究结果的扩展。图2显示了图1中矿图的时间扩展，此时T = 3。

In Sect.2 we give the mathematical model of the problem considered.In Sect.3 we present the maximum flow problem in the time-expanded mine graph and show that a minimum cut in this graph defines an optimal solution to the multi-period

第2部分给出了数学模型。第3部分呈现了时间扩张矿图中的最大流问题，并且表明，本图的最小割集定义了多期问题的最优解。

Fig.1 A 2-D block model of a mine with block profit values and its mine graph 图1

一个带有利润价值及矿图的矿块模型

Fig.2 A time-expanded mine graph with three time periods open-pit mining problem.Section 4 presents a small illustrative example.The last section gives a couple of concluding remarks.图2 三个时间段露天开采问题时间扩张矿图。

第4部分给出了一个小例子。最后一部分节给出了结束语。The mathematical model 数学模型

The following notation will be used.将使用到下面的符号。

T

number of time periods.时间段的数量

V

set of all blocks that can be mined.可以开采的矿块集合A

set of pairs(i, j)of blocks such that block j is a neighbouring block to i that must be removed before block i can be mined.矿块(i, j)的集合，矿块j与矿块i 相邻的矿块，要想开采矿块i，必须先移除矿块j contribution to the objective value if block i is mined in time period t or earlier,如果在时间段t 或早些时候开采矿块i，对于客观价值的贡献

Defining the decision variables for all对于所有的，定义决策变量

if block i is mined in time period t or earlier如果在时间段t 或早些时候开采矿块i

0

Otherwise

其他情况 the multi-period open-pit mining problem is formulated as 多期露天矿山开采问题可表述为

subject to 满足

The first and second sets of constraints are spatial respective temporal precedence restrictions.As shall be shown, an optimal solution to this problem is found by solving a maximum flow problem in the time-expanded mine graph.第一个和第二个约束集合是各个空间暂时的优先限制。正如所表明的一样，通过求解时间扩张矿图中的最大流问题，找到这一问题的最优解。The maximum flow formulation最大流公式

In order to state the time-expanded maximum flow problem, we introduce the sets of block nodes

and

and further letandbe the source and sink nodes respectively of the network, which includes arcs from the source node to the nodesnodes

to the sink node.Lettingthe maximum flow problem is as follows.and arcs from the

and

subject to

为了陈述时间扩张的最大流问题，我们引入矿块结点的集合和络的源结点和汇聚结点，包括从源结点到结点到汇聚结点的弧。让，最大流问题如下。，进一步让和成为各个网的弧，从结点

并且

满足

Here, f is the total flow, the quantityin time period t, and each

is the flow from block node i to block node j

corresponds to a forward arc between corresponding

is the flow from the source node block nodes in succeive time periods.Further,to block node i in period t, while

is the flow from block node i in period t to the sink node.An example of the maximum flow network is given in Fig.3, with 9 blocks and 3 time periods(but with only some of the arcs shown).这里，f是总流量，分量

是在时间段t内从结点i到结点j的流量，每个

对应一个连续时间段内对应矿块结点之间的正向弧。此外，源结点到矿块结点i的流量，是在时间段 t内从

在时间段 t内从矿块结点i到汇聚结点的流量。图3给出了一个最大流量网络的例子，图中有9个矿块和3个时间段（但是只表示了部分弧）。

Letbe a minimum cut in the time-expanded maximum flow network.Then

andthrough the mine graph copy for time period t.让成为时间扩张最大流网络中的最小割集。那么，图副本的割集。

Theorem 1 An optimal solution to Problem(1)is given by

是通过时间段t的矿where

is the cut

And

Proof

We study the linear programming dual of the above maximum flow problem.Letblock nodes in the network, and letaociated introducingwith

the

source

and

be the dual variables corresponding to the

be the respective dual variables the

sink.By

further

as the dual variables for the upper bound constraints, the dual problem becomes

subject to

An optimal solution to the dual problem is then(e.g., Bazaraa and Jarvis 1977)given by

理论一

问

题

(1)的最优解为

并且

证明

我们学习了上述最大流问题的对偶线性规划。让成为和网络图中的矿块结点相一致的对偶变量，让和汇聚结点相关联的对偶变量。通过进一步引入偶变量是上界约束，对偶问题变为

成为分别与源结点，由于对满足

(例如., Bazaraa 和 Jarvis 1977)给出对偶问题的最优解

Fig.3 Example of the maximum flow network(with sample arcs)图3 最大流网络图实例（样本弧）And 并且

Then, for

那么，对于

and for

对于

It then holds that 然后，得到

subject to the constraints(3)–(8)and to 满足限制条件(3)–(8)并使

with the optimal solution to Problem(2)still being optimal, since restrictingandto their respective optimal values and enforcing the equalities(9)and(10)to hold for any solutions will not affect its optimality.对于问题（2）来说，最优解仍然是最佳的，因为和r局限于各自的最佳值并且执行等式（9）和（10）以保证任何解都不会影响其最优性。

As is easily verified, constraints(3)–(5)can be removed from Problem(11), since they will always be fulfilled.By further eliminating the variables,and

from Problem(11)it is reduced to

很容易验证，限制条件（3）–（5）可以从问题（11）中去除，因为它们一直被满足。通过进一步从问题（11）中消除变量它减小为,和，subject to 满足

Now, letproblem can be stated as 现在，对于所有的问题可以陈述为

让

然后，上述

for all

Then the above

subject to满足

which is solved by 得到

Since this optimal solution is binary, it follows that it is also an optimal solution to Problem(1).The expreion for its optimal value follows directly from the above objective function.因为这个最优解是二元的，因此，它也是问题（1）的最优解。其最佳值的表达式直接符合上面的目标函数。

Since the forward arcs corresponding to the variablesfollows thatwhenever

so that

are not capacitated, it

holds.Hence, the sequence of cutsdefine larger and larger pits.The blocks mined precisely in the first time period are those corresponding to the nodes in the set the sets由于与变量得到while for t =2,...,Tit is the blocks corresponding to the nodes in

相应的向前弧是非限量的，它符合当

。因此，割集序列

时，所以，定

中的结点，当t 义越来越大的矿坑。在第一时间段，精确开采的矿块对应集合=2,...,时，Tit就是与集合中的结点相对应的矿块。An example

As mentioned in the introduction, the problem under consideration is of interest because it appears when an open-pit mine scheduling problem is Lagrangean relaxed.To illustrate this, we consider the following scheduling model, which is a special case of the model considered by Bley et al.(2010).4 例子

简介中提到，我们所考虑的问题很有趣，因为当露天矿山的调度问题是拉格朗日轻松时，它才出现。为了说明这一点，我们考虑以下的调度模型，布莱等人认为这是此模型的特殊情况（2010）。

subject to 满足

The decision variables

are

defined

as

above.(Note

that

the differenceperiod t).Further,takes the value one when block i is mined in exactly time is the profit made from mining block i in time period t,is the tonnage of block i, andLetting

is an upper bound on the tonnage mined in time period t.be multipliers aociated with the constraints on maximal tonnage mined in each time period and Lagrangean relaxing these constraints, we obtain an instance of Problem(1), with the coefficients in the objective function being the Lagrangean reduced profits

决策变量的定义同上。（注意，当矿块 i正好在时间段t开采时，差值为1）。此外，的吨位，是在时间段t开采矿块 i时获得的利润，是矿块 i是时间段t的一个上限吨位。让 作为与每个时间段内最大吨位约束相关联的乘数，拉格朗日松弛这些限制，我们得到问题（1）的一个实例，目标函数的系数成为拉格朗日下降利润。

The reader may note that Problem(1)would also arise as a column generation problem(or, pricing problem)if the linear programming relaxation of Problem(12)is solved by a column generation scheme.读者可能会注意到，如果问题（12）的线性规划松弛是通过一个列生成方案解决的话，问题（1）也将作为一个列生成问题出现（或者，定价问题）。

To illustrate the result of the theorem, we consider the block model in Fig.1 and construct an instance of Problem(12)by lettingand

for all t, for all i.Further, the profit values are discounted by a factor 0.90 for each time period.To create an instance of Problem(1)we Lagrangean relax the Capacity constraints with the multiplier values

Fig.4 Minimum cut that defines the mining sequence

图4 定义挖掘顺序的最小割集

and[These values come from the dual of the linear programming relaxation of Problem(12)].The minimum cut for the time-expanded maximum flow problem is shown in Fig.4.It indicates that blocks 2 and 3 are mined in the first time period, blocks 4 and 6 in the second, and blocks 1 and 5 in the last.The optimal profit is 12.21.为了说明该定理的结果，我们考虑到图1中的模型，通过让所有的t满足，让所有的 i满足

构造问题（12）的一个实例。而且，利润值被每个时间段的系数0.90所折扣。为了创建问题（1）的一个实例，我们 将能力约束与乘数值

进行拉格朗日松弛。[这些数值来自于问题（12）的线性规划松弛的对偶]。时间扩张最大流问题的最小割集如图4所示。结果表明，矿块2和矿3是在第一时间段开采的，矿块4和矿块6在第二时间段开采的，矿块1和矿块5是在最后一个时间段开采的。最优利润是12.21。Conclusion

We have given a maximum flow formulation of a multi-period open-pit mining problem.It extends the claic maximum flow formulation of Picard(1976)for a single time period by means of a time-expanded network.Picard’s derivation is based on a reformulation of the open-pit mine design problem into a quadratic binary program, while our proof of the validity of the time-expanded maximum flow formulation is based on linear programming duality.5

结论

我们已经给出了多期露天开采的最大流量公式。它扩充了皮卡尔(1976)经典的最大流公式，该公式借助时间扩张网络，针对单一时间段进行研究。皮卡尔的推导基于将露天矿山设计问题转化为一个二次二进制程序的再形成，基于线性规划对偶，我们正确证明了时间扩张最大流。

The problem under consideration in this paper arises naturally if all constraints of an open-pit scheduling problem but the spatial and temporal precedence restrictions are Lagrangean dualized, or priced out in a column generation fashion.For any values of the Lagrangean multipliers, the maximum flow solution in the time expanded network will correspond to a mining schedule that is feasible with respect to both the spatial and temporal precedence restrictions.The Lagrangean multipliers can then be thought of as parameters that shall be tuned such that the capacity restrictions become fulfilled, in an optimal way.Because of the prevalence of a duality gap, this strategy cannot however be expected to be sufficient to optimally solve the scheduling problem.本文中所考虑的问题是自然产生的，如果除空间和时间约束条件外，所有的 露天矿山的调度问题都是拉格朗日对偶，或被排出列生成。对于拉格朗日因子的任何值，在时间扩张网络图中的最大流的解对应一个对于空间和时间优先限制都可行的采掘计划。拉格朗日因子可以被认作应调整的参数，这样以最佳的方式实现能力限制。因为普遍存在对偶间隙，这种策略不能最好地解决调度问题。

Opportunities for further research are clearly the study of Lagrangean dual and column generation approaches based on the time-expanded maximum flow problem,as a vehicle for solving open-pit mine scheduling problems, heuristically or optimally.很明显，进一步的研究机会是基于时间扩张最大流问题的拉格朗日对偶和列生成方法的研究，作为启发式地或最佳地解决露天矿山调度问题的工具。