對策模型和算法

對策模型和算法第一頁，共六十九頁，編輯于2023年，星期六在對策論中，應(yīng)有以下要素：(1)局中人。是指參與對抗的各方，可以是一個人，也可以是一個集團。在例1.1的甲、乙兩名兒童就是局中人。(2)

策略。是指局中人所擁有的對付其他局中人的手段、方案的集合。如例1.1中共有石頭、剪子、布三種策略。(3)支付函數(shù)（或收益函數(shù)）。是指一局對策后各局中人的得與失，通常用正數(shù)字表示局中人的得，用負數(shù)字表示局中人的失。在例1.1的局中人甲的支付函數(shù)如表所示。5/28/20232第二頁，共六十九頁，編輯于2023年，星期六乙石頭剪子布甲石頭01-1剪子-101布1-10例1.1“石頭--剪子--布”中兒童甲的支付函數(shù)第三頁，共六十九頁，編輯于2023年，星期六當(dāng)局中人得失總和為零時，稱這類對策為零和對策；否則稱為非零和對策。當(dāng)局中人只有兩個，且對策得失總和為零，則稱為二人零和對策，若總得失總和為常數(shù)，則稱為二人常數(shù)和對策，若得失總和是非常數(shù)的，則稱為二人非常數(shù)和對策。若二人對策雙方的得失是用矩陣形式表示，則稱支付函數(shù)為支付矩陣，相應(yīng)的對策稱為矩陣對策。通常，支付矩陣表示局中人A的支付函數(shù)。第四頁，共六十九頁，編輯于2023年，星期六鞍點對策是對策的最基本策略，為更好地理解鞍點對策，先看一個簡單的例子。1.對策的基本策略---鞍點對策例9.2設(shè)A、B兩人對策，各自擁有三個策略：a1,a2,a3和b1,b2,b3,局中人A的支付（收益）矩陣由表1.2所示。試求A、B各自的最優(yōu)策略。b1b2b3mina11391a26575a38422max859第五頁，共六十九頁，編輯于2023年，星期六問題分析： 從直觀來看，局中人A應(yīng)該出策略a1,因為這樣選擇，他有可能得到9.但局中人B看到了這一點，他出策略b1，這樣局中人A不能得到9，而只能得到1.因此，局中人A也充分認識到這一點，他應(yīng)當(dāng)出策略a3,這樣做，就有可能得到8，而這種情況下局中人B，就要出策略b3，局中人A也只能得到2. 這樣做下來，局中人A只能選擇策略a2,而局中人B也只能選擇策略b2，大家達到平衡，最后局中人A贏得的值為5，局中人B輸?shù)舻闹禐?.第六頁，共六十九頁，編輯于2023年，星期六 從上面的分析可以看出，無論局中人A選擇什么策略，他贏得的值總是小于等于5，而無論局中人B選擇什么策略，他輸?shù)舻闹悼偸谴笥诘扔?，5就是支付矩陣的鞍點。 現(xiàn)討論一般情況。假設(shè)局中人A的支付矩陣由表1.3所示。12…n1C11C12…Cn12C21C22…Cn2┆┆┆┆mCm1Cm2…Cmn第七頁，共六十九頁，編輯于2023年，星期六 其中局中人A有m個策略α1,…,α

m,局中人B有n個策略β1,…,β

n,分別記為S1={α1,…,α

m},S2={β1,…,β

n} C為局中人A的支付矩陣，而-C為局中人B的支付矩陣。因此，矩陣對策記為G={A,B;S1,S2,C},或G={S1,S2,C} 對于一般矩陣對策，有如下定義和定理。第八頁，共六十九頁，編輯于2023年，星期六定義9.1設(shè)G={S1,S2,C}是一矩陣對策，若等式成立，則記vG=,ci*j*并稱vG為對策G的值。 稱使式(1)成立純局勢(α

i*,β

j*)為G在純策略下的解（或平衡局勢），稱α

i*和β

