大學(xué)運籌學(xué)經(jīng)典課件第十五章――對策論匯總

1、2第十五章對策論 1對策論的基本概念4其他類型的對策論簡介第十五章對策論由“齊王賽馬”弓I入2矩陣對策的最優(yōu)純策略3矩陣對策的混合策略 珂運 學(xué)4 1對策論的基本槪念對策模型的三個基本要素:1局中人：參與對抗的各方;2策略集：局中人選擇對付其它局中人的行動方案稱為策略；某局中人的所有可能策略全體稱為策3局勢對策的益損值：局中人各自使用一個對策就形成了一個局勢，一個局勢決定了各局中人的對策結(jié)果（量化）稱為該局勢對策的益損值?！褒R王賽馬”齊王在各局勢中的益損值表（單位：千金）S2齊王損 益值P1（上.化下）（上.咿.下）（上.U下）內(nèi)（上.咿.下）05（上.006下）（上.中.下）（X1（上.中.

2、下）3111-11（X2（匕中卞）13111-10（3（上中.卞）1-131110C4（上.g 下）-111311（X5（上.中.下）111-131 珂運 學(xué)4（X6（上.中.下）11-11136 1對策論的基本概念局中人為2；每個局中人的策略集的策略數(shù)目都是有限的；每一局勢的對策均有確定的損益值，并且對同一局勢的兩個局中人的益損值之和為零。F面矩陣稱齊王的贏得矩陣：廠31111113 111-1A=1-13 111-1113 111 1 113 10 J16 3矩陣對策的混合策略2）無論乙取何策略，甲的平均贏得應(yīng)不少于V:對乙取5XJ+ 8X2 AV對乙取02：9X1+ 6X2 nv注意V0

3、,因為A各元素為正。STEP 2作變換：xx= x：/v ；x2= X27V得到上述關(guān)系式變?yōu)椋簭SX+ x2=i/v（V愈大愈好）待定5X1+ 8X219Xi+ 6X21Xp X20建立線性模型:minX1+X2s. t.5X1+8X21!=1/219X+6X?niiX2= 2/21XpX20ll/V=Xi+Vl/7l所以，V=7返回原問題：X；= XV= 1/3X2= X2V= 2/3于是甲的最優(yōu)混合策略為：以1 /3的概率選 5,以2/3的概率選a?,最優(yōu)值V=7 0令18 3矩陣對策的混合策略同樣可求乙的最優(yōu)混合策略:設(shè)乙使用策略01的概率為丫1Y；+丫2 =1 1設(shè)乙使用策略02的概率

4、為丫2Y； , Y/ 0 I設(shè)在最壞的情況下，甲贏得的平均值為/這也是乙損失的平均 值，越小越好。作變換：Y產(chǎn)Y/V ,Y2= Y27V建立線性模型：丫盧丫2丫產(chǎn)1/148Y1+6Y2GY2= 1/14Y, Y201/V=丫1+丫2司/7所以，V=7返回原問題：Yj = YjV = 1/2Y2= Y2V = 1/2于是乙的最優(yōu)混合策略為：以力的概率選01；以力的概率選卩2，最優(yōu)值V=7o當(dāng)贏得矩陣中有非正元素時，V0的條件不一定成立，可以 作下列變換：選一正數(shù)紅 令矩陣中每一元素加上去得到新的正 矩陣A,其對應(yīng)的矩陣對策G = SpS2, A 與G = SpS2, A 解相同，但 VG= VG

5、-R。max20陣對策如昆合策略例：求解“齊王賽馬”問題。max min ci：= min max a：f= 3 i JJJ iJ故不存在純策略問題下的解，可求其混合策略。A中有負(fù)元素，可以取22,在A的每個元素上加2得到力如下:533313353331315333133533333153331335圾* 學(xué)陣對策如昆合策略建立對 C =SL, S2, A 中求甲方最佳策略的線性規(guī)劃如下：Min x1+x2+x3+x4+x5+x6約束條件：5X1+3X2+3X34X4+3X5+3X6 Ml3X1+5X2+X3+3X4+3X5+3X6 Ml3XI+3X2+5X3+3X4+3X5+X6 Ml3X1

