2.1-第二讲 初等模型ppt课件

1、 第二讲第二讲 初等模型初等模型2.1 商人们怎样安全过河商人们怎样安全过河2.2 城市污水治理规划问题城市污水治理规划问题2.1 商人们怎样安全过河商人们怎样安全过河问题问题( (智力游戏智力游戏) ) 3名商人名商人 3名随从名随从随从们密约随从们密约, , 在河的任一在河的任一岸岸, , 一旦随从的人数比商一旦随从的人数比商人多人多, , 就杀人越货就杀人越货. .但是乘船渡河的方案由商人决定但是乘船渡河的方案由商人决定. .商人们怎样才能安全过河商人们怎样才能安全过河? ?问题分析问题分析多步决策过程多步决策过程决策决策 每一步每一步( (此岸到彼岸或彼岸到此岸此岸到彼岸或彼岸到此岸)

2、 )船上的人员船上的人员要求要求 在安全的前提下在安全的前提下( (两岸的随从数不比商人多两岸的随从数不比商人多),),经有经有限步使全体人员过河限步使全体人员过河. .河河小船小船(至多至多2人人)模型构成模型构成xk第第k次渡河前此岸的商人数次渡河前此岸的商人数yk第第k次渡河前此岸的随从数次渡河前此岸的随从数xk, yk=0,1,2,3; k=1,2, sk=(xk , yk)过程的状态过程的状态S=(x , y) x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,2S 允许状态集合允许状态集合uk第第k次渡船上的商人数次渡船上的商人数vk第第k次渡船上的随从数

3、次渡船上的随从数dk=(uk , vk)决策决策D=(u , v) u+v=1, 2 允许决策集合允许决策集合uk, vk=0,1,2; k=1,2, sk+1=sk dk +(-1)k状态转移律状态转移律求求dkD(k=1,2, n), 使使skS, 并并按转移律由按转移律由 s1=(3,3)到达到达 sn+1=(0,0).多步决策多步决策问题问题模型求解模型求解xy3322110 穷举法穷举法 编程上机编程上机 图解法图解法状态状态s=(x,y) 16个格点个格点 10个个 点点允许决策允许决策 移动移动1或或2格格; k奇奇,左下移左下移; k偶偶,右上移右上移.s1sn+1d1, ，d

4、11给出安全渡河方给出安全渡河方案案评注和思考评注和思考规格化方法规格化方法, ,易于推广易于推广考虑考虑4名商人各带一随从的情况名商人各带一随从的情况d1d11允许状态允许状态S=(x , y) x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,22.2 城市污水治理规划问题城市污水治理规划问题20km38km河流河流三城镇地理位置示意图三城镇地理位置示意图123 污水处理，排入河流污水处理，排入河流三城镇可单独建处理厂，三城镇可单独建处理厂，或联合建厂或联合建厂(用管道将污水用管道将污水送送)Q1=5Q3=5Q2=3Q污水量，污水量，L管道长度管道长度建厂费用建厂

