2.1-第二講 初等模型ppt課件

1、 第二講第二講 初等模型初等模型2.1 商人們怎樣安全過河商人們怎樣安全過河2.2 城市污水治理規(guī)劃問題城市污水治理規(guī)劃問題2.1 商人們怎樣安全過河商人們怎樣安全過河問題問題( (智力游戲智力游戲) ) 3名商人名商人 3名隨從名隨從隨從們密約隨從們密約, , 在河的任一在河的任一岸岸, , 一旦隨從的人數(shù)比商一旦隨從的人數(shù)比商人多人多, , 就殺人越貨就殺人越貨. .但是乘船渡河的方案由商人決定但是乘船渡河的方案由商人決定. .商人們怎樣才能安全過河商人們怎樣才能安全過河? ?問題分析問題分析多步?jīng)Q策過程多步?jīng)Q策過程決策決策 每一步每一步( (此岸到彼岸或彼岸到此岸此岸到彼岸或彼岸到此岸)

2、 )船上的人員船上的人員要求要求 在安全的前提下在安全的前提下( (兩岸的隨從數(shù)不比商人多兩岸的隨從數(shù)不比商人多),),經(jīng)有經(jīng)有限步使全體人員過河限步使全體人員過河. .河河小船小船(至多至多2人人)模型構(gòu)成模型構(gòu)成xk第第k次渡河前此岸的商人數(shù)次渡河前此岸的商人數(shù)yk第第k次渡河前此岸的隨從數(shù)次渡河前此岸的隨從數(shù)xk, yk=0,1,2,3; k=1,2, sk=(xk , yk)過程的狀態(tài)過程的狀態(tài)S=(x , y) x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,2S 允許狀態(tài)集合允許狀態(tài)集合uk第第k次渡船上的商人數(shù)次渡船上的商人數(shù)vk第第k次渡船上的隨從數(shù)

3、次渡船上的隨從數(shù)dk=(uk , vk)決策決策D=(u , v) u+v=1, 2 允許決策集合允許決策集合uk, vk=0,1,2; k=1,2, sk+1=sk dk +(-1)k狀態(tài)轉(zhuǎn)移律狀態(tài)轉(zhuǎn)移律求求dkD(k=1,2, n), 使使skS, 并并按轉(zhuǎn)移律由按轉(zhuǎn)移律由 s1=(3,3)到達(dá)到達(dá) sn+1=(0,0).多步?jīng)Q策多步?jīng)Q策問題問題模型求解模型求解xy3322110 窮舉法窮舉法 編程上機(jī)編程上機(jī) 圖解法圖解法狀態(tài)狀態(tài)s=(x,y) 16個格點(diǎn)個格點(diǎn) 10個個 點(diǎn)點(diǎn)允許決策允許決策 移動移動1或或2格格; k奇奇,左下移左下移; k偶偶,右上移右上移.s1sn+1d1, ，d

4、11給出安全渡河方給出安全渡河方案案評注和思考評注和思考規(guī)格化方法規(guī)格化方法, ,易于推廣易于推廣考慮考慮4名商人各帶一隨從的情況名商人各帶一隨從的情況d1d11允許狀態(tài)允許狀態(tài)S=(x , y) x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,22.2 城市污水治理規(guī)劃問題城市污水治理規(guī)劃問題20km38km河流河流三城鎮(zhèn)地理位置示意圖三城鎮(zhèn)地理位置示意圖123 污水處理，排入河流污水處理，排入河流三城鎮(zhèn)可單獨(dú)建處理廠，三城鎮(zhèn)可單獨(dú)建處理廠，或聯(lián)合建廠或聯(lián)合建廠(用管道將污水用管道將污水送送)Q1=5Q3=5Q2=3Q污水量，污水量，L管道長度管道長度建廠費(fèi)用建廠