6、+3X2+3X3+5X4+X5+3X61X1+3X2+3X3+3X4+5X5+3X6Ml3X1+X2+3X3+3X4+3X5+5X6MlXf 0, i=l, 2,6可解得解為：x1=x4=x5=0, x2=x3=x6=0. Ill, v =3, x/ =x4 =x5 = 0, x；=x3z=x/ =1/3,即 X*=(0, 1/3, 1/3, 0,0,1/3)所以甲的最優(yōu)策略為作出策 略 a?. a3 %的概率都為 0. 333,而作出a4. a5的概率為 0.此時 VG二 V =3。已知齊王的贏得矩陣A求得311-11113-11111 1 -11113111311-131111111322

7、 3矩陣對策的混合策略|同樣可以建立對策 Gz=SPS2, A 中求乙方垠佳策略的線性規(guī)劃如下：Min yi+yz+ya+yyg+ye約束條件：5yi+3y2+3y3+3y4+ys+3y6W13yi+5y2+3y3+3y4+3y5+y6W13yi+y2+5y3+3y4+3y5+3y6W1y1+3y2+3y3+5y4+3y5+3y6W13yi+3y2+3y3+y4+5y5+3y6W13yi+3y2+y3+3y4+3y5+5y6W1yQO, i=l, 2,6可解得解為：y 產(chǎn)丫 4=5=0111, y2=y3=y6=0 V =3, y；=y4* =y5,= 1/3,y2#=y3,=y6z=0,即

8、Y =（1/3,0,0,1/3,1/3,0）J所以田忌的最優(yōu)混合策略為作出策略卩 i、卩 5 的概率都為 1/3,而作出卩 2，卩 3, 仇的概率為 0,此時 VG二 V：-k=l.齊王賽馬問題的對策最優(yōu)解可簡記為X*=(0, 1/3, 1/3, 0, 0, 1/3)丁，Y*=(l/3,0, 0, 1/3, 1/3, 0)丁，對策值 VG=1。例 兩個局中人進(jìn)行對策，規(guī)則是兩人互相獨立的各自從1、2、3這三個 數(shù)字中任意選寫一個數(shù)字。如果兩人所寫的數(shù)字之和為偶數(shù)，則局中人乙 支付給局中人甲以數(shù)量為此和數(shù)的報酬；如果兩人所寫數(shù)字之和為奇數(shù)， 則局中人甲付給局中人乙以數(shù)最為此和數(shù)的報酬。試求出其最

9、優(yōu)策略。解：首先計算局中人甲的贏得矩陣如下表:畧的八令策略Pi（出1）p2（出2）03（出3）cq（出1）2 3423a2（出2）-34 5Og（出3）456 珂坦環(huán)學(xué)令24 3矩陣對策的混合策略可知無純策略意義的解，下面求其在混合策略下的解。A的各元素都加上6得到3X1+IOX2+X3 Ml10X1+X2+12X3MlX, x2, X3 MO31010 11 128yi+3y2+10y3l3y1+10y2+y3W1lOyi+y2+12y301 3矩陣對策的混合策略得到X =0. 25, x2 =0. 50, X3 =0. 25；y/ =0. 25, y2 =0. 50, y3z=0. 25O

10、即此對策的解為X* = (0. 25, 0. 50, 0. 25)T,Y* = (0. 25, 0. 50, 0. 25)ToVG=V；-k=0o即甲的嬴得矩陣為A：2-34-56建立線性規(guī)劃模型如下:Min X1+X2+X3S T 8X1+3X2+IOX3 Ml831026 3矩陣對篥的混合策略|例4甲乙兩個企業(yè)生產(chǎn)同一種電子產(chǎn)品，甲企業(yè)可以采取的策略措施 有：（1）降低產(chǎn)品價格；（2）提高產(chǎn)品質(zhì)量；（3）推出新產(chǎn)品。乙企業(yè)考慮采 取的策略措施有（1）增加廣告費用；（2）增設(shè)維修網(wǎng)點，加強售后服務(wù)；（3）改進(jìn)產(chǎn)品性能。由于甲乙兩個企業(yè)財力有限，都只能釆取一個措施。假定 這兩個企業(yè)所占有的市場

