861-第二讲 初等模型.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). 多步决策问题 模型求解 x y 3 3 2 2 1 1 0 穷举法 ~ 编程上机 图解法 状态s=(x,y) ~ 16个格点 ~ 10个 点 允许决策 ~ 移动1或2格; k奇,左下移; k偶,右上移. s1 sn+1 d1, ?，d11给出安全渡河方案 评注和思考 规格化方法,易于推广 考虑4名商人各带一随从的情况 d1 d11 允许状态 S={(x , y)? x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,2} 2.2 城市污水治理规划问题 20km 38km 河流 三城镇地理位置示意图 1 2 3 污水处理，排入河流 三城镇可单独建处理厂，或联合建厂(用管道将污水送) Q1=5 Q3=5 Q2=3 Q~污水量，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=73 D5 城3建议：d1 按 5:3:5分担, d2,d3由城1,2担负 城2建议：d3由城1,2按 5:3分担, d2由城1担负 城1计算：城3分担d1?5/13=174C(3), 城2分担d1?3/13+d3 ?3/8 =132C(2), 城1分担d1?5/13+d3 ?5/8+ d2 =250C(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从节约投资中得到的分配x1 1 1 2 1 3 I 0 40 0