第五部分

决策分析

389

!"#

多目标决策分析（Multi-Criteria Decision Analysis，MCDA）是依据备择决策方案（Alternatives）

的不同特征（属性、准则或目标）构造偏好模型，用以辅助决策、󰄁升决策效率与效果的一门学

科。假设备选决策方案集合A = {A

}

i=1

，决策准则集合C = {C

}

j=1

，如下表所示：表中，第一

表 27.2: MCDM决策矩阵

··· C

··· ω

··· a

行是准则集合C，第二行表示准则的权重向量ω，第一列表示备选决策方案集A，a

表示方案A

在

准则C

下的表现。

MCDA解决的问题包括：搜索最佳决策方案、对决策方案分类、根据偏好对决策方案排

名、 󰄀 述每个决策方案同时满足所有准则的程度，经典的方法包括数据包络分析方法（Data

Envelopment Analysis，DEA）、层次分析法（ Analytic Hierarchy Process，AHP）[364, 365]、

ELETRE[366]、PROMETHEE和TOPSIS。

$%"&'#(

391

)!*+",$

第二十八章数据包络分析

)!*+",$%"&'#(

28.1 引言

效率（绩效）评价在现实生活中是一项常见并且重要的工作。但是，当被评价系统存在多输入

和多输出指标时，绩效评价工作则变得非常困难，尤其当输入和输出指标之间存在复杂的甚至是未

知关系时，评价工作将更加难以进行。数据包络分析（Data Envelopment Analysis，DEA）作为

处理多输入多输出系统评价问题的一种有效的非参数效率评价方法，在组织相对效率评价和组织

改进投入产出效率方面越来越受到重视。

DEA方法是由Abraham Charnes、 William Cooper和Edwardo Rhodes[367]基于“相对效

率”（Relative Efﬁciency）概念发展而来的，常用于评价多输入-多输出类型决策单元（Decision

Making Unit, DMU），如医院、银行、政府部门、生产供应商等企事业单位的生产或服务的相对

效率。在数据包络分析框架下，相对效率定义为“加权输出总量与加权输入总量的比值”。

假设有n个性质完全相同的生产厂商，都是使用原材料A生产出产品B，各厂商的生产状况如

下表：

DMU A B

1 x

2 x

... ... ...

n x

如果需要评价各个厂商的生产效率，就需要一个标准的定量指标。对于单投入-单产出的生

产问题，最简单的评价指标莫过于原材料利用率：单位原材料能够产出的产品数量，那么，对

于DMU

，其原材料利用率e

= y

，则原材料利用率越高的厂商可以认定其生产效率越高。

393

搜索与排名 Searching and Ranking

!"#

然而，原材料利用率忽略了投入-产出价格因素的影响，皆假设“各个厂商以相同的价格购买

原材料，产品的定价也是相同的”。实际上，如果从投入-产出的价值（考虑了价格因素，以金钱作

为度量单位）角度出发，评价结果不会有任何变化。

在实际生产过程中，单投入-单产出的生产情形几乎不存在，比较常见的利用多用原材料生产

多种产品，即多投入-多产出问题。假设存在n个同种类型的决策单元，每个决策单元有m个输入

量x

,i=1,...,m，s个输出量y

,r =1,...,s。

表 28.1: 决策单元的输入输出

DMU I

... I

... O

1 x

... x

... y

2 x

... x

... y

... ... ... ... ... ... ... ... ...

n x

... x

... y

每个DMU使用s种原材料I

,...,I

生产m种产品O

,...,O

。

从经济学角度来看，各个决策单元对输入原料的利用率千差万别，要衡量DMU使用原料生产

产品（输出）的效率，数据包络分析为任意决策单元DMU

定义如下形式的相对效率指标：

(28.1)

其中，u ∈ R

表示输入权值向量，w ∈ R

表示输出权值向量。此外，假设所有生产厂商的相对效

率值均小于1，则经典的CCR模型可以表示成如下形式的线性规划问题：

max

w,u

s.t.

≤ 1,j =1, 2,...,n

w ≥ 0,u≥ 0

(28.2)

从以上模型可以发现，每个决策单元实际上都是从自身角度出发，倾向于选择于自己最有利

的输入- 输出“价格”（w, u）[368]。同时，模型对应的最优权值也反映出目标决策单元DMU

对输

入-输出的󰔁种评价。

由于计算分式规划问题比较复杂，引入Charnes-Cooper变换，

➊

得到如下形式的线性规划模

型：

max

µ,ν

min

µ,ν

s.t. µ

− ν

≤ 0,j =1, 2,...,n s.t. µ

− ν

≤ 0,j =1, 2,...,n

=1 µ

ν ≥ 0,µ≥ 0 ν ≥ 0,µ≥ 0

(28.3)

➊ 令t =1/w

，ν = tw，µ = tu，则有u

= µ

/ν

，ν

= tw

=1。

$%"&'#(

394

)!*+",$

28.1. 引言

!"#

前者为输入型CCR模型，后者为输出型CCR模型。

➊

在评价决策单元是否为DEA有效时，需要判断是否存在最优解ν

∗

,µ

∗

，满足

∗

> 0,µ

∗

> 0,µ

∗T

= 1(ν

∗T

= 1) (28.4)

从计算的角度分析，单纯形法（Simplex Method）就可以有效地求解CCR模型[369]，由

于DMU的个数通常远大于用于决策的特征属性（输入-输出）的数目，使用对偶模型对󰄁升求

解性能大有裨益。根据线性规划中的对偶理论（Duality Theory），乘法形式（ Multiplier Form）

的CCR模型等价对偶形式，也称包络形式（Envelopment Form）如下所示：

min θ max θ

s.t.