j*分別為局中人A、B的最優(yōu)純策略。第九頁，共六十九頁，編輯于2023年，星期六定理9.1 矩陣對策G={S1,S2,C}在純策略意義下有解的充分必要條件是：存在純局勢(α

i*,β

j*)使得定義9.25/28/202310第十頁，共六十九頁，編輯于2023年，星期六當(dāng)矩陣對策的最優(yōu)解不唯一時，有如下定理：定理9.2定理9.3第十一頁，共六十九頁，編輯于2023年，星期六2.無鞍點的對策策略---混合對策如果支付矩陣有鞍點，選擇鞍點對策是最優(yōu)的對策策略，如果支付矩陣無鞍點，則需要選擇混合對策。 我們回過頭再看例9.1（“石頭--剪子--布”），對于支付矩陣,有 沒有純最優(yōu)策略。因此無法用定理9.1來確定最優(yōu)策略。在這種情況下，只能求相應(yīng)的混合策略。類似于純策略，混合策略有如下定義和定理。第十二頁，共六十九頁，編輯于2023年，星期六定義9.3設(shè)有矩陣對策G＝｛S1，S2，C｝稱分別為局中人A和B的混合策略。稱(x,y)(xS1*,yS2*)為一個混合局，稱為局中人A的支付函數(shù)（贏得函數(shù)）。第十三頁，共六十九頁，編輯于2023年，星期六定義9.4 設(shè)G*＝｛S1*，S2*，C｝是G＝｛S1，S2，C｝的混合擴充，若則稱vG為對策G*的值。稱使式(7)成立混合局勢(x*,y*)為G在混合策略下的解，稱x*和y*分別為局中人A和B的最優(yōu)混合策略。第十四頁，共六十九頁，編輯于2023年，星期六定理9.4 矩陣對策G＝｛S1，S2，C｝在混合策略意義下有解的充分必要條件是：存在(xS1*,yS2*)使(x*,y*)為函數(shù)E(x,y)的一個鞍點，即第十五頁，共六十九頁，編輯于2023年，星期六3.混合對策求解方法通常用線性規(guī)劃方法求混合策略的解。設(shè)局中人A分別以x1,x2,…,xm的概率混合使用他的m種策略，局中人B分別以y1,y2,…,ym的概率混合使用他的n種策略。第十六頁，共六十九頁，編輯于2023年，星期六當(dāng)A采用混合策略，B分別采用純策略bj(j=1,2,…,n),A的贏得分別為依據(jù)最大最小原則，應(yīng)有其中vA是局中人A的贏得值。第十七頁，共六十九頁，編輯于2023年，星期六將問題（9）寫成線性規(guī)劃問題 也就是說，線性規(guī)劃問題(10)～(13)的解就是局中人A采用混合策略的解。類似可求局中人B的最優(yōu)策略的解。第十八頁，共六十九頁，編輯于2023年，星期六例9.3 用線性規(guī)劃方法求解例1的 最優(yōu)混合策略。按照線性規(guī)劃（10）～（13）寫出相應(yīng)的LINGO程序，程序名：exam0903a.lg4MODEL:1]sets:2]playerA/1..3/:x;3]playerB/1..3/;4]game(playerA,playerB):C;5]endsets第十九頁，共六十九頁，編輯于2023年，星期六6]data:7]C=01-18]-1019]1-10;10]enddata11]max=v_A;12]@free(v_A);13]@for(playerB(j):14]@sum(playerA(i):C(i,j)*x(i))>=v_A);15]@sum(playerA:x)=1;END第二十頁，共六十九頁，編輯于2023年，星期六得到最優(yōu)解（只保留相關(guān)部分）Globaloptimalsolutionfoundatiteration:3Objectivevalue:0.000000VariableValueReducedCostV_A0.0000000.000000X(1)0.33333330.000000X(2)0.33333330.000000X(3)0.33333330.000000第二十一頁，共六十九頁，編輯于2023年，星期六 即兒童甲以1/3的概率出石頭、剪子、布中每種策略的一種，其贏得值為0. 用線性規(guī)劃求出兒童乙有同樣的結(jié)論。 計算到此，讀者可能會產(chǎn)生一個問題：一個具有鞍點的對策問題，如果采用線性規(guī)劃方法求解，將會出現(xiàn)什么情況？第二十二頁，共六十九頁，編輯于2023年，星期六例9.4用線性規(guī)劃方法求解例2解：寫出LINGO程序，程序名：exam0904.lg4MODEL:1]sets:2]playerA/1..3/:x;3]playerB/1..3/;4]game(playerA,playerB):C;5]endsets6]data:7]C=139第二十三頁，共六十九頁，編輯于2023年，星期六8]6579]842;10]enddata11]max=v_A;12]@free(v_A);13]@for(playerB(j):14]@sum(playerA(i):C(i,j)*x(i))>=v_A);15]@sum(playerA:x)=1;END第二十四頁，共六十九頁，編輯于2023年，星期六計算結(jié)果為（保留有效部分）Globaloptimalsolutionfoundatiteration:0Objectivevalue:5.000000VariableValueReducedCostV_A5.0000000.000000X(1)0.0000002.000000X(2)1.0000000.000000X(3)0.0000001.000000第二十五頁，共六十九頁，編輯于2023年，星期六 由結(jié)果可以看到，局中人A仍然選擇純策略。對局中人B的計算也會出現(xiàn)同樣的情況。 從例9.3和例9.4可以看出，無論矩陣對策有無鞍點，我們均可以采用線性規(guī)劃的方法求其對策，只不過具有鞍點的對策可以有更簡單的算法罷了。第二十六頁，共六十九頁，編輯于2023年，星期六1.2二人常數(shù)和對策 所謂常數(shù)和對策是指局中人A和局中人B所贏得的值之和為一常數(shù).顯然，二人零和對策是二人常數(shù)和的特例，即常數(shù)為零。 對于二人常數(shù)和對策，有純策略對策和混合策略對策。其求解方法基本上是相同的。1.鞍點對策 對于二人常數(shù)和對策，仍然有鞍點對策，其求解方法與二人零和對策相同。第二十七頁，共六十九頁，編輯于2023年，星期六例9.4 在晚8點至9點這個時段，兩家電視臺在競爭100萬電視觀眾收看自己的電視節(jié)目，并且電視臺必須實時公布自己在下一時段的展播內(nèi)容。電視臺1可能選擇的展播方式及可能得到的觀眾如表所示。電視臺min西部片連續(xù)劇喜劇片電視臺1西部片35156015連續(xù)劇45585045喜劇片38147014max455870第二十八頁，共六十九頁，編輯于2023年，星期六解：事實上，對方得到的，就是自己失去的，完全利用二人零和的方法確定最優(yōu)純策略，即 因此，電視臺1選擇播放連續(xù)劇，贏得45萬觀眾，電視臺2播放西部片，贏得100-45=55萬觀眾。2.混合對策 對于常數(shù)和對策，也存在混合對策，同樣可以采用線性規(guī)劃方法求解，這里就不舉例子了。第二十九頁，共六十九頁，編輯于2023年，星期六§2二人非常數(shù)和對策 二人非常數(shù)和對策也稱為雙矩陣對策。在前面介紹的常數(shù)和（零和）對策中，均包含兩種情況，純策略和混合策略。對于非常數(shù)對策，也包含這兩種策略。1.純對策問題例9.6：囚徒的困境(表9.2.1)乙坦白不坦白甲坦白（-3，-3）(0,-10)不坦白（-10，0）(-1,-1)第三十頁，共六十九頁，編輯于2023年，星期六例9.6 設(shè)有甲、乙兩名嫌疑犯因同一樁罪行被捕，由于希望他們坦白并提供對方的犯罪證據(jù)，規(guī)定如兩人均坦白各判刑3年；如上方坦白另一方不坦白，坦白一方從輕釋放，不坦白一方判刑10年；如兩人均不坦白，由于犯罪事實很多不能成立，只能各判1年，見表9.2.1所示。 試分析甲、乙兩犯罪嫌疑人各自采用什么策略使自己的刑期最短。第三十一頁，共六十九頁，編輯于2023年，星期六例9.6給出了典型的二人非常數(shù)和對策，每人的收益矩陣是不相同的，因此稱為雙矩陣對策。通常規(guī)定，雙矩陣中，第一個元素是局中人A的贏得值，第二個元素是局中人B的贏得值。 問題分析：這是一個二人非常數(shù)和對策問題。從表面看，兩犯罪嫌疑人拒不坦白，只能被判1年徒刑，結(jié)果是最好的。但仔細分析，確無法做到這一點。因為犯罪嫌疑人甲如果采用不坦白策略，他可能被判的刑期為1到10年，而犯罪嫌疑人乙可能判的刑期為0到1年。第三十二頁，共六十九頁，編輯于2023年，星期六 而甲選擇坦白，他被判的刑期為0到3年，此時，犯罪嫌疑人乙可能判的刑期為3到10年。因此，犯罪嫌疑人甲一定選擇坦白。 基于同樣的道理，犯罪嫌疑人乙也只能選擇坦白。 選擇坦白是他們最好的選擇，各自被判3年。第三十三頁，共六十九頁，編輯于2023年，星期六 事實上，設(shè)(cijA,cijB)是甲、乙贏得值，則甲、乙采用的策略是1.純對策問題的基本概念 按照上面的論述，對于一般純對策問題，局中人A、B的支付（贏得）矩陣由表9.2.2所示。第三十四頁，共六十九頁，編輯于2023年，星期六局中人A、B的支付矩陣β1β2…βnα1…α2…┆┆┆┆αm…第三十五頁，共六十九頁，編輯于2023年，星期六 為局中人A的支付（贏得）矩陣， 為局中人B的支付（贏得）矩陣。因此，矩陣對策記為：