11、總份額一定，由于各自采取的措施不同，通過預(yù) 測今后兩個企業(yè)的市場占有份額變動情況如下表，試求出這兩個企業(yè)各自 的最優(yōu)策略。易的八逬策略Pi（措施1）02（措施2）P3（措施3）5 （措施1）10 63a?（措施2）85-5a3（措施3）-1210822615A9=20177O2220建立線性規(guī)劃模型如下：Min x1+x2+x3S. T. 22XI+20X21 6X1+17X2+22X3Ml15X1+7X2+20X3Ml Xp X2, X3MO得到：Xi=O027, X2=0020, X3=0023；yO.0225, y2=0. 0225, y3=0. 025。V=14. 29。 x；=0.

12、3858, x2r=02858, x3#=0. 3286；y；=0. 3215, y2r=0. 3215, y3r=03572 即此對策的解為 X* = （0. 3858, 0. 2858, 0. 3286）T, Y* = （0. 3215, 0. 3215, 0. 3572） 6 V5=VG/-k=2.29 o解：易知此對策無純策略意義下的解。把 A 的每一個元素加上 12,得到 AMax yi+y2+y322y】+6y 尹 15y3 W120yi+17y2+7y3W122y2+20y3yPy2y328 3矩陣對策的混合策略優(yōu)超原則：假設(shè)矩陣對策G = SpS2, A 甲方贏得矩陣A=aij

13、mxn若存在兩行（列），s行（列）的各元素均優(yōu)于t行（列）的元 素，即asjatjj=l, 2 n （ aisV aiti=l, 2 .m ）稱甲方策略優(yōu)超于（ 0s優(yōu)超于0t）。優(yōu)超原則：當(dāng)局中人甲方的策略被其它策略所優(yōu)超時，可在 其贏得矩陣A中劃去第t行（同理，當(dāng)局中人乙方的策略隊被其它策 略所優(yōu)超時，可在矩陣A中劃去第t列）。如此得到階數(shù)較小的贏得矩陣A,其對應(yīng)的矩陣對策G= S, S2, A與G = S, S2, A 得到（7 3 9 5 9.被第1列所優(yōu)超A1=4 6 8 7 5.5披第2列所優(yōu)超3250A= 7 34660X0 3 02 5 99 5 98 7 5.58 8 3被第