(

i=1

≤ θx

s.t.

(

i=1

≤ x

(

i=1

≥ y

(

i=1

≥ θy

≥ 0,i=1,...,n λ

≥ 0,i=1,...,n

(28.5)

对输入型CCR包络模型添加松弛变量S

−

，转化为下式：

min θ

s.t.

(

i=1

+ S

−

= θx

(

i=1

− S

= y

≥ 0,i=1,...,n

−

≥ 0,S

≥ 0

(28.6)

根据线性规划对偶理论中的松紧定理，判断决策单元DMU

是否DEA有效，需要首先判定模

型的最优解λ

∗

−∗

+∗

, θ

∗

是否满足

∗

=1,S

−∗

=0,S

+∗

=0 (28.7)

无论是利用(28.3)还是(28.6)，直接判断DEA有效性都不容易。为此，通过引入非阿基米德无穷

小量（non-Archimedean）ε > 0的概念[370, 303]，可以成功地解决计算上和技术上的困难。

max

min θ − ε(1

−

)

s.t. µ

− ν

≤ 0,j =1, 2,...,n s.t.

(

i=1

+ S

−

= θx

(

i=1

− S

= y

ν ≥ ε λ

≥ 0,i=1,...,n

µ ≥ ε S

−

≥ 0,S

≥ 0

(28.8)

➊ DEA模型根据目标函数的不同，可以分成两类：投入型（Input-Oriented）和产出型（Output-Oriented）。产出型 DEA模型是在给定

投入生产要素下最大化生产产出，而投入型是在给定产出水品下最小化投入成本。

$%"&'#(

395

)!*+",$

搜索与排名 Searching and Ranking

!"#

28.2 两阶段方法

魏权龄在[371]给出一个引理：考虑线性规划问题

min c

s.t. Ax = b

x ≥ 0

(28.9)

若其最优解集合为E，则存在¯ε > 0，对于任意的ε ∈ (0, ¯ε)，线性规划问题

min c

x − εd

s.t. Ax = b

x ≥ 0

(28.10)

的最优解也是下面线性规划问题的最优解：

max d

s.t. x ∈ E

(28.11)

对于含有非阿基米德无穷小量的对偶CCR模型：

min θ − ε(1

−

)

s.t.

(

i=1

+ S

−

= θx

(

i=1

− S

= y

≥ 0,i=1,...,n

−

≥ 0,S

≥ 0

(28.12)

可以使用2-阶段法（阶段I与阶段II）求解：

（I）求解对偶规划

min θ

s.t.

(

i=1

+ S

−

= θx

(

i=1

− S

= y

≥ 0,i=1,...,n

−

≥ 0,S

≥ 0

(28.13)

的最优解θ

∗

。如果θ

∗

< 1，则DMU

不为DEA弱有效；若θ

∗

=1，则转到阶段II（将最优

值θ

∗

=1带入上述模型中得到其最优解集合）。

$%"&'#(

396

)!*+",$

28.3. DEA变体模型

!"#

（II）求解下面问题的最优解λ

∗

−∗

+∗

：

max 1

−

s.t.

(

i=1

+ S

−

= x

(

i=1

− S

= y

≥ 0,i=1,...,n

−

≥ 0,S

≥ 0

(28.14)

如果1

−∗

+∗

̸=0，则DMU

弱DEA有效；否则DMU

DEA有效。

对于n个决策单元组成的评价系统，假设参考集为

T = {(x

)|i =1,...,n} (28.15)

形如下面的生产可能集

CCR

= {(x, y)|

i=1

≤ x,

i=1

≥ y,λ

≥ 0,i=1,...,n} (28.16)

与CCR模型相对应。判断决策单元是否DEA有效，本质上是检验决策单元是否落在生产可能集的

生产前沿面上。

假设λ

∗

−∗

+∗

, θ

∗

是通过2−阶段法求解不含有非阿基米德无穷小量的CCR原始模型与对偶

模型的最优解，令

ˆx

= θ

∗

− S

−∗

ˆy

= y

+ S

+∗

(28.17)

称(ˆx

, ˆy

)是DMU

在生产可能集T

CCR

的生产前沿面上的“投影”，根据“投影定理”[371]，它们

是DEA有效的。

DEA能够计算分配效率（Allocate Efﬁciency，AE）和技术效率（Technical Efﬁciency，TE），

后者分为规模效率（Scal e Efﬁciency，SE）和纯技术效率（Pure Technical Efﬁciency，PTE），隐

含着很强的经济学背景，其中，技术效率与规模效率分别是生产函数和生产函数的规模收益不变性

质的推广[371]。

28.3 DEA变体模型

1984年，Banker等人[372]󰄁出一种新的模型――BCC模型，使用凸约束（Convexity Con-

straint）度量决策单元的技术效率。在凸约束中，可以确保复合决策单元与被评测单元大小相当。

BCC模型估计的相对效率值不小于对应CCR模型计算的相对效率分值。BCC与CCR模型不同，后

者是基于规模收益不变（Constant Return to Scales，CRS）的假设，而BCC则适用于规模收益可

$%"&'#(

397

)!*+",$

搜索与排名 Searching and Ranking

!"#

变（Variable Return to Scales，VRS）的场景。

max µ

− u

min θ

s.t. µ

− ν

− u

≤ 0,i=1,...,n s.t.

(

i=1

≤ θx

(

i=1

≥ y

ν ≥ 0,µ≥ 0

(

i=1

=1, λ

≥ 0,i=1,...,n

(28.18)

此为输入型BCC模型，而输出型BCC模型如下所示：

min ν

+ u

max θ

s.t. ν

− µ

+ u

≥ 0,i=1,...,n s.t.

(

i=1

≥ θy

(

i=1

≤ x

ν ≥ 0,µ≥ 0

(

i=1

=1, λ

≥ 0,i=1,...,n

(28.19)

1985年，F

are和Grosskopf[373]在使用非参数的费用方法研究规模收益时，使用的DEA模型称

为FG模型，其基本假设是规模收益递减：

max µ

− u

min θ

s.t. µ

− ν

− u

≤ 0,i=1,...,n s.t.

(

i=1

≤ θx

(

i=1

≥ y

ν ≥ 0,µ≥ 0,u

≥ 0

(

i=1

≤ 1, λ

≥ 0,i=1,...,n

(28.20)

1990年，Seiford与Thrall[374]󰄁出了基于规模收益递增假设下的ST模型：

max µ

− u

min θ

s.t. µ

− ν

− u

≤ 0,i=1,...,n s.t.

(

i=1

≤ θx

(

i=1

≥ y

ν ≥ 0,µ≥ 0,u

≤ 0

(

i=1

≥ 1, λ

≥ 0,i=1,...,n

(28.21)

1985年，Charnes等人[375]认为CCR 模型中关于生产函数凸性的假设在󰔁些条件下是不合

理的，将目标规划首次应用到DEA方法，推出了一种新的效率评价模型――加法模型（Additive

Model）（亦称“C

模型”）。加法模型基于规模收益可变假设，最大化被评估决策单元与有效

$%"&'#(

398

)!*+",$

28.3. DEA变体模型

!"#

前沿面（或包络面）的ℓ

距离。

max ||(x

) − (

(

i=1

(

i=1

)||

s.t. x

≥

(

i=1

≤

(

i=1

(

i=1

≥ 0,i=1,...,n

(28.22)

由于

||(x

) − (

(

i=1

(

i=1

)||

= |x

−

(

i=1

| + ···+ |x

−

(

i=1

| + ···+ |y

−

(

i=1

| + ···+ |y

−

(

i=1

=(x

−

(

i=1

)+···+(x

−

(

i=1

)+···+(

(

i=1

− y

)+···+(

(

i=1

− y

)

−

(28.23)

从而，可以得到下面等价的加法模型：

max 1

−

s.t. S

(

i=1

− y

−

= x

−

(

i=1

(

i=1

≥ 0,S

−

≥ 0, λ

≥ 0,i=1,...,n

(28.24)

原始的DEA模型对权重无任何限制，允许被评估决策单元选择对于自身最有利的权重，得出

的结果明显不符合实际，因此，人们一直重视对权重的研究。1986年，Charnes等人[376]通过调整

锥比率以反映决策者的偏好或者意愿，给出一个含有偏好的C

WH模型。

28.3.1. 一般性DEA模型

为了分析DEA模型的一般性质，避免无谓的重复工作，研究人员开始构建综合的数据包络分

析模型。1988年，Charnes等人[377]给出了第一个综合的DEA 模型C

WY，包含CCR模型，加法

模型和C

WH等模型，遗憾的是C

WY 模型不能直接进行编程实现。根据[378]构造的一般性DEA

$%"&'#(

399

)!*+",$

搜索与排名 Searching and Ranking

!"#

模型，可以统一CCR、BCC、FG与ST 模型为下面形式的输入型综合DEA模型：

max µ

− δ

min θ

s.t. ν

− µ

+ δ

≥ 0,i=1,...,n s.t.

(

i=1

≤ θx

(

i=1

≥ y

ν ≥ 0,µ≥ 0 δ

(

i=1

+ δ

(−1)

n+1

)=δ

(−1)

≥ 0 λ

≥ 0,i=1,...,n+1

(28.25)

其中，δ

∈ {0, 1},i =1, 2, 3。当δ

=0时，模型(28.25)就是标准的输入型CCR模型；当δ

1, δ

=0时，模型退化为输入型BCC模型；当δ

=1, δ

=0时，模型就是输入型FG模型；

当δ

=1, δ

=1时，就是输入型ST模型。

2004年，Yun等人[379]应用增强的切比雪夫标量化函数构造如下形式的一般型数据包络分析模

型（GDEA）：

max

µ,ν

∆

s.t. ∆ ≤

+ α(µ

− y

)+ν

(−x

+ x

)),i=1,...,n

1+ν

1=1

µ, ν ≥ ε

(28.26)

其中，α > 0需要根据具体问题做适当调整；ε > 0是一个非阿基米德无穷小量，一般取值范

围在[10

−6

, 10

−5

]；

是向量y

− y

与−x

+ x

中数值最大的元素与对应权值的乘积。如果目标

值∆ =0，则对应决策单元DMU

称为α−有效；若∆ < 0，那么决策单元就是α−无效的。

28.3.2. 退化的DEA模型

原始的CCR模型主要用以解决多输入多输出问题，在现实评价问题中，常会遇到诸如只有输

入或者输出的“退化”情况。1995年何静给出了评价只有输出（入）指标的模型，并讨论了其相关

性质[380]。

假设所有决策单元输入指标相等（等输入），那么根据分式CCR模型(28.2)有：

max (

)

s.t. (

)

≤ 1

µ ≥ 0, ν ≥ 0

(28.27)

由于ν

= ν

= ...= ν

= λ

, ∀ν ≥ 0，若取µ = µ/λ

，上面的模型等价于：

max µ

min

(

i=1

s.t. µ

≤ 1,i=1, 2,...,n ⇒ s.t.

(

i=1

≥ y

,i=1, 2,...,n

µ ≥ 0 λ

≥ 0,i=1, 2,...,n

(28.28)

$%"&'#(

400

)!*+",$

28.3. DEA变体模型

!"#

类似地，可以得到相应的等输出CCR模型：

min ν

max

(

i=1

s.t. ν

≥ 1,i=1, 2,...,n ⇒ s.t.

(

i=1

≥ x

,i=1, 2,...,n

ν ≥ 0 λ

≥ 0,i=1, 2,...,n

(28.29)

对于等输出的CCR模型(28.28)，其对偶形式可以通过变换

⎧

⎪

⎨

⎪

⎩

t =

(

i=1

θ =1/t

= λ

(28.30)

得到如下形式的等价模型：

max θ

s.t.

(

i=1

≥ θy

(

i=1

≥ 0,i=1,...,n

(28.31)

对于等输入的输出型BCC模型：

min ν

+ v

s.t. ν

− µ

+ v

≥ 0

µ ≥ 0, ν ≥ 0

(28.32)

有ν

+ v

= ...= ν

+ v

= θ，则上述模型等价于

min θ

s.t. θ − µ

≥ 0

µ ≥ 0, θ ≥ 0

(28.33)

设置新的权值向量ω = µ/θ，则可以得到等价的线性模型如下：

max ω

s.t. ω

≤ 1

ω ≥ 0

(28.34)

由此可知，等输入的输出型CCR模型与等输入的输出型BCC模型等价[381, 382, 383]。

如果所有决策单元只有输出（输入相等均为0），根据输出型CCR对偶模型(28.5)，取x

=0,i=

$%"&'#(

401

)!*+",$

搜索与排名 Searching and Ranking

!"#

1,...,n，则可以得到下面形式模型：

max θ

s.t.

(

i=1

≥ θy

≥ 0,i=1,...,n

(28.35)

由于在θ =1, λ

=1, λ

=0,i ̸= k是模型的一个可行解，显然θ = k, λ

= k, λ

=0,i ̸= k也是其可

行解（k =1, 2,...）。显然，模型最优效率值 θ

∗

>M,∀M>0。所有的决策单元的最优效率值均

是无穷的，有效的与无效的决策单元无法区分，因此结果是没有意义的[381]。对于只有输入指标

的CCR模型，可以得到相同的结论。

根据输出型BCC对偶模型(28.19)，只要取x

=0,i =1,...,n，则可以得到只有输出的BCC模

型：

max θ

s.t.

(

i=1

≥ θy

(

i=1

≥ 0,i=1,...,n

(28.36)

与等输入的输出型CCR模型(28.31)形式完全相同，是等价的，从而与等输入的BCC模型也是等价

的，输出型BCC模型中输出指标是最重要的。类似地，可以得到输入型模型（BCC与CCR）的等

价对应关系。

如果决策单元只有一个输入（输出）指标，但各个决策单元的输入（输出）指标不全相等，在

规模收益不变的假设前󰄁下，可以通过同时放缩一定比例的输出（输入）指标，使得决策单元的单

个输入（输出）指标相等，从而转换为等输入（等输出）的应用环境。

我们对规模收益变化不做任何假设，则CCR模型就退化为单输入-多输出（多输入-单输出）的

模型，根据模型(28.3)可得：

max

µ,ν

min

µ,ν

s.t. µ

− νx

≤ 0,i=1, 2,...,n s.t. µy

− ν

≤ 0,i=1, 2,...,n

νx

=1 µy

ν ≥ 0,µ≥ 0 ν ≥ 0,µ≥ 0

(28.37)

由模型可以明显的看到，对于单输入-多输出的CCR模型，如果存在x

=0，模型无可行解；类似

地，对于多输入-单输出的CCR模型，如果存在y

=0，则模型亦无可行解。否则，可以将模型中

的等式约束带入到第一个约束条件，可得：

max

min

s.t. x

− x

≤ 0,i=1, 2,...,n s.t. y

− y

≤ 0,i=1, 2,...,n

µ ≥ 0 ν ≥ 0

(28.38)

$%"&'#(

402

)!*+",$

28.3. DEA变体模型
!"#
目前，无输出类型的DEA模型已经得到广泛应用：多目标规划[384, 385]、智能系统[386, 387]、
数据挖掘[388]、偏好投票系统[389, 390]、技术选择[391, 392, 393]、信息检索与搜索引擎排名聚
合[394]等。
28.3.3. 逆数据包络分析模型
逆DEA的思想源于构建投资预测模型（IPM）[395, 396]，在已知其输入输出变量和相对效率
分值的前󰄁下，对于󰔁个决策单元，在部分输入发生改变时，预测其输出所发生的改变。
假设存在决策单元DMU
1
,...,DMU
n
，构建一个虚拟决策单元DMU
n+1
，逆DEA模型通过
其输入输出值同其他n个决策单元建立联系，不妨假设其输入向量为x
n+1
∈ R
m
，输出向量
为y
n+1
∈ R
s
。逆DEA 模型实际上可以由以下两个基本问题予以概括[397]：
（1） 在每个决策单元相对效率不变的前󰄁下，只变动󰔁个决策单元的󰔁些输入值，预测该决
策单元输出值的变化。假设对于决策单元DMU
k
，其输入向量变化为∆x
k
，在保持其相
对效率不变的情况下，其输出值变化为∆y
k
，不妨将变化以后的决策单元记作DMU
n+1
，
则x
n+1
= x
k
+ ∆x
k
,y
n+1
= y
k
+ ∆y
k
。那么，输出值的变化可以通过求解如下形式的数学规
划问题获得：
max
s
(
r=1
c
r
∆y
kr
s.t.
n
(
i=1
λ
i
x
i
+ λ
n+1
(x
k
+ ∆x
k
)
V WX Y
x
n+1
+s
−
=(x
k
+ ∆x
k
)
V WX Y
x
n+1
θ
k
n
(
i=1
λ
i
y
i
+ λ
n+1
(y
k
+ ∆y
k
V WX Y
y
n+1
) − s
+
= y
k
+ ∆y
k
V WX Y
y
n+1
s
−
,s
+
≥ 0
λ
i
≥ 0,i=1,...,n,n+1
(28.39)
考虑到原始决策单元DMU
k
输出值的比例，可以取c
r
= y
r
> 0,r =1,...,s。
（2） 在每个决策单元相对效率不变的前󰄁下，只变动󰔁个决策单元的󰔁些输出值，预测该决
策单元输入值的变化。假设对于决策单元DMU
k
，其输出向量变化为∆y
k
，在保持其相
对效率不变的情况下，其输入值变化为∆x
k
，不妨将变化以后的决策单元记作DMU
n+1
，
则x
n+1
= x
k
+ ∆x
k
,y
n+1
= y
k
+ ∆y
k
。那么，输入值的变化可以通过求解如下形式的数学规
划问题获得：
min
m
(
r=1
c
r
∆x
kr
s.t.
n
(
i=1
λ
i
x
i
+ λ
n+1
(x
k
+ ∆x
k
)
V WX Y
x
n+1
+s
−
=(x
k
+ ∆x
k
)
V WX Y
x
n+1
θ
k
n
(
i=1
λ
i
y
i
+ λ
n+1
(y
k
+ ∆y
k
V WX Y
y
n+1
) − s
+
= y
k
+ ∆y
k
V WX Y
y
n+1
s
−
,s
+
≥ 0
λ
i
≥ 0,i=1,...,n,n+1
(28.40)
$%"&'#(
403
)!*+",$

搜索与排名 Searching and Ranking
!"#
考虑到原始决策单元DMU
k
输入值的比例，可以取c
r
=1/x
r
> 0,r =1,...,m。
28.4 计算问题
任何方法都有其最佳适用范围，DEA也不例外，如果能够恰当的使用，它由于以下特征显得
功能强大：（1）它能够处理多输入-多输出问题。（2）它不需要知道输入与输出之间的显性函数
关系。（3）DMU可以与其他DMU或者其他DMU的组合直接比较。（4）它具有单位不变性（Unit
Invariant）的特点，DEA衡量的DMU的结果不受投入产出数据所选择单位的影响。（5）DEA模型
不需要事前设定投入与产出的权重，因此不受人为主观因素的影响。
分析人员在决定使用DEA时，需要时刻注意DEA存在的一些局限性：（1）DEA是一种极点技
术（Extreme Point Technique）对噪声（如测量误差）十分敏感，即便是零均值的对称噪声都能
够造成严重的问题。（2）DEA 适于估计决策单元的“相对”效率，难以计算“绝对”效率，使
用它可以对决策单元相互比较，而无法同“理论最大值”（Theoretical Maximum）做比较。（3）
DEA是一种非参数技术，很难基于它做统计假设检验，这也是未来研究的焦点。（4）由于标准形
式的DEA模型，需要对每个决策单元计算一个线性规划模型，属于计算密集型模型，对于大数据
集合时间开销不容忽视。
对于DEA方法中使用的输入变量与输出变量，Cooper等人给出如下的选取准则[398]：（ 1）对
所有决策单元，可以得到每个输入和输出值，而且这些数值须为正数。（2）对这些项目选择，必须
反映分析者或者管理者对于使用相对效率评估相关要素的兴趣。（3）从相对效率的定义出发，输入
的数值应越小越好，而输出的数值应越大越好。
传统的DEA模型，如CCR、BCC的求解需要对每个DMU计算一个LP问题，在处理大规模数据
时，计算开销形成一个巨大的瓶颈[399, 400]。改善DEA模型的求解效率，存在两条路径：设计高
效的通用LP优化算法，根据DEA模型的特征设计高效的优化算法。本节主要讨论选择第二条路径，
设计高效的DEA优化算法。
对于乘法形式的CCR模型，任意两个LP问题的区别仅仅在于目标函数的不同，[401]利用乘
法形式的DEA模型，使用GAMS（General Algebraic Modeling System）将多个小型LP问题合并
为一个LP模型，以实现批量高效求解。[402, 403]从DEA的精度与计算健壮性两个问题出发，研
究CCR、 BBC和加法型三个典型的DEA模型，并根据DEA的特性设计高效的求解算法。如果󰔁
个DMU相对于部分数据集是无效的，那么它相对于整个数据集也一定是无效的。根据这个原则，
[404]使用分解技术，将数据集分割成多个大小相似的数据块，并对每个数据块独立求解DEA模
型，并充分利用并行化优势，通过求解部分模型分析所有数据集，有效󰄁高求解速度。 Chen等
人[405]认为DMU数目对DEA的计算构成压力，因此，󰄁出了一种增速流程，在BCC模型上的实
现结果表现不错。Emrouznejad和Shale[406]随机选取部分数据样本，使用传统DEA方法计算它们
的相对效率，并以此作为输出变量训练神经网络，进而利用训练得到的模型，直接用于预测测
试DMU的相对效率，从而大幅󰄁高计算的效率。Omur[407]将其应用到对医院的效率评价问题上，
$%"&'#(
404
)!*+",$

28.5. 数据包络分析与数据挖掘

!"#

其性能甚至超过判别分析方法。[408]认为非零最优权值的求解是制约模型优化速度的主要因素，

由此󰄁出使用内点法快速计算非零权值。

对于n个决策单元，假设

T =

(µ, ν) | µ

− ν

≤ 0,µ≥ 0, ν ≥ 0,i=1,...,n

(28.41)

对于决策单元DMU

，可以利用下面的CCR模型评估其相对效率：

max µ

s.t. (µ, ν) ∈ T

(28.42)

假设其最优权值向量为µ

∗

, ν

∗

，定义

i | µ

∗T

=1, ∀i =1,...,n

(28.43)

为DMU

的效率参考集（Efﬁciency Reference Set，ERS）[409]。

➊

对于任意决策单元集合DMU

，可以利用下面的CCR模型评估其效率：

max µ

s.t. (µ, ν) ∈ T

(28.44)

如果j ∈ S

，则根据ERS的定义可知µ

∗T

=1，并且(µ

∗

, ν

∗

) ∈ T ，故µ

∗

, ν

∗

是模型(28.44)的可

行解。对于任意的(µ, ν) ∈ T ，由于µ

≤ 1，故µ

∗

, ν

∗

也是模型(28.44)的一个最优解。由此可知，

利用决策单元的效率参考集，可以减少不必要的计算，对于包含大量相对有效的决策单元，效果尤

其明显。

28.5 数据包络分析与数据挖掘

Troutt等人[410]给出BBC模型的变体，构建一个接受边界（Acceptance Boundary），作为区分

决策单元的超平面。尽管方法无需输入数据非负，但是对决策单元󰄁出以下几个限制条件：1）决

策单元是单调的（对于任意两个决策单元，如果其他属性值全部相同，󰔁个属性值越大则该决策单

元属于󰔁个类别的可能性也更大，反之亦然）；2）决策单元中不含第二类错误；3）分类函数是凸

函数等。基于[410]中定义的接受边界的概念，[411] 更近一步，不仅能够确定新样本是否可以被接

受，而且还能够确定新数据与之前已经分类好的数据之间的距离。[412]将数据包络分析和神经网

络解决决策单元效率评价问题进行了比较。

➊ J C Paradi: An efﬁciency reference set, or peer group, deﬁned by a (small) subset of efﬁcient units “closest” to the unit under

evaluation; i.e. with similar mixes of inputs and outputs.

$%"&'#(

405

)!*+",$

搜索与排名 Searching and Ranking
!"#
Pendharkar等人[413]给出一种融合数据包络分析和径向基函数网络（RBFN）的混合模型，解
决带有负值输入，非线性可分的分类问题。
Yan和Wei[414]将每个样本数据都看作一个决策单元，以数据的全部特征作为输入，单位1为输
出，确立数据包络分析模型和数据分类器之间的等价关系，从而将决策单元的分类问题转化为确定
决策单元能否为“接受域”（Acceptance Domain）所接受。“接受域”是从训练数据集中构建的，
也就是传统数据包络分析模型中的生产可能集。[414] 基于生产可能集的基本公理体系，使用线性
不等式组来表示“接受域”，与一个分类函数一起构成了基于数据包络分析模型的分类器。
除了直接根据DEA模型构建分类器以外，研究人员根据已经发展成熟的经典数据挖掘分类
算法，使用集成技术构建分类器。如Sohn和Choi[415]选择分类器的四个性能指标：Sensitivity，
Speciﬁcity，False negative，Positive error作为输出，常量1作为输入，一个分类器构成一个决策
单元，求解多个分类器构成的数据包络模型，然后根据各个分类器的相对效率值为分类器赋权，获
得集成分类器。
2007年，Zheng和Padmanabhan[416]使用数据包络分析模型（输入型BBC）选择、组合多个
基本分类模型。对于二元分类模型，如果假阳性（False Positive）、 真 阳 性 （ True Positive）分别
作为输入和输出，利用数据包络分析模型构建的效率前沿面（凸壳）与ROC曲线是等价的。对于
多元分类模型，基于分类预测混淆矩阵，他们使用以对角元素（正确分类）为输出，其他元素为
输入的决策单元，计算各个分类器的相对效率分值，并󰄁出两种方法集成分类器：只使用相对有
效的模型（EMO）根据多数投票原则确定组合模型的预测分类；使用效率值作为权值组合所有
模型（ESW）。 2009年，Song等人[417]根据DEA方法SF模型计算得到的炼油企业的相对效率分值，
将企业分为两种类型：相对有效（记作+1），相对无效（记作−1）， 取 出 部 分 样 本 及 标 记 作 为 训
练集，部分样本及标记作为测试集，利用SVM训练二元分类模型。2011年，Bazleh等人[418]以精
度与计算时间作为主要特征，利用数据包络分析模型给基本分类模型排名。2012年，Eftekhary等
人[419]利用数据包络分析模型分析不同标准化预处理方法对影响，根据预处理后分类器的表现性
能对标准化预处理方法排名。2013年，Jiang等人[420]根据Performance 与Efﬁciency 两种指标，将
供应商分成四类：HI，HE，LI，LE，使用两个步骤区分出供应商的类型。第一步：将供应商的6
种能力属性与5 种性能属性分别作为输入、输出变量，利用数据包络分析模型CCR计算供应商的相
对分值。第二步：将供应商的相对效率分值添加到原始的属性（特征）空间，根据SVM训练一种
四元分类模型。实验表明，DEA-SVM混合模型表现良好。疑问：[420]在使用分类模型对新加入的
供应商预测其类属时28.1，为了获得其相对效率分值，需要对模型建立所基于的所有供应商重新计
算相对效率分值，增加了大量的计算开销。
DEA模型天生就是一个分类器，无需建立输入输出之间显性的函数关系，就可以将决策单
元划分为两组：相对有效的决策单元（相对效率值等于1）、相对无效的决策单元（相对效率值小
于1）。 研 究 人 员 已 经 开 始 研 究 数 据 包 络 分 析 模 型 自 然 分 类 的 能 力 ， 融 合 机 器 学 习 中 经 典 的 分 类 方
法，如支持向量机（SVM）， 构 建 集 成 形 式 的 分 类 器 [421, 420]。无论是直接利用相对效率值实现自
$%"&'#(
406
)!*+",$

28.6. 基于数据包络分析的排名模型
!"#
图 28.1: DEA-SVM混合模型
动标记[421]，还是将相对效率值作为新的独立特征引入数据集[420]，都取得良好的表现。
由传统DEA方法产生的生产前沿面实际上可以看做一个分段生产函数（Piecewise Production
Function）， Po等人[422]根据据此对决策单元做聚类分析。
通常，关联规则的兴趣度可以使用支持度和置信度两个指标度量。然而，在实际生活中，能
够反映兴趣度的因素可能有多个，使得关联规则评价变成多属性决策问题。于是，Chen[388]、
Toloo等人[423]使用DEA方法解决关联规则挖掘问题。
28.6 基于数据包络分析的排名模型
对于前沿面上相对有效的DMU，原始的DEA模型没有󰄁供更多的信息区分它们，从而无法
得到所有DMU 的完全排名（Full Ranking）结果。如果能够󰄁升DEA的区分能力，则完全排名的
问题就可以迎刃。在传统的DEA模型中，每个DMU都存在一个相对整个DMU集合，对于自身最
佳的权值，由此确定了各个DMU相对于整个DMU集合的相对效率值。如果能够从整个DMU集合
出发，寻找最佳的DMU作为参考，从而可以确定一个公共权值（Common Weight）， 作 为 衡 量 各
个DMU“绝对效率”的标准，从而实现完全排名的目的。
关于公共权值和排名问题，目前已经有很多研究人员参与研究。1990年，Cook等人[389]首
次󰄁出公共权值的概念。1991年， Roll等人[424]首次使用公共权值评价高速路养护单位。
Cook和Kress[389, 425]通过缩小权值上下界的差距，利用有界DEA的公共权值给出主观有序
偏好排名。Cook等人[426]，Andersen和Petersen[427]分别发展了排列相对有效决策单元的过程。
Ganley与Cubbin[428]通过最大化所有DMU的效率分值之和，确定一个公共权值用于对各个决
策单元排名。Doyle 和Green [429] 利用交叉效率矩阵发展了一种排名尺度方法（Rank Scale
Method）。 Sinuany–Stern等人[430]引入了包括两阶段线性判定分析（Two-stage Linear Discrim-
inate Analysis）在内的多种分析方法对DMU集合进行排名。Cooper和Tone 通过计算基于松弛变
量的相对效率值，使用其中相对无效的效率值尺度度量进行排名[431]。Liu和Peng[432]󰄁出公共
权值分析（Common Weights Analysis, CWA）的概念，利用公共权值集合，可以预计算相对有效
的DMU的绝对效率分值，即构建一条隐含的绝对效率前沿面作为标准参照。
$%"&'#(
407
)!*+",$

搜索与排名 Searching and Ranking

!"#

近年来，利用DEA方法对决策单元进行效率排序的方法层出不穷[433, 434]，如交叉效率评价

方法[435]，超效率排名技术[427]，融合多目标决策（MCDM）的数据包络分析方法[436]等，得到

长足的发展与广泛的应用。

28.6.1. 交评价方法

在传统DEA模型，如CCR模型中，各DMU都选择对于自己最有利的权值，不同DMU拥有

不同的最优权值，导致相互之间的效率失去可比性，传统DEA单纯依靠自评体系来评价决策单

元有失公允。Sexton 等人[435]充分利用所有DMU的评价信息，通过建立交叉评估矩阵（Cross-

Evaluation Matrix），利用平均交叉效率值，对 DMU 进行优劣评价和排名。交叉效率评价方法希

望利用互评体系来弥补自评体系的缺陷。

对于任意两个决策单元DMU

和DMU

，交叉效率评价方法执行以下几个步骤：

（1）计算各自的相对效率h

= h

、h

= h

。

（2）计算交叉效率h

、h

，对于h

，可以通过下面条件DEA模型确定：

= max

s.t. h

− µ

≥ 0

≥

(28.45)

由第一个约束条件可知，可行解源于决策单元DMU

的最优权值，反映决策单元DMU

对

输入、输出指标的评价，而目标函数µ

则反映了DMU

对DMU

的评价。h

的计算方法类

似。

（3）使用交叉效率构造交叉效率矩阵：

H =

⎡

⎢

⎣

··· h

⎤

⎥

⎦

(28.46)

由此，可以获得决策单元DMU

(k =1,...,n)的平均效率[429]：

(

j=1

(Averaged Apprai s al of Peers)

(

i=1

(Averaged App rai s al by Peers)

(28.47)

由于平均效率是全部决策单元共同表决的结果，因此可作为各个决策单元排名的依据。

$%"&'#(

408

)!*+",$

28.6. 基于数据包络分析的排名模型

!"#

交叉效率评价方法依然存在缺陷，如交叉效率值不唯一；平均交叉效率值和权重之间没有相应

的联系，无法帮助决策者改进其效率；最终的平均交叉效率值并非帕累托最优或是可以进行帕累托

改进，无法使所有的决策单元确信接受最终的评价结果。对于交叉效率评价方法的一些缺陷，陆续

有研究人员󰄁出改进。比如，Doyle 等人[429]使用全局优化技术，以确定出全局最优解，确保最优

解是唯一的。

交叉效率评价方法的应用比较丰富，比如对夏季奥林匹克运动会参赛国家进行排名[437, 438,

439]。

28.6.2. 超效率排名模型

利用传统DEA方法评估决策单元，通常存在多个相对有效的决策单元，无法直接利用相对效

率值对相对有效的决策单元做进一步区分。为了弥补这一不足，Banker与Gifford[440]首次󰄁出将

有效决策单元从效率前沿面分离开来，在CCR模型的基础上构建超效率DEA模型，度量各决策单

元的超效率分值。在Andersen 与Petersen[427]的努力下，得到进一步完善。超效率模型（Super

Efﬁciency Model）的基本思想：将待评测决策单元的投入和产出使用其它所有单元的投入和产出

的线性组合替代，而将被评测单元排除在参考集（Reference Set）之外来评估其效率。

max µ

min θ

s.t. ν

− µ

≥ 0 s.t.

(

i=1

≤ θx

(

i=1

≥ y

ν ≥ 0,µ≥ 0 λ

≥ 0

i =1,...,n,i ̸= k i =1,...,n,i̸= k

(28.48)

对于无效决策单元，超效率模型估计的结果与CCR模型结果一致；对于CCR模型下有效的决策单

元，在超效率模型下效率值θ一般都是大于1。超效率DEA模型的经济含义是：一个有效决策单元

可以将其投入按比例增加而效率值保持不变，投入增加的最大比例就是其超效率值θ − 1。

超效率模型存在一个不足：使用传统CCR模型确定的相对有效的决策单元，在超效率模型中

可能无可行解。对此，Lovell与Rouse[441]󰄁出一个新的超效率模型解决这一问题，确保所有决策

单元都有可行解。

28.6.3. 公共权值向量集

传统的DEA方法允许每个决策单元选择最有利于自身的指标权值向量，作为评价其生产效率

的基准，由此确立的各个决策单元的相对效率缺乏可比性，无法作为决策单元排名的依据。为了

对所有的决策单元采用统一的标准进行评估，研究人员便󰄁出公共权值向量集（Common Set of

Weights）的概念。公共权值向量集解自多目标规划，是生产可能集（Production Possibility Set,

PPS）

➊

支持超平面（Supporting Hyperplane）的法向量（Normal Vector）。使用公共权值向量

➊ PPS将决策单元分成两组：处于PPS内的是无效率的决策单元，位于PPS前沿面上的是有效的决策单元。

$%"&'#(

409

)!*+",$

搜索与排名 Searching and Ranking

!"#

集对决策单元进行排名是一个重要的方法，对决策单元进行排名需要首先定义一个度量决策单元

与超平面距离的范数[442, 424, 443, 444, 445]。

[446]利用决策单元集合构造输入最小输出最大的虚拟决策单元，根据CCR模型确定虚拟决策

单元的最大效率，从而解得其最优权值作为公共权值，据此可以评估各个决策单元的相对效率，并

进行效率排名。

28.6.4. DR/DEA方法

根据DEA模型计算的相对效率可以将决策单元分成两个类簇：相对有效的（P）与相对无效的

（N）， Sinuany-Stern和Friedman[447]根据两个类簇定义了一个比率分值

,i=1,...,n (28.49)

并基于“最大化类簇间比率分值差异，最小化类簇内比率分值差异”的原则，寻找最佳公共权值向

量，作为分离两个类簇决策单元的分类函数。对于类簇P 与N，各自的平均比率分值定义为：

(

i∈P

(

i∈N

(28.50)

其中，n

分别表示类簇P, N的大小。由此可以确定所有决策单元平均比率分值：

T =

+ n

选择最佳公共权值向量转化为如下最优化问题：

max

µ,ν

λ =

(T )

(28.51)

其中，SS

(T ),SS

(T )表示类簇间（内）比率分值差异，定义为：

(T )=n

(

−

T )

+ n

(

−

T )

(

−

)

(T )=

(

i∈P

−

)

(

i∈N

−

)

(28.52)

DR/DEA属于非线性优化问题，[447]使用的共轭梯度算法（Conjugate Gradient Algorithm）

优化模型，但无法保证能够找到全局最优解。

利用最优公共权值，可以实现对所有决策单元进行完全排序，并保证相对有效的决策单元排列

在无效决策单元之前。

$%"&'#(

410

)!*+",$

28.6. 基于数据包络分析的排名模型

!"#

28.6.5. 基于切比雪夫距离的排名方法

Tavares与Antunes[448]󰄁出一种类似于加法模型的效率评价方法，唯一的区别就是最小化被

评价单元与有效前沿面的L

∞

范数距离（也称切比雪夫距离，或棋盘距离）：

min ∥(x

) − (

(

i=1

(

i=1

)∥

∞

s.t. x

≥

(

i=1

≤

(

i=1

(

i=1

≥ 0,i=1,...,n

(28.53)

可以证明，模型(28.53)等价于下面的线性模型[449]：

max u

s.t. x

≥

(

i=1

+ u

≤

(

i=1

− u

(

i=1

≥ 0,i=1,...,n

(28.54)

其中，u

∈ [0, ∞)表示效率值，当且仅当u

=0时，决策单元DMU

是有效的，或者取θ

1/(1 + u

)，当θ

=1时，决策单元有效。

[449]将待评测的决策单元从生产可能集中剔除，使用下面的模型计算其效率值：

min ∥(x

) − (

(

i=1,i̸=k

(

i=1,i̸=k

)∥

∞

s.t. x

≤

(

i=1,i̸=k

≥

(

i=1,i̸=k

≥ 0,i=1,...,n

(28.55)

根据L

∞

的定义可知：

∥(x

) − (

(

i=1,i̸=k

(

i=1,i̸=k

)∥

∞

= max

−

(

i=1,i̸=k

l=1

−

(

i=1,i̸=k

r=1

= max

(

i=1,i̸=k

− x

l=1

−

(

i=1,i̸=k

r=1

! v

(28.56)

$%"&'#(

411

)!*+",$

搜索与排名 Searching and Ranking

!"#

则有下面模型：

min v

s.t. v

≥

(

i=1,i̸=k

− x

≥ y

−

(

i=1,i̸=k

≥ 0,i=1,...,n

(28.57)

根据对偶理论，可得其对偶模型：

max µ

− ν

s.t. µ

≤ ν

µ +1

ν =1

µ ≥ 0, ν ≥ 0

i =1,...,n,i̸= k

(28.58)

28.6.6. PCA排名

Joe Zhu[450]做过关于DEA与PCA两种方法的比较实验，发现二者对决策单元的排名具有一致

性。后来，Premachandra[451]对Zhu的方法做了进一步的改进。

$%"&'#(

412

)!*+",$

第二十九章 AHP

20世纪中后期，美国运筹学家Saaty[364, 365]󰄁出了层次分析法（Analytic Hierarchy Process，

简称AHP）。它是一种定性与定量相结合的、系统的、层次化的，能够有效解决多准则多目标问题

分析方法，主要用于解决复杂的决策、评价、分析和预测问题。AHP应用比较广泛，可解决人力

资源管理[452]、医学诊断[453]、经济计划与管理、能源政策与分配、生产决策、交通运输、预测

等问题[454] 等。

AHP将决策问题分解为子问题，建立一种层次化的结构，通过逐层分析，确定最佳的备选方

案。从心理学的角度来看， AHP将决策问题理性地拆分，从不同层面理解决策者的意图，并运用

各个层面之间的内在联系，寻找最能契合决策者目标的方案。一般地，AHP将决策问题分为三个

层次：目标层（Goal）、准则层（Criteria）和方案层（Alternatives）。

例29.1. 决策者需要从桂林、黄山、北戴河三个目的地选择一个作为度假旅游的去处，那么按照正

常的思路，她（他）会根据景色、餐饮、居住、行程等多个因素综合分析，并确定最终的方案。这

个决策问题的目标即确定一个旅游目的地，而方案就三个：桂林、黄山与北戴河，而准则就是决策

者选择方案所考虑的因素，包括景色、餐饮、居住、行程等。据此，AHP建立如图 29.1所示形式的

层次关系图

➊

。

图 29.1: Analytic Hierarchy Process: Decision on a Vacation Spot

➊ 浙江大学数学建模课程

413

搜索与排名 Searching and Ranking

!"#

29.1 基本步骤

AHP确立层次结构以后，会根据各个准则相对于目标的重要程度做两两比较，然后根据各个

方案对于各项准则的权重量化准则和方案层。尔后，根据两组权重综合确定各方案对目标的权重。

具体包含以下几个步骤：

（1）建立层次分析结构模型，如图29.1所示。

（2）构造判断矩阵。使用序对比较法和1 ∼ 9尺度，构造每层相对上一层各个因素的判断矩阵。

（3）计算权向量并作一致性检验。对每个判断矩阵计算最大特征值和特征向量，作一致性检验，

若通过，则特征向量即权重向量，否则重新构造判断矩阵。

（4）计算组合权重向量。如果组合权向量通过一致性检验，则可以作为决策的依据，否则重新构

造一致性较弱的判断矩阵。

根据基本步骤，我们在下文尝试着解决前述旅游景点选择问题。

29.1.1. 构造判断矩阵

根据各个准则c

,...,c

相对目标O的重要程度，决策者对准则层两两比较，任选准则c

和c

，

确定相对权值a

。为了方便从定性到定量的转化，Saaty󰄁出使用1 ∼ 9尺度，即1 ≤ a

≤ 9，或者

尺度1 ∼ 9的倒数。相对权值构成判断矩阵A =(a

)

n×n

，且满足a

=1/a

=1,i,j =1,...,n，

因此A>0 是正互反矩阵（Positive Reciprocal Matrix）。

A =

⎡

⎢

⎣

11/24 3 3

21755

1/41/711/21/3

1/31/52 1 1

1/31/53 1 1

⎤

⎥

⎦

(29.1)

对于任意三个准则c

、c

和c

，i, j, k =1, 2,...,n，两两比较得到相对权值a

，如果满

足a

= a

，则称判断矩阵A 是一致矩阵。此时，可以认为决策者的判断行为是可信的、严格

一致的[455]。如果判断矩阵是一致矩阵，可以认为决策者严格根据自身对于各个元素相对上一层

的相对权值进行判断。这种关系可以从数学上予以证明。

$%"&'#(

414

)!*+",$

29.1. 基本步骤

!"#

假如决策者认为准则c

,...,c

相对目标O的重要程度分别为w

,...,w

，据此对元素两两比较，

得到相对权值a

= w

，由此构造的判断矩阵

A =

⎡

⎢

⎣

··· w

⎤

⎥

⎦

(29.2)

是一致矩阵。

由于A = αβ

，其中

α =(w

,...,w

)

, β =(

,...,

)

因此，矩阵A的秩为1，并且由于Aα = αβ

α = nα，表明矩阵A存在唯一的非负特征值n，对

应的特征向量α，正是准则层相对目标层的相对权值。

29.1.2. 一致性检验

一致性的判断终究只是一个理想的假设，实际上，决策者在决策时，比较合理也是可行的一

种方式是两两比较，而直接对准则层构造一个权值列表是困难的。对于一个包含了n个元素的准则

层，只需做

次序对比较，即可构造出决策者的判断矩阵。

在构造判断矩阵时，AHP允许一定程度的不一致性，但不一致性不能偏离过大以致判断行为

不可信。为了衡量判断矩阵的一致性，Alexander和Saaty󰄁出一致性检验的基本步骤[456]：

（I）计算一致性指标CI：

CI =

max

− n

n − 1

CI越大表明判断矩阵不一致性越严重，λ

max

是判断矩阵主特征值，可以证明λ

max

≥ n，且

当λ

max

= n，从而CI=0，判断矩阵是一致性矩阵。

（II）计算平均随机一致性指标RI：表29.1是Alexander和Saaty的模拟结果，通过多次模拟生成

表 29.1: Saaty’s RI

n 1 2 3 4 5 6 7 8 9 10 11

RI 000.58 0.90 1.12 1.24 1.32 1.41 1.45 1.49 1.51

判断矩阵，计算一致性指标CI，将多次模拟结果取平均。

（III）计算一致性比率CR：

CR =

根据Alexander和Saaty的模拟结果，认为当CR < 0.1，则通过一致性检验。实际上这个阈

值从理论上很难给出严格的证明，只是一种粗糙的估计，并引发了诸多争议。

$%"&'#(

415

)!*+",$

搜索与排名 Searching and Ranking

!"#

针对上例，通过计算可知λ

max

=5.073，对应特征向量为

(2)

=(0. 263, 0.475, 0.055, 0.090, 0.110)

矩阵的一致性指标CI =(5.073 − 5)/4=0.018，查表29.1可知RI =1.12，一致性比率CR =0.016 <

0.1，表明矩阵A通过一致性检验。由此确定准则层相对目标层的权值向量ω

(2)

∈ R

。

同理，可以确定相对󰔁个准则，方案层的相对权值向量列表如下：

(0.595, 0.277, 0.129)

, (0.082, 0.236, 0.682)

, (0.429, 0.429, 0.142)

(0.633, 0.193, 0.175)

, (0.166, 0.166, 0.668)

并且都通过了一致性检验。

29.1.3. 组合权重和组合一致性检验

组合权重是指根据各准则相对目标的权重向量和各方案相对每一准则的权重向量计算的各个

方案相对目标的权重向量。

根据确定的相对󰔁个准则，方案层的相对权值向量，可以确定各个方案a

,...,a

相对准则层

的权值向量ω

(3)

,...,ω

(3)

∈ R

。根据上例确定的三个方案相对准则层（5个准则）的相对权值分别

为：

(3)

=(0. 595, 0.082, 0.429, 0.633, 0.166)

(3)

=(0. 277, 0.236, 0.429, 0.193, 0.166)

(3)

=(0. 129, 0.682, 0.142, 0.175, 0.668)

根据准则层相对目标层的权值ω

(2)

，以及方案层相对准则层的相对权值ω

(3)

, ω

(3)

, ω

(3)

可以确定各个

方案相对目标的最终权值。

• 桂林相对目标的权值为

=(0. 595, 0.082, 0.429, 0.633, 0.166)(0.263, 0.475, 0.055, 0.090, 0.110)

=0.3

• 黄山相对目标的权值为

=(0. 277, 0.236, 0.429, 0.193, 0.166)(0.263, 0.475, 0.055, 0.090, 0.110)

=0.246

• 北戴河相对目标的权值为

=(0. 129, 0.682, 0.142, 0.175, 0.668)(0.263, 0.475, 0.055, 0.090, 0.110)

=0.456

$%"&'#(

416

)!*+",$

29.1. 基本步骤

!"#

如果通过组合一致性检验，根据计算可知，决策者最终会选择北戴河作为旅游目的地。

下文主要介绍如何做组合一致性检验。组合一致性检验需要逐层进行，假设第1层只有一个

元素，即单目标情形，第k层对第k − 1层的一致性指标为CI

(k)

, CI

(k)

,...,CI

(k)

k−1

，随机一致性指标

为RI

(k)

, RI

(k)

,...,RI

(k)

k−1

，其中n

k−1

是第k − 1 层元素的个数，则第k层对第1层的组合一致性指标

定义为：

(k)

=(CI

(k)

, CI

(k)

,...,CI

(k)

k−1

)ω

k−1

组合随机一致性指标定义为：

(k)

=(RI

(k)

, RI

(k)

,...,RI

(k)

k−1

)ω

k−1

组合一致性比率定义为：

(k)

=CR

(k−1)

(k)

其中，k =3, 4,...

29.1.4. 判断矩阵主特征值

由于判断矩阵是正互反矩阵，则其主特征值λ

max

≥ n，我们现在给出证明[457]。

证明：假设判断矩阵A主特征值是λ

max

，对应特征向量是ω =(ω

,...,ω

)

，根据Aω = λ

max

ω，

则对任意的i =1, 2,...,n，都有

max

j=1

那么

max

j=1

于是

max

− 1=

j=1

− 1=

j̸=i

由于

j̸=i

= S

+ S

其中，

1≤j<i

i<j≤n

j<i≤n

所以有等式

nλ

max

− n =

i=1

j̸=i

1≤j<i≤n

+ a

)

由此可得

max

1≤j<i≤n

+ a

)+1

$%"&'#(

417

)!*+",$

搜索与排名 Searching and Ranking

!"#

那么一致性指标CI有：

CI =

n(n − 1)

1≤j<i≤n

+ a

) − 1

要证λ

max

>n，只要证明CI > 0即可。

假设判断矩阵是一致性矩阵

A =(

)扰动的结果，而且

, ϵ

> 0, ∀i, j =1, 2,...,n

则据此可得

CI =

n(n − 1)

1≤j<i≤n

(ϵ

) − 1

若令δ

= ϵ

− 1 > −1, ∀i, j =1, 2,...,n，则

表明δ

可视为扰动比例。

将ϵ

= δ

+1代入一致性指标，则有

CI =

n(n − 1)

1≤j<i≤n

(δ

+1+

) − 1=

n(n − 1)

1≤j<i≤n

(δ

+ 1)

− 2

即

CI =

n(n − 1)

1≤j<i≤n

> 0

由此，证得λ

max

>n。

计算判断矩阵的主特征值和特征向量的方法有多种，如幂法、和积法、方根法都可以非常高效

地完成计算。

29.1.5. 方根法

（1）计算判断矩阵每一行元素的乘积：

,i=1, 2,...,n

（2）计算m

的n次方根：

¯w

√

,i=1, 2,...,n

（3）对向量 ¯w =(¯w

, ¯w

,..., ¯w

)

归一化处理：

¯w

(

¯w

则w =(w

,...,w

)

即为主特征向量。

$%"&'#(

418

)!*+",$

29.2. AHP与排名

!"#

（4）计算主特征值λ

max

：

max

(Aw)

式中，(Aw)

表示Aw的第i个元素。

29.1.6. 和积法

（1）将判断矩阵每一列归一化：

¯a

(

,i,j=1, 2,...,n

（2）将按列归一化后的判断矩阵按行相加：

¯w

¯a

,i=1, 2,...,n

（3）对向量 ¯w =(¯w

, ¯w

,..., ¯w

)

归一化处理：

¯w

(

i=1

¯w

则w =(w

,...,w

)

即为主特征向量。

（4）计算主特征值λ

max

：

max

(Aw)

式中，(Aw)

表示Aw的第i个元素。

29.2 AHP与排名

29.2.1. 排名聚合

[458]将AHP应用到搜索引擎排名聚合：（1）根据各个独立搜索引擎历史表现两两比较，构造

搜索引擎的判断矩阵，根据AHP特征向量法确定各个搜索引擎的权值；（2）对于每个搜索引擎返

回的搜索结果列表，对列表中的所有文档对，根据它们在列表中的排名或者分值构造文档判断矩

阵，从而确定各自在列表中的权值；（3）对于每篇文档，根据其文档权值与搜索引擎自身的权重，

确定其综合相关分值。

假设使用的独立搜索引擎是SE

,...,SE

，决策者根据它们的历史表现构造出判断矩阵A

，

计算其主最大特征向量α =(α

,...,α

) 作为各个搜索引擎自身的权重；对于搜索引擎SE

,i =

1,...,m，假设其返回的搜索结果列表是D

=(d

,...,d

)，对所有n

个文档在列表中的排名或者

$%"&'#(

419

)!*+",$

搜索与排名 Searching and Ranking

!"#

分值建立文档判断矩阵A，利用相似的方法可以确定其各自在列表中的权值β

=(β

,...,β

)。对

于任意的文档d，可能同时出现在多个搜索引擎的搜索结果列表中，则其最终相关性分值：

s =

i=1

I(d ∈ D

)α

∗ β

(29.3)

其中，I(d ∈ D

)是判别函数，如果文档d出现在D

中，则I(d ∈ D

)=1，否则I(d ∈ D

)=0。β

表

示文档在列表D

中的权重。

LETOR2.0上的实验结果表明，基于AHP的排名聚合方法（AHP-Rank，AHP-Score）性能要

优于Borda Fuse和Weighted Borda Fuse两种方法。

29.2.2. 因子排名

Guo等人[459]认为影响推文（Tweet）排名的因子主要有七种：评论次数、转发次数、发布时

间、博主的粉丝数目、匹配的标签、是否进入热点榜单、博主是否经过实名认证，并 󰄁 出一种基

于AHP的推文排名方法（TweetRank）。 TweetRank根据用户的偏好，对所有影响因子两两比较形

成影响因子比较矩阵，使用比较矩阵的主特征向量作为各个影响因子的权值，实现个性化推文排名

的目的。实验表明，相比单纯使用时间因素对博文排名，TweetRank与用户的个性化偏好更为吻

合。

在排序学习问题中，每个文档特征都可以作为一个独立的排名函数，对文档进行排名。基

于AHP，可以根据特征在训练集中各个检索词下的排名精度（性能），两两比较构造比较矩阵，根

据AHP理论确定各个特征的权重，由此构建出简单的线性排名函数，简称AHPRank。

假设检索词集合是Q = {q

}

j=1

，对于检索词q

∈ Q，记特征i在检索词q

上的排名精度是e

，

那么全部特征在训练数据集检索词集合上的排名精度矩阵E =(e

)

，其中m是文档特征维数。

对于任意两个特征i

，它们各自在训练数据集上的排名精度是E

=(e

,...,e

),E

,...,e

)，比较二者在所有检索词上的排名精度，使用下面的规则进行积分（j =

1, 2,...,n）：

)

⎧

⎨

⎩

1,e

≥ e

0,e

(29.4)

根据特征i

与i

的排名精度比较，得到其在不同检索词上的积分结果，统计加和得到总的积

分：

)

j=1

)

(29.5)

同理，可以得到特征i

的积分结果b

)

。

令

)

(29.6)

$%"&'#(

420

)!*+",$

29.2. AHP与排名

!"#

则可以构造得到成对比较矩阵A =(a

)

m×m

，其中

(i,j)

(29.7)

利用方根法或者和积法可以迅速计算得到矩阵A的主特征向量ω =(ω

,...,ω

)，那么特征i的

权值就是ω

，由此可以用作在测试集上的线性排名函数对文档进行排名。对于任意文档d，假设其

特征向量为x，AHPRank的预测分值为：

s = ω

29.2.3. AHP与成对比较

假设存在n个方案，通过投票表决各自获得票数是m

,...,m

，那么对于任意两个方案A

，

利用得票差值可以构造判断矩阵A =(a

)，其中

= e

−m

那么，判断矩阵显然是一个正互反矩阵，并且满足一致性：

= e

−m

= e

−m

= a

对于文档检索问题，文档特征集构成准则层，文档集构成方案层，对于󰔁个检索词，我们可以

尝试利用AHP方法，从文档数据集中筛选并排列出同检索词最相关的文档。

29.2.4. 排序逆转

所谓排序逆转（Rank Reversal）是指决策方法对同一决策方案给出自相矛盾的评价，比如在

成对比较时，可能会从不同的角度得出A ≻ B，B ≻ C，C ≻ A 的结论。排序逆转存在多种类型，

有时选作评价决策方法优劣的标准。

$%"&'#(

421

)!*+",$

第三十章 ELECTRE
ELECTRE方法在[460]中首次󰄁出，借助于超越关系（Outranking Relation）评估包含多个
决策准则的决策方案。在第一个ELECTRE I[366]
诞生以后，陆续扩展了多个版本：
ELECTRE
I, II, III, IV, TRI与TOPSIS[461]，各个版本适用的范围、操作的方法是不同的，比如ELECTRE
I[366]和ELECTRE IS主要用于选择问题（Selection Problem）， ELECTRE TRI主要用作指派问
题（Assignment Problem）， 或 者 应 用 到 序 分 类 （ Ordinal Classiﬁcation）问题。ELECTRE II,
III, IV 主要用于排序问题（Ranking Problem）， 其 中 ELECTRE II[462, 463]是老版本，ELECTRE
III[464]考虑了准则间的相对重要程度，也是同IV 的差异之处。
ELECTRE III具有以下几个特征：
（1） 引入无差异阈值（Indifference Threshold）和偏好阈值（Preference Threshold）的概念，
将决策问题的模糊性（不精确和不确定性）考虑进来。
（2） 不同于其他多目标求解方法，它不允许补偿（non-compensatory）。 也 就 是 说 ， 当 一 种 准 则
分值过低，它不能通过其他高分值的准则获得补偿。
（3） 允许不可比（incomparability）的情况，即给定两个备选方案，无法给出明确的偏好。
30.1 偏好模型
偏好模型是基于偏好关系（Preference Relation）建立的，传统模型定义偏好关系：
• Preference：a>b⇔ g(a) >g(b)
• Indifference：a = b ⇔ g(a)=g(b)
当备选方案a、b差别很小，从而无法抉择，这种偏好模型显然不能满意地解决该问题。
ELECTRE方法中定义了两个重要概念：Threshold和OutRanking，对于偏好模型，还引入无
差异阈值（Indifference Threshold）q，并重新定义偏好关系：
• Preference：a>b⇔ g(a) − g(b) >q
• Indifference：a = b ⇔ |g(a) − g(b)| ≤ q
423

搜索与排名 Searching and Ranking

!"#

由于这个模型为严格偏好（Strict Preference）与无差异（Indifference）明确划定了一个界

限，在实际问题中二者之间仍然存在着模糊性，因此有必要为二者设置一个缓冲带。为此，

ELECTRE又引入了偏好阈值（Preference Threshold）p，并将偏好关系细化为两个二元关系：强

偏好（Strong Preference）与弱偏好（Weak Preference），定义如下形式的偏好模型：

• Strong Preference：a>b⇔ g(a) − g(b) >p

• Weak Preference：a ≻ b ⇔ q<g(a) − g(b) ≤ p

• Indifference：a = b ⇔ |g(a) − g(b)| ≤ q

根据偏好模型，ELECTRE确定了Outranking关系：

• Outranking：a ≽ b ⇔ (a>b)

(a ≻ b)

(a = b)

由此可知：a = b等价于a ≽ b, b ≽ a。

如果a ≽ b，且b ≽ a，则a和b是无法比较的（Incomparability）。

图 30.1: 偏好关系

30.2 基本步骤

假设󰔁决策问题包含m个备选方案，方案集记为A；n个决策准则g

,j =1, 2,...,n，准则集合

记为G；每个决策准则对所有备选方案都能够做出评价，评价矩阵记为X =(x

)

m×n

，x

表示决

策准则g

对备选方案a

做出的评价，或者备选方案a

在决策准则g

上的得分。从备选方案集A任选

两个方案(a

)，从准则集中任意一个准则g

。

30.2.1. 确定阈值

对准则g

定义三种类型的阈值：无差异阈值q

，偏好阈值p

，否决阈值（Veto Threshold）v

。

一般而言，0 <q

，并根据给定条件判定方案a

与a

之间的关系:

（1）无差异：若|x

− x

| ≤ q

，则认为在准则g

下，方案a

与a

是无差异的

（2）弱偏好：若q

− x

≤ p

，则认为在准则g

下，方案a

略优于a

$%"&'#(

424

)!*+",$

30.2. 基本步骤

!"#

（3）强偏好：若p

− x

，则认为在准则g

下，方案a

优于a

（4）否决：若x

− x

≤−v

，则总体上，不再承认方案a

≽ a

30.2.2. 计算一致优先度、非一致优先度

一致优先度表示一个备选方案优于另一备选方案的程度。对于准则g

，备选方案a

优于方

案a

的一致优先度c

(i, k)可以表示为下式：

(i, k)=

⎧

⎪

⎨

⎪

⎩

0, x

− x

≤−p

1, x

− x

≥−q

+ x

i,j

− x

k,j

− q

, −p

≤ x

− x

≤−q

(30.1)

由所有有序方案对的一致优先度构成的矩阵为一致优先度矩阵，表示成下式：

C(i, k)=

(i, k)

其中，w

表示决策准则g

的相对重要程度，并且

非一致优先度表示一个备选方案劣于另一备选方案的程度，是一种否决权的执行结果。备选方

案a

劣于方案a

的程度d

(i, k)，可表示如下：

(i, k)=

⎧

⎪

⎨

⎪

⎩

0, x

− x

≥−p

1, x

− x

≤−v

+ x

i,j

− x

k,j

− v

, −v

≤ x

− x

≤−p

(30.2)

综上可知，一致优先度和非一致优先度都在[0, 1]区间。

30.2.3. 计算可信度

可信度衡量的是一种备选方案优于另一备选方案的可信程度（Credibility Degree）。备选方

案a

优于方案a

的可信度S(i, k)，可表示如下：

S(i, k)=

⎧

⎪

⎨

⎪

⎩

C(i, k), d

(i, k) ≤ C(i, k),

C(i, k)

j∈J(i,k)

1 − d

(i, k)

1 − C(i, k)

(i, k) >C(i, k),

(30.3)

其中，J( i, k)是d

(i, k) >C(i, k)的准则指标集。

由可信度构成的矩阵为可信度矩阵，记为S。

$%"&'#(

425

)!*+",$

搜索与排名 Searching and Ranking

!"#

30.2.4. 排名

ELECTRE III推出蒸馏方法（Distillation Method），根据可信度矩阵对备选方案排名。首先，

分别使用递增（Ascending）和递减（Descending）蒸馏过程构造出两个预序集合Z

和Z

。然后，

对两个集合取交得到偏预序集Z = Z

。

$%"&'#(

426

)!*+",$

第三十一章 PROMETHEE

PROMETHEE是Preference Ranking Organization METHod for Enrichment Evaluation的缩

写，是由Jean-Pierre Brans[465, 466, 467, 468]

在

世纪

年代󰄁出的。

PROMETHEE

方法在其发展

过程衍生出多个版本，用于解决不同类型的问题，如PROMETHEE I用于部分排序，PROMETHEE

II用于完全排序，PROMETHEE III 基于区间数，PROMETHEE IV主要应用在连续状态。1988 年，

Bertrand Mareschal和Jean-Pierre Brans[469] 设计出PROMETHEE 方法的可视化软件。在1992年

至1994年间，Brans 和Mareschal 又陆续推出两个扩展模型PROMETHEE V 和PROMETHEE VI，

分别处理包含分段约束（Segmentation Constraints）的多准则决策分析，表达人的大脑行为。目

前，PROMETHEE方法已经在成功应用于银行和工业选址、电力规划、水资源分配，投资、医药、

化学、健康医疗、旅游等多个领域。

对于一个包含m个决策方案，n个决策准则的决策问题A =(a

)

m×n

，使用PROMETHEE方法

给决策方案排名的步骤包括：根据决策矩阵在每个决策准则上对决策方案进行成对比较，利用偏好

函数将成对比较的结果映射为单准则偏好度，根据各个准则的权值计算多准则偏好度，根据多准则

偏好度计算多准则偏好流，利用多准则偏好流对决策方案排名。

在决策准则k上，比较任意的决策方案对，如(i, j)，计算两者的准则k上的分差d

(i, j)=

− a

|。由于每个准则度量标准不同，直接使用分差判读决策方案优劣有失偏颇，我们使用单

准则偏好函数f

结合无差异阈值q

、偏好阈值p

将准则分差转化为[0, 1]区间上的偏好程度，比如线

性的单准则偏好函数

(x)=

⎧

⎪

⎨

⎪

⎩

0, x ≤ q

x − q

− q

<x≤ p

1, x>p

(31.1)

将准则分差转化为偏好度π

(i, j)=f

(i, j))。当分差小于无差异阈值时，则系统对i和j的偏好无

差异，若分差大于偏好阈值，则对i的偏好甚于j，否则0 < π

(i, j) ≤ 1。

假设决策者对每个决策准则赋予一定的权值，权值向量为ω ∈ R

，由此可以将单准则偏好度

进行加权组合得到多准则综合偏好指标

π(i, j)=

(i, j) (31.2)

其中，ω

表示第k个决策准则的权值，并且

(

=1。

427

搜索与排名 Searching and Ranking

!"#

根据任意两个决策方案对的相对偏好度指标，我们可以确定决策方案i的正偏好流Φ

(i)与负偏

好流Φ

−

(i)

(i)=

m − 1

π(i, j) (31.3)

−

(i)=

m − 1

π(j, i) (31.4)

以及净偏好流Φ(i)

Φ(i)=Φ

(i) − Φ

−

(i) (31.5)

由此可知Φ(i) ∈ [−1, 1]，并且

(

Φ(i)=

(

[Φ

(i) − Φ

−

(i)]

m−1

(

[

(

π(i, j) −

(

π(j, i)]

=0,

(31.6)

净偏好流可以直接用于排名。

PROMETHEE方法使用的单准则偏好函数主要有六种[466]（每个函数最多包含两个参数）：

• Usual Criteria

f(x)=

⎧

⎨

⎩

0,x≤ 0,

1,x>0.

(31.7)

• Quasi-Criteria

f(x)=

⎧

⎨

⎩

0,x≤ l,

1,x>l.

(31.8)

• Criterion with Linear Preference

f(x)=

⎧

⎨

⎩

x/m, x ≤ m,

1, x > m.

(31.9)

• Level-Criteria

f(x)=

⎧

⎪

⎨

⎪

⎩

0,x≤ q,

0.5,q<x≤ q + p,

1,x>q+ p.

(31.10)

• Criterion with Linear Preference and Indifference Area

f(x)=

⎧

⎪

⎨

⎪

⎩

0, x ≤ s,

(x − s)/r, s < x ≤ s + r,

1, x>s+ r.

(31.11)

$%"&'#(

428

)!*+",$

!"#

• Gaussian Criteria

f(x)=

⎧

⎨

⎩

0, x ≤ 0,

1 − e

−x

/2σ

,x>0.

(31.12)

对于不同的决策准则，可以使用不同的偏好函数。在使用偏好函数计算相对偏好时，一定注意使用

的决策准则目标是最大化还是最小化。

$%"&'#(

429

)!*+",$

第三十二章 TOPSIS

1981年，Ching-Lai Hwang与Kwangsun Yoon[461]首次󰄁出TOPSIS法（Technique for Order

Preference by Similarity to Ideal Solution）法，从评价单元集合中构建两种理想对象：最优对象

（Positive Ideal Solution）与最劣对象（Negative Ideal Solution），根据评价单元与理想对象之间

的几何距离，对评价单元进行优劣排序。

假设评价单元集合S = {X

,...,X

}，每个评价单元都是一个多元向量X

=(x

,...,x

)，

含有m个决策准则，既含有利因素，又含不利因素。在决策评价中，有利因素越大而不利因素越小

对决策单元越有利。TOPSIS根据有限的决策单元集合，确定每一个决策准则维度的边界：选择有

利准则的上界，不利准则的下界作为最佳对象X

∈ R

，选择有利准则的下界，不利准则的上界

作为最劣对象X

−

∈ R

。从数值来看，表示在评价单元集合的每个特征维度上，选取特征值的最

大值与最小值作为理想对象的特征值，形成一个闭包。

给定决策准则集合的权值向量ω ∈ R

，可以计算每个评价单元相对理想对象X

−

的加权距

离：

]

j=1

[ω

− x

)]

−

]

j=1

[ω

− x

−

)]

(32.1)

在确定每个评价单元与两种理想对象的加权欧式距离后，可以使用比值

−

+ d

,i=1,...,n (32.2)

对评价单元进行排序。一般地，r

∈ [0, 1]，比值越大则排名越靠前。对于r

=1的评价单元，与最

佳对象的加权欧式距离d

=0，说明它就是最佳对象X

；对于r

=0的评价单元，与最劣对象的

加权欧式距离d

−

=0，表明它就是最劣对象。

TOPSIS方法包含一个预处理的程序，在正式评价前对评价数据集每个决策准则（维度）做归

一化处理。此外，它还依赖于决策准则权值向量（∥ω∥ =1），反映出决策者对不同准则在决策制定

时的重要程度，以及决策者对它们的不同偏好。

431

第三十三章偏好模型

33.1 WPM: Weighted Product Model

33.2 WSM: Weighted Sum Model

33.3 SAR: Simple Additive Ranking

33.4 SIR: Superiority and Inferiority Ranking

433