第八章离散模型 8.1 层次分析模型 8.2 循环比赛的名次 8.3 社会经济系统的冲量过程 8.4效益的合理分配 离散模型 ?离散模型：差分方程（第7 章）、整数规划（第4章）、图 论、对策论、网络流、… ?分析社会经济系统的有力工具 ?只用到代数、集合及图论（少 许）的知识 8.1 层次分析模型 ?日常工作、生活中的决策问题 背 景 ?涉及经济、社会等方面的因素 ?作比较判断时人的主观选择起相当 大的作用，各因素的重要性难以量化 ? Saaty于1970年代提出层次分析法 AHP(Analytic Hierarchy Process) ? AHP——一种定性与定量相结合 的、系统化、层次化的分析方法 一. 层次分析法的基本步骤 如何在3个目的地中按照景色、 费用、居住条件等因素选择. 例. 选择旅游地 O(选择旅游地) 目标层 P 2 黄山 P 1 桂林 P 3 北戴河 C 3 居住 C 1 景色 C 2 费用 C 4 饮食 C 5 旅途 准则层 方案层 “选择旅游地”思维过程的归纳 ?将决策问题分为3个层次：目标层O，准则层C， 方案层P；每层有若干元素，各层元素间的关系 用相连的直线表示。 ?通过相互比较确定各准则对目标的权重，及各方 案对每一准则的权重。 ?将上述两组权重进行综合，确定各方案对目标的 权重。 层次分析法将定性分析与定量分析结合起来 完成以上步骤，给出决策问题的定量结果。 层次分析法的基本步骤 成对比较阵 和权向量 元素之间两两对比，对比采用相对尺度 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = 1135/13/1 1125/13/1 3/12/117/14/1 55712 3342/11 A ij jiijnnij a aaaA 1 ,0,)( =>= × 设要比较各准则C 1 ,C 2 ,…C n 对目标O的重要性 ijji aCC ?: 选 择 旅 游 地 A~成对比较阵 A是正互反阵 要由A确定C 1 ,…C n 对O的权向量 ? ? ? ? ? ? ? ? ? ? = LL L L 712 42/11 A ):(8 3223 CCa = 一致比较 不一致 成对比较阵和权向量 成对比较的不一致情况 ):(2/1 2112 CCa = ):(4 3113 CCa = 允许不一致，但要确定不一致的允许范围 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = n nnn n n w w w w w w w w w w w w w w w w w w A L LL L L 21 2 2 2 1 2 1 2 1 1 1 n wwwW L,,)1( 21 ?= jiij wwa /=令 权向量~),,( 21 T n wwww L= 考察完全一致的情况 成对比较阵和权向量 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = n nnn n n w w w w w w w w w w w w w w w w w w A L LL L L 21 2 2 2 1 2 1 2 1 1 1 成对比较完全一致的情况 nkjiaaa ikjkij L,2,1,,, ==? 满足 的正互反阵A称一致阵，如 ? A的秩为1，A的唯一非零特征根为n ? A的任一列向量是对应于n 的特征向量 一致阵 性质 ? A的归一化特征向量可作为权向量 对于不一致(但在允许范围内)的成对 比较阵A，建议用对应于最大特征根λ 的特征向量作为权向量w ，即 wAw λ= 成对比较阵和权向量 Saaty等人提出1~9尺度——a ij 取 值1,2,…9及其互反数1,1/2, ,…1/9 比较尺度a ij 2 4 6 8尺度1 3 5 7 9 ij a 相同稍强强明显强绝对强的重要性 ji CC : ?便于定性到定量的转 化： ji CC :~ a ij = 1,1/2, ,…1/9 的重要性与上面相反 ?心理学家认为成对比较的因素不宜超过9个 ?用1~3,1~5,…1~17,…,1 p ~9 p (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 n CI λ 定义一致性指标: CI 越大，不一致越严重 为衡量CI 的大小，引入随机一致性指标RI——随机模 拟得到a ij , 形成A，计算CI 即得RI。 Saaty的结果如下 RI 0 0 0.58 0.90 1.12 1.24 1.32 1.41 1.45 1.49 1.51 n 12345 6 78 9 1110 当CR<0.1时，通过一致性检验 定义一致性比率CR = CI/RI ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = 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.0 15 5073.5 = ? ? =CI 一致性指标 随机一致性指标RI=1.12 (查表) 通过一致 性检验 一致性比率CR=0.018/1.12=0.016<0.1 记第2层（准则）对第1层（目标） 的权向量为 T n www ),,( )2()2( 1 )2( L= 组合权向量 同样求第3层(方案)对第2层每一元素(准则)的权向量 ? ? ? ? ? ? ? ? ? ? = 12/15/1 212/1 521 1 B 方案层对C 1 (景色) 的成对比较阵 ? ? ? ? ? ? ? ? ? ? = 138 3/113 8/13/11 2 B 方案层对C 2 (费用) 的成对比较阵 …C n …B n 最大特征根λ 1 λ 2 …λ n 权向量w 1 (3) w 2 (3) … w n (3) 第3层对第2层的计算结果 k )3( k w k λ k CI 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 组合权向量 w (2) 0.263 0.475 0.055 0.090 0.110 RI=0.58 (n=3), CI k 均可通过一致性检验 方案P 1 对目标的组合权重为0.595×0.263+ …=0.300 方案层对目标的组合权向量为(0.300, 0.246, 0.456) T T n www ),,( )2()2( 1 )2( L= 第1层O 第2层C 1 ,…C n 第3层P 1 , …P m nkwww T kmkk ,,2,1,),,( )3()3( 1 )3( LL == 第2层对第1层的权向量 组合 权向量 第3层对第2层各元素的权向量 ],,[ )3()3( 1 )3( n wwW L= 构造矩阵 )2()3()3( wWw = 则第3层对第1层的组合权向量 第s层对第1层的组合权向量 其中W (p) 是由第p层对第 p-1层权向量组成的矩阵 )2()3()1()()( wWWWw sss L ? = 层次分析法的基本步骤 1）建立层次分析结构模型 深入分析实际问题，将有关因素自上而下分层（目标— 准则或指标—方案或对象），上层受下层影响，而层内 各因素基本上相对独立。 2）构造成对比较阵 用成对比较法和1~9尺度，构造各层对上一层每一因素的 成对比较阵。 3）计算权向量并作一致性检验 对每一成对比较阵计算最大特征根和特征向量，作一致性 检验，若通过，则特征向量为权向量。 4）计算组合权向量（作组合一致性检验 * ） 组合权向量可作为决策的定量依据。 二. 层次分析法的广泛应用 ?应用领域：经济计划和管理，能源政策和分配， 人才选拔和评价，生产决策，交通运输，科研选 题，产业结构，教育，医疗，环境，军事等。 ?处理问题类型：决策、评价、分析、预测等。 ?建立层次分析结构模型是关键一步，要有主要决 策层参与。 ?构造成对比较阵是数量依据，应由经验丰富、判 断力强的专家给出。 国家综合实力 国民 收入 军事 力量 科技 水平 社会 稳定 对外 贸易 美、俄、中、日、德等大国 例1国家 实力分析 工作选择 贡 献 收 入 发 展 声 誉 关 系 位 置 供选择的岗位 例2 工作选择 过河的效益 A 经济效益 B 1 社会效益 B 2 环境效益 B 3 节 省 时 间 C 1 收 入 C 2 岸 间 商 业 C 3 当 地 商 业 C 4 建 筑 就 业 C 5 安 全 可 靠 C 6 交 往 沟 通 C 7 自 豪 感 C 8 舒 适 C 9 进 出 方 便 C 10 美 化 C 11 桥梁 D 1 隧道 D 2 渡船 D 3 （1）过河效益层次结构 例3横渡 江河、海峡 方案的抉择 过河的代价 A 经济代价 B 1 环境代价 B 3 社会代价 B 2 投 入 资 金 C 1 操 作 维 护 C 2 冲 击 渡 船 业 C 3 冲 击 生 活 方 式 C 4 交 通 拥 挤 C 5 居 民 搬 迁 C 6 汽 车 排 放 物 C 7 对 水 的 污 染 C 8 对 生 态 的 破 坏 C 9 桥梁 D 1 隧道 D 2 渡船 D 2 （2）过河代价层次结构 例3横渡 江河、海峡 方案的抉择 待评价的科技成果 直接 经济 效益 C 11 间接 经济 效益 C 12 社会 效益 C 13 学识 水平 C 21 学术 创新 C 22 技术 水平 C 23 技术 创新 C 24 效益C 1 水平C 2 规模C 3 科技成果评价 例4 科技成果 的综合评价 三. 层次分析法的若干问题 ?正互反阵的最大特征根是否为正数？特征向量 是否为正向量？一致性指标能否反映正互反阵接 近一致阵的程度？ ?怎样简化计算正互反阵的最大特征根和特征向 量？ ?为什么用特征向量作为权向量？ ?当层次结构不完全或成对比较阵有空缺时怎样用 层次分析法？ 1.正互反阵的最大特征根和特征向量的性质 定理1正矩阵A 的最大特征根λ是正单根，对应 正特征向量w，且 T kT k k ew eAe eA )1,1,1(,lim L== ∞→ 正互反阵的最大特征根是正 数，特征向量是正向量。 定理2 n阶正互反阵A的最大特征根λ? n , λ= n是A为一致阵的充要条件。 一致性指标定义合理 1? ? = n n CI λ 2.正互反阵最大特征根和特征向量的简化计算 ?精确计算的复杂和不必要 ?简化计算的思路——一致阵的任一列向量都是特征向 量，一致性尚好的正互反阵的列向量都应近似特征向 量，可取其某种意义下的平均。 和法——取列向量的算术平均 w= ? ? ? ? ? ? ? ? ? ? 089.0 324.0 587.0 算术 平均 ? ? ? ? ? ? ? ? ? ? = 14/16/1 412/1 621 A例 ? ? ? ? ? ? ? ? ? ? 091.0077.01.0 364.0308.03.0 545.0615.06.0 列向量 归一化 ? ? ? ? ? ? ? ? ? ? = 286.0 974.0 769.1 Aw wAw λ= 009.3) 089.0 268.0 324.0 974.0 587.0 769.1 ( 3 1 =++=λ 精确结果:w=(0.588,0.322,0.090) T , λ=3.010 根法——取列向量的几何平均 简化 计算 幂法——迭代算法 1）任取初始向量w (0) , k:=0，设置精度ε )()1( ~ kk Aww = + 2) 计算 ∑ = +++ = n i k i kk www 1 )1()1()1( ~ / ~ 3）归一化 4）若，停 止；否则，k:=k+1, 转2 ε<? + )()1( max k i k i i ww ∑ = + = n i k i k i w w n 1 )( )1( ~ 1 λ 5) 计算 3.特征向量作为权向量——成对比较的多步累积效应 一致阵A, 权向量w=(w 1 ,…w n ) T , a ij =w i /w j 问题 A不一致, 应选权向量w使w i /w j 与a ij 相差 尽量小（对所有i,j)。 2 11 ),,1( min ∑∑ == = ? ? ? ? ? ? ? ? ? n i n j j i ij niw w w a i L 用拟合方法确定w 非线性 最小二乘 线性化—— 对数最小二乘 2 11 ),,1( lnlnmin ∑∑ == = ? ? ? ? ? ? ? ? ? n i n j j i ij niw w w a i L 结果与根法相同 ?按不同准则确定的权向量 不同，特征向量有什么优 点。 成对比较 C i :C j (直接比较）a ij ~ 1步强度 )( )2(2 ij aA = sj n s isij aaa ∑ = = 1 )2( a ij (2) ~ 2步强度 更能反映C i 对C j 的强度 多步累积效应 a is a sj ~ C i 通过C s 与C j 的比较 步强度kaaA k ij k ij k ~),( )()( =体现多步累积效应 ),1,,,, )()()()( 00 nsaaaakkkji k js k is k js k is L=≤≥>??（或 当k足够大, A k 第i行元素反映C i 的权重求A k 的行和 定理1 w eAe eA kT k k = ∞→ lim 特征向量体现多步累积效应 4.不完全层次结构中组合权向量的计算 完全层次结构：上层每一元素与下层所有元素相关联 不完全层次结构 例: 评价教师贡献的层次结构 贡献O 教学C 1 科研C 2 P 2 P 1 P 3 P 4 设第2层对第1层权向量 w (2) =(w 1 (2) ,w 2 (2) ) T 已定 第3层对第2层权向量 w 1 (3) =(w 11 (3) ,w 12 (3) ,w 13 (3) ,0) T w 2 (3) =(0,0,w 23 (3) ,w 24 (3 ) T 已得 P 1 ,P 2 只作教学, P 4 只作科研, P 3 兼作教学、科研。 讨论由w (2) ,W (3) =(w 1 (3) , w 2 (3) ) 计算第3层对第1层权向量 w (3） 的方法 C 1 ,C 2 支配元素的数目不等 若C 1 ,C 2 重要性相同, w (2) =(1/2,1/2 )T, P 1 ~P 4 能力相同, w 1 (3) =(1/3,1/3,1/3,0) T ,w 2 (3) =(0,0,1/2,1/2) T 考察一个特 例： 公正的评价应为：P 1 :P 2 :P 3 :P 4 =1:1:2:1 ?不考虑支配元素数目不等的影响 )2()3()3( wWw = 仍用计算w (3) =(1/6,1/6,5/12,1/4) T ?支配元素越多权重越大教学、科研任务由上级安排 )/(),( ~ )2( 22 )2( 11 )2( 22 )2( 11 )2( wnwnwnwnw T += 用支配元素数目n 1 ,n 2 对w (2) 加权修正 T w nn )5/2,5/3( ~ ,2,3 )2( 21 = == 再用计算 )2()3()3( ~ wWw = w (3) =(1/5,1/5,2/5,1/5) T ?支配元素越多权重越小 教学、科研靠个人积极性 5.残缺成对比较阵的处理 ? ? ? ? ? ? ? ? ? ? = 12/1/ 212/1 /21 13 31 ww ww C ? ? ? ? ? ? ? ? ? ? = 12/1 212/1 21 θ θ A例 ?为残缺元素 辅助矩阵 wCw λ= T w )1429.0,2857.0,5714.0(,3 ==λ ? ? ? ? ? ? ? ? ? ? = 22/10 212/1 022 A wwA λ= ? ? ? ? ? =+ = ≠ = jim a aa a i ij ijij ij ,1 ,0 , θ θ m i ~A第i 行 中?的个数 6.更复杂的层次结构 ?递阶层次结构：层内各元素独立，无相互影响和 支配；层间自上而下、逐层传递，无反馈和循环。 ?更复杂的层次结构：层内各元素间存在相互影响 或支配；层间存在反馈或循环。 制动底盘车轮方向盘发动机减震装置 刹车转向运行加速性能 汽车行驶性能 汽车1汽车2汽车n …… 例 层次分析法的优点 ?系统性——将对象视作系统，按照分解、比较、判 断、综合的思维方式进行决策——系统分析（与机理分 析、测试分析并列）； ?实用性——定性与定量相结合，能处理传统的优化方 法不能解决的问题； ?简洁性——计算简便，结果明确，便于决策者 直接了解和掌握。 层次分析法的局限 ?囿旧——只能从原方案中选优，不能产生新方案； ?粗略——定性化为定量，结果粗造； ?主观——主观因素作用大，结果可能难以服人。 8.2 循环比赛的名次 6支球队比赛结果 ? n支球队循环赛，每场比赛 只计胜负，没有平局。 12 3 4 5 6 无法排名 ?根据比赛结果排出各队名次 方法1：寻找按箭头方向通过 全部顶点的路径。 …… 312456 146325 方法2：计算得分：1队胜4场，2, 3队各胜3场，4, 5 队各胜2场，6队胜1场。 2, 3队，4, 5队无法排名 排名132456 合理吗3→2，4 →5 1 2 3 (1) 1 2 3 (2) 1 2 3 4 (1) 1 2 3 4 (2) 1 2 3 4 (3) 1 2 3 4 (4) 循环比赛的结果——竞赛图 每对顶点间都有边相连的有向图 3个顶点 的竞赛图 名次{1，2，3} {(1,2,3)}并列 4个顶点 的竞赛图 {(1,2),(3,4)} {1, 2, 3, 4} {2,(1,3,4)} {(1,3,4), 2}名次 {1, 2, 3, 4}? 1 2 3 4 1 2 3 4 1 2 3 4 (1) (2) (3) 1 2 3 4 (4) 竞赛图的 3种形式 ?具有唯一的完全路径，如 (1)； ?双向连通图——任一对顶点存在两条有 向路径相互连通，如(4)； ?其他，如(2)，(3) 。 竞赛图 的性质 ?必存在完全路径； ?若存在唯一的完全路径，则由它确定的顶 点顺序与按得分排列的顺序一致，如(1) 。 T eAes )1,,1,1(, L== 级得分向量1~)1,1,2,2( )1( T Aes == ? ? ? ? ? ? ? ? ? ? ? ? = 0001 1000 1100 0110 A ? ? ? ? ∈ = Evv Evv a ji ji ij ,0 ,1 1 2 3 4 (4) T n ssss ),,,( 21 L= 得分向量 双向连通竞赛图G=(V,E)的名次排序 邻接矩阵 级得分向量2~)2,1,2,3( )1()2( T Ass == TT ss )3,3,5,5(,)3,2,3,3( )4()3( == eAAss kkk == ? )1()( TT ss )8,5,8,9(,)5,3,6,8( )6()5( == ?, )( →∞→ k sk LL TT ss )13,9,17,21(,)9,8,13,13( )8()7( == eAAss kkk == ? )1()( 双向连通竞赛图的名次排序 ?对于n(>3)个顶点的双向连通竞赛图，存在 正整数r，使邻接矩阵A 满足A r >0，A称素阵 s eA k k k = ∞→ λ lim ?素阵A的最大特征根为正单 根λ，对应正特征向量s，且 ? ? ? ? ? ? ? ? ? ? ? ? = 0001 1000 1100 0110 A ssk k →∞→ )(, )( 归一化后 T s )230.0,167.0,280.0,323.0( ,4.1 = =λ 用s排名 1 2 3 4 (4) 排名为{1，2，4，3} {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( == == 12 3 4 5 6 6支球队比赛结果 T s )104.0,150.0,113.0,231.0,164.0,238.0(,232.2 ==λ 排名次序为{1，3，2，5，4，6} 8.3 社会经济系统的冲量过程 + - + - + + + + - - + v 2 ? v 1 v 3 v 4 v 6 v 7 v 5 例能源利用系统的预测 v 1 —能源利用量；v 2 —能源价格； v 3 —能源生产率；v 4 —环境质量； v 5 —工业产值；v 6 —就业机会； v 7 —人口总数。 系统的元素——图的顶点 元素间的影响——带方向的弧 带符号的有向图 影响的正反面——弧旁的+、–号 影响——直接影响 符号——客观规律；方针政策 带符号有向图G 1 =(V,E)的邻接矩阵A V~顶点集E~弧集 ? ? ? ? ? ? ?? + = Evv vv vv a ji ji ji ij 若， 为若 为若， 0 ,1 1 - v i v j + 某时段v i 增加导致 下时段v j 增加减少 + - + - 带符号的有向图G 1 + + + + - - + v 2 ? v 1 v 3 v 4 v 6 v 7 v 5 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? = 0000001 1000000 0100001 1000000 0010010 0000001 0001110 A 定性模型 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? = 0000005.1 1000000 05.100002.1 3.0000000 0010020 0000007.0 0002.18.05.00 W 加权有向图G 2 及其邻接矩阵W 0.3 1 1.5 1 1.5 1.2 0.8 -2 -2 -0.7 -0.5 ? v 1 v 2 v 3 v 4 v 5 v 6 v 7 加权有向图G 2 某时段v i 增加1单位导致 下时段v j 增加w ij 单位 j w i vv ij ?→? 的特例视为WA 定量模型 j w i vv ij ?→? 冲量过程（Pulse Process) 研究由某元素v i 变化引起的系统的演变过程 v i (t) ~ v i 在时段t 的值；p i (t) ~ v i 在时段t 的改变量(冲量) LL ,2,1,0,,,2,1),1()()1( ==++=+ tnitptvtv iii ∑∑ == =+=+ n i n i iijjiijj tpatptpwtp 11 )()1(),()1(或 ))(),(),(()()),(,),(),(()( 2121 tptptptptvtvtvtv nn LL == )1()()1( ++=+ tptvtv 冲量过程模型 Wtptp )()1( =+ Atptp )()1( =+ 或 简单冲量过程——初始冲量p(0)中 某个分量为1，其余为0的冲量过程 )0()0( pv = )1()()1( ++=+ tptvtv Atptp )()1( =+ 设 能源利用系统的预测 若开始时能源利用量有突然增加，预测系统的演变 能源利用系统的p(t)和v(t) 2 3 1 -10010-1 2-21-110-1 1-11-1010 3-32-21 1 -1 LL LL -1 1 0-11-1000 1 1-10000 t 4 p 3 p 5 p 6 p 7 p 2 p 4 v 3 v 2 v 1 v 5 v 6 v 7 v 0 100000 0 100 0000 1 p 简单冲量过程S的稳定性 ?任意时段S的各元素的值和冲量是否为有限(稳定) ? S不稳定时如何改变可以控制的关系使之变为稳定 )1()()1( ++=+ tptvtv Wtptp )()1( =+ 值稳定 冲量稳定 S冲量稳定~对任意i,t, | p i (t) |有界 S值稳定~对任意i,t, | v i (t) |有界 t Wptp )0()( = S的稳定性取决于W的特征根 记W的非零特征根为λ 简单冲量过程S的稳定性 ? S冲量稳定? |λ | ≤ 1 ? S冲量稳定? |λ | ≤ 1且均为单根 ? S值稳定? S冲量稳定且λ不等于1 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? = 0000001 1000000 0100001 1000000 0010010 0000001 0001110 A 对于能源利用系统的邻接矩阵A )1()( 2352 ?λ?λ?λλ=λf 特征多项式 76)2(,2)1( =?= ff )2,1(∈?λ 能源利用系统存在冲量 不稳定的简单冲量过程 简单冲量过程的稳定性 + - + - + + + + - - + v 2 ? v 1 v 3 v 4 v 6 v 7 v 5 改进的玫瑰形图S * ~带符号的 有向图双向连通，且存在一个 位于所有回路上的中心顶点。 回路长度~ 构成回路的边数 回路符号~ 构成回路的各有向边符号+1或-1之乘积 a k ~长度为k的回路符号和 r~使a k 不等于0的最大整数 ? S * 冲量稳定? )1,2,1( ?=??= rkaaa r-krk L ,1±= r a ?若S * 冲量稳定，则S * 值稳定? 1≠ ∑ = r 1k k a ? S * 冲量稳定? )1,2,1( ?=??= rkaaa r-krk L,1±= r a + + - + - + + + + - - + v 2 ? v 1 v 3 v 4 v 6 v 7 v 5 简单冲量过程S * 的稳定性 a 1 =0, a 2 = (-1) v1v2 × (-1) v2v1 =1 a 3 =(+1) v1v3v5v1 +(-1) v1v4v7v1 +(+1) v1v3v2v1 =1, a 4 =0, a 5 =1, r=5 352 aaa ??≠ S * 冲量不稳定v 1 ~利用量, v 2 ~价格 (-1) v1v2 →(+1) v1v2 (由鼓励利用变为限制利用)? a 2 =-1 )1()( 2352 ??+= λλλλλfA的特征多项式 且为单根1 2/)31(,,1,0,0 ≤? ±?±= λ λ ii S * 冲量稳定 ? S * 冲量稳定? |λ | ≤ 1且均为单根 ?若S * 冲量稳定，则S * 值稳定? 1≠ ∑ = r 1k k a }1,0,1,1,0{},,,,{ 54321 ?=aaaaa ? S * 冲量稳定? )1,2,1( ?=??= rkaaa r-krk L ,1±= r a 1,1, 5353 ?=?= aaaa S * 值不稳定 (+1) v3v5 →(-1) v3v5 + - + + + + + - - + v 2 ? v 1 v 3 v 4 v 6 v 7 v 5 + - S * 值 稳定 v 3 —能源生产率 v 5 —工业产值 (-1) v3v5 违反客观规律 能源利用系统的值不应稳定？ 甲乙丙三人合作经商，若甲乙合作获利7元， 甲丙合作获利5元，乙丙合作获利4元， 三人合作获利11元。又知每人单干获利1元。 问三人合作时如何分配获利？ 8.4效益的合理分配 例 记甲乙丙三人分配为 ),,( 321 xxxx = 11 321 =++ xxx 解不唯一 4 5 7 32 31 21 ≥+ ≥+ ≥+ xx xx xx (5，3，3) (4，4，3) (5，4，2) …… 1,, 321 ≥xxx (1) Shapley合作对策 满足实函数，子集)(svIs ?∈?},,2,1{ nI L=集合 φ φ =+≥ = 212121 ),()()( 0)( sssvsvssv v UU 的获利 子集 s sv ~)( [ I,v] ~n人合作对策，v~特征函数 ),,,( 21 n xxxx L= ~n人从v(I)得到的分配，满足 )( 1 Ivx n i i = ∑ = niivx i ,,2,1),( L=≥ Shapley合作对策 Shapley值 公理化方法 ! )!1()!( )( n ssn sw ?? = niisvsvswx i Ss i L,2,1)],\()()[( =?= ∑ ∈ ?s?~子集s中的元素数目，S i ~包含i的所有子集 )]\()([ isvsv ? ~ i 对合作s 的“贡献” )( si∈ )( sw ~由?s?决定的“贡献”的权重 三人(I={1,2,3})经商中甲的分配x 1 的计算 )]1\()()[( 1 1 svsvswx Ss ?= ∑ ∈ 1/3 1/6 1/6 1/3 )]1\()()[( svsvsw ? )( sw s )1\()( svsv ? )1\(sv )(sv 1 S 1 1 2 1 3 I UU 1 7 5 11 0 1 1 4 1 6 4 7 1/3 1 2/3 7/3 1 2 2 3 类似可得x 2 =23/6, x 3 =17/6 x 1 =13/3 合作对策的应用例1 污水处理费用的合理分担 20km 38km 河流 三城镇地理位置示意图 1 2 3 Q 1 =5 Q 3 =5 Q 2 =3 ?污水处理，排入河流 Q~污水量，L~管道长度 建厂费用P 1 =73Q 0.712 管道费用P 2 =0.66Q 0.51 L ?三城镇可单独建处理厂， 或联合建厂(用管道将污水 由上游城镇送往下游城镇) 污水处理的5 种方案 1）单独建厂 230)3(,160)2(,230573)1( 712.0 ===?= CCC 620)3()2()1( 1 =++= CCCD 总投资 35020566.0)35(73)2,1( 51.0712.0 =??++?=C 2）1, 2合作 580)3()2,1( 2 =+= CCD 总投资 36538366.0)53(73)3,2( 51.0712.0 =??++?=C 3）2, 3合作 595)3,2()1( 3 =+= CCD 总投资 46358566.0)55(73)3,1( 51.0712.0 =??++?=C 4）1, 3合作 460)3()1( =+> CC合作不会实现 55638)35(66.0 20566.0)535(73)3,2,1( 51.0 51.0712.0 5 =?++ ??+++?==CD 建厂费：d 1 =73×(5+3+5) 0.712 =453 1→2管道费：d 2 =0.66 ×5 0.51 ×20=30 2→3管道费：d 3 =0.66 ×(5+3) 0.51 ×38=73 D 5 { 230)3( 160)2( 230)1( = = = C C C 5）三城合 作总投资 D 5 最小, 应联合建厂D 5 如何分担？ 城3建议：d 1 按5:3:5分担, d 2 ,d 3 由城1,2担负 城2建议：d 3 由城1,2按5:3分担, d 2 由城1担负 城1计算：城3分担d 1 ×5/13=174<C(3), 城2分担d 1 ×3/13+d 3 ×3/8 =132<C(2), 城1分担d 1 ×5/13+d 3 ×5/8+ d 2 =250>C(1) 不 同 意 Shapley合作对策 }3,2,1{=I集合 特征函数v(s)~联合(集s)建厂比单独建厂节约的投资 0)3()2()1(,0)( ==== vvvv φ 40350160230)2,1()2()1()21( =?+=?+= CCCv U 64556230160230)3,2,1()3()2()1()( 0)31( 25365230160)3,2()3()2()32( =?++=?++= = =?+=?+= CCCCIv v CCCv U U ),,( 321 xxxx = ~三城从节约投资v(I)中得到的分配 计算城1从节约投资中得到的分配x 1 )]1\()()[( svsvsw ? )( sw s )1\()( svsv ? )1\(sv )(sv s 1 1 2 1 3 I UU 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 x 1 =19.7, 三城在总投资556中的分担 x 2 最大，如何解释？x 2 =32.1, x 3 =12.2 城1 C(1)-x 1 =210.4, 城2 C(2)-x 2 =127.8, 城3 C(3)-x 3 =217.8 合作对策的应用例2 派别在团体中的权重 90人的团体由3个派别组成，人数分别为40, 30, 20人。 团体表决时需过半数的赞成票方可通过。 若每个派别的成员同时投赞成票或反对票，用Shapley 合作对策计算各派别在团体中的权重。 团体I={1,2,3}，依次代表3个派别 ? ? ? = 否则， 的成员超过 定义特征函数 0 45,1 )( s sv 1)()32()31()21( ,0)3()2()1(,0)( ==== ==== Ivvvv vvvv UUU φ 虽然3派人数相差很大3/1 321 === xxx权重 Shapley合作对策小结 优点：公正、合理，有公理化基础。 缺点：需要知道所有合作的获利，即要定义I={1,2,…n}的所有 子集(共2 n -1个)的特征函数，实际上常做不到。 如n个单位治理污染, 通常知道第i方单独治理的投资y i 和n方共 同治理的投资Y, 及第i方不参加时其余n-1方的投资z i (i=1,2, …n). 要确定共同治理时各方分担的费用 若定义特征函数为合作的获利(节约的投资)，则有 ,)(),,2,1(0)( 1 YyIvniiv n i i ?=== ∑ = L i ij j zyiIv ?= ∑ ≠ )\( 其它v(s)均不知道, 无法用Shapley合作对策求解 求解合作对策的其他方法 设只知道 ~)\( iIvb i = 无i参加时n-1方合作的获利 ~)(IvB=及 全体合作的获利 ),( 1 n bbb L=记 0),,,( 21 ≥= in xxxxxB L的分配求各方对获利 例. 甲乙丙三人合作经商，若甲乙合作获利7元， 甲丙合作获利5元，乙丙合作获利4元，三人 合作获利11元。问三人合作时如何分配获利？ ),,(),7,5,4(11 321 xxxxbB ===求，即已知 （2）协商解 ? ? ? ? ? ? ? ? ? ? =≥? 0 0 , OAbAx TT 1 1 ? ? ? ? ? ≥? ≥? = ∑ ∑ ∑ nni i i bxx bxx Bx M 11 T T bxA =求解 ∑ ? ? = iii bb n x 1 1 以n-1方合作的获利为下限 模 型 ~ x i 的下限 将剩余获利平均分配 ∑ ? i xB 11),7,5,4(. == Bb例 ,3),1,3,4( =?= ∑ i xBx n B bb n xB n xx iiiii +?=?+= ∑∑ 1 )( 1 )2,4,5()1,1,1( =+=xx （3）Nash解 ),,( 1 n ddd L=记 为现状点（谈判时的威慑点） 在此基础上“均匀地”分配全体合作的获利B ii i i i i dx Bxts dxxma ≥ = ? ∑ ∏ .. )( 模 型 ∑ ?+= )( 1 iii dB n dx 0= i d 平均分配获利B i i xd = 3）Nash解? 2）协商解 （4）最小距离解 的上限为记xxxx n ),,( 1 L= ii i i ii xx Bxts xxnmi ≤ = ? ∑ ∑ .. )( 2 ∑ ??= )( 1 Bx n xx iii 模 型 n B bb n x iii +?= ∑ 1 ii bBx ?=若令 第i 方的边际效益 4）最小距离解 ? 2）协商解 11),7,5,4(. == Bb例 ,6),4,6,7( =?= ∑ Bxx i )2,4,5()2,2,2( =?=xx （5）基于满意度的解 d i ~现状点(最低点) e i ~理想点(最高点) ii ii i de dx u ? ? =满意度 )( iiiii ii i i deudx de dB u ?+= ? ? = ∑∑ ∑ Bxts unmixma i i i = ∑ .. )(模 型 ii i i xexd == , 5）基于满意度的解? 2）协商解 的比例分配中在按 ∑ ∑ = ii i i i xxB x x x ~ iii xed == ,0 （6）Raiffi解 与协商解x=(5,4,2)比较 :)1的分配基础上进行方合作获利的分配（在Bnx ? jj xbBnjj =??获利为方合作时的原来无参与当,1)( jini n x xx x x j ii j j ≠= ? +== ,,,1, )1(2 , 2 L 方再等分方平分，和先由11 ?? nnjx j 得到再平均取,,,2,1 nj L 11),7,5,4(. == Bb例 )4,6,7(),1,3,4( == xx ∑ ≠ ? ++ ? = ij j i ii x n x n x n n x ] )1(2 1 2 [ 11 ) 12 5 2, 12 11 3, 3 2 4（=x 求解合作对策的6种方法（可分为三类） ! )!1()!( )( n ssn sw ?? = niisvsvswx i Ss i ,,2,1)],\()()[( L=?= ∑ ∈ )(),\( IvBiIvb i ==只需 Issv ∈),(需要所有 A 类 Shapley合作对策 B 类 协商解 )( 1 ∑ ?+= iii xB n xx 下限~ i x Nash解 ∑ ?+= )( 1 iii dB n dx 现状~ i d 最小距离解 ∑ ??= )( 1 Bx n xx iii 上限~ i x 基于满意度的解 )( iiiii ii i i deudx de dB u ?+= ? ? = ∑∑ ∑ d i ~现状, e i ~理想 ii i i xexd == , ii bBx ?= , 1 bAx ? = B类4种方法相同 )(),\( IvBiIvb i ==只需 Raiffi解C 类 方再等分方平分，和先由上限对每个11, ?? nnjxj j 例：有一资方(甲)和二劳方(乙,丙), 仅当资方与至少 一劳方合作时才获利10元，应如何分配该获利？ )67.1,67.1,67.6().( =xShapleyA 10)(),10,10,0(),\(. ==== IvBbiIvbB i )0,0,10(, =?= xbBx ii )0,0,10( 1 == ? T T bAx )83.0,83.0,34.8(=x ∑ ≠ ? ++ ? = ij j i ii x n x n x n n xRaiffiC ] )1(2 1 2 [ 11 ).( )0,0,10(=x 求解合作对策的三类方法小结 A类：公正合理；需要信息多，计算复杂。 B类：计算简单，便于理解，可用于各方实 力相差不大的情况；一般来说它偏袒强者。 C类：考虑了分配的上下限，又吸取了 Shapley的思想，在一定程度上保护弱者。