第八章 离散系统建模
8.1 层次分析模型
8.2 循环比赛的名次
8.3 社会经济系统的冲量过程
8.4 效益的合理分配
y
离散模型
离散模型：差分方程（第 7章）、
整数规划（第 4章）、图论、对策论、网络流,… …
分析社会经济系统的有力工具
只用到代数、集合及图论（少许）
的知识
8.1 层次分析模型背景
日常工作、生活中的决策问题
涉及经济、社会等方面的因素
作比较判断时人的主观选择起相当大的作用，各因素的重要性难以量化
Saaty于 1970年代提出层次分析法
AHP (Analytic Hierarchy Process)
AHP——一种 定性与定量相结合的、
系统化、层次化 的分析方法目标层 O(选择旅游地 )
P2
黄山
P1
桂林
P3
北戴河准则层方案层
C3
居住
C1
景色
C2
费用
C4
饮食
C5
旅途一,层次分析法的基本步骤例,选择旅游地 如何在 3个目的地中按照景色、
费用、居住条件等因素选择,
―选择旅游地,思维过程的归纳? 将决策问题分为 3个层次：目标层 O，准则层 C，
方案层 P；每层有若干元素,各层元素间的关系用相连的直线表示。
通过相互比较确定各准则对目标的权重，及各方案对每一准则的权重。
将上述两组权重进行综合，确定各方案对目标的权重。
层次分析法将定性分析与定量分析结合起来完成以上步骤，给出决策问题的定量结果。
1135/13/1
1125/13/1
3/12/117/14/1
55712
3342/11
A
ij
jiijnnij aaaaA
1,0,)(
层次分析法的基本步骤成对比较阵和权向量 元素之间两两对比，对比采用相对尺度设要比较各准则 C1,C2,…,C n对目标 O的重要性
ijji aCC?:
A~成对比较阵
A是正互反阵要由 A确定 C1,…,C n对 O的权向量选择旅游地
n
nnn
n
n
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
A
21
2
2
2
1
2
1
2
1
1
1
712
42/11
A成对比较的不一致情况
):(2/1 2112 CCa?
):(4 3113 CCa? ):(8 3223 CCa?
一致比较 不一致允许不一致，但要确定不一致的允许范围考察完全一致的情况
nwwwW?,,)1( 21
jiij wwa /?令权向量~),,( 21 Tnwwww
成对比较阵和权向量
wAw
n
nnn
n
n
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
A
21
2
2
2
1
2
1
2
1
1
1
成对比较完全一致的情况
nkjiaaa ikjkij,,2,1,,,满足的正互反阵 A称 一致阵,如
A的秩为 1,A的唯一非零特征根为 n
A的任一列向量是对应于 n 的特征向量
A的归一化特征向量可作为权向量对于不一致 (但在允许范围内 )的成对比较阵 A，建议用对应于最大特征根?
的特征向量作为权向量 w,即一致阵性质成对比较阵和权向量
2 4 6 8
比较尺度 aij
Saaty等人提出 1~9尺度 ——aij取值
1,2,…,9 及其互反数 1,1/2,…,1/9
尺度 1 3 5 7 9
ija
相同 稍强 强 明显强 绝对强的重要性
ji CC,
ji CC,~
aij = 1,1/2,,…1/9 的重要性与上面相反
心理学家认为成对比较的因素不宜超过 9个
用 1~3,1~5,…1~17,…,1 p~9p (p=2,3,4,5),d+0.1~d+0.9
(d=1,2,3,4)等 27种比较尺度对若干实例构造成对比较阵，算出权向量，与实际对比发现,1~9尺度较优。
便于定性到定量的转化：
成对比较阵和权向量一致性检验 对 A确定不一致的允许范围已知,n 阶一致阵的唯一非零特征根为 n
可证,n 阶正互反阵最大特征根n,且? =n时为一致阵
1?
n
nCI?定义一致性指标,CI 越大，不一致越严重
RI 0 0 0.58 0.90 1.12 1.24 1.32 1.41 1.45 1.49 1.51
n 1 2 3 4 5 6 7 8 9 1110
为衡量 CI 的大小，引入 随机一致性指标 RI——随机模拟得到 aij,形成 A，计算 CI 即得 RI。
定义一致性比率 CR = CI/RI 当 CR<0.1时，通过一致性检验
Saaty的结果如下
,选择旅游地”中准则层对目标的权向量及一致性检验
1135/13/1
1125/13/1
3/12/117/14/1
55712
3342/11
A
准则层对目标的 成对比较阵最大特征根?=5.073
权向量 (特征向量 )w =(0.263,0.475,0.055,0.090,0.110)T
018.015 5073.5CI
一致性指标随机一致性指标 RI=1.12 (查表 )
一致性比率 CR=0.018/1.12=0.016<0.1
通过一致性检验组合权向量 记第 2层（准则）对第 1层（目标）
的权向量为 T
nwww ),,(
)2()2(
1
)2(
同样求第 3层 (方案 )对第 2层每一元素 (准则 )的权向量
12/15/1
212/1
521
1B
方案层对 C1(景色 )
的成对比较阵
138
3/113
8/13/11
2B
方案层对 C2(费用 )
的成对比较阵
…C n
…B n
最大特征根?1?2 …?n
权向量 w1(3) w2(3) … wn(3)
第 3层对第 2层的计算结果
k
)3(kw
k?
kCI
1
0.595
0.277
0.129
3.005
0.003 0.001 0 0.005 0
3.002
0.682
0.236
0.082
2
3
0.142
0.429
0.429
3
3.009
0.175
0.193
0.633
4
3
0.668
0.166
0.166
5
组合权向量
RI=0.58 (n=3),CIk 均可通过一致性检验
w(2)
0.263
0.475
0.055
0.090
0.110
方案 P1对目标的组合权重为 0.595?0.263+ …=0.300
方案层对目标的组合权向量为 (0.300,0.246,0.456)T
T
nwww ),,(
)2()2(
1
)2(
)2()3()3( wWw?
组合权向量第 1层 O
第 层 C1,…C n
第 3层 P1,…P m
nkwww Tkmkk,,2,1,),,( )3()3( 1)3(
第 2层对第 1层的权向量第 3层对第 2层各元素的权向量
],,[ )3()3(1)3( nwwW构造矩阵则第 3层对第 1层的组合权向量
)2()3()1()()( wWWWw sss
第 s层对第 1层的组合权向量 其中 W(p)是由第 p层对第
p-1层权向量组成的矩阵层次分析法的基本步骤
1）建立层次分析结构模型深入分析实际问题，将有关因素自上而下分层（目标 —
准则或指标 —方案或对象），上层受下层影响，而层内各因素基本上相对独立。
2）构造成对比较阵用成对比较法和 1~9尺度，构造各层对上一层每一因素的成对比较阵。
3）计算权向量并作一致性检验对每一成对比较阵计算最大特征根和特征向量，作一致性检验，若通过，则特征向量为权向量。
4）计算组合权向量（作组合一致性检验 *）
组合权向量可作为决策的定量依据。
二,层次分析法的广泛应用
应用领域：经济计划和管理，能源政策和分配，
人才选拔和评价，生产决策，交通运输，科研选题，
产业结构，教育，医疗，环境，军事等。
处理问题类型：决策、评价、分析、预测等。
建立层次分析结构模型是关键一步，要有主要决策层参与。
构造成对比较阵是数量依据，应由经验丰富、判断力强的专家给出。
国家综合实力国民收入军事力量科技水平社会稳定对外贸易美、俄、中、日、德等大国工作选择贡献收入发展声誉关系 位置供选择的岗位例 1 国家实力分析例 2 工作选择过河的效益
A
经济效益
B1
社会效益
B2 环境效益 B
3
节省时间
C1
收入
C2
岸间商业
C3
当地商业
C4
建筑就业
C5
安全可靠
C6
交往沟通
C7
自豪感
C8
舒适
C9
进出方便
C1
0
美化
C11
桥梁
D1
隧道
D2
渡船
D3
（ 1）过河效益层次结构例 3 横渡江河、海峡方案的抉择过河的代价
A
经济代价
B1
环境代价
B3
社会代价
B2
投入资金
C1
操作维护
C2
冲击渡船业
C3
冲击生活方式
C4
交通拥挤
C5
居民搬迁
C6
汽车排放物
C7
对水的污染
C8
对生态的破坏
C9
桥梁
D1
隧道
D2
渡船
D2
（ 2）过河代价层次结构例 3 横渡江河、海峡方案的抉择待评价的科技成果直接经济效益
C11
间接经济效益
C12
社会效益
C13
学识水平
C21
学术创新
C22
技术水平
C23
技术创新
C24
效益 C1 水平 C2 规模 C3
科技成果评价例 4 科技成果的综合评价三,层次分析法的若干问题
正互反阵的最大特征根是否为正数？特征向量是否为正向量？一致性指标能否反映正互反阵接近一致阵的程度？
怎样简化计算正互反阵的最大特征根和特征向量？
为什么用特征向量作为权向量？
当层次结构不完全或成对比较阵有空缺时怎样用层次分析法？
1,正互反阵的最大特征根和特征向量的性质定理 1 正矩阵 A 的 最大特征根?是正单根，对应正特征向量 w，且
T
kT
k
k
eweAe eA )1,,1,1(,lim
定理 2 n阶 正互反阵 A的最大特征根 n,
= n是 A为一致阵的充要条件。
正互反阵的最大特征根是正数，
特征向量是正向量。
一致性指标 定义合理
1?
n
nCI?
2,正互反阵最大特征根和特征向量的简化计算
精确计算的复杂和不必要
简化计算的思路 ——一致阵的任一列向量都是特征向量，
一致性尚好的正互反阵的列向量都应近似特征向量，可取其某种意义下的平均。
和法 ——取列向量的算术平均
14/16/1
412/1
621
A例
091.0077.01.0
364.0308.03.0
545.0615.06.0
w?
089.0
324.0
587.0
286.0
974.0
769.1
Aw 009.3)089.0 268.0324.0 974.0587.0 769.1(31
列向量归一化算术平均
wAw
精确结果,w=(0.588,0.322,0.090)T,?=3.010
根法 ——取列向量的几何平均幂法 ——迭代算法
1）任取初始向量 w(0),k:=0，设置精度?
)()1(~ kk Aww2) 计算
n
i
k
i
kk www
1
)1()1()1( ~/~3）归一化
n
i
k
i
k
i
w
w
n 1 )(
)1(~1
5) 计算简化计算
4）若,停止；
否则,k:=k+1,转 2
)()1(m a x kikii ww
3,特征向量作为权向量 ——成对比较的多步累积效应问题 一致阵 A,权向量 w=(w1,…w n)T,aij=wi/wj
A不一致,应选权向量 w使 wi/wj与 aij相差尽量小（对所有 i,j)。
2
1 1),,1(
m i n
n
i
n
j
j
i
ijniw w
wa
i?
用拟合方法确定 w 非线性最小二乘
2
1 1),,1(
lnlnm i n
n
i
n
j j
i
ijniw w
wa
i?
线性化 ——
对数最小二乘结果与根法相同
按不同准则确定的权向量不同，特征向量有什么优点。
成对比较 Ci:Cj (直接比较） aij ~ 1步强度
)( )2(2 ijaA? sjn
s
isij aaa?
1
)2(
aisasj~ Ci通过 Cs 与 Cj的比较
aij(2) ~ 2步强度更能反映 Ci对 Cj 的强度步强度kaaA kijkijk ~),( )()(?
多步累积效应体现 多步累积效应
),1,,,,)()()()(00 nsaaaakkkji kjskiskjskis （或定理 1 w
eAe
eA
kT
k
k
lim 特征向量体现 多步累积效应当 k足够大,Ak第 i行元素反映 Ci的权重 求 Ak的行和
4.不完全层次结构中组合权向量的计算完全层次结构：上层每一元素与下层所有元素相关联不完全层次结构设第 2层对第 1层权向量
w(2)=(w1(2),w2(2))T已定第 3层对第 2层权向量
w1(3)=(w11(3),w12(3),w13(3),0)T
w2(3)=(0,0,w23(3),w24(3)T已得讨论由 w(2),W(3)=(w1(3),w2(3))
计算 第 3层对第 1层权向量
w(3） 的方法贡献 O
教学 C1 科研 C2
P2P1 P3 P4
例,评价教师贡献的层次结构
P1,P2只作教学,P4只作科研,
P3兼作教学、科研。
C1,C2支配元素的数目不等
)/(),(~ )2(22)2(11)2(22)2(11)2( wnwnwnwnw T
不考虑支配元素数目不等的影响
)2()3()3( wWw?仍用 计算
支配元素越多权重越大用支配元素数目 n1,n2对 w(2)加权修正若 C1,C2重要性相同,w(2)=(1/2,1/2)T,
P1~P4能力相同,w1(3)=(1/3,1/3,1/3,0)T,w2(3)=(0,0,1/2,1/2)T
公正的评价应为,P1:P2:P3:P4=1:1:2:1
再用 计算 )2()3()3( ~wWw?
w(3)=(1/6,1/6,5/12,1/4)T
w(3)=(1/5,1/5,2/5,1/5)T
Tw
nn
)5/2,5/3(~
,2,3
)2(
21
支配元素越多权重越小教学、科研任务由上级安排教学、科研靠个人积极性考察一个特例：
5,残缺成对比较阵的处理
12/1/
212/1
/21
13
31
ww
ww
C
wCw
22/10
212/1
022
A
wwA
jim
aji
ajia
a
i
ij
ijij
ij
,1
,,0
,,
m
i~A第 i 行中?的个数
12/1
212/1
21
A例
为残缺元素辅助矩阵
Tw )1 42 9.0,2 85 7.0,5 71 4.0(,3
6,更复杂的层次结构
递阶层次结构：层内各元素独立，无相互影响和支配；层间自上而下、逐层传递，无反馈和循环。
更复杂的层次结构,层内各元素间存在相互影响或支配；层间存在反馈或循环。
制动 底盘 车轮方向盘 发动机 减震装置刹车 转向 运行 加速性能汽车行驶性能汽车 1 汽车 2 汽车 n……
例层次分析法的优点
系统性 ——将对象视作系统，按照分解、比较、判断、
综合的思维方式进行决策 ——系统分析（与机理分析、
测试分析并列）；
实用性 ——定性与定量相结合，能处理传统的优化方法不能解决的问题；
简洁性 ——计算简便，结果明确，便于决策者直接了解和掌握。
层次分析法的局限
囿旧 ——只能从原方案中选优，不能产生新方案；
粗略 ——定性化为定量，结果粗糙；
主观 ——主观因素作用大，结果可能难以服人。
8.2 循环比赛的名次
n支球队循环赛，每场比赛只计胜负，没有平局。
根据比赛结果排出各队名次方法 1,寻找按箭头方向通过全部顶点的路径。
1 2
3
45
6
312456 146325
方法 2,计算得分,1队胜 4场,2,3队各胜 3场,4,5
队各胜 2场,6队胜 1场。
无法排名
2,3队,4,5队无法排名
6支球队比赛结果
……
3?2,4?5 排名 132456 合理吗
1
2
3(1) 1
2
3(2)
1
2
34
(1)
1
2
34
(2)
1
2
34
(3)
1
2
34
(4)
循环比赛的结果 ——竞赛图每对顶点间都有边相连的有向图
3个顶点的竞赛图名次 {1,2,3} {(1,2,3)}并列
{1,2,3,4} {2,(1,3,4)} {(1,3,4),2}
4个顶点的竞赛图名次 {(1,2),(3,4)}
{1,2,3,4}?
1
2
34
1
2
34
1
2
34
(1) (2) (3)
1
2
34
(4)
竞赛图的
3种形式
具有唯一的完全路径，如 (1)；
双向连通图 ——任一对顶点存在两条有向路径相互连通，如 (4)；
其他，如 (2),(3) 。
竞赛图的性质
必存在完全路径；
若存在唯一的完全路径，则由它确定的顶点顺序与按得分排列的顺序一致，如 (1) 。
TeAes )1,,1,1(,
级得分向量1~)1,1,2,2()1( TAes
级得分向量2~)2,1,2,3()1()2( TAss
0001
1000
1100
0110
A
Evv
Evv
a
ji
ji
ij,0
,1
1
2
34 (4)
双向连通竞赛图 G=(V,E)的名次排序邻接矩阵
Tnssss ),,,( 21得分向量
TT ss )3,3,5,5(,)3,2,3,3( )4()3(
eAAss kkk )1()(
,)( ksk
TT ss )8,5,8,9(,)5,3,6,8( )6()5(
TT ss )13,9,17,21(,)9,8,13,13( )8()7(
双向连通竞赛图的名次排序
对于 n(>3)个顶点的双向连通竞赛图，存在正整数 r，使邻接矩阵 A 满足 Ar >0,A称 素阵
seA k
k
k
lim
素阵 A的最大特征根为正单根?，对应正特征向量 s,且
eAAss kkk )1()(
0001
1000
1100
0110
A
排名为 {1,2,4,3}
ssk k )(,)( 归一化后
Ts )230.0,167.0,280.0,323.0(
,4.1
用 s排名
1
2
34
(4)
{1,2,3,4}?
000100
100100
110000
001010
111000
111010
A
TT
TT
ss
ss
)16,25,21,32,28,38(,)9,12,7,16,10,15(
)3,4,3,9,5,8(,)1,2,2,3,3,4(
)4()3(
)2()1(
1 2
3
45
6
6支球队比赛结果
Ts )104.0,150.0,113.0,231.0,164.0,238.0(,232.2
排名次序为 {1,3,2,5,4,6}
v1—能源利用量； v2—能源价格；
v3—能源生产率； v4—环境质量；
v5—工业产值； v6—就业机会；
v7—人口总数。
8.3 社会经济系统的冲量过程系统的元素 ——图的顶点元素间的影响 ——带方向的弧影响的正反面 ——弧旁的 +,–号带符号的有向图影响 ——直接影响 符号 ——客观规律；方针政策例 能源利用系统的预测
+
-
+
-
+ +
+
+
- - +
v2
v
1
v3
v4
v6
v7
v5
Evv
vv
vv
a
ji
ji
ji
ij
若，
为若为若，
0
,1
1
0000001
1000000
0100001
1000000
0010010
0000001
0001110
A
带符号有向图 G1=(V,E)的邻接矩阵 A V~顶点集 E~弧集定性模型
-vi vj+
某时段 vi 增加导致下时段 vj 增加 减少带符号的有向图 G1
+
-
+
-
+ +
+
+
- - +
v2
v
1
v3
v4
v6
v7
v5
0000005.1
1000000
05.100002.1
3.0000000
0010020
0000007.0
0002.18.05.00
W
加权有向图 G2及其邻接矩阵 W
定量模型某时段 vi 增加 1单位导致下时段 vj 增加 wij单位
j
w
i vv
ij
的特例视为 WA
v7
0.3
1
1.5
1
1.5
1.2
0.8
-2-2
-0.7
-0.5
v
1
v2
v3
v4
v5 v6
加权有向图 G2
,2,1,0,,,2,1),1()()1( tnitptvtv iii
n
i
n
i
iijjiijj tpatptpwtp
1 1
)()1(),()1( 或
)1()()1( tptvtv
冲量过程 （ Pulse Process)
研究由某元素 vi变化引起的系统的演变过程
vi(t) ~ vi在时段 t 的 值 ； pi(t) ~ vi在时段 t 的 改变量 (冲量 )
))(,),(),(()() ),(,),(),(()( 2121 tptptptptvtvtvtv nn
j
w
i vv
ij
冲量过程模型
Wtptp )()1( Atptp )()1(或
2
3
1 -1 0 0 1 0 -1 2 -2 1 -1 1 0 -1
1 -1 1 -1 0 1 0 3 -3 2 -2 1 1 -1
能源利用系统的预测简单冲量过程 ——初始冲量 p(0)中某个分量为 1，其余为 0的冲量过程若开始时能源利用量有突然增加，预测系统的演变
)0()0( pv?
)1()()1( tptvtv
Atptp )()1(
设能源利用系统的 p(t)和 v(t)
-11 0 -1 1 -1 0 0 0 1 1 -1 0 0 0
t 4p3p 5p 6p 7p2p 4v3v2v1v 5v 6v 7v
0 1 0 0 0 0 0 0 1 0 0 0 0 0 0
1p
简单冲量过程 S的稳定性
任意时段 S的各元素的值和冲量是否为有限 (稳定 )
S不稳定时如何改变可以控制的关系使之变为稳定
S冲量稳定 ~对任意 i,t,| pi(t) |有界
S值稳定 ~对任意 i,t,| vi(t) |有界值稳定冲量稳定
)1()()1( tptvtvWtptp )()1(
tWptp )0()(? S的稳定性取决于 W的特征根记 W的非零特征根为?
S冲量稳定? |? |? 1
S冲量稳定? |? |? 1且均为单根
S值稳定? S冲量稳定 且?不等于 1
0000001
1000000
0100001
1000000
0010010
0000001
0001110
A 对于能源利用系统的邻接矩阵 A
)1()( 2352f
特征多项式
76)2(,2)1( ff )2,1(
能源利用系统存在 冲量不稳定 的简单冲量过程简单冲量过程 S的稳定性简单冲量过程的稳定性改进的玫瑰形图 S* ~带符号的有向图双向连通，且存在一个位于所有回路上的中心顶点。
回路长度 ~ 构成回路的边数回路符号 ~ 构成回路的各有向边符号 +1或 -1之乘积
ak~长度为 k的回路符号和 r~使 ak不等于 0的最大整数
S*冲量稳定? )1,,2,1( rkaaa r - krk?,1
ra
若 S*冲量稳定，则 S*值稳定?
1
r
1k
ka
+
-
+
-
+ +
+
+
- - +
v2
v
1
v3
v4
v6
v7
v5
简单冲量过程 S*的稳定性
a1=0,a2= (-1)v1v2? (-1)v2v1 =1
a3=(+1)v1v3v5v1+(-1)v1v4v7v1
+(+1)v1v3v2v1=1,a4=0,a5=1,r=5
S*冲量稳定? )1,,2,1( rkaaa
r - krk?,1ra
352 aaa
(-1)v1v2?(+1)v1v2(由鼓励利用变为限制利用 )?a2 =-1
+
S*冲量不稳定
)1()( 2352fA的 特征多项式且为单根1
2/)31(,,1,0,0
ii
S*冲量稳定
S*冲量稳定? |? |? 1且均为单根
v1~利用量,v2~价格
v7
+
-
+
-
+ +
+
+
- - +
v2
v
1
v3
v4
v6v5
若 S*冲量稳定，则 S*值稳定?
1
r
1k
ka
}1,0,1,1,0{},,,,{ 54321aaaaa
S*冲量稳定? )1,2,1( rkaaa
r - krk?,1ra
v3—能源生产率
v5—工业产值
1,1,5353 aaaa
(-1)v3v5 违反客观规律
S*值不稳定
S*值稳定
(+1)v3v5?(-1)v3v5
能源利用系统的值不应稳定？
-+
-
+
+ +
+
+
- - +
v2
v
1
v3
v4
v6
v7
v5
+
8.4 效益的合理分配
11321 xxx
4
5
7
32
31
21
xx
xx
xx
例 甲乙丙三人合作经商，若甲乙合作获利 7元，
甲丙合作获利 5元，乙丙合作获利 4元，
三人合作获利 11元。又知每人单干获利 1元。
问三人合作时如何分配获利？
记甲乙丙三人分配为 ),,( 321 xxxx?
解不唯一
(5,3,3)
(4,4,3)
(5,4,2)
……1,,
321?xxx
)(
1
Ivxn
i
i
niivx i,,2,1),(
212121 ),()()(
0)(
sssvsvssv
v
},,2,1{ nI集合
(1) Shapley合作对策满足实函数，子集 )( svIs
[ I,v] ~n人合作对策,v~特征函数
),,,( 21 nxxxx ~n人从 v(I)得到的分配，满足
v(s)~ 子集
s的获利
!
)!1()!()(
n
ssnsw
niisvsvswx
iSs
i?,2,1) ],\()()[(
公理化方法
s?~子集 s中的元素数目,Si ~包含 i的所有子集
)( sw ~由?s?决定的“贡献”的权重
Shapley值
)]\()([ isvsv? ~ i 对合作 s 的“贡献” )( si?
Shapley合作对策三人 (I={1,2,3})经商中甲的分配 x1的计算
1/3 1/6 1/6 1/3
)]1\()()[( svsvsw?
)(sw
s
)1\()( svsv?
)1\(sv
)(sv
1S 1 1 2 1 3 I
1 7 5 11
0 1 1 4
1 6 4 7
1/3 1 2/3 7/3
x1=13/3 类似可得 x2=23/6,x3=17/6
)]1\()()[(
1
1 svsvswx
Ss
1 2 2 3
合作对策的应用 例 1 污水处理费用的合理分担
20km 38km
河流三城镇地理位置示意图
1
2 3
污水处理，排入河流
三城镇可单独建处理厂，
或联合建厂 (用管道将污水由上游城镇送往下游城镇 )
Q1=5 Q
3=5Q2=3
Q~污水量,L~管道长度建厂费用 P1=73Q0.712
管道费用 P2=0.66Q0.51L
230)3(,160)2(,230573)1( 7 1 2.0 CCC
35020566.0)35(73)2,1( 51.0712.0C
36538366.0)53(73)3,2( 51.0712.0C
4 6358566.0)55(73)3,1( 51.07 1 2.0C
460)3()1( CC
污水处理的 5 种方案
1）单独建厂
6 2 0)3()2()1(1 CCCD总投资
2） 1,2合作
3） 2,3合作
4） 1,3合作
5 8 0)3()2,1(2 CCD总 投资
5 9 5)3,2()1(3 CCD总投资合作不会实现
55638)35(66.0
20566.0)535(73)3,2,1(
51.0
51.07 1 2.0
5
CD
5）三城合作总投资
D5最小,应联合建厂建厂费,d1=73?(5+3+5)0.712=453
1?2管道费,d2=0.66?50.51?20=30
2?3管道费,d3=0.66?(5+3)0.51?38=73
D5
城 3建议,d1 按 5:3:5分担,d2,d3由城 1,2担负城 2建议,d3由城 1,2按 5:3分担,d2由城 1担负城 1计算,城 3分担 d1?5/13=174<C(3),
城 2分担 d1?3/13+d3?3/8=132<C(2),
城 1分 担 d1?5/13+d3?5/8+ d2 =250>C(1)
不同意
D5如何分担？
2 3 0)3(
1 6 0)2(
2 3 0)1(
C
C
C
0)3()2()1(,0)( vvvv?
}3,2,1{?I集合特征函数 v(s)~联合 (集 s)建厂比单独建厂节约的投资
),,( 321 xxxx? ~三 城从 节约投资 v(I)中得到的分配
403 5 01 6 02 3 0)2,1()2()1()21( CCCv?
6455 623 016 023 0)3,2,1()3()2()1()(
0)31(
2536 523 016 0)3,2()3()2()32(
CCCCIv
v
CCCv
Shapley合作对策计算 城 1从 节约投资中得到的分配 x1
)]1\()()[( svsvsw?
)(sw
s
)1\()( svsv?
)1\(sv
)(sv
s 1 1 2 1 3 I
0 40 0 64
0 0 0 25
0 40 0 39
1 2 2 3
1/3 1/6 1/6 1/3
0 6.7 0 13
x1 =19.7,
城 1 C(1)-x1=210.4,城 2 C(2)-x2=127.8,城 3 C(3)-x3=217.8
三城在总投资 556中的分担
x2 =32.1,x3=12.2 x2最大，如何解释？
合作对策的应用 例 2 派别在团体中的权重
90人的团体由 3个派别组成，人数分别为 40,30,20人。
团体表决时需过半数的赞成票方可通过。
1)()32()31()21(
,0)3()2()1(,0)(
Ivvvv
vvvv
虽然 3派人数相差很大若每个派别的成员同时投赞成票或反对票，用 Shapley
合作对策 计算 各派别在团体中的权重。
3/1321 xxx权重团体 I={1,2,3}，依次代表 3个派别
否则，
的成员超过定义 特征函数
0
45,1)( ssv
优点,公正、合理，有公理化基础。
如 n个单位治理污染,通常知道第 i方单独治理的投资 yi 和 n方共同治理的投资 Y,及第 i方不参加时其余 n-1方的投资 zi (i=1,2,… n),
确定共同治理时各方分担的费用。
iij j zyiIv)\(
其它 v(s)均不知道,无法用 Shapley合作对策 求解
Shapley合作对策小结若定义特征函数为合作的获利 (节约的投资 )，则有
,)(),,2,1(0)(
1
YyIvniiv n
i
i
缺点,需要知道所有合作的获利，即要定义 I={1,2,… n}的所有子集 (共 2n-1个 )的特征函数，实际上常做不到。
),,( 1 nbbb记设只知道 ~)\( iIvb
i?
无 i 参加时 n-1方合作的获利
~)( IvB?及 全体合作的获利
0),,,,( 21 in xxxxxB?的分配求各方对获利
),,(),7,5,4(11 321 xxxxbB 求，即已知求解合作对策的其他方法例,甲乙丙三人合作经商，若甲乙合作获利 7元，
甲丙合作获利 5元，乙丙合作获利 4元，三人合作获利 11元。问三人合作时如何分配获利？
（ 2）协商解
0
0
,?AbAx TT
1
1
nni
i
i
bxx
bxx
Bx
11
将剩余获利 平均分配
ixB
n
Bbb
nxBnxx iiiii
1)(1
11),7,5,4(, Bb例模型以 n-1方合作的获利为下限
TT bxA?
求解
iii bbnx 1
1 ~ xi 的下限
,3),1,3,4( ixBx
)2,4,5()1,1,1( xx
（ 3） Nash解
),,( 1 nddd记 为现状点（谈判时的威慑点）
ii
i
i
i
i
dx
Bxts
dxxma
..
)(
ii xd?
在此基础上“均匀地”分配全体合作的获利 B
模型
0?id
)(1 iii dBndx
平均分配获利 B
3） Nash解? 2）协商解
（ 4）最小距离解 的上限为记 xxxx
n ),,( 1
ii
i
i
ii
xx
Bxts
xxnmi
..
)(
2
模型第 i 方的边际效益
ii bBx
若令
n
Bbb
nx iii
1
11),7,5,4(, Bb例
)(1 Bxnxx iii
4）最小距离解
2）协商解,6),4,6,7( Bxx i
)2,4,5()2,2,2( xx
（ 5）满意解
ii
ii
i de
dxu
满意度
Bxts
unmixma
i
i
i
..
)(
di~现状点 (最低点 )
ei~理想点 (最高点 )
模型
iiii xexd,
5）基于满意度的解? 2）协商解
iii xed,0
)(
iiiii
ii
i
i
deudx
de
dB
u
的比例分配中在按 ii
i
i
i xxBx
xx ~
（ 6） Raiffi 解
jj xbBnjj 获利为方合作时的原来无参与当,1)(
jini
n
x
xx
x
x jiijj
,,,1,
)1(2
,
2
:)1 的分配基础上进行方合作获利的分配（在 Bnx?
方再等分方平分，和先由 11 nnjx j
得到再平均取,,,2,1 nj?
ij
j
i
ii xn
x
n
x
n
nx ]
)1(2
1
2
[11
)4,6,7(),1,3,4( xx
与协商解 x=(5,4,2)比较
11),7,5,4(, Bb例
)1252,12113,324（?x
求解合作对策的 6种方法（可分为三类）
Shapley合作对策A
类
B
类
!
)!1()!()(
n
ssnsw
niisvsvswx
iSs
i,,2,1) ],\()()[(
)(),\( IvBiIvb i只需
Issv?),(需要所有协商解
)(1 iii xBnxx
下限~ix
Nash解
)(1 iii dBndx
现状~id
最小距离解
)(1 Bxnxx iii
上限~ix
满意解
)( iiiii
ii
i
i
deudx
de
dBu
di~现状,ei~理想
iiii xexd,
ii bBx,1bAx
B类 4种方法相同例：有一资方 (甲 )和二劳方 (乙,丙 ),仅当资方与至少一劳方合作时才获利 10元，应如何分配该获利？
Raiffi解C
类
)(),\( IvBiIvb i只需方再等分方平分，和先由上限对每个 11, nnjxj j
10)(),10,10,0(),\(, IvBbiIvbB i
)67.1,67.1,67.6().(?xS h a p l e yA
)0,0,10(, xbBx ii
)0,0,10(1 TT bAx
)83.0,83.0,34.8(?x
ij
j
i
ii xn
x
n
x
n
nxR a i f f iC ]
)1(2
1
2
[11).(
)0,0,10(?x
B类：计算简单，便于理解，可用于各方实力相差不大的情况；一般来说它偏袒强者。
C类,考虑了分配的上下限，又吸取了
Shapley的思想，在一定程度上保护弱者。
A类：公正合理；需要信息多，计算复杂。
求解合作对策的三类方法小结
8.1 层次分析模型
8.2 循环比赛的名次
8.3 社会经济系统的冲量过程
8.4 效益的合理分配
y
离散模型
离散模型：差分方程（第 7章）、
整数规划（第 4章）、图论、对策论、网络流,… …
分析社会经济系统的有力工具
只用到代数、集合及图论（少许）
的知识
8.1 层次分析模型背景
日常工作、生活中的决策问题
涉及经济、社会等方面的因素
作比较判断时人的主观选择起相当大的作用，各因素的重要性难以量化
Saaty于 1970年代提出层次分析法
AHP (Analytic Hierarchy Process)
AHP——一种 定性与定量相结合的、
系统化、层次化 的分析方法目标层 O(选择旅游地 )
P2
黄山
P1
桂林
P3
北戴河准则层方案层
C3
居住
C1
景色
C2
费用
C4
饮食
C5
旅途一,层次分析法的基本步骤例,选择旅游地 如何在 3个目的地中按照景色、
费用、居住条件等因素选择,
―选择旅游地,思维过程的归纳? 将决策问题分为 3个层次：目标层 O，准则层 C，
方案层 P；每层有若干元素,各层元素间的关系用相连的直线表示。
通过相互比较确定各准则对目标的权重，及各方案对每一准则的权重。
将上述两组权重进行综合，确定各方案对目标的权重。
层次分析法将定性分析与定量分析结合起来完成以上步骤，给出决策问题的定量结果。
1135/13/1
1125/13/1
3/12/117/14/1
55712
3342/11
A
ij
jiijnnij aaaaA
1,0,)(
层次分析法的基本步骤成对比较阵和权向量 元素之间两两对比，对比采用相对尺度设要比较各准则 C1,C2,…,C n对目标 O的重要性
ijji aCC?:
A~成对比较阵
A是正互反阵要由 A确定 C1,…,C n对 O的权向量选择旅游地
n
nnn
n
n
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
A
21
2
2
2
1
2
1
2
1
1
1
712
42/11
A成对比较的不一致情况
):(2/1 2112 CCa?
):(4 3113 CCa? ):(8 3223 CCa?
一致比较 不一致允许不一致，但要确定不一致的允许范围考察完全一致的情况
nwwwW?,,)1( 21
jiij wwa /?令权向量~),,( 21 Tnwwww
成对比较阵和权向量
wAw
n
nnn
n
n
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
A
21
2
2
2
1
2
1
2
1
1
1
成对比较完全一致的情况
nkjiaaa ikjkij,,2,1,,,满足的正互反阵 A称 一致阵,如
A的秩为 1,A的唯一非零特征根为 n
A的任一列向量是对应于 n 的特征向量
A的归一化特征向量可作为权向量对于不一致 (但在允许范围内 )的成对比较阵 A，建议用对应于最大特征根?
的特征向量作为权向量 w,即一致阵性质成对比较阵和权向量
2 4 6 8
比较尺度 aij
Saaty等人提出 1~9尺度 ——aij取值
1,2,…,9 及其互反数 1,1/2,…,1/9
尺度 1 3 5 7 9
ija
相同 稍强 强 明显强 绝对强的重要性
ji CC,
ji CC,~
aij = 1,1/2,,…1/9 的重要性与上面相反
心理学家认为成对比较的因素不宜超过 9个
用 1~3,1~5,…1~17,…,1 p~9p (p=2,3,4,5),d+0.1~d+0.9
(d=1,2,3,4)等 27种比较尺度对若干实例构造成对比较阵，算出权向量，与实际对比发现,1~9尺度较优。
便于定性到定量的转化：
成对比较阵和权向量一致性检验 对 A确定不一致的允许范围已知,n 阶一致阵的唯一非零特征根为 n
可证,n 阶正互反阵最大特征根n,且? =n时为一致阵
1?
n
nCI?定义一致性指标,CI 越大，不一致越严重
RI 0 0 0.58 0.90 1.12 1.24 1.32 1.41 1.45 1.49 1.51
n 1 2 3 4 5 6 7 8 9 1110
为衡量 CI 的大小，引入 随机一致性指标 RI——随机模拟得到 aij,形成 A，计算 CI 即得 RI。
定义一致性比率 CR = CI/RI 当 CR<0.1时，通过一致性检验
Saaty的结果如下
,选择旅游地”中准则层对目标的权向量及一致性检验
1135/13/1
1125/13/1
3/12/117/14/1
55712
3342/11
A
准则层对目标的 成对比较阵最大特征根?=5.073
权向量 (特征向量 )w =(0.263,0.475,0.055,0.090,0.110)T
018.015 5073.5CI
一致性指标随机一致性指标 RI=1.12 (查表 )
一致性比率 CR=0.018/1.12=0.016<0.1
通过一致性检验组合权向量 记第 2层（准则）对第 1层（目标）
的权向量为 T
nwww ),,(
)2()2(
1
)2(
同样求第 3层 (方案 )对第 2层每一元素 (准则 )的权向量
12/15/1
212/1
521
1B
方案层对 C1(景色 )
的成对比较阵
138
3/113
8/13/11
2B
方案层对 C2(费用 )
的成对比较阵
…C n
…B n
最大特征根?1?2 …?n
权向量 w1(3) w2(3) … wn(3)
第 3层对第 2层的计算结果
k
)3(kw
k?
kCI
1
0.595
0.277
0.129
3.005
0.003 0.001 0 0.005 0
3.002
0.682
0.236
0.082
2
3
0.142
0.429
0.429
3
3.009
0.175
0.193
0.633
4
3
0.668
0.166
0.166
5
组合权向量
RI=0.58 (n=3),CIk 均可通过一致性检验
w(2)
0.263
0.475
0.055
0.090
0.110
方案 P1对目标的组合权重为 0.595?0.263+ …=0.300
方案层对目标的组合权向量为 (0.300,0.246,0.456)T
T
nwww ),,(
)2()2(
1
)2(
)2()3()3( wWw?
组合权向量第 1层 O
第 层 C1,…C n
第 3层 P1,…P m
nkwww Tkmkk,,2,1,),,( )3()3( 1)3(
第 2层对第 1层的权向量第 3层对第 2层各元素的权向量
],,[ )3()3(1)3( nwwW构造矩阵则第 3层对第 1层的组合权向量
)2()3()1()()( wWWWw sss
第 s层对第 1层的组合权向量 其中 W(p)是由第 p层对第
p-1层权向量组成的矩阵层次分析法的基本步骤
1）建立层次分析结构模型深入分析实际问题，将有关因素自上而下分层（目标 —
准则或指标 —方案或对象），上层受下层影响，而层内各因素基本上相对独立。
2）构造成对比较阵用成对比较法和 1~9尺度，构造各层对上一层每一因素的成对比较阵。
3）计算权向量并作一致性检验对每一成对比较阵计算最大特征根和特征向量，作一致性检验，若通过，则特征向量为权向量。
4）计算组合权向量（作组合一致性检验 *）
组合权向量可作为决策的定量依据。
二,层次分析法的广泛应用
应用领域：经济计划和管理，能源政策和分配，
人才选拔和评价，生产决策，交通运输，科研选题，
产业结构，教育，医疗，环境，军事等。
处理问题类型：决策、评价、分析、预测等。
建立层次分析结构模型是关键一步，要有主要决策层参与。
构造成对比较阵是数量依据，应由经验丰富、判断力强的专家给出。
国家综合实力国民收入军事力量科技水平社会稳定对外贸易美、俄、中、日、德等大国工作选择贡献收入发展声誉关系 位置供选择的岗位例 1 国家实力分析例 2 工作选择过河的效益
A
经济效益
B1
社会效益
B2 环境效益 B
3
节省时间
C1
收入
C2
岸间商业
C3
当地商业
C4
建筑就业
C5
安全可靠
C6
交往沟通
C7
自豪感
C8
舒适
C9
进出方便
C1
0
美化
C11
桥梁
D1
隧道
D2
渡船
D3
（ 1）过河效益层次结构例 3 横渡江河、海峡方案的抉择过河的代价
A
经济代价
B1
环境代价
B3
社会代价
B2
投入资金
C1
操作维护
C2
冲击渡船业
C3
冲击生活方式
C4
交通拥挤
C5
居民搬迁
C6
汽车排放物
C7
对水的污染
C8
对生态的破坏
C9
桥梁
D1
隧道
D2
渡船
D2
（ 2）过河代价层次结构例 3 横渡江河、海峡方案的抉择待评价的科技成果直接经济效益
C11
间接经济效益
C12
社会效益
C13
学识水平
C21
学术创新
C22
技术水平
C23
技术创新
C24
效益 C1 水平 C2 规模 C3
科技成果评价例 4 科技成果的综合评价三,层次分析法的若干问题
正互反阵的最大特征根是否为正数？特征向量是否为正向量？一致性指标能否反映正互反阵接近一致阵的程度？
怎样简化计算正互反阵的最大特征根和特征向量？
为什么用特征向量作为权向量？
当层次结构不完全或成对比较阵有空缺时怎样用层次分析法？
1,正互反阵的最大特征根和特征向量的性质定理 1 正矩阵 A 的 最大特征根?是正单根，对应正特征向量 w，且
T
kT
k
k
eweAe eA )1,,1,1(,lim
定理 2 n阶 正互反阵 A的最大特征根 n,
= n是 A为一致阵的充要条件。
正互反阵的最大特征根是正数，
特征向量是正向量。
一致性指标 定义合理
1?
n
nCI?
2,正互反阵最大特征根和特征向量的简化计算
精确计算的复杂和不必要
简化计算的思路 ——一致阵的任一列向量都是特征向量，
一致性尚好的正互反阵的列向量都应近似特征向量，可取其某种意义下的平均。
和法 ——取列向量的算术平均
14/16/1
412/1
621
A例
091.0077.01.0
364.0308.03.0
545.0615.06.0
w?
089.0
324.0
587.0
286.0
974.0
769.1
Aw 009.3)089.0 268.0324.0 974.0587.0 769.1(31
列向量归一化算术平均
wAw
精确结果,w=(0.588,0.322,0.090)T,?=3.010
根法 ——取列向量的几何平均幂法 ——迭代算法
1）任取初始向量 w(0),k:=0，设置精度?
)()1(~ kk Aww2) 计算
n
i
k
i
kk www
1
)1()1()1( ~/~3）归一化
n
i
k
i
k
i
w
w
n 1 )(
)1(~1
5) 计算简化计算
4）若,停止；
否则,k:=k+1,转 2
)()1(m a x kikii ww
3,特征向量作为权向量 ——成对比较的多步累积效应问题 一致阵 A,权向量 w=(w1,…w n)T,aij=wi/wj
A不一致,应选权向量 w使 wi/wj与 aij相差尽量小（对所有 i,j)。
2
1 1),,1(
m i n
n
i
n
j
j
i
ijniw w
wa
i?
用拟合方法确定 w 非线性最小二乘
2
1 1),,1(
lnlnm i n
n
i
n
j j
i
ijniw w
wa
i?
线性化 ——
对数最小二乘结果与根法相同
按不同准则确定的权向量不同，特征向量有什么优点。
成对比较 Ci:Cj (直接比较） aij ~ 1步强度
)( )2(2 ijaA? sjn
s
isij aaa?
1
)2(
aisasj~ Ci通过 Cs 与 Cj的比较
aij(2) ~ 2步强度更能反映 Ci对 Cj 的强度步强度kaaA kijkijk ~),( )()(?
多步累积效应体现 多步累积效应
),1,,,,)()()()(00 nsaaaakkkji kjskiskjskis （或定理 1 w
eAe
eA
kT
k
k
lim 特征向量体现 多步累积效应当 k足够大,Ak第 i行元素反映 Ci的权重 求 Ak的行和
4.不完全层次结构中组合权向量的计算完全层次结构：上层每一元素与下层所有元素相关联不完全层次结构设第 2层对第 1层权向量
w(2)=(w1(2),w2(2))T已定第 3层对第 2层权向量
w1(3)=(w11(3),w12(3),w13(3),0)T
w2(3)=(0,0,w23(3),w24(3)T已得讨论由 w(2),W(3)=(w1(3),w2(3))
计算 第 3层对第 1层权向量
w(3） 的方法贡献 O
教学 C1 科研 C2
P2P1 P3 P4
例,评价教师贡献的层次结构
P1,P2只作教学,P4只作科研,
P3兼作教学、科研。
C1,C2支配元素的数目不等
)/(),(~ )2(22)2(11)2(22)2(11)2( wnwnwnwnw T
不考虑支配元素数目不等的影响
)2()3()3( wWw?仍用 计算
支配元素越多权重越大用支配元素数目 n1,n2对 w(2)加权修正若 C1,C2重要性相同,w(2)=(1/2,1/2)T,
P1~P4能力相同,w1(3)=(1/3,1/3,1/3,0)T,w2(3)=(0,0,1/2,1/2)T
公正的评价应为,P1:P2:P3:P4=1:1:2:1
再用 计算 )2()3()3( ~wWw?
w(3)=(1/6,1/6,5/12,1/4)T
w(3)=(1/5,1/5,2/5,1/5)T
Tw
nn
)5/2,5/3(~
,2,3
)2(
21
支配元素越多权重越小教学、科研任务由上级安排教学、科研靠个人积极性考察一个特例：
5,残缺成对比较阵的处理
12/1/
212/1
/21
13
31
ww
ww
C
wCw
22/10
212/1
022
A
wwA
jim
aji
ajia
a
i
ij
ijij
ij
,1
,,0
,,
m
i~A第 i 行中?的个数
12/1
212/1
21
A例
为残缺元素辅助矩阵
Tw )1 42 9.0,2 85 7.0,5 71 4.0(,3
6,更复杂的层次结构
递阶层次结构：层内各元素独立，无相互影响和支配；层间自上而下、逐层传递，无反馈和循环。
更复杂的层次结构,层内各元素间存在相互影响或支配；层间存在反馈或循环。
制动 底盘 车轮方向盘 发动机 减震装置刹车 转向 运行 加速性能汽车行驶性能汽车 1 汽车 2 汽车 n……
例层次分析法的优点
系统性 ——将对象视作系统，按照分解、比较、判断、
综合的思维方式进行决策 ——系统分析（与机理分析、
测试分析并列）；
实用性 ——定性与定量相结合，能处理传统的优化方法不能解决的问题；
简洁性 ——计算简便，结果明确，便于决策者直接了解和掌握。
层次分析法的局限
囿旧 ——只能从原方案中选优，不能产生新方案；
粗略 ——定性化为定量，结果粗糙；
主观 ——主观因素作用大，结果可能难以服人。
8.2 循环比赛的名次
n支球队循环赛，每场比赛只计胜负，没有平局。
根据比赛结果排出各队名次方法 1,寻找按箭头方向通过全部顶点的路径。
1 2
3
45
6
312456 146325
方法 2,计算得分,1队胜 4场,2,3队各胜 3场,4,5
队各胜 2场,6队胜 1场。
无法排名
2,3队,4,5队无法排名
6支球队比赛结果
……
3?2,4?5 排名 132456 合理吗
1
2
3(1) 1
2
3(2)
1
2
34
(1)
1
2
34
(2)
1
2
34
(3)
1
2
34
(4)
循环比赛的结果 ——竞赛图每对顶点间都有边相连的有向图
3个顶点的竞赛图名次 {1,2,3} {(1,2,3)}并列
{1,2,3,4} {2,(1,3,4)} {(1,3,4),2}
4个顶点的竞赛图名次 {(1,2),(3,4)}
{1,2,3,4}?
1
2
34
1
2
34
1
2
34
(1) (2) (3)
1
2
34
(4)
竞赛图的
3种形式
具有唯一的完全路径，如 (1)；
双向连通图 ——任一对顶点存在两条有向路径相互连通，如 (4)；
其他，如 (2),(3) 。
竞赛图的性质
必存在完全路径；
若存在唯一的完全路径，则由它确定的顶点顺序与按得分排列的顺序一致，如 (1) 。
TeAes )1,,1,1(,
级得分向量1~)1,1,2,2()1( TAes
级得分向量2~)2,1,2,3()1()2( TAss
0001
1000
1100
0110
A
Evv
Evv
a
ji
ji
ij,0
,1
1
2
34 (4)
双向连通竞赛图 G=(V,E)的名次排序邻接矩阵
Tnssss ),,,( 21得分向量
TT ss )3,3,5,5(,)3,2,3,3( )4()3(
eAAss kkk )1()(
,)( ksk
TT ss )8,5,8,9(,)5,3,6,8( )6()5(
TT ss )13,9,17,21(,)9,8,13,13( )8()7(
双向连通竞赛图的名次排序
对于 n(>3)个顶点的双向连通竞赛图，存在正整数 r，使邻接矩阵 A 满足 Ar >0,A称 素阵
seA k
k
k
lim
素阵 A的最大特征根为正单根?，对应正特征向量 s,且
eAAss kkk )1()(
0001
1000
1100
0110
A
排名为 {1,2,4,3}
ssk k )(,)( 归一化后
Ts )230.0,167.0,280.0,323.0(
,4.1
用 s排名
1
2
34
(4)
{1,2,3,4}?
000100
100100
110000
001010
111000
111010
A
TT
TT
ss
ss
)16,25,21,32,28,38(,)9,12,7,16,10,15(
)3,4,3,9,5,8(,)1,2,2,3,3,4(
)4()3(
)2()1(
1 2
3
45
6
6支球队比赛结果
Ts )104.0,150.0,113.0,231.0,164.0,238.0(,232.2
排名次序为 {1,3,2,5,4,6}
v1—能源利用量； v2—能源价格；
v3—能源生产率； v4—环境质量；
v5—工业产值； v6—就业机会；
v7—人口总数。
8.3 社会经济系统的冲量过程系统的元素 ——图的顶点元素间的影响 ——带方向的弧影响的正反面 ——弧旁的 +,–号带符号的有向图影响 ——直接影响 符号 ——客观规律；方针政策例 能源利用系统的预测
+
-
+
-
+ +
+
+
- - +
v2
v
1
v3
v4
v6
v7
v5
Evv
vv
vv
a
ji
ji
ji
ij
若，
为若为若，
0
,1
1
0000001
1000000
0100001
1000000
0010010
0000001
0001110
A
带符号有向图 G1=(V,E)的邻接矩阵 A V~顶点集 E~弧集定性模型
-vi vj+
某时段 vi 增加导致下时段 vj 增加 减少带符号的有向图 G1
+
-
+
-
+ +
+
+
- - +
v2
v
1
v3
v4
v6
v7
v5
0000005.1
1000000
05.100002.1
3.0000000
0010020
0000007.0
0002.18.05.00
W
加权有向图 G2及其邻接矩阵 W
定量模型某时段 vi 增加 1单位导致下时段 vj 增加 wij单位
j
w
i vv
ij
的特例视为 WA
v7
0.3
1
1.5
1
1.5
1.2
0.8
-2-2
-0.7
-0.5
v
1
v2
v3
v4
v5 v6
加权有向图 G2
,2,1,0,,,2,1),1()()1( tnitptvtv iii
n
i
n
i
iijjiijj tpatptpwtp
1 1
)()1(),()1( 或
)1()()1( tptvtv
冲量过程 （ Pulse Process)
研究由某元素 vi变化引起的系统的演变过程
vi(t) ~ vi在时段 t 的 值 ； pi(t) ~ vi在时段 t 的 改变量 (冲量 )
))(,),(),(()() ),(,),(),(()( 2121 tptptptptvtvtvtv nn
j
w
i vv
ij
冲量过程模型
Wtptp )()1( Atptp )()1(或
2
3
1 -1 0 0 1 0 -1 2 -2 1 -1 1 0 -1
1 -1 1 -1 0 1 0 3 -3 2 -2 1 1 -1
能源利用系统的预测简单冲量过程 ——初始冲量 p(0)中某个分量为 1，其余为 0的冲量过程若开始时能源利用量有突然增加，预测系统的演变
)0()0( pv?
)1()()1( tptvtv
Atptp )()1(
设能源利用系统的 p(t)和 v(t)
-11 0 -1 1 -1 0 0 0 1 1 -1 0 0 0
t 4p3p 5p 6p 7p2p 4v3v2v1v 5v 6v 7v
0 1 0 0 0 0 0 0 1 0 0 0 0 0 0
1p
简单冲量过程 S的稳定性
任意时段 S的各元素的值和冲量是否为有限 (稳定 )
S不稳定时如何改变可以控制的关系使之变为稳定
S冲量稳定 ~对任意 i,t,| pi(t) |有界
S值稳定 ~对任意 i,t,| vi(t) |有界值稳定冲量稳定
)1()()1( tptvtvWtptp )()1(
tWptp )0()(? S的稳定性取决于 W的特征根记 W的非零特征根为?
S冲量稳定? |? |? 1
S冲量稳定? |? |? 1且均为单根
S值稳定? S冲量稳定 且?不等于 1
0000001
1000000
0100001
1000000
0010010
0000001
0001110
A 对于能源利用系统的邻接矩阵 A
)1()( 2352f
特征多项式
76)2(,2)1( ff )2,1(
能源利用系统存在 冲量不稳定 的简单冲量过程简单冲量过程 S的稳定性简单冲量过程的稳定性改进的玫瑰形图 S* ~带符号的有向图双向连通，且存在一个位于所有回路上的中心顶点。
回路长度 ~ 构成回路的边数回路符号 ~ 构成回路的各有向边符号 +1或 -1之乘积
ak~长度为 k的回路符号和 r~使 ak不等于 0的最大整数
S*冲量稳定? )1,,2,1( rkaaa r - krk?,1
ra
若 S*冲量稳定，则 S*值稳定?
1
r
1k
ka
+
-
+
-
+ +
+
+
- - +
v2
v
1
v3
v4
v6
v7
v5
简单冲量过程 S*的稳定性
a1=0,a2= (-1)v1v2? (-1)v2v1 =1
a3=(+1)v1v3v5v1+(-1)v1v4v7v1
+(+1)v1v3v2v1=1,a4=0,a5=1,r=5
S*冲量稳定? )1,,2,1( rkaaa
r - krk?,1ra
352 aaa
(-1)v1v2?(+1)v1v2(由鼓励利用变为限制利用 )?a2 =-1
+
S*冲量不稳定
)1()( 2352fA的 特征多项式且为单根1
2/)31(,,1,0,0
ii
S*冲量稳定
S*冲量稳定? |? |? 1且均为单根
v1~利用量,v2~价格
v7
+
-
+
-
+ +
+
+
- - +
v2
v
1
v3
v4
v6v5
若 S*冲量稳定，则 S*值稳定?
1
r
1k
ka
}1,0,1,1,0{},,,,{ 54321aaaaa
S*冲量稳定? )1,2,1( rkaaa
r - krk?,1ra
v3—能源生产率
v5—工业产值
1,1,5353 aaaa
(-1)v3v5 违反客观规律
S*值不稳定
S*值稳定
(+1)v3v5?(-1)v3v5
能源利用系统的值不应稳定？
-+
-
+
+ +
+
+
- - +
v2
v
1
v3
v4
v6
v7
v5
+
8.4 效益的合理分配
11321 xxx
4
5
7
32
31
21
xx
xx
xx
例 甲乙丙三人合作经商，若甲乙合作获利 7元，
甲丙合作获利 5元，乙丙合作获利 4元，
三人合作获利 11元。又知每人单干获利 1元。
问三人合作时如何分配获利？
记甲乙丙三人分配为 ),,( 321 xxxx?
解不唯一
(5,3,3)
(4,4,3)
(5,4,2)
……1,,
321?xxx
)(
1
Ivxn
i
i
niivx i,,2,1),(
212121 ),()()(
0)(
sssvsvssv
v
},,2,1{ nI集合
(1) Shapley合作对策满足实函数，子集 )( svIs
[ I,v] ~n人合作对策,v~特征函数
),,,( 21 nxxxx ~n人从 v(I)得到的分配，满足
v(s)~ 子集
s的获利
!
)!1()!()(
n
ssnsw
niisvsvswx
iSs
i?,2,1) ],\()()[(
公理化方法
s?~子集 s中的元素数目,Si ~包含 i的所有子集
)( sw ~由?s?决定的“贡献”的权重
Shapley值
)]\()([ isvsv? ~ i 对合作 s 的“贡献” )( si?
Shapley合作对策三人 (I={1,2,3})经商中甲的分配 x1的计算
1/3 1/6 1/6 1/3
)]1\()()[( svsvsw?
)(sw
s
)1\()( svsv?
)1\(sv
)(sv
1S 1 1 2 1 3 I
1 7 5 11
0 1 1 4
1 6 4 7
1/3 1 2/3 7/3
x1=13/3 类似可得 x2=23/6,x3=17/6
)]1\()()[(
1
1 svsvswx
Ss
1 2 2 3
合作对策的应用 例 1 污水处理费用的合理分担
20km 38km
河流三城镇地理位置示意图
1
2 3
污水处理，排入河流
三城镇可单独建处理厂，
或联合建厂 (用管道将污水由上游城镇送往下游城镇 )
Q1=5 Q
3=5Q2=3
Q~污水量,L~管道长度建厂费用 P1=73Q0.712
管道费用 P2=0.66Q0.51L
230)3(,160)2(,230573)1( 7 1 2.0 CCC
35020566.0)35(73)2,1( 51.0712.0C
36538366.0)53(73)3,2( 51.0712.0C
4 6358566.0)55(73)3,1( 51.07 1 2.0C
460)3()1( CC
污水处理的 5 种方案
1）单独建厂
6 2 0)3()2()1(1 CCCD总投资
2） 1,2合作
3） 2,3合作
4） 1,3合作
5 8 0)3()2,1(2 CCD总 投资
5 9 5)3,2()1(3 CCD总投资合作不会实现
55638)35(66.0
20566.0)535(73)3,2,1(
51.0
51.07 1 2.0
5
CD
5）三城合作总投资
D5最小,应联合建厂建厂费,d1=73?(5+3+5)0.712=453
1?2管道费,d2=0.66?50.51?20=30
2?3管道费,d3=0.66?(5+3)0.51?38=73
D5
城 3建议,d1 按 5:3:5分担,d2,d3由城 1,2担负城 2建议,d3由城 1,2按 5:3分担,d2由城 1担负城 1计算,城 3分担 d1?5/13=174<C(3),
城 2分担 d1?3/13+d3?3/8=132<C(2),
城 1分 担 d1?5/13+d3?5/8+ d2 =250>C(1)
不同意
D5如何分担？
2 3 0)3(
1 6 0)2(
2 3 0)1(
C
C
C
0)3()2()1(,0)( vvvv?
}3,2,1{?I集合特征函数 v(s)~联合 (集 s)建厂比单独建厂节约的投资
),,( 321 xxxx? ~三 城从 节约投资 v(I)中得到的分配
403 5 01 6 02 3 0)2,1()2()1()21( CCCv?
6455 623 016 023 0)3,2,1()3()2()1()(
0)31(
2536 523 016 0)3,2()3()2()32(
CCCCIv
v
CCCv
Shapley合作对策计算 城 1从 节约投资中得到的分配 x1
)]1\()()[( svsvsw?
)(sw
s
)1\()( svsv?
)1\(sv
)(sv
s 1 1 2 1 3 I
0 40 0 64
0 0 0 25
0 40 0 39
1 2 2 3
1/3 1/6 1/6 1/3
0 6.7 0 13
x1 =19.7,
城 1 C(1)-x1=210.4,城 2 C(2)-x2=127.8,城 3 C(3)-x3=217.8
三城在总投资 556中的分担
x2 =32.1,x3=12.2 x2最大，如何解释？
合作对策的应用 例 2 派别在团体中的权重
90人的团体由 3个派别组成，人数分别为 40,30,20人。
团体表决时需过半数的赞成票方可通过。
1)()32()31()21(
,0)3()2()1(,0)(
Ivvvv
vvvv
虽然 3派人数相差很大若每个派别的成员同时投赞成票或反对票，用 Shapley
合作对策 计算 各派别在团体中的权重。
3/1321 xxx权重团体 I={1,2,3}，依次代表 3个派别
否则，
的成员超过定义 特征函数
0
45,1)( ssv
优点,公正、合理，有公理化基础。
如 n个单位治理污染,通常知道第 i方单独治理的投资 yi 和 n方共同治理的投资 Y,及第 i方不参加时其余 n-1方的投资 zi (i=1,2,… n),
确定共同治理时各方分担的费用。
iij j zyiIv)\(
其它 v(s)均不知道,无法用 Shapley合作对策 求解
Shapley合作对策小结若定义特征函数为合作的获利 (节约的投资 )，则有
,)(),,2,1(0)(
1
YyIvniiv n
i
i
缺点,需要知道所有合作的获利，即要定义 I={1,2,… n}的所有子集 (共 2n-1个 )的特征函数，实际上常做不到。
),,( 1 nbbb记设只知道 ~)\( iIvb
i?
无 i 参加时 n-1方合作的获利
~)( IvB?及 全体合作的获利
0),,,,( 21 in xxxxxB?的分配求各方对获利
),,(),7,5,4(11 321 xxxxbB 求，即已知求解合作对策的其他方法例,甲乙丙三人合作经商，若甲乙合作获利 7元，
甲丙合作获利 5元，乙丙合作获利 4元，三人合作获利 11元。问三人合作时如何分配获利？
（ 2）协商解
0
0
,?AbAx TT
1
1
nni
i
i
bxx
bxx
Bx
11
将剩余获利 平均分配
ixB
n
Bbb
nxBnxx iiiii
1)(1
11),7,5,4(, Bb例模型以 n-1方合作的获利为下限
TT bxA?
求解
iii bbnx 1
1 ~ xi 的下限
,3),1,3,4( ixBx
)2,4,5()1,1,1( xx
（ 3） Nash解
),,( 1 nddd记 为现状点（谈判时的威慑点）
ii
i
i
i
i
dx
Bxts
dxxma
..
)(
ii xd?
在此基础上“均匀地”分配全体合作的获利 B
模型
0?id
)(1 iii dBndx
平均分配获利 B
3） Nash解? 2）协商解
（ 4）最小距离解 的上限为记 xxxx
n ),,( 1
ii
i
i
ii
xx
Bxts
xxnmi
..
)(
2
模型第 i 方的边际效益
ii bBx
若令
n
Bbb
nx iii
1
11),7,5,4(, Bb例
)(1 Bxnxx iii
4）最小距离解
2）协商解,6),4,6,7( Bxx i
)2,4,5()2,2,2( xx
（ 5）满意解
ii
ii
i de
dxu
满意度
Bxts
unmixma
i
i
i
..
)(
di~现状点 (最低点 )
ei~理想点 (最高点 )
模型
iiii xexd,
5）基于满意度的解? 2）协商解
iii xed,0
)(
iiiii
ii
i
i
deudx
de
dB
u
的比例分配中在按 ii
i
i
i xxBx
xx ~
（ 6） Raiffi 解
jj xbBnjj 获利为方合作时的原来无参与当,1)(
jini
n
x
xx
x
x jiijj
,,,1,
)1(2
,
2
:)1 的分配基础上进行方合作获利的分配（在 Bnx?
方再等分方平分，和先由 11 nnjx j
得到再平均取,,,2,1 nj?
ij
j
i
ii xn
x
n
x
n
nx ]
)1(2
1
2
[11
)4,6,7(),1,3,4( xx
与协商解 x=(5,4,2)比较
11),7,5,4(, Bb例
)1252,12113,324（?x
求解合作对策的 6种方法（可分为三类）
Shapley合作对策A
类
B
类
!
)!1()!()(
n
ssnsw
niisvsvswx
iSs
i,,2,1) ],\()()[(
)(),\( IvBiIvb i只需
Issv?),(需要所有协商解
)(1 iii xBnxx
下限~ix
Nash解
)(1 iii dBndx
现状~id
最小距离解
)(1 Bxnxx iii
上限~ix
满意解
)( iiiii
ii
i
i
deudx
de
dBu
di~现状,ei~理想
iiii xexd,
ii bBx,1bAx
B类 4种方法相同例：有一资方 (甲 )和二劳方 (乙,丙 ),仅当资方与至少一劳方合作时才获利 10元，应如何分配该获利？
Raiffi解C
类
)(),\( IvBiIvb i只需方再等分方平分，和先由上限对每个 11, nnjxj j
10)(),10,10,0(),\(, IvBbiIvbB i
)67.1,67.1,67.6().(?xS h a p l e yA
)0,0,10(, xbBx ii
)0,0,10(1 TT bAx
)83.0,83.0,34.8(?x
ij
j
i
ii xn
x
n
x
n
nxR a i f f iC ]
)1(2
1
2
[11).(
)0,0,10(?x
B类：计算简单，便于理解，可用于各方实力相差不大的情况；一般来说它偏袒强者。
C类,考虑了分配的上下限，又吸取了
Shapley的思想，在一定程度上保护弱者。
A类：公正合理；需要信息多，计算复杂。
求解合作对策的三类方法小结
