教学课件第二讲初等模型.ppt

第第二二讲讲 初等模型初等模型2.1 商人商人们怎怎样安全安全过河河2.2 城市城市污水治理水治理规划划问题2.1 商人商人们怎怎样安全安全过河河问题(智力游智力游戏)      3名商人名商人       3名随从名随从随从们密约随从们密约, , 在河的任一在河的任一岸岸, , 一旦随从的人数比商一旦随从的人数比商人多人多, , 就杀人越货就杀人越货. .但是乘船渡河的方案由商人决定但是乘船渡河的方案由商人决定. .商人们怎样才能安全过河商人们怎样才能安全过河?问题分析分析多步决策过程多步决策过程决策决策~ 每一步每一步(此岸到彼岸或彼岸到此岸此岸到彼岸或彼岸到此岸)船上的人船上的人员要求要求~在安全的前提下在安全的前提下(两岸的随从数不比商人多两岸的随从数不比商人多),经有限有限步使全体人步使全体人员过河河.河河小船小船(至多至多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,2}S ~ 允许状态集合允许状态集合uk~第第k次渡船上的商人数次渡船上的商人数vk~第第k次渡船上的随从数次渡船上的随从数dk=(uk , vk)~决策决策D={(u , v)  u+v=1, 2} ~允许允许决策决策集合集合uk, vk=0,1,2; k=1,2, sk+1=sk dk +(-1)k~状态转移律状态转移律求求dk D(k=1,2, n), 使使sk S, 并并按按转移律转移律由由 s1=(3,3)到达到达 sn+1=(0,0).多步决策多步决策问题模型求解模型求解xy3322110• 穷举法穷举法 ~ 编程上机编程上机• 图解法解法状态状态s=(x,y) ~ 16个格点个格点 ~ 10个个 点点允许决策允许决策 ~ 移动移动1或或2格格; k奇奇,左下移左下移; k偶偶,右上移右上移.s1sn+1d1, ，，d11给出安全渡河方案给出安全渡河方案评注和思考注和思考规格化方法规格化方法, ,易于推广易于推广考虑考虑4名商人各带一随从的情况名商人各带一随从的情况d1d11允许状态允许状态S={(x , y) x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,2}2.2 城市城市污水治理水治理规划划问题20km38km河流河流三城镇地理位置示意图三城镇地理位置示意图123• 污水处理，排入河流污水处理，排入河流•三城镇可单独建处理厂，三城镇可单独建处理厂，或联合建厂或联合建厂(用管道将污水用管道将污水送送)Q1=5Q3=5Q2=3Q~污水量，污水量，L~管道长度管道长度建厂费用建厂费用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））污水水处理的理的5 种方案种方案1）单独建厂）单独建厂总投资总投资2））1, 2合作合作3））2, 3合作合作4））1, 3合作合作总总投资投资总投资总投资合作不会实现合作不会实现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=73D5城城3建议：建议：d1 按按 5:3:5分担分担, d2,d3由城由城1,2担负担负城城2建议：建议：d3由城由城1,2按按 5:3分担分担, d2由城由城1担负担负城城1计算：计算：城城3分担分担d1 5/13=174C(1)不不同同意意D5如何分担？如何分担？既然合作的话，要有利可图既然合作的话，要有利可图分别为联合较独立建厂节约的费用分别为联合较独立建厂节约的费用满满足足三城市分摊方案公共部分中心公共部分中心城城1 C(1)-x1=210.5, 城城2 C(2)-x2=127.5, 城城3 C(3)-x3=218三城在总投资三城在总投资556中的分担中的分担 (1) Shapley合作合作对策策[ I,v] ~n人合作对策，人合作对策，v~特征函数特征函数~n人从人从v(I)得到的分配，满足得到的分配，满足v(s)~ 子集子集s的获利的获利公理化方法公理化方法 s ~子集子集 s中的元素数目，中的元素数目， Si ~包含包含i的所有子集的所有子集~由由 s 决定的决定的“贡献贡献”的权重的权重 Shapley值值~ i 对合作对合作s 的的“贡献贡献”Shapley合作合作对策策特征函数特征函数v(s)~联合联合(集集s)建厂比单独建厂节约的投资建厂比单独建厂节约的投资~三三城从城从节约投资节约投资v(I)中得到的分配中得到的分配 Shapley合作合作对策策计算计算城城1从从节约投资中得到的分配节约投资中得到的分配x11 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, 城城3 C(3)-x3=217.8三城在总投资三城在总投资556中的分担中的分担x2 =32.1, x3=12.2x2最大，如何解释？最大，如何解释？合作合作对策的策的应用用 例例 派派别在在团体中的体中的权重重 90人的团体由人的团体由3个派别组成，人数分别为个派别组成，人数分别为40, 30, 20人。