G={A,B;S1,S2,CA,CB}或G={S1,S2,CA,CB}第三十六頁，共六十九頁，編輯于2023年，星期六定義9.5：設(shè)G={S1,S2,CA,CB}是一雙矩陣對策，若等式 成立，則記vA=，并稱vA為局中人A的贏得值，記vB=，并稱vB為局中人B的贏得值，稱（αi*,β

j*)為G在純策略下的解（或Nash平衡點），稱αi*和β

j*分別為局中人A、B的最優(yōu)純策略。第三十七頁，共六十九頁，編輯于2023年，星期六2.純對策問題的求解方法 實際上，定義9.5也同時給出了純對策問題的求解方法。因此，對于例9.6,((1,0),,(1,0))是Nash平衡點，也就是說，坦白他們的最佳策略。再看一個例子。例：9.7（夫妻周末安排問題）一對夫妻，商量周末安排。丈夫喜歡看足球，妻子喜歡聽音樂會。他們的贏得值由表9.7所示。請為這對夫妻設(shè)計最好的度周末的方案。第三十八頁，共六十九頁，編輯于2023年，星期六解：由定義9.5可知，對于策略((1,0),(1,0))或策略((0,1),(0,1))均是Nash平衡點，也就是最優(yōu)解，即他們選擇是共同看足球，或共同聽音樂會。表中帶有下劃線是他們采用策略的贏得值。妻足球音樂會夫足球(3,1)(-1,-1)音樂會(-1,-1)(1,3)第三十九頁，共六十九頁，編輯于2023年，星期六2.混合對策問題如果不存在使式(18)成立的對策，則需要求混合對策。類似于二人常數(shù)和對策情況，需要給出混合對策的最優(yōu)解。1.混合對策問題的基本概念定義9.6在對策G=\{S1,S2,CA,CB}中，若存在策略對使得第四十頁，共六十九頁，編輯于2023年，星期六則稱 為G的一個非合作平衡點。記則稱vA,vB分別為局中人A、B的贏得值。對于混合對策問題有如下定理定理9.5每個雙矩陣對策至少存在一個非合作平衡點。定理9.6混合策略為對策G=\{S1,S2,CA,CB}的平衡點的充分必要條件是：第四十一頁，共六十九頁，編輯于2023年，星期六2.混合對策問題的求解方法 由定義9.6可知，求解混合對策就是求非合作對策的平衡點。進一步，由定理9.6得到，求解非合作對策的平衡點，就是求解滿足不等式約束(20)的可行點。因此，混合對策問題的求解問題就轉(zhuǎn)化為求不等式約束(20)的可行點，而LINGO軟件可以很容易做到這一點。第四十二頁，共六十九頁，編輯于2023年，星期六例9.8