14、3、4行所優(yōu)超被第3行所優(yōu)超等價，即解相同。例.設(shè)甲方的益損值，贏得矩陣為管ML K躋學(xué)30 3矩陣對策的混合策略得到73 9A2= 4 6 5.560 3被第1行所優(yōu)超 得到73_被第1列所優(yōu)超4 6 5.573最終得到A4=4 6 對人計算，用線性規(guī)劃方法得到：(注意：余下的策略為ct3，a4, 0i，P2甲：X*=(0, 0, 1/15, 2/15, 0)TV=5X* = (0, 0, 1/3 , 2/3, 0)T乙：Y* = (l/10, 1/10, 0, 0, 0)TV=5Y* = (1/2 , 1/2 , 0, 0, 0)To注：-利用優(yōu)超原則化簡贏得矩陣時，有可能將原對策問題的解

15、也 劃去一些(多解情況)；-線性規(guī)劃求解時有可能是多解問3*堆環(huán)學(xué)32在對策論中可以根據(jù)不同方式對對策問題進(jìn)行分類，通 常分類的方式有（1）根據(jù)局中人的個數(shù)，分為二人對策和多 人對策；（2）根據(jù)各局中人的贏得函數(shù)的代數(shù)和是否為零， 可分為零和對策和非零和對策；（3）根據(jù)局中人是否合作， 又可分為合作對策和非合作對策；（4）根據(jù)局中人的策略集 中個數(shù)，又分為有限對策和無限對策（或連續(xù)對策）；（5）也可根據(jù)局中人掌握信息的情況及決策選擇是否和時間有關(guān) 可分為完全信息靜態(tài)對策、完全信息動態(tài)對策、非完全信息 靜態(tài)對策及非完全信息動態(tài)對策；也可以根據(jù)對策模型的數(shù) 字特征又分為矩陣對策、連續(xù)對策、微分對策

16、、陣地對策、 凸對策、隨機對策。本節(jié)只對對策論中非合作對策的完全信息對策、多人非 合作對策、非零和對策作一個簡單的敘述性介紹。一.完全信息靜態(tài)對策該對策是指掌握了參與人的特征、戰(zhàn)略空間、支付函數(shù)等知識和信 息并且參與人同時選擇行動方案或雖非同時但后行動者并不知道前行動 者釆取了什么行動方案。納什均衡是一個重要概念。在一個戰(zhàn)略組合中，給定其他參與者戰(zhàn) 略的情況下，任何參與者都不愿意脫離這個組合，或者說打破這個僵局， 這種均衡就稱為納什均衡。下面以著名的“囚徒困境”來進(jìn)一步闡述。例 1 “囚徒困境”說的是兩個囚犯的故事。這兩個囚徒一起做壞事，結(jié)果被 警察發(fā)現(xiàn)抓了起來，分別關(guān)在兩個獨立的不能互通信息

17、的牢房里進(jìn)行審訊。在這 種情形下，兩個囚犯都可以做出自己的選擇：或者坦白（即與警察合作，從而背 叛他的同伙），或者抵賴（也就是與他的同伙合作，而不是與警察合作）。這兩 個囚犯都知道，如果他倆都能抵賴的話，就都會被釋放，因為只要他們拒不承認(rèn), 警方無法給他們定罪。但警方也明白這一點， 所以他們就給了這兩個囚犯一點兒 刺激： 如果他們中的一個人坦白， 即吿發(fā)他的同伙，那么他就可以被無罪釋放。 而他的同伙就會被按照最重的罪來判決。當(dāng)然，如果這兩個囚犯都坦白，兩個人 都會被按照輕罪來判決。如圖 1-1 所示。4其他類型的對策論簡介他類型的對策論簡介34他類si的對策論簡介坦白抵賴坦白輕罪，輕罪重罪，無

18、罪抵賴重罪，無罪釋放，釋放圖卜1囚徒困境由分析可知，上例中每個囚犯都會選擇坦白，因此這個戰(zhàn)略組合 是固定的，（坦白，坦白）就是納什均衡解。而這個均衡是不會被打破的, 即使他們在坐牢之前達(dá)成協(xié)議。囚徒困境反映了個人理性和集體理性的矛盾。對于雙方，（抵賴, 抵賴）的結(jié)果是最好的，但因為每個囚徒都是理性人，他們追求自身效 應(yīng)的最大化，結(jié)果就變成了（坦白，坦白）。個人理性導(dǎo)致了集體不理 性。二、完全信息動態(tài)對策在完全信息靜態(tài)對策中，假設(shè)各方都同時選擇行動?，F(xiàn)在情況稍復(fù) 雜一些。如果各方行動存在先后順序，后行的一方會參考先行者的策略 而釆取行動，而先行者也會知道后行者會根據(jù)他的行動釆取何種行動， 因此先

19、行者會考慮自己行動會對后行者的影響后選擇行動。這類問題稱 為完全信息動態(tài)對策問題。例 2 某行業(yè)中只有一個壟斷企業(yè) A,有一個潛在進(jìn)入者企業(yè) B。B 可以選 擇進(jìn)入或不進(jìn)入該行業(yè)這兩種行動，而 A 當(dāng) B 進(jìn)入時，可以選擇默認(rèn)或者報復(fù)兩種 行動。如果 B 進(jìn)入后 A 企業(yè)報復(fù)，將造成兩敗俱傷的結(jié)果，但如果 A 默認(rèn) B 進(jìn)入，必 然對A 的收益造成損失。同樣的，如果 B 進(jìn)入而 A 報復(fù)，貝 IJB 受損，反之，將受益。把此關(guān)系用圖 1-2 表示。50,100-20,00, 2000, 200進(jìn)入不進(jìn)入默圧 l 報復(fù)圖1-2 A. B的行動及結(jié)果36他類型的對礙論簡介由分析可知，上例中（B選擇

20、不進(jìn)入，A選擇報復(fù)）和（B選擇進(jìn)入，A選擇默許）都是納什均衡解。但在實際中，（B選擇不進(jìn)入，A選擇報復(fù)）這種情況是不可能出現(xiàn)的。因為B知道他如果進(jìn)入，A只能默許，所以只有（B選擇進(jìn)入，A選擇 默許）會發(fā)生?；蛘哒f，A選擇報復(fù)行動是不可置信的威脅。 對策論的術(shù)語中，稱（A選擇默許，B選擇進(jìn)入）為精煉納什 均衡。當(dāng)只當(dāng)參與人的戰(zhàn)略在每一個子對策中都構(gòu)成納什均 衡，這個納什均衡才稱為精煉納什均衡。當(dāng)然，如果A下定決心一定要報復(fù)B,即使自己暫時損失。這時威脅就變成了可置信的，B就會選擇不進(jìn)入，（B選擇不 進(jìn)入，A選擇報復(fù)）就成為精煉納什均衡。軍事交戰(zhàn)時，“破釜沉舟”講的就是一種可置信威脅。 實際企業(yè)經(jīng)

21、營中也有很多類似的例子。三.多人非合作對策有三個或三個以上對策方參加的對策就是“多人對策”。多人對策 同樣也是對策方在意識到其他對策方的存在，意識到其他對策方對自己 決策的反應(yīng)和反作用存在的情況下尋求自身最大利益的決策活動。因而, 它們的基本性質(zhì)和特征與兩人對策是相似的，我們常?？梢杂醚芯績扇?對策同樣的思路和方法來研究它們，或?qū)扇藢Σ叩慕Y(jié)論推廣到多人對 策。不過，畢競多人對策中出現(xiàn)了更多的追求各自利益的獨立決策者， 因此，策略的相互依存關(guān)系也就更為復(fù)雜，對任一對策方的決策引起的 反應(yīng)也就要比兩人對策復(fù)雜得多。并且，在多人對策中還有一個與兩人 對策有本質(zhì)區(qū)別的特點，即可能存在“破壞者”。所謂

22、破壞者即一個對 策中具有下列特征的對策方：其策略選擇對自身的得益沒有任何影響，但卻會影響其它對策方的得益， 有時這種影響甚至有決定性的作用。 例 如有三個城市爭奪某屆奧運會的主辦權(quán)。38多人對策可以分為合作的和非合作的。非合作對策顧名 思義，就是局中人之間不存在合作，即各局中人在采取行動 之前，沒有事前的交流和約定，在其行為發(fā)生相互作用時， 也不會達(dá)成任何有約束力的協(xié)議。每個局中人都選擇于已最 有利的策略以使效用水平最大化“然而，在非合作對策中, 雙方的利益也并非是完全沖突的，即對一個局中人有利的局 勢并不一定對其他局中人一定不利，故多人非合作對策不一 定是零和對策。如同矩陣對策中純策略意義下的解有時不存在一樣，有 中人就必須考慮混合策略。所謂零和對策，就是一方的收益必定是另一方的損失。這種對策的 特點是不管各對策方如何決策，最后各對策方得