5、费用P1=73Q0.712管道费用管道费用P2=0.66Q0.51L假假设设联合建厂的话，污水处理厂建在下游城镇联合建厂的话，污水处理厂建在下游城镇记号记号C(i):第第i城镇建厂的费用城镇建厂的费用i=1,2,3）C(i,j):第第i、j城镇联合在城镇联合在j处建厂由于费用处建厂由于费用 （i、j=1,2,3）C(i,j,k):第第i、j、k城镇联合在城镇联合在k处建厂由于费用处建厂由于费用 （i、j、k=1,2,3）230)3(,160)2(,230573) 1 (712. 0CCC35020566. 0)35(73)2 , 1 (51. 0712. 0C36538366. 0)53(73

6、)3 , 2(51. 0712. 0C46358566. 0)55(73) 3 , 1 (51. 0712. 0C460)3() 1 (CC污水处理的污水处理的5 5 种方种方案案1单独建厂单独建厂620)3()2() 1 (1CCCD总投资总投资21, 2合作合作32, 3合作合作41, 3合作合作580)3()2 , 1 (2CCD总投资总投资595) 3 , 2() 1 (3CCD总投资总投资合作不会实现合作不会实现55638) 35(66. 020566. 0)535(73) 3 , 2 , 1 (51. 051. 0712. 05 CD5三城合三城合作总投资作总投资D5最小最小, 应

7、联合建厂应联合建厂 建厂费：建厂费：d1=73(5+3+5)0.712=453 12管道费：管道费：d2=0.66 50.51 20=30 23管道费：管道费：d3=0.66 (5+3)0.51 38=73D5城城3建议：建议：d1 按按 5:3:5分担分担, d2,d3由城由城1,2担负担负城城2建议：建议：d3由城由城1,2按按 5:3分担分担, d2由城由城1担担负负城城1计算：城计算：城3分担分担d15/13=174C(3), 城城2分担分担d13/13+d3 3/8 =132C(1)不不同同意意D5如何分担？如何分担？230) 3(160) 2(230) 1 (CCC既然合作的话，要

8、有利可图既然合作的话，要有利可图321,xxx分别为联合较独立建厂节约的费用分别为联合较独立建厂节约的费用满足满足64) 3 , 2 , 1 () 3() 2() 1 (321 CCCCxxx0, 0, 0321 xxx40) 2 , 1 () 2 () 1 (21 CCCxx25) 3 , 2() 3() 2(32 CCCxx0)3 , 1()3()1(31 CCCxx三城市分摊方案321)3(,)2(,)1(xCxCxC 等等价价于于21, xx21364xxx 64039064402121 xxxx21, xx图图解解1x2x391 x6421 xx4021 xx公共部分中心公共部分中心

9、5 .32,5 .1921 xx城城1 C(1)-x1=210.5, 城城2 C(2)-x2=127.5, 城城3 C(3)-x3=218三城在总投资三城在总投资556中的分中的分担担123 x)(1Ivxniiniivxi, 2 , 1),(212121),()()(0)(sssvsvssvv,2, 1nI集合 (1) Shapley合作对策合作对策满足实函数，子集)(svIs I,v n人合作对策，人合作对策，v特征函数特征函数),(21nxxxxn人从人从v(I)得到的分配，满足得到的分配，满足v(s) 子集子集s的获利的获利!)!1()!()(nssnswniisvsvswxiSsi,

10、 2 , 1),()()(公理化方法公理化方法 s 子集子集 s中的元素数目，中的元素数目， Si 包含包含i的所有子集的所有子集)( sw由由s决定的决定的“奉献的权奉献的权重重 Shapley值值)()(isvsv i 对合作对合作s 的的“奉献奉献”)(si Shapley合作对策合作对策0)3()2()1 (,0)(vvvv3 ,2, 1I集合特征函数特征函数v(s)结合结合(集集s)建厂比单独建厂节约的投资建厂比单独建厂节约的投资),(321xxxx 三城从节约投资三城从节约投资v(I)中得到的分配中得到的分配40350160230)2 , 1 ()2() 1 ()21 (CCCv

11、64556230160230) 3 , 2 , 1 () 3() 2() 1 ()(0) 31 (25365230160) 3 , 2() 3() 2() 32(CCCCIvvCCCv Shapley合作对策合作对策计算城计算城1从节约投资中得到的分配从节约投资中得到的分配x1)1()()(svsvsw)(sws) 1()(svsv) 1(sv)(svs1 1 2 1 3 I 0 40 0 640 0 0 250 40 0 39 1 2 2 31/3 1/6 1/6 1/3 0 6.7 0 13 x1 =19.7,城城1 C(1)-x1=210.3, 城城2 C(2)-x2=127.9, 城城

12、3 C(3)-x3=217.8三城在总投资三城在总投资556中的分担中的分担x2 =32.1, x3=12.2x2最大，如何解释？最大，如何解释？合作对策的应用合作对策的应用 例例 派别在团体中的权重派别在团体中的权重 90人的团体由人的团体由3个派别组成，人数分别为个派别组成，人数分别为40, 30, 20人。人。团体表决时需过半数的赞成票方可通过。团体表决时需过半数的赞成票方可通过。1)()32()31 ()21 (, 0)3()2() 1 (, 0)(Ivvvvvvvv虽然虽然3派人数相差很大派人数相差很大若每个派别的成员同时投赞成票或反对票，用若每个派别的成员同时投赞成票或反对票，用S

13、hapley合作对策计算各派别在团体中的权重。合作对策计算各派别在团体中的权重。3/1321xxx权重团体团体 I=1,2,3，依次代表，依次代表3个派别个派别否则否则，的成员超过的成员超过定义特征函数定义特征函数045, 1)(ssv优点：公正、合理，有公理化基础。优点：公正、合理，有公理化基础。如如n个单位治理污染个单位治理污染, 通常知道第通常知道第i方单独治理的投资方单独治理的投资yi 和和n方共方共同治理的投资同治理的投资Y, 及第及第i方不参加时其余方不参加时其余n-1方的投资方的投资zi (i=1,2, n). 确定共同治理时各方分担的费用。确定共同治理时各方分担的费用。iijj

14、zyiIv)(其它其它v(s)均不知道均不知道, 无法用无法用Shapley合作对策求解合作对策求解Shapley合作对策小结合作对策小结若定义特征函数为合作的获利若定义特征函数为合作的获利(节约的投资节约的投资)，则有，则有,)(), 2 , 1(0)(1YyIvniivnii缺点：需要知道所有合作的获利，即要定义缺点：需要知道所有合作的获利，即要定义I=1,2,n的所有的所有子集子集(共共2n-1个个)的特征函数，实际上常做不到。的特征函数，实际上常做不到。),(1nbbb记设只知道设只知道)(iIvbi无无 i 参加时参加时n-1方合作的获利方合作的获利)(IvB及全体合作的获利全体合作

15、的获利0),(21inxxxxxB的分配求各方对获利),(),7 , 5 , 4(11321xxxxbB求，即已知求解合作对策的其他方法求解合作对策的其他方法例例. 甲乙丙三人合作经商，若甲乙合作获利甲乙丙三人合作经商，若甲乙合作获利7元，元，甲丙合作获利甲丙合作获利5元，乙丙合作获利元，乙丙合作获利4元，三人元，三人合作获利合作获利11元。问三人合作时如何分配获利？元。问三人合作时如何分配获利？（2协商解协商解00,AbAxTT11nniiibxxbxxBx11将剩余获利将剩余获利 平均分配平均分配 ixBnBbbnxBnxxiiiii1)(111),7 , 5 , 4(.Bb例模模型型以以

16、n-1方合作的获利为下限方合作的获利为下限TTbxA求解求解iiibbnx11 xi 的下限的下限, 3),1 , 3 , 4(ixBx) 2 , 4 , 5() 1 , 1 , 1 ( xx（3Nash解解 ),(1nddd记为现状点谈判时的威慑点）为现状点谈判时的威慑点）iiiiiidxBxtsdxxma. .)(iixd 在此基础上在此基础上“均匀地分配全体合作的获利均匀地分配全体合作的获利B模模型型0id)(1iiidBndx平均分配获利平均分配获利B3Nash解解 2协商解协商解（4最小距离解最小距离解的上限为记xxxxn),(1iiiiiixxBxtsxxnmi. .)(2模模型型

17、 第第i 方的边际效益方的边际效益iibBx若令若令nBbbnxiii111),7 , 5 , 4(.Bb例)(1Bxnxxiii4最小距离解最小距离解 2协商解协商解, 6),4 , 6 , 7(Bxxi) 2 , 4 , 5 () 2 , 2 , 2 (xx（5满意解满意解iiiiidedxu满意度Bxtsunmixmaiii. .)(di现状点现状点(最低点最低点)ei理想点理想点(最高点最高点)模模型型iiiixexd,5基于满意度的解基于满意度的解 2协商解协商解iiixed , 0)(iiiiiiiiideudxdedBu的比例分配中在按iiiiixxBxxx（6Raiffi 解解

18、jjxbBnjj获利为方合作时的原来无参与当,1)(jininxxxxxjiijj, 1,) 1(2,2:)1的分配基础上进行方合作获利的分配（在Bnx方再等分方平分，和先由11nnjxj得到再平均取,2, 1njijjiiixnxnxnnx) 1(21211) 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()!()(nssnswniisvsvswxiSsi, 2 , 1),()()()(),(IvBiIvbi只需Issv),(需要所有协商解协商解)(1iiixBnxx下限ixNash解解 )(1iiidBndx现状id最小距