决策与对策模型.ppt

《决策与对策模型.ppt》由会员分享，可在线阅读，更多相关《决策与对策模型.ppt（111页珍藏版）》请在三一办公上搜索。

1、8.决策与对策模型,工程、经济、管理、军事以及社会生活诸领域中经常遇到决策和对策问题.,每个方案有确定结果,要选出使决策目标达到最优的方案.,确定性决策,风险性、非确定性决策,每个方案结果是随机的,要选出使目标平均值达到最优的方案.,存在多个决策者并且他们的决策相互影响.,只一个决策者,非合作对策与合作对策,8.1 多属性决策与层次分析法8.2 风险性决策与非确定性决策8.3 非合作对策8.4 合作对策,8.决策与对策模型,8.1 多属性决策与层次分析法,多属性决策（MADM）（Multiple Attribute Decision Making）,为一特定目的在备选方案中确定一个最优的(或给

2、出优劣排序、优劣数值),而方案的优劣由若干属性(准则、特征、性能)给以定量或定性的表述.,多属性决策应用领域非常广泛,国家综合实力评价,大学排名榜,公司新厂址选择,个人工作岗位抉择,8.1 多属性决策与层次分析法,层次分析法（AHP）（Analytic Hierarchy Process）,针对经济、社会领域作比较判断时主观因素作用较大,准则和方案的重要性难以量化的情况.,Saaty于20世纪70年代提出,稍晚于多属性决策.,定性与定量相结合的、系统化、层次化的分析方法.,在实际应用领域、处理问题类型、具体计算方法等方面,与多属性决策有不少类似和相通之处.,8.1.1 多属性决策(MADM)的

3、问题与要素8.1.2 多属性决策的决策矩阵与属性权重8.1.3 多属性决策几种主要的综合方法8.1.4 层次分析法8.1.5 多属性决策问题的求解8.1.6 多属性决策和层次分析法应用中的几个问题,8.1 多属性决策与层次分析法,8.1.1 多属性决策(MADM)的问题与要素,对待选汽车作出综合评价,为选购确定决策.,汽车选购,确定3个属性(指标),经济适用、性能良好、款式新颖,对3个属性在汽车选购中的重要性有大致比较.,对待选汽车在每一属性中的优劣程度有基本判断.,基于实际背景提出几个案例:,申报晋升者根据在每项属性中所处等级对号入座取得分值,计算总分,根据总分确定能否晋升.,职员晋升,工作

4、年限、教育程度、工作能力、道德品质,每一属性分为若干等级:年限、程度用入职时间和学历分级,能力、品质按照优、良、中划分.,确定4项属性在职员晋升中的权重，及每项属性中各个等级的分值.,确定4项属性(指标),对学生宿舍设计方案的评价（全国大学生数学建模竞赛2010 D题）,学生宿舍的设计必须考虑以下问题：经济性：建设成本、运行成本和收费标准等.舒适性：人均面积、使用方便、互不干扰、采光和通风等.安全性：人员疏散和防盗等.,附件给出4种比较典型的学生宿舍的设计方案.请你们用数学建模的方法就它们的经济性、舒适性和安全性作出综合量化评价和比较.,8.1.1 多属性决策(MADM)的问题与要素,要素：1

5、.决策目标、备选方案与属性集合 2.决策矩阵 3.属性权重 4.综合方法,1.确定属性集合的一般原则：,全面考虑,选取影响力(或重要性)强的.,属性间尽量独立(至少相关性不太强),不选难以辨别方案优劣的(即使影响力很强).,若数量太多(如大于7个),应将它们分层.,尽量选可量化的,定性的也要能明确区分档次.,2.决策矩阵,以方案为行、属性为列、每一方案对每一属性的取值为元素构成的矩阵.,表示方案对属性的优劣(或偏好)程度.,可以定量的属性,只能定性的属性,3.属性权重,对目标影响力(或重要性)的权重分配,将决策矩阵与属性权重加以综合,得到最终决策的数学方法.,4.综合方法,要素：1.决策目标、

6、备选方案与属性集合 2.决策矩阵 3.属性权重 4.综合方法,8.1.2 多属性决策的决策矩阵与属性权重,3个属性为选购准则 价格X1,性能X2,款式X3,汽车选购,3个方案供决策 选购的汽车型号A1,A2,A3,dijAi对Xj的取值(原始权重),3种汽车价格(万元):25,18,12,3种汽车性能(打分,10分满分):9,7,5,3种汽车性能:7,7,5,1）决策矩阵及其标准化,m个备选方案 A1,A2,Am,决策矩阵,dij Ai对Xj的取值,决策矩阵的获取,调查、量测各方案对属性的取值(定量,偏于客观).,决策者打分评定或用层次分析法的成对比较得到(定性,偏于主观).,8.1.2 多属

