【教學(xué)】第二講 初等模型

第二講初等模型2.1商人們怎樣安全過河2.2城市污水治理規(guī)劃問題2.1商人們怎樣安全過河問題(智力游戲)3名商人3名隨從隨從們密約,在河的任一岸,一旦隨從的人數(shù)比商人多,就殺人越貨.但是乘船渡河的方案由商人決定.商人們怎樣才能安全過河?問題分析多步?jīng)Q策過程決策~每一步(此岸到彼岸或彼岸到此岸)船上的人員要求~在安全的前提下(兩岸的隨從數(shù)不比商人多),經(jīng)有限步使全體人員過河.河小船(至多2人)模型構(gòu)成xk~第k次渡河前此岸的商人數(shù)yk~第k次渡河前此岸的隨從數(shù)xk,yk=0,1,2,3;

k=1,2,sk=(xk,yk)~過程的狀態(tài)S={(x

,y)x=0,y=0,1,2,3;x=3,y=0,1,2,3;x=y=1,2}S~允許狀態(tài)集合uk~第k次渡船上的商人數(shù)vk~第k次渡船上的隨從數(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)移律求dkD(k=1,2,n),使skS,并按轉(zhuǎn)移律由s1=(3,3)到達sn+1=(0,0).多步?jīng)Q策問題模型求解xy3322110窮舉法~編程上機圖解法狀態(tài)s=(x,y)~16個格點~10個點允許決策~移動1或2格;k奇,左下移;k偶,右上移.s1sn+1d1,，d11給出安全渡河方案評注和思考規(guī)格化方法,易于推廣考慮4名商人各帶一隨從的情況d1d11允許狀態(tài)S={(x

,y)x=0,y=0,1,2,3;

x=3,y=0,1,2,3;x=y=1,2}2.2城市污水治理規(guī)劃問題20km38km河流三城鎮(zhèn)地理位置示意圖123污水處理，排入河流三城鎮(zhèn)可單獨建處理廠，或聯(lián)合建廠(用管道將污水送)Q1=5Q3=5Q2=3Q~污水量，L~管道長度建廠費用P1=73Q0.712管道費用P2=0.66Q0.51L假設(shè)聯(lián)合建廠的話，污水處理廠建在下游城鎮(zhèn)記號C(i):第i城鎮(zhèn)建廠的費用（i=1,2,3）C(i,j):第i、j城鎮(zhèn)聯(lián)合在j處建廠由于費用（i、j=1,2,3）C(i,j,k):第i、j、k城鎮(zhèn)聯(lián)合在k處建廠由于費用（i、j、k=1,2,3）污水處理的5種方案1）單獨建廠總投資2）1,2合作3）2,3合作4）1,3合作總投資總投資合作不會實現(xiàn)5）三城合作總投資D5最小,應(yīng)聯(lián)合建廠建廠費：d1=73(5+3+5)0.712=45312管道費：d2=0.6650.5120=3023管道費：d3=0.66(5+3)0.5138=73D5城3建議：d1按5:3:5分擔(dān),d2,d3由城1,2擔(dān)負城2建議：d3由城1,2按5:3分擔(dān),d2由城1擔(dān)負城1計算：城3分擔(dān)d15/13=174<C(3),

城2分擔(dān)d13/13+d33/8

=132<C(2),城1分擔(dān)d15/13+d35/8+d2

=250>C(1)不同意D5如何分擔(dān)？既然合作的話，要有利可圖分別為聯(lián)合較獨立建廠節(jié)約的費用滿足三城市分攤方案公共部分中心城1C(1)-x1=210.5,城2C(2)-x2=127.5,城3C(3)-x3=218三城在總投資556中的分擔(dān)(1)

Shapley合作對策[I,v]~n人合作對策，v~特征函數(shù)~n人從v(I)得到的分配，滿足v(s)~子集s的獲利公理化方法s~子集s中的元素數(shù)目，Si~包含i的所有子集~由s決定的“貢獻”的權(quán)重Shapley值~i對合作s的“貢獻”Shapley合作對策特征函數(shù)v(s)~聯(lián)合(集s)建廠比單獨建廠節(jié)約的投資~三城從節(jié)約投資v(I)中得到的分配Shapley合作對策計算城1從節(jié)約投資中得到的分配x111213I0400640002504003912231/31/61/61/3

06.7

013

x1=19.7,城1C(1)-x1=210.3,城2C(2)-x2=127.9,城3C(3)-x3=217.8三城在總投資556中的分擔(dān)x2=32.1,x3=12.2x2最大，如何解釋？合作對策的應(yīng)用例派別在團體中的權(quán)重90人的團體由3個派別組成，人數(shù)分別為40,30,20人。團體表決時需過半數(shù)的贊成票方可通過。雖然3派人數(shù)相差很大若每個派別的成員同時投贊成票或反對票，用Shapley合作對策計算各派別在團體中的權(quán)重。團體I={1,2,3}，依次代表3個派別?íì=否則，的成員超過定義特征函數(shù)045,1)(ssv優(yōu)點：公正、合理，有公理化基礎(chǔ)。如n個單位治理污染,通常知道第i方單獨治理的投資yi和n方共同治理的投資Y,及第i方不參加時其余n-1方的投資zi(i=1,2,…n).確定共同治理時各方分擔(dān)的費用。其它v(s)均不知道,無法用Shapley合作對策求解Shapley合作對策小結(jié)若定義特征函數(shù)為合作的獲利(節(jié)約的投資)，則有缺點：需要知道所有合作的獲利，即要定義I={1,2,…n}的所有子集(共2n-1個)的特征函數(shù)，實際上常做不到。設(shè)只知道無i參加時n-1方合作的獲利全體合作的獲利求解合作對策的其他方法例.甲乙丙三人合作經(jīng)商，若甲乙合作獲利7元，甲丙合作獲利5元，乙丙合作獲利4元，三人合作獲利11元。問三人合作時如何分配獲利？（2）協(xié)商解11將剩余獲利平均分配模型以n-1方合作的獲利為下限求解~xi的下限（3）Nash解為現(xiàn)狀點（談判時的威懾點）在此基礎(chǔ)上“均勻地”分配全體合作的獲利B模型平均分配獲利B3）Nash解2）協(xié)商解（4）最小距離解模型第i方的邊際效益若令4）最小距離解2）協(xié)商解（5）滿意解di~現(xiàn)狀點(最低點)ei~理想點(最高點)模型5）基于滿意度的解2）協(xié)商解（6）Raiffi解與協(xié)商解x=(5,4,2)比較求解合作對策的6種方法（可分為三類）Shapley合作對策A類B類協(xié)商解Nash解最小距離解滿意解di