5、費(fèi)用P1=73Q0.712管道費(fèi)用管道費(fèi)用P2=0.66Q0.51L假假設(shè)設(shè)聯(lián)合建廠的話，污水處理廠建在下游城鎮(zhèn)聯(lián)合建廠的話，污水處理廠建在下游城鎮(zhèn)記號記號C(i):第第i城鎮(zhèn)建廠的費(fèi)用城鎮(zhèn)建廠的費(fèi)用i=1,2,3）C(i,j):第第i、j城鎮(zhèn)聯(lián)合在城鎮(zhèn)聯(lián)合在j處建廠由于費(fèi)用處建廠由于費(fèi)用 （i、j=1,2,3）C(i,j,k):第第i、j、k城鎮(zhèn)聯(lián)合在城鎮(zhèn)聯(lián)合在k處建廠由于費(fèi)用處建廠由于費(fèi)用 （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單獨(dú)建廠單獨(dú)建廠620)3()2() 1 (1CCCD總投資總投資21, 2合作合作32, 3合作合作41, 3合作合作580)3()2 , 1 (2CCD總投資總投資595) 3 , 2() 1 (3CCD總投資總投資合作不會實(shí)現(xiàn)合作不會實(shí)現(xiàn)55638) 35(66. 020566. 0)535(73) 3 , 2 , 1 (51. 051. 0712. 05 CD5三城合三城合作總投資作總投資D5最小最小, 應(yīng)

7、聯(lián)合建廠應(yīng)聯(lián)合建廠 建廠費(fèi)：建廠費(fèi)：d1=73(5+3+5)0.712=453 12管道費(fèi)：管道費(fèi)：d2=0.66 50.51 20=30 23管道費(fèi)：管道費(fèi)：d3=0.66 (5+3)0.51 38=73D5城城3建議：建議：d1 按按 5:3:5分擔(dān)分擔(dān), d2,d3由城由城1,2擔(dān)負(fù)擔(dān)負(fù)城城2建議：建議：d3由城由城1,2按按 5:3分擔(dān)分擔(dān), d2由城由城1擔(dān)擔(dān)負(fù)負(fù)城城1計(jì)算：城計(jì)算：城3分擔(dān)分擔(dān)d15/13=174C(3), 城城2分擔(dān)分擔(dān)d13/13+d3 3/8 =132C(1)不不同同意意D5如何分擔(dān)？如何分擔(dān)？230) 3(160) 2(230) 1 (CCC既然合作的話，要

8、有利可圖既然合作的話，要有利可圖321,xxx分別為聯(lián)合較獨(dú)立建廠節(jié)約的費(fèi)用分別為聯(lián)合較獨(dú)立建廠節(jié)約的費(fèi)用滿足滿足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三城市分?jǐn)偡桨?21)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中的分中的分擔(dān)擔(dān)123 x)(1Ivxniiniivxi, 2 , 1),(212121),()()(0)(sssvsvssvv,2, 1nI集合 (1) Shapley合作對策合作對策滿足實(shí)函數(shù)，子集)(svIs I,v n人合作對策，人合作對策，v特征函數(shù)特征函數(shù)),(21nxxxxn人從人從v(I)得到的分配，滿足得到的分配，滿足v(s) 子集子集s的獲利的獲利!)!1()!()(nssnswniisvsvswxiSsi,

10、 2 , 1),()()(公理化方法公理化方法 s 子集子集 s中的元素數(shù)目，中的元素數(shù)目， Si 包含包含i的所有子集的所有子集)( sw由由s決定的決定的“奉獻(xiàn)的權(quán)奉獻(xiàn)的權(quán)重重 Shapley值值)()(isvsv i 對合作對合作s 的的“奉獻(xiàn)奉獻(xiàn)”)(si Shapley合作對策合作對策0)3()2()1 (,0)(vvvv3 ,2, 1I集合特征函數(shù)特征函數(shù)v(s)結(jié)合結(jié)合(集集s)建廠比單獨(dú)建廠節(jié)約的投資建廠比單獨(dú)建廠節(jié)約的投資),(321xxxx 三城從節(jié)約投資三城從節(jié)約投資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合作對策合作對策計(jì)算城計(jì)算城1從節(jié)約投資中得到的分配從節(jié)約投資中得到的分配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中的分擔(dān)中的分擔(dān)x2 =32.1, x3=12.2x2最大，如何解釋？最大，如何解釋？合作對策的應(yīng)用合作對策的應(yīng)用 例例 派別在團(tuán)體中的權(quán)重派別在團(tuán)體中的權(quán)重 90人的團(tuán)體由人的團(tuán)體由3個派別組成，人數(shù)分別為個派別組成，人數(shù)分別為40, 30, 20人。人。團(tuán)體表決時需過半數(shù)的贊成票方可通過。團(tuán)體表決時需過半數(shù)的贊成票方可通過。1)()32()31 ()21 (, 0)3()2() 1 (, 0)(Ivvvvvvvv雖然雖然3派人數(shù)相差很大派人數(shù)相差很大若每個派別的成員同時投贊成票或反對票，用若每個派別的成員同時投贊成票或反對票，用S

13、hapley合作對策計(jì)算各派別在團(tuán)體中的權(quán)重。合作對策計(jì)算各派別在團(tuán)體中的權(quán)重。3/1321xxx權(quán)重團(tuán)體團(tuán)體 I=1,2,3，依次代表，依次代表3個派別個派別否則否則，的成員超過的成員超過定義特征函數(shù)定義特征函數(shù)045, 1)(ssv優(yōu)點(diǎn)：公正、合理，有公理化基礎(chǔ)。優(yōu)點(diǎn)：公正、合理，有公理化基礎(chǔ)。如如n個單位治理污染個單位治理污染, 通常知道第通常知道第i方單獨(dú)治理的投資方單獨(dú)治理的投資yi 和和n方共方共同治理的投資同治理的投資Y, 及第及第i方不參加時其余方不參加時其余n-1方的投資方的投資zi (i=1,2, n). 確定共同治理時各方分擔(dān)的費(fèi)用。確定共同治理時各方分擔(dān)的費(fèi)用。iijj

14、zyiIv)(其它其它v(s)均不知道均不知道, 無法用無法用Shapley合作對策求解合作對策求解Shapley合作對策小結(jié)合作對策小結(jié)若定義特征函數(shù)為合作的獲利若定義特征函數(shù)為合作的獲利(節(jié)約的投資節(jié)約的投資)，則有，則有,)(), 2 , 1(0)(1YyIvniivnii缺點(diǎn)：需要知道所有合作的獲利，即要定義缺點(diǎn)：需要知道所有合作的獲利，即要定義I=1,2,n的所有的所有子集子集(共共2n-1個個)的特征函數(shù)，實(shí)際上常做不到。的特征函數(shù)，實(shí)際上常做不到。),(1nbbb記設(shè)只知道設(shè)只知道)(iIvbi無無 i 參加時參加時n-1方合作的獲利方合作的獲利)(IvB及全體合作的獲利全體合作

15、的獲利0),(21inxxxxxB的分配求各方對獲利),(),7 , 5 , 4(11321xxxxbB求，即已知求解合作對策的其他方法求解合作對策的其他方法例例. 甲乙丙三人合作經(jīng)商，若甲乙合作獲利甲乙丙三人合作經(jīng)商，若甲乙合作獲利7元，元，甲丙合作獲利甲丙合作獲利5元，乙丙合作獲利元，乙丙合作獲利4元，三人元，三人合作獲利合作獲利11元。問三人合作時如何分配獲利？元。問三人合作時如何分配獲利？（2協(xié)商解協(xié)商解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記為現(xiàn)狀點(diǎn)談判時的威懾點(diǎn)）為現(xiàn)狀點(diǎn)談判時的威懾點(diǎn)）iiiiiidxBxtsdxxma. .)(iixd 在此基礎(chǔ)上在此基礎(chǔ)上“均勻地分配全體合作的獲利均勻地分配全體合作的獲利B模模型型0id)(1iiidBndx平均分配獲利平均分配獲利B3Nash解解 2協(xié)商解協(xié)商解（4最小距離解最小距離解的上限為記xxxxn),(1iiiiiixxBxtsxxnmi. .)(2模模型型

17、 第第i 方的邊際效益方的邊際效益iibBx若令若令nBbbnxiii111),7 , 5 , 4(.Bb例)(1Bxnxxiii4最小距離解最小距離解 2協(xié)商解協(xié)商解, 6),4 , 6 , 7(Bxxi) 2 , 4 , 5 () 2 , 2 , 2 (xx（5滿意解滿意解iiiiidedxu滿意度Bxtsunmixmaiii. .)(di現(xiàn)狀點(diǎn)現(xiàn)狀點(diǎn)(最低點(diǎn)最低點(diǎn))ei理想點(diǎn)理想點(diǎn)(最高點(diǎn)最高點(diǎn))模模型型iiiixexd,5基于滿意度的解基于滿意度的解 2協(xié)商解協(xié)商解iiixed , 0)(iiiiiiiiideudxdedBu的比例分配中在按iiiiixxBxxx（6Raiffi 解解

18、jjxbBnjj獲利為方合作時的原來無參與當(dāng),1)(jininxxxxxjiijj, 1,) 1(2,2:)1的分配基礎(chǔ)上進(jìn)行方合作獲利的分配（在Bnx方再等分方平分，和先由11nnjxj得到再平均取,2, 1njijjiiixnxnxnnx) 1(21211) 4 , 6 , 7 (),1 , 3 , 4(xx與協(xié)商解與協(xié)商解x=(5,4,2)比較比較11),7 , 5 , 4(.Bb例)1252,12113,324（x求解合作對策的求解合作對策的6種方法可分為三類）種方法可分為三類）Shapley合作對策合作對策A類類B類類!)!1()!()(nssnswniisvsvswxiSsi, 2 , 1),()()()(),(IvBiIvbi只需Issv),(需要所有協(xié)商解協(xié)商解)(1iiixBnxx下限ixNash解解 )(1iiidBndx現(xiàn)狀id最小距