有甲、乙兩支游泳隊舉行包括三個項目的對抗賽。這兩支游泳隊各有一名健將級運動員（甲隊為李，乙隊為王），在三個項目中成績很突出。但規(guī)則準許他們每個人分別只能參加兩項比賽，而每隊的其他兩名運動員則可參加全部三項比賽。各運動員的成績?nèi)绫?-8所示。甲隊乙隊趙錢李王張孫蝶泳54.758.252.153.656.459.8仰泳62.263.458.256.559.761.5蛙泳69.170.565.367.868.471.3第四十三頁，共六十九頁，編輯于2023年，星期六解：分別用甲1、甲2和甲3表示甲隊中李姓健將不參加蝶泳、仰泳、蛙泳比賽的策略，分別用乙1、乙2和乙3表示乙隊中王姓健將不參加蝶泳、仰泳、蛙泳比賽的策略。當(dāng)甲隊采用策略甲1，乙隊采用策略乙1時，在100米蝶泳中，甲隊中趙獲第一、錢獲第三得6分，乙隊中張獲第二，得3分；在100米仰泳中，甲隊中李獲第二，得3分，乙隊中王獲第一，張獲第三，得6分；在100米蛙泳中，甲隊中李獲第一，得5分，乙隊中王獲第二、張獲第三，得4分。也就是說，對應(yīng)于策略（甲1，乙1），甲、乙兩隊各自的得分為(14,13).表9-9中給出了在全部策略下各隊的得分。第四十四頁，共六十九頁，編輯于2023年，星期六表9-9甲、乙兩隊采用不同策略的得分乙1乙2乙3甲1(14,13)(13,14)(12,15)甲2(13,14)(12,15)(12,15)甲3(12,15)(12,15)(13,14) 按照定理9.6，求最優(yōu)混合策略，就是求不等式約束(20)的可行解.寫出相應(yīng)的LINGO程序，程序名：exam0908.lg4"第四十五頁，共六十九頁，編輯于2023年，星期六MODEL:1]sets:2]optA/1..3/:x;3]optB/1..3/:y;4]AXB(optA,optB):Ca,Cb;5]endsets6]data:7]Ca=1413128]131212第四十六頁，共六十九頁，編輯于2023年，星期六9]121213;10]Cb=13141511]14151512]151514;13]enddata14]Va=@sum(AXB(i,j):Ca(i,j)*x(i)*y(j));15]Vb=@sum(AXB(i,j):Cb(i,j)*x(i)*y(j));16]@for(optA(i):第四十七頁，共六十九頁，編輯于2023年，星期六17]@sum(optB(j):Ca(i,j)*y(j))<=Va);18]@for(optB(j):19]@sum(optA(i):Cb(i,j)*x(i))<=Vb);20]@sum(optA:x)=1;@sum(optB:y)=1;21]@free(Va);@free(Vb);END用LINGO軟件求解，得到第四十八頁，共六十九頁，編輯于2023年，星期六Feasiblesolutionfoundatiteration:3VariableValueVA12.50000VB14.50000X(1)0.5000000X(2)0.000000X(3)0.5000000Y(1)0.000000Y(2)0.5000000Y(3)0.5000000第四十九頁，共六十九頁，編輯于2023年，星期六即甲隊采用的策略是甲1、甲3方案各占50%,乙隊采用的策略是乙2、乙3方案各占50%,甲隊的平均得分為12.5分，乙隊的平均得分為14.5分。當(dāng)純對策的解不唯一時，也存在混合對策的平衡點。第五十頁，共六十九頁，編輯于2023年，星期六例9.9用混合對策方法求解例9.7。解：寫出求不等式(20)的LINGO程序，程序名："ex0909.lg4“MODEL:1]sets:2]optA/1..2/:x;3]optB/1..2/:y;4]AXB(optA,optB):Ca,Cb;5]endsets第五十一頁，共六十九頁，編輯于2023年，星期六6]data:7]Ca=3-1-11;8]Cb=1-1-13;9]enddata10]Va=@sum(AXB(i,j):Ca(i,j)*x(i)*y(j));11]Vb=@sum(AXB(i,j):Cb(i,j)*x(i)*y(j));12]@for(optA(i):13]@sum(optB(j):Ca(i,j)*y(j))<=Va);14]@for(optB(j):第五十二頁，共六十九頁，編輯于2023年，星期六15]@sum(optA(i):Cb(i,j)*x(i))<=Vb);16]@sum(optA:x)=1;@sum(optB:y)=1;17]@free(Va);@free(Vb);END 計算得到混合對策的平衡點((2/3,1/3),(1/3,2/3)各自的贏得值為1/3. 從上述分析來看，二人常數(shù)和對策是非常數(shù)和對策的特例，因此也可以用求解非常數(shù)和對策的方法求解常數(shù)和對策。第五十三頁，共六十九頁，編輯于2023年，星期六例9.10用求解非常數(shù)和對策的方法求解例9.5解：寫出相應(yīng)的LINGO程序，程序名：exam0910.lg4MODEL:1]sets:2]optA/1..3/:x;3]optB/1..3/:y;4]AXB(optA,optB):Ca,Cb;5]endsets第五十四頁，共六十九頁，編輯于2023年，星期六6]data:7]Ca=3515608]4558509]381470;10]Cb=65854011]55425012]628630;13]enddata第五十五頁，共六十九頁，編輯于2023年，星期六14]Va=@sum(AXB(i,j):Ca(i,j)*x(i)*y(j));15]Vb=@sum(AXB(i,j):Cb(i,j)*x(i)*y(j));16]@for(optA(i):17]@sum(optB(j):Ca(i,j)*y(j))<=Va);18]@for(optB(j):19]@sum(optA(i):Cb(i,j)*x(i))<=Vb);20]@sum(optA:x)=1;@sum(optB:y)=1;21]@free(Va);@free(Vb);END第五十六頁，共六十九頁，編輯于2023年，星期六計算結(jié)果如下（只保留有效部分）Feasiblesolutionfoundatiteration:12VariableValueVA45.00000VB55.00000X(1)0.000000X(2)1.000000X(3)0.000000Y(1)1.000000Y(2)0.000000Y(3)0.000000第五十七頁，共六十九頁，編輯于2023年，星期六 即局中人A采用第二種策略，贏得45萬觀眾，局中人B采用第一種策略，贏得55萬觀眾，與前面計算的結(jié)果相同。第五十八頁，共六十九頁，編輯于2023年，星期六§3n人合作對策初步