团体表决时需过半人团体表决时需过半数的赞成票方可通过数的赞成票方可通过虽然虽然3派人数相差很大派人数相差很大若每个派别的成员同时投赞成票或反对票，用若每个派别的成员同时投赞成票或反对票，用Shapley合作对策合作对策计算计算各派各派别在团体中的权重别在团体中的权重团体团体 I={1,2,3}，依次代表，依次代表3个派别个派别îíì=否则否则，的成员超过的成员超过定义定义特征函数特征函数045, 1)(ssv优点：优点：公正、合理，有公理化基础公正、合理，有公理化基础如如n个单位治理污染个单位治理污染, 通常知道第通常知道第i方单独治理的投资方单独治理的投资yi 和和n方共同治理的投资方共同治理的投资Y, 及第及第i方不参加时其余方不参加时其余n-1方的投资方的投资zi (i=1,2, …n). 确定共同治理时各方分担的费用确定共同治理时各方分担的费用其它其它v(s)均不知道均不知道, 无法用无法用Shapley合作对策合作对策求解求解Shapley合作对策小结合作对策小结若定义特征函数为合作的获利若定义特征函数为合作的获利(节约的投资节约的投资)，则有，则有缺点：缺点：需要知道所有合作的获利，即要定义需要知道所有合作的获利，即要定义I={1,2,…n}的所有子集的所有子集(共共2n-1个个)的特征的特征函数，实际上常做不到。

函数，实际上常做不到设只知道设只知道无无 i 参加时参加时n-1方合作的获利方合作的获利全体合作的获利全体合作的获利求解合作求解合作对策的其他方法策的其他方法例例. 甲乙丙三人合作经商，若甲乙合作获利甲乙丙三人合作经商，若甲乙合作获利7元，元，甲丙合作获利甲丙合作获利5元，乙丙合作获利元，乙丙合作获利4元，三人元，三人合作获利合作获利11元问三人合作时如何分配获利？元问三人合作时如何分配获利？（（2））协商解商解11将剩余获利将剩余获利 平均分配平均分配 模模型型以以n-1方合作的获利为下限方合作的获利为下限求解求解~ xi 的下限的下限（（3））Nash解解 为现状点（谈判时的威慑点）为现状点（谈判时的威慑点）在此基础上在此基础上“均匀地均匀地”分配全体合作的获利分配全体合作的获利B模模型型平均分配获利平均分配获利B3））Nash解解  2）协商解）协商解（（4）最小距离解）最小距离解模模型型 第第i 方的边际效益方的边际效益若令若令4）最小距离解）最小距离解  2）协商解）协商解（（5））满意解意解di~现状点现状点(最低点最低点)ei~理想点理想点(最高点最高点)模模型型5）基于满意度的解）基于满意度的解 2）协商解）协商解（（6））Raiffi 解解与协商解与协商解x=(5,4,2)比较比较求解合作求解合作对策的策的6种方法（可分种方法（可分为三三类））Shapley合作对策合作对策A类类B类类协商解协商解Nash解解 最小距离解最小距离解满意解满意解di~现状现状, ei~理想理想B类类4种方法相同种方法相同例：有一资方例：有一资方(甲甲)和二劳方和二劳方(乙乙,丙丙), 仅当资方与至少仅当资方与至少一劳方合作时才获利一劳方合作时才获利10元，应如何分配该获利？元，应如何分配该获利？Raiffi解解C类类B类：计算简单，便于理解，可用于各方实类：计算简单，便于理解，可用于各方实力相差不大的情况；一般来说它偏袒强者。

力相差不大的情况；一般来说它偏袒强者 C类：类： 考虑了分配的上下限，又吸取了考虑了分配的上下限，又吸取了Shapley的思想，在一定程度上保护弱者的思想，在一定程度上保护弱者A类：公正合理；需要信息多，计算复杂类：公正合理；需要信息多，计算复杂求解合作求解合作对策的三策的三类方法小方法小结。