7、性决策的决策矩阵与属性权重,n个属性 X1,X2,Xn,汽车选购,1）决策矩阵及其标准化,决策矩阵D的列各方案对某属性的取值(属性值).,各属性物理意义(包括量纲)不同,效益型属性,对费用型的属性值dij作倒数变换将全部属性统一为效益型.,性能X2,款式X3,费用型属性,标准化第1步：区分,价格X1,R的列最大值为1最大化,R的列和为1 归一化,R的列模为1 模一化,1）决策矩阵及其标准化,标准化第2步：对dij作比例尺度变换,当且仅当dij=0时才有rij=0,R标准化的决策矩阵,比例变换假定:属性的重要性随属性值线性变化.,2）属性权重的确定,w1,w2,wn属性X1,X2,Xn的权重,，

8、,用层次分析法的成对比较得到.,偏于主观,根据决策目的和经验先验地给出.,信息熵法,偏于客观,熵 信息论中衡量不确定性的指标，信息量的(概率)分布越一致，不确定性越大.,R归一化的每一列,各方案对Xj信息量的(概率)分布.,2）属性权重的确定,方案关于属性Xj的熵,rij=1/m时Ej=1.,属性Xj对于方案的区分度,rij只有一个1其余为0时Ej=0,rij(i=1,2,m)相差越大,Ej越小,Xj越能辨别优劣.,Xj的权重(归一化的区分度),汽车选购,2）属性权重的确定,3种汽车价格X1取值相差最大,款式X3取值相差最小.,w1最大,rij(i=1,2,m)的均方差可作为区分度Fj(m较大

9、时).,w3最小,8.1.3 多属性决策几种主要的综合方法,方案对目标的权重（综合取值）,1.简单加权和法(SAW,Simple Additive Weighting),方案Ai 对n个属性的综合取值为,对决策矩阵采用不同的标准化,得到的结果会不同.,2.加权积法（WP,Weighted Product）,可直接用方案对属性的原始值dij,不需要标准化.,若效益型属性的权重取正值，则费用型属性的权重应取负值.,将SAW的算术加权平均改为几何加权平均：,3.接近理想解的偏好排序法(TOPSIS,Technique for Order Preference by Similarity to Ide

10、al Solution）,n个属性、m个方案视为n维空间中m个点的几何系统,每个点的坐标由各方案标准化的加权属性值确定.,决策矩阵模一化,以便在空间定义欧氏距离.,正理想解(最优方案)由所有最优加权属性值构成.,负理想解由所有最劣加权属性值构成.,定义距正、负理想解距离的数量指标:相对接近度.,按照相对接近度确定备选方案的优劣顺序.,汽车选购,统一为效益型的决策矩阵,用3种综合方法确定3种汽车的优劣顺序,属性权重取信息熵法结果:w=(0.5330,0.3293,0.1377)T,8.1.3 多属性决策几种主要的综合方法,1.简单加权和法(SAW),2.加权积法(WP),v=(0.3162,0.

11、3277,0.3562)T,v=(0.4847,0.5316,0.5639)T,v=(0.3067,0.3364,0.3569)T,汽车选购,用3种综合方法确定3种汽车的优劣顺序,3.理想解法(TOPSIS）,R模一化,vij=rij wj,正理想解,负理想解,Ai与v+距离,Ai与v-距离,S+=(0.2141,0.1470,0.1087),S-=(0.1087,0.0966,0.2141),相对接近度,C+=(0.3368,0.3966,0.6633),汽车选购,用3种综合方法确定3种汽车的优劣顺序,SAW(R归一化,最大化),WP结果差别很小,TOPSIS结果差别稍大.,优劣顺序均为A3

12、,A2,A1,简单、直观的加权和法(SAW)是人们的首选.,SAW的前提属性之间相互独立,并且具有互补性.,8.1.4 层次分析法(AHP),将决策问题自上而下地分为目标、准则、方案3个层次,直观地用一个层次结构图表示.,将二者综合得到方案对目标的权重.,确定各准则(属性)对目标的权重.,确定各方案对每一准则的权重.,确定某层n个元素X1,X2,Xn对上层元素Y的权重,A成对比较阵,aij Xi和Xj对Y的重要性之比,价格X1,性能X2,款式X3对目标Y(汽车选购)的成对比较阵:,正互反阵,n个元素两两相互对比,对比采用相对尺度,1.成对比较矩阵和特征向量,1.成对比较矩阵和特征向量,成对比较

13、的一致性,n个元素需做n(n1)/2次成对比较,要求全部一致是不现实、也不必要的.,AHP容许成对比较存在不一致，并确定了这种不一致的容许范围.,a12=2X1与X2重要性之比是2:1,X1与X3重要性之比应是4:1,a23=2X2与X3重要性之比是2:1,成对比较完全一致,1.成对比较矩阵和特征向量,假定X1,X2,Xn对Y的重要性之比已精确测定为w1:w2:wn,令aij=wi/wj,成对比较阵A满足,一致阵的各列均相差一个比例因子,一致阵A的代数性质：,任一列向量都是对应于n的特征向量.,秩为1,唯一非零特征根为n.,设,1.成对比较矩阵和特征向量,取权向量为w=(w1,w2,wn)T,

14、一致阵A的任一列向量都是对应于n的特征向量.,如果成对比较阵A不一致(但在容许范围内),2.1-9比较尺度,Saaty提出19尺度:aij=1,2,9及1,1/2,1/9.,心理学家认为成对比较的因素不宜超过9个.,用13,15,117,1p9p(p=2,3,4,5),d+0.1d+0.9(d=1,2,3,4)等27种比较尺度对若干实例构造成对比较阵，算出权向量，与实际对比发现，19尺度较优.,便于定性到定量的转化：,Xi和Xj对Y重要性,aij,3.一致性指标和一致性检验,Saaty定义一致性指标:,界定成对比较阵(正互反阵)A不一致的范围.,n阶正互反阵A的最大特征根 n，A是一致阵的充要

15、条件为=n.,CI=0时A是一致阵,CI越大A越不一致.,比n大得越多,A与一致阵相差越大,用特征向量作为权向量引起的判断误差越大.,当CR0.1时通过一致性检验,Saaty引入随机一致性指标 RI从1,2,9及1,1/2,1/9随机取值构成A,计算CI的平均值作为RI.,3.一致性指标和一致性检验,制定衡量CI 数值的标准，界定A不一致的范围.,Saaty给出,应用时将n阶成对比较阵A的CI与同阶的RI比较.,4.综合权重,第2层对第1层的成对比较阵,用MATLAB软件计算最大特征根和特征向量w.,RI=0.58,归一化的w=(0.5954，0.2764，0.1283)T为权向量.,4.综合

16、权重,，,第3层对第2层的成对比较阵,=(0.2817,0.2754,0.4429)T,由A得到归一化的w,3方案对目标的综合权重,4.综合权重,与多属性决策的简单加权和法 比较:,W(3)第3层(方案)对第2层(准则)的权向量构成的矩阵,w(2)第2层(准则)对第1层(目标)的权向量,w(3)第3层(方案)对第1层(目标)的权向量,二者综合方法相同(矩阵W(3)和R的来源不同).,AHP推广到s层,W(k)第k层对第k1层的权向量构成的矩阵,w(s)最下层对第1层的权向量,8.1.5 多属性决策问题的求解,职员晋升,构造 层次结构图,用层次分析法等确定4项准则对目标的权重wi,确定每一准则各

17、个等级在该准则中的权重wij,将wi归一化,wij最大化,职员晋升,工作4年、能力优秀、品质良好的本科毕业生Ak总分:0.60.3+0.90.2+10.3+0.80.2=0.82.,每个申报者根据在准则中所处等级的位置对号入座.,评定前确定标准分(如0.80),标准分以上才可以晋升.,0.82,对学生宿舍设计方案的评价,1.建立层次结构，确定准则的权重,主观与客观相结合确定准则和子准则的权重(可以向专家及使用对象大学生调查).,1.建立层次结构，确定准则的权重,w1,w2,w3 准则对目标的权重(归一化),w11,w12,w13；w21,w22,w23,w24,w25；w31,w32 各个子准

18、则对相应准则的权重(归一化),u1,u2,u10子准则对目标的权重.,u1=w11w1,u2=w12w1,u10=w32w3,u1+u10=1,2.确定各个方案对每个子准则的权重,多数子准则可采用客观、定量方法比较方案优劣.,X1正比于每个学生的平均总建筑面积(可细分为宿舍、卫浴、公共面积等),各个方案对建筑面积、学生人数加以量化.,每个学生的平均卫浴面积及盥洗槽、喷头、马桶的数量等.,对一层楼面考虑每个学生的平均楼道宽度、楼梯宽度、房间与楼梯的最远距离等.,3.各个方案权重的标准化及综合权重,对费用型子准则如建设成本X1等的权重作倒数变换,化为效益型.,方案对子准则的权重作最大化比例尺度变换

19、.,vkj 方案k对第j子准则的权重.,方案k对目标的综合得分(权重),u1,u2,u10子准则对目标的权重.,多数方法得到的最终结果是方案2最优.,8.1.6 多属性决策和层次分析法应用中的几个问题,1.权重度量的相对量测与绝对量测,已有充分了解的老问题;明确、具体的准则.,当新方案加入或老方案退出时,用绝对量测原有方案的结果不变；用相对量测要重新做对比,原有方案的结果可能改变.,尚无太多知识的新问题；模糊、抽象的准则.,2.比例尺度的分配模式与理想模式,分配模式(Distributive Mode)归一化,某一方案属性值改变引起其他方案属性值随之改变,理想模式(Ideal Mode)最大化

20、,任一方案的属性值独立于最优方案外的其他方案.,列最大值为1:各方案与占资源1的最优方案比较.,列和为1:各方案分配总量固定(1单位)的资源.,2.比例尺度的分配模式与理想模式,方案的优劣排序大体上一致(方案数量不多时).,两种模式计算的结果数值上一般不会相同.,在实际应用中究竟应该采用哪种模式?,分配模式决策者关心每个方案相对其他方案的占优程度;需要对候选方案的优劣给出定量评价;特别用于资源分配问题.,理想模式决策者关心每个方案相对于基准指标的优劣;从众多候选方案中只选一个最优者.,3.区间尺度使用中的问题,区间尺度变换结果的最小值一定是0.,区间尺度不符合Saaty提出的使用比例尺度构造成

21、对比较阵(正互反阵)的要求.,对原始权重dij作伸缩与平移变换,不被层次分析法采用,只是多属性决策可使用的方法之一.,常识：教学0.5万平分,科研0.5万给B.,与常识一致,与常识有别,区间尺度,严重不妥!,3.区间尺度使用中的问题,例.奖金1万元按教学和科研并重原则分配给A,B.,理想模式,分配模式,把非常接近的教学原始分51和49分别变成1和0,为什么？,4.方案的排序保持与排序逆转,问题：若各准则对目标的权重不变,当新方案加 入或旧方案退出时，原有方案的优劣排序 是保持还是会逆转？,选择工作岗位考虑发展前景和当前报酬2个指标,权重为0.6和0.4.某人有3个岗位A1,A2,A3可选,由岗

22、位对指标的原始分确定选择.,用理想模式和分配模式可能会得到不同的结果.,例.工作选择,两种模式得到的优劣排序都是A1,A2,A3,例.工作选择,例.工作选择,增加新岗位A4,原始分与A1相同.,A1,A2排序:理想模式保持;分配模式逆转.,例.工作选择,增加新岗位A4,发展前景更好.,A1,A2排序保持,A1,A2排序逆转,新方案加入时,只要它对每个准则的权重都不超过原方案,用理想模式计算原方案的排序保持不变,用分配模式计算原方案的排序可能逆转.,4.方案的排序保持与排序逆转,分配模式各方案对每一准则权重rij对i之和恒为1,新方案加入导致原来rij减少,稀释了原有资源,资源的重新分配可能导致

23、原方案排序逆转.,理想模式各方案对每一准则权重rij 对i最大值为1,新方案加入只要不改变原来的最大值,就不会稀释原有资源,原方案排序将保持不变.,4.方案的排序保持与排序逆转,分配模式适用于封闭系统,或者承认资源稀释合法的开放系统(允许排序逆转).,封闭系统方案固定,开放系统方案不固定,85%95%,模拟计算结果(Saaty):方案排序逆转的比例较小.,准则和方案数量增加,方案排序不变的比例下降.,90%以上,理想模式,分配模式,原方案全部排序不变,最优方案不变,95%以上,60%90%,小结与评注,多属性决策和层次分析法都用于解决确定性决策问题.,小结与评注,可以将多属性决策和层次分析中的

24、方法结合起来运用,如用成对比较阵来确定属性(准则)权重，用绝对量测确定决策矩阵.,一般来说相对量测偏于主观、定性,绝对量测偏于客观、定量,应尽量采用绝对量测.,采用不同的标准化和综合方法对最终决策的影响远小于不同属性集合及属性权重对最终决策的影响.不要过度注意前者,应对后者多些关注.,8.2 风险性决策与非确定性决策,备选方案存在两种或更多种状态，不确定哪一种状态实际上会出现,风险性决策：每一种状态出现的概率已知,非确定性决策：每一种状态出现的概率未知,两类决策问题,每个备选方案都可以确定地实现,8.2.1 风险性决策与非确定性决策问题的提出8.2.2 风险性决策8.2.3 非确定性决策,8.

25、2 风险性决策与非确定性决策,例1 新建还是改建,现有两种备选方案：新建或改建厂房,某公司为增加产量、拓展市场拟制定10年规划,问题,据估计未来市场销路好和销路差的概率分别是0.7和0.3,若投资400万元新建厂房，销路好时年收益100万元，销路差时年亏损20万元,若投资100万元改建厂房，销路好和销路差时的年收益分别为40万元和10万元,从净利润最大化角度为公司确定决策,问题1,8.2.1 问题的提出,例1 新建还是改建,对未来市场的估计不可能准确，问对销路概率的估计变化多大就会导致决策的改变？,问题2,第3种方案：先做改建，3年后视市场情况再定,若3年销路好，则未来7年销路仍然好的概率将提

26、高到0.9,若投资200万元扩建，销路好时年收益将为90万元，销路差时不赢不亏,问题3,若不扩建，年收益不变,若3年销路差,未来7年销路一定差,不扩建,收益不变,从净利润最大化角度如何作出新的决策？,例1 新建还是改建,仍从问题1的两种方案（新建、改建）出发,为了降低由于对市场销路估计不准确带来的风险，拟重金聘请专家团队利用科学方法进行预测,问题4,根据可靠资料,该团队预测的准确性高达90%,从净利润最大化的角度,公司最多能出多少聘用金？,例2 选择投资决策,某人一笔资金有4种投资方案供选择：股票、基金、债劵、储蓄,收益前景可分为好、中、差3个状态(无法估计出现概率),问题,若某人是冒险型，或

27、保守型，或持中性态度的投资者，制定合适的准则并据此选择最优决策,8.2.2 风险性决策(结合例1“新建还是改建”介绍),两方案在两状态下的收益(10年)和投资,期望值准则,E(1)E(2),最优决策是新建厂房净利润期望值为240（万元）-回答问题1,E(1)=100100.7+(2010)0.3400=240,E(2)=40100.7+10100.3100=210,8.2.2 风险性决策,两方案在两状态下的收益(10年)和投资,敏感性分析,决策对估计概率的变化相当敏感-回答问题2,E(1)=10010p+(2010)(1p)400=1200p600,E(2)=4010p+1010(1p)100

28、=300p,当p=2/3时E(1)=E(2)；当p2/3时E(1)E(2),8.2.2 风险性决策,两方案在两状态下的收益(10年)和投资,敏感性分析,决策对估计概率的变化相当敏感-回答问题2,E(1)=10010p+(2010)(1p)400=1200p600,E(2)=4010p+1010(1p)100=300p,当p=2/3时E(1)=E(2)；当p2/3时E(1)E(2),8.2.2 风险性决策,：决策节点，：状态节点，：结果节点,决策树,下面用此方法回答问题3,=240,=210,=240,/,=367,8.2.2 风险性决策,问题3是2次决策过程：第1次在方案1，2，3 中选择，方

29、案1,2计算同前，只需分析方案3,决策树,=367,=259,/,=259,=259,8.2.2 风险性决策,由主观判断或不完全信息得到的概率称先验概率,贝叶斯决策,贝叶斯公式,设若事件B出现，则事件A1,A2中的一个且仅一个出现,收集更多信息，用贝叶斯公式修正的概率称后验概率,8.2.2 风险性决策,A1,A2分别记销路好和差，先验概率P(A1)=0.7,P(A2)=0.3,贝叶斯决策,按照全概率公式,B1,B2分别记专家团队预测的销路好和销路差，根据“预测的准确性高达90%”可知,P(B1)=0.90.7+0.10.3=0.66P(B2)=0.10.7+0.90.3=0.34,按照贝叶斯公

30、式,8.2.2 风险性决策,贝叶斯决策,决策树,8.2.2 风险性决策,1.若专家预测销路好，则选择新建方案，期望利润540若真的销路好(概率0.95)，净利润为600万一真的销路差(概率0.05)，亏损600,贝叶斯决策,2.若专家预测销路差，则选择改建方案，期望利润63若真的销路差(概率0.79)，公司将不赢不亏若真的销路好(概率0.21)，净利润为300,3.问题4的回答聘请专家预测(准确性90%)，期望利润377.8不请专家预测（问题1），期望利润240相差137.8（万元），这是最多能出的聘金,8.2.3 非确定性决策(结合例2“选择投资决策”介绍),问题回顾,出现每一种状态的概率未

31、知，无法计算收益的期望值,需要先确定一些准则，根据准则给出最优决策 不同的准则将会得到不同的决策,8.2.3 非确定性决策,最大最大准则,或大中取大准则、乐观准则（适合于冒险型决策者）决策者从每个方案最大的收益中再选出最大者对应这个最大者的方案便是最优决策,例2：最大最大值=14，对应的方案是股票,8.2.3 非确定性决策,最大最小准则,或小中取大准则、悲观准则（适合于保守型决策者）决策者从每个方案最小的收益中再选出最大者对应这个最大者的方案便是最优决策,例2：最小最大值=4，对应的方案是储蓄,8.2.3 非确定性决策,乐观系数准则,或小中取大准则、悲观准则（适合于风险中性决策者）用和1分别对

32、每个方案的最大收益和最小收益加权求和（称为乐观系数）再从中选出最大者，对应方案便是最优决策,例2：=0.7，计算max+(1)min,7.8最大 投资基金,8.2.3 非确定性决策,后悔值准则,或大中取小后悔值准则（适合于特别害怕后悔者）计算后悔值（一定状态下的最大收益与选定方案的收益之差）选每一方案在各种状态下的最大后悔值，再取其中最小值对应的方案,例2：计算后悔值,5最小 投资债券,8.2.3 非确定性决策,评注,可以提出其他准则，如等概率准则(又称平均值准则),不需要也不可能说明哪一种准则最好，只能由决策者根据客观实际情况和自己的主观愿望选取,还有介于风险性决策与非确定性决策之间的情况，

33、如虽然不知道几种随机状态的概率值，但是知道这些数值的大小排序（称为概率排序型决策）,8.3 非合作对策,单一决策主体,决策主体的决策行为发生直接相互作用(相互影响),非合作对策,合作对策,多个决策主体,两类决策问题,军事、政治、经济、企业管理和社会科学中应用广泛,8.3 非合作对策,8.3.1 非合作对策的两个例子8.3.2 非合作对策的解纳什均衡8.3.3 点球大战模型的纳什均衡8.3.4 拥堵的早高峰模型的纳什均衡,例1 点球大战,完全随机选择策略(50%对 50%)？,假设 同时决策（球速很快，否则来不及反应）,如果不是，射门方向和扑球方向应该有什么规律？,假设 不考虑球踢向中路及守门员

34、停在中间位置,问题,守门员基本策略,罚球队员基本策略,8.3.1 两个例子,例1 点球大战,不应完全随机选择策略,共同知识：所有人都知道(所有人知道)以上信息,方向以其中一人如罚球队员的位置为基准,问题,守门员,罚球队员,经验进球概率（1400次罚球）,决策(方向选择)相互影响,完全信息静态对策,例2 拥堵的早高峰,“正点”出发：路上拥堵，既烦心又费时、耗油,只考虑一条独立道路，只考虑唯一拥堵出口（瓶颈）,决策(出发时间选择)相互影响,问题,早点发：路上不太拥堵，但早到浪费时间,道路拥堵:出行需求超过了通行能力(不考虑突发因素),晚出发：迟到“后果很严重”(扣钱,甚至解雇),完全信息静态对策,

35、参与人（局中人，决策者）策略空间（决策变量的取值范围）效用函数（决策的目标函数）,对策模型基本要素,点球大战,参与人集合N=1,2(1:罚球队员，2:守门员),罚球队员效用函数u1(a1，a2)，即进球概率,罚球队员策略a1 A1=1,2(1：左，2：右)；(纯战略)守门员策略a2 A2=1,2(1：左，2：右).(纯战略),守门员效用函数u2(a1，a2)=-u1(a1，a2)(零和对策),8.3.2 非合作对策的解纳什均衡,对策双方完全理性：使己方支付尽可能大,点球大战,u1(i，j)=mij,支付矩阵(Payoff Matrix),守门员的支付矩阵为 M(或：1 M,即不进球的概率),u

36、2(i，j)=-mij,会出现什么结果？,非合作对策的解纳什均衡,非合作对策的解纳什均衡(NE:Nash Equilibrium),不存在(纯)NE,(纯战略)纳什均衡,Nash:1994年获诺贝尔经济学奖,NE:单向改变战略不能提高自己效用，即每一方的战略对于他方的战略而言都是最优的（称为最优反应）.,(纯)NE:a*=(a1*,a2*)=(2,2),混合策略纳什均衡,罚球队员混合战略集,期望支付,S1=p=(p1,p2)|,守门员混合战略集,S2=q=(q1,q2)|,可类似地定义（混合策略）纳什均衡,纳什定理：有限对策(即有限个参与人，每人只有有限个纯策略的对策)一定存在混合策略纳什均衡

37、.,纯策略也是混合策略,8.3.3 点球大战模型的纳什均衡,理性推理：不管自己怎么做，另一方总是希望使自己得分尽量低.（二人零和对策，完全竞争）,线性规划,从一个给定的策略中期望得到的支付，总是采用该策略时可能得到的最坏的支付！,罚球队员可以用min pM来衡量策略p的好坏,max U1(p)=min pM,min U2(q)=max MqT,守门员可以用max MqT来衡量策略q的好坏,p*=(0.383,0.617),q*=(0.417,0.583),最优值 0.796,点球大战模型的纳什均衡,模型检验：,两人常数和对策：严格竞争，仍可采用线性规划求解,459次实际罚球,模型应用：对于特定

38、的点球大战，需采用具体出场的罚球队员和守门员以前对阵的进球概率数据,非严格竞争的对策：可采用纳什均衡的定义求解,纳什均衡：可扩展到多人、纯策略空间为无限集合,左40%,右60%,罚:p*=(0.383,0.617),守:q*=(0.417,0.583),左42%,右58%,仅考虑一条独立道路，单一瓶颈（不妨设为出口）,模型假设,忽略瓶颈处排队对路上所需时间的影响（常数，0）,假设瓶颈到公司所需时间为常数（不妨设为0）,每个出行者所需时间等于他在出口处排队等待时间,每个出行者（车或人）的决策：出发时刻,在纳什均衡状态下建立出行者出发时刻的分布规律,8.3.4 拥堵的早高峰模型的纳什均衡,问题的分

39、析与假设,所有出行者正点上班时刻为t*，每天早高峰有n辆完全相同的车，瓶颈最大通行能力为s(车/单位时间),第一辆、最后一辆车出发时刻为t1,t2,期间出口一直拥堵，时刻t*到公司的车的出发时刻为t0(t1t0t2),时刻t累计出发的车辆数为F(t)(t1tt2)；排队车辆数为Q(t)，Q(t1)=Q(t2)=0；累计通过出口车辆数为G(t),n较大把F(t)，Q(t)，G(t)当成连续量,单位时间等待成本为，早到成本为，迟到成本为(0)；每个出行者的总出行成本相同,模型的建立与求解,t 时刻出发的车辆在道路上的时间（等待时间）为T(t)=Q(t)/s,如果t t0（t t1），时刻t出发的车

40、辆的早到时间E(t)t*tT(t)（迟到时间：0）总成本为 C(t)T(t)+E(t)(t*t)()/s)Q(t)因所有早到者成本相同，dC/dt=0，利用Q(t1)=0有 Q(t)(s/()(tt1),模型的建立与求解,同理：tt0(tt2)时,时刻t出发车辆迟到时间L(t)t+T(t)t*总成本 C(t)T(t)L(t)(tt*)()/s)Q(t)因所有晚到者成本相同，dC/dt=0，利用Q(t2)=0得 Q(t)(s/()(t2t),比较 t t0:Q(t)(s/()(tt1)排队长度Q(t)是分段线性函数(在 t=t0 连续),模型的建立与求解,t t0 时:Q(t)(s/()(t2t

41、)t t0 时:Q(t)(s/()(tt1),累计到达F(t)=G(t)+Q(t)，而G(t)=(t-t1)s,剩下的任务：确定t1,t2,t0的值,模型的建立与求解,区间t1,t2的长度：t2t1=n/s,求解得,t1t*(/(+)(n/s)t2t*+(/(+)(n/s)t0t*(/(+)(n/s),t0 t*Q(t0)/s t0t*(/()(t0t1),Q(t)在t0连续：(s/()(t2t0)=(s/()(t0t1),t t0 时:Q(t)(s/()(t2t)t t0 时:Q(t)(s/()(tt1),0 t*t1 t2t*,模型的建立与求解,每辆车成本 C(t)(n/s)/()(与和t

42、*无关),n辆车出行的总成本是TC(n2/s)/(),模型的建立与求解,每辆车成本 C(t)(n/s)/()(与和t*无关),所有车总等待成本(TTC),n辆车出行的总成本是TC(n2/s)/(),模型的分析与应用：拥堵费,集中决策：从t1到t2的任意时刻t,出发率等于瓶颈的通行能力s（累计的出发车辆数与OCD线重合）,固定的高收费：可达到最优但实际收不到费不公平(不同车成本不同),如何收拥堵费？是否可达到上述“系统最优”？,模型的分析与应用：拥堵费,早到成本：E(t)(t*tT(t)（当t t0）消除排队即T(t)=0,收费让每辆车成本相同,按时刻t收费(a:常数),取aC(t)(n/s)/

43、(),则车成本不增,但p(t)0,较简单的收费（如分时段的固定收费）复杂路网(多出发地、多目的地、多瓶颈等)随机因素交通诱导、信息的作用 交通经济学,模型的扩展,主要参考文献：,8.4 合作对策与Shapley值,决策人无法达成有约束力的合作协议的前提下，讨论均衡的结果,决策人能够达成有约束力的合作协议的前提下，讨论公平合理的利益分配或成本分担,两类对策问题,军事、政治、经济、企业管理和社会科学中应用广泛,8.4.1 合作对策问题的提出8.4.2 n人合作对策与Shapley值8.4.3 Shapley值方法在n人合作对策中的应用,8.4 合作对策与Shapley值,例1 联合建厂费用的合理分

44、担,问题：应该怎样合理地分担总费用450呢？,3城镇筹建污水处理厂：单独建厂？联合建厂？,问题,单独建厂,1,2联合,1,3联合,2,3联合,合计500,3镇费用分别为200,150,200,费用为300,费用为330,费用为310,3镇联合,费用为450,合计550,合计480,合计510,实现大联合，节省总费用,8.4.1 合作对策问题的提出,例1 联合建厂费用的合理分担,3镇联合节省100，记分得的效益分别为x1,x2,x3,分析,费用分担 效益分配,单独建厂,1,2联合,分别200,150,200,费用为300 节省50,x1+x2+x3=100,x1+x250,0 x3 50,同理,

45、x1+x370,0 x2 30,x2+x340,0 x1 60,但满足以上条件的(x1,x2,x3)不唯一：(40,20,40),(30,30,40),(37.4,28.5,34.1),负担200-x1,150-x2,200-x3,例2 加权投票中权力的度量,背景,“一人一票”显示投票和表决的公正.,股份制公司每位股东投票和表决权的大小由所占有的股份多少决定.,一些国家、地区的议会、政府的产生，由所属的州、县等各个区域推出的代表投票决定.,代表投票的权重取决于所代表区域的人口数量.,经济或政治机构权力的分配,加权投票,例2 加权投票中权力的度量,假设一县5区(A,B,C,D,E)人口为 12,

46、4,2,1,1(万),每区一位代表按人口比例分配其投票权重为12,4,2,1,1.,将A区分成人口相等的2个子区A1，A2,每区代表的投票权重为6，6，4，2，1，1,决定结果的区域集合：A1,A2,A1,B,C,A1,B,D,改革,按简单多数规则(权重和超过总权重一半)决定投票结果.,A区代表是独裁者(能决定投票结果),其他代表都是傀儡.,权力:每位代表对投票结果的影响力,A1权:C权=6:2?,N,v n人合作对策，v特征函数,n人从v(I)得到的分配，满足,子集S称为联盟；v(S)联盟S的效益,n人合作对策与Shapley值,公理化方法,由S(子集 S中的元素数目)决定的权重,i 对S

47、的贡献(边际效益),n人合作对策与Shapley值,n个成员的全排列数,排在i之前的|S|1个成员恰是联合S中成员的排列数,例1 联合建厂费用的合理分担,下面计算Shapley值,模型,合作对策,特征函数v,记费用 c(1)=200，c(2)=150，c(3)=200，c(1,2)=300,c(1,3)=330,c(2,3)=310,c(1,2,3)=450,N=1,2,3,v()=0,v(1)=v(2)=v(3)=0 v(1,2)=c(1)+c(2)c(1,2)=50 v(1,3)=c(1)+c(3)c(1,3)=70 v(2,3)=c(2)+c(3)c(2,3)=40 v(N)=v(1,2

48、,3)=c(1)+c(2)+c(3)c(1,2,3)=100,8.4.3 Shapley值方法在n人合作对策中的应用,1/3 1/6 1/6 1/3,(1)(1,2)(1,3)(1,2,3),0 50 70 100,0 0 0 40,0 50 70 60,0 50/6 70/6 120/6,x1=40,x2=25,x3=35,1 2 2 3,例1 联合建厂费用的合理分担,总费用450分担：c(1)x1=20040=160，c(2)x2=15025=125，c(3)x3=20035=165,例2 加权投票中权力的度量,记N=1,2,3,4,5,6,依次代表A1,A2,B,C,D,E,如何计算Sh

49、apley值？,子集合(联盟)共26=64个，直接枚举比较麻烦,模型,实际上，计算i(v)时只需找出满足v(S)=1且v(S i)=0的包含i的获胜联盟S,即包含i时成员权重之和大于等于11、而i退出后成员权重之和小于11的那些S,特征函数v：当N某一子集（联盟）S的成员全部投赞成票使投票通过时，定义v(S)=1，否则v(S)=0,获胜联盟：使v(S)=1的联盟S,例2 加权投票中权力的度量,6位代表的投票权重为6,6,4,2,1,1,计算,1(v)=2(v)=19/60，3(v)=16/60,4(v)=2/60,5(v)=6(v)=2/60,权力之比19:19:16:2:2:2,权重之比6:

50、6:4,2:1:1,例2 加权投票中权力的度量,调整投票权重或者简单多数的选举规则,改革,例如：例2可表示成加权投票系统11;6,6,4,2,1,1,加权投票系统,投票人集合N=A,B,C,(n人),权重w1,w2,wn,定额q 投赞成票的投票人权重之和 q时决议通过.,w=w1+w2+wn，一般 w/2qw,对简单多数规则且权重取整数，q为大于w/2的最小整数,S=q;w1,w2,wn,此时Shapley值称为加权投票系统的Shapley权力指标,合作对策的小结与评注,定义特征函数时需要知道集合N的每一个子集S（2n个）获得的效益，在实际上常常做不到。当掌握的信息较少时分配问题的处理办法有均