n人合作對策在理論上較為復(fù)雜，這里只用一些例子簡單介紹n人合作對策的基本思想，和用LINGO軟件求解對策的方法。例9.11

甲有一匹馬，對他自己來說，其價值為0,而對乙和丙（買主）來說分別價值90和100個貨幣單位。試建立3人合作對策，使得每人的利益最大。第五十九頁，共六十九頁，編輯于2023年，星期六解：設(shè)甲、乙、丙三人的價值分別為x1,x2,x3,因此對于每個人來說，其價值為0，即v{1}=v{2}=v{3}=0 如果甲與乙合作，其價值為90，甲與丙合作，其價值為100，若乙與丙合作，其價值仍為0，因此有v{1,2}=90,v{1,3}=100,v{2,3}=0.但三人合作的總價值為100，即v{1,2,3}=100.建立相應(yīng)的數(shù)學(xué)規(guī)劃問題第六十頁，共六十九頁，編輯于2023年，星期六第六十一頁，共六十九頁，編輯于2023年，星期六寫出相應(yīng)的LINGO程序，程序名：exam0909.lg4MODEL:1]sets:2]condition/1..3/:b;3]players/1..3/:x;4]constraint(condition,players):A;5]endsets6]data:7]A=110第六十二頁，共六十九頁，編輯于2023年，星期六8]1019]011;10]b=901000;11]total=100;12]enddata13]max=z;14]@for(players:z<=x);15]@for(condition(i):16]@sum(players(j):A(i,j)*x(j))>=b(i));17]@sum(players:x)<=total;END第六十三頁，共六十九頁，編輯于2023年，星期六經(jīng)計算得到（只保留有用部分）Globaloptimalsolutionfoundatiteration:8Objectivevalue:0.000000Variable ValueReducedCostTOTAL 100.00000.000000Z 0.0000000.000000X(1) 90.000000.000000X(2) 0.0